Definition:Many-to-One Relation

From ProofWiki
Jump to: navigation, search


A relation $\mathcal R \subseteq S \times T$ is many-to-one if:

$\forall x \in \operatorname{Dom} \left({\mathcal R}\right): \left({x, y_1}\right) \in \mathcal R \land \left({x, y_2}\right) \in \mathcal R \implies y_1 = y_2$

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


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$ iff $s \in \operatorname{dom} f$, the domain of $f$.

Defined on Set

Let $R \subseteq S$.

Then $f$ is defined on $R$ iff it is defined at all $r \in R$.

Equivalently, iff $R \subseteq \operatorname{dom} f$, the domain of $f$.

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).

Also known as

Such a relation is also referred to as:

  • 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.

Some approaches, for example 1999: András Hajnal and Peter Hamburger: Set Theory, use this as the definition for a mapping from $S$ to $T$, and then separately specify the requisite left-total nature of the conventional definition 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.