Diagonal Relation is Many-to-One
Jump to navigation
Jump to search
Theorem
The diagonal relation is many-to-one.
That is:
- $\forall x \in \Dom {\Delta_S}: \tuple {x, y_1} \in \Delta_S \land \tuple {x, y_2} \in \Delta_S \implies y_1 = y_2$
where $\Delta_S$ is the diagonal relation on a set $S$.
Proof
Let $S$ be a set and let $\Delta_S$ be the diagonal relation on $S$.
Let $\tuple {x, y_1} \in \Delta_S \land \tuple {x, y_2} \in \Delta_S$.
From the definition of the diagonal relation:
- $\tuple {x, y_1} = \tuple {x, x}$
- $\tuple {x, y_2} = \tuple {x, x}$
and so $y_1 = y_2$.
$\blacksquare$
Also see
Sources
- 1975: T.S. Blyth: Set Theory and Abstract Algebra ... (previous) ... (next): $\S 4$. Relations; functional relations; mappings: Example $4.5$