Definition:Many-to-One Relation

From ProofWiki
(Redirected from Definition:Partial Mapping)
Jump to navigation Jump to search

Definition

A relation $\RR \subseteq S \times T$ is many-to-one if and only if:

$\forall x \in \Dom \RR: \forall y_1, y_2 \in \Cdm \RR: \tuple {x, y_1} \in \RR \land \tuple {x, y_2} \in \RR \implies y_1 = y_2$


That is, every element of the domain of $\RR$ relates to no more than one element of its codomain.


Defined

Let $f \subseteq S \times T$ be a many-to-one relation.


Defined at Element

Let $s \in S$.


Then $f$ is defined at $s$ if and only if $s \in \Dom f$, the domain of $f$.


Defined on Subclass

Let $R \subseteq S$.


Then $f$ is defined on $R$ if and only if it is defined at all $r \in R$.

Equivalently, if and only if $R \subseteq \Dom f$, the domain of $f$.


Examples

Square

Let $\RR \subseteq \R \times \R$ be the relation on $\R$ defined as:

$\forall \tuple {x, y} \in \R \times \R: \tuple {x, y} \in \RR \iff x^2 = y$

Then $\RR$ is a many-to-one relation


Also known as

A many-to-one relation is also referred to as:

a many-one correspondence
a rule of assignment
a functional relation
a right-definite relation
a right-unique relation
a partial mapping.

Some sources break with mathematical convention and call this a (partial) function.

These sources subsequently define a total function to be what on $\mathsf{Pr} \infty \mathsf{fWiki}$ is called a mapping.


None of these names is as intuitively obvious as many-to-one relation, so the latter is the preferred term on $\mathsf{Pr} \infty \mathsf{fWiki}$.

However, it must be noted that a one-to-one relation is an example of a many-to-one relation, which may confuse.

The important part is the to-one part of the definition, which is as opposed to the to-many characteristic of a one-to-many relation and a many-to-many relation.


Also defined as

Some approaches, for example 1999: András Hajnal and Peter Hamburger: Set Theory, define a mapping as a many-to-one relation from $S$ to $T$, and then separately specify its requisite left-total nature by restricting $S$ to the domain.

However, this approach is sufficiently different from the mainstream approach that it will not be used on $\mathsf{Pr} \infty \mathsf{fWiki}$ and limited to this mention.


Also see

If in addition, every element of the domain relates to exactly one element in the codomain, the many-to-one relation is known as a mapping (or function).

  • Results about many-to-one relations can be found here.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Many-to-One_Relation&oldid=698182"