Many-to-one relations

Describe the formal logic of many-to-one relations

The formal logic of many-to-one relations

Let (A,B) be (nonempty) sets and (R\subseteq A\times B) a binary relation, written (R(a,b)).

Core idea

A relation (R) is many-to-one (from (A) to (B)) iff each (a\in A) relates to at most one (b\in B). Formally (right-uniqueness): [ \forall a\in A,\forall b_1,b_2\in B:\ \big(R(a,b_1)\land R(a,b_2)\big)\Rightarrow b_1=b_2. ] This is exactly the property of being single-valued (a partial function). If in addition every (a) is related to some (b), i.e. [ \forall a,\exists b:\ R(a,b), ] then (R) is total and is simply the graph of a (possibly non-injective) function (f:A\to B).

When people say “many-to-one” informally, they usually mean “a function that need not be injective.”

Optional “strictly many-to-one”

If you want to rule out injective cases and guarantee that some two distinct (a)’s share a value, add: [ \exists b,\exists a_1\neq a_2:\ R(a_1,b)\land R(a_2,b). ] So:

• Many-to-one (broad): right-unique (and typically total).
• Strictly many-to-one: right-unique and not injective.

Related notions (for orientation)

• Injective (one-to-one): [ \forall a_1,a_2,b:\ \big(R(a_1,b)\land R(a_2,b)\big)\Rightarrow a_1=a_2. ]
• Surjective (onto (B)): [ \forall b,\exists a:\ R(a,b). ]
• Bijection: injective (\wedge) surjective.

Many-to-one concerns right-uniqueness only; it says nothing by itself about surjectivity.

Inverse relation viewpoint

Let (R^{-1}\subseteq B\times A) be the converse relation. If (R) is many-to-one (right-unique), then (R^{-1}) is in general one-to-many (not left-unique): a single (b) may relate to many (a)’s.

Functional quantifier shorthand

Using the “exists exactly one” quantifier (\exists!),

• Total many-to-one (function): (\forall a,\exists! b:\ R(a,b)).
• Partial many-to-one: (\forall a,\exists\le 1,b:\ R(a,b)), i.e. the right-uniqueness axiom alone.

Closure under composition

If (R\subseteq A\times B) and (S\subseteq B\times C) are many-to-one, then the composition [ S\circ R ;=; {(a,c)\mid \exists b:\ R(a,b)\land S(b,c)}\ \subseteq A\times C ] is also many-to-one (right-unique). If both are total, the composition is a total function. (Injectivity may fail even if each is right-unique.)

Examples

• Parity: (f:\mathbb{Z}\to{0,1}), (f(n)=n\bmod 2). Many inputs map to the same output (strictly many-to-one).
• Floor: (f:\mathbb{R}\to\mathbb{Z}), (f(x)=\lfloor x\rfloor). Each integer has an interval’s worth of preimages.
• Parent relation (fatherOf): (R(\text{child},\text{father})). Typically total and right-unique; many children can share the same father.

Database/logical dependency connection

In first-order logic over a table (T), a functional dependency (X\to Y) expresses a many-to-one constraint from (X)-values to (Y)-values: [ \forall t_1,\forall t_2:\ \big(t_1[X]=t_2[X]\wedge T(t_1)\wedge T(t_2)\big)\Rightarrow t_1[Y]=t_2[Y]. ] This is the same right-uniqueness principle at the level of attributes.

---

Bottom line: In formal logic, “many-to-one” is just the right-uniqueness (single-valued) property of a relation; with totality it’s a function, and with a witness of non-injectivity it’s strictly many-to-one.