Notes - Set Theory HT25, Products and relations
Flashcards
Products
Suppose $x$ and $y$ are sets. @Define the ordered pair $\langle x, y \rangle$.
Suppose $X$ and $Y$ are sets. @Prove that there exists a Cartesian product $X \times Y$, where the elements are the ordered pairs $\langle x, y \rangle$ where $x \in X$ and $y \in Y$.
Note that if $x \in X$ and $y \in Y$, then $\langle x, y\rangle = \{\{x\}, \{x, y\}\} \subseteq \mathcal P(X \cup Y)$, therefore $\langle x, y \rangle \in \mathcal P(\mathcal P(X \cup Y))$. Hence
\[X \times Y := \\{z \in \mathcal P(\mathcal P(X \cup Y)) : \exists x \in X \text{ } \exists y \in Y \text{ } z = \langle x, y\rangle\\}\]exists by comprehension, since the property $z = \langle x, y \rangle$ can be expressed in $\mathcal L$ via
\[\forall w(w \in z \leftrightarrow (\forall u(u \in w \leftrightarrow u = x) \lor \forall u (u \in w \leftrightarrow (u = x \lor u = y))))\]Relations
What is a binary relation $R$ formally?
A set of ordered pairs $\langle x, y\rangle$.
@Define the domain of a binary relation $R$.
@Define the range of a binary relation $R$.
Orders
@Define a strict partial order on a set $X$, and also define what it means for this order to be total.
A relation $(<) \subseteq X \times X$ satisfying for all $x, y, z \in X$:
- Irreflexivity: $\lnot (x < x)$
- Transitivity: If $x < y$ and $y < z$, then $x < z$.
It is total if for all $x, y \in X$, we have trichotomy:
- Trichotomy: $x < y$, or $x = y$ or $y < x$.
Equivalence relations
@Define an equivalence relation on a set $X$ and formally define the set of equivalence classes for this relation.
A binary relation $(\sim) \subseteq X \times X$ such that for all $x, y, z \in X$:
- Reflexivity: $x \sim x$
- Symmetry: If $x \sim y$, then $y \sim x$.
- Transitivity: If $x \sim y$ and $y \sim z$, then $x \sim z$
The set of equivalence classes is given by:
\[\begin{aligned} X/\sim &:= \\{S \in \mathcal P(X) : \exists x \in X . S = \\{y \in X : y \sim x\\}\\} \\\\ &= \\{\\{y \in X : y \sim x\\} : x \in X\\} \end{aligned}\]