JakeMath

Relations

Definition 1. Let \(A\) be a set. If \(R \subseteq A \times A\), then \(R\) is a relation on \(A\). If \(a,b\in A\), we denote \((a,b)\in R\) by \(aRb\).

Definition 2. Let \(R\) be a relation on a set \(A\).

  1. We call \(R\) reflexive if \[\forall a\in A \quad aRa\]

  2. We call \(R\) irreflexive if \[\forall a\in A \quad \lnot aRa\]

  3. We call \(R\) symmetric if \[\forall a,b\in A \quad aRb \implies bRa\]

  4. We call \(R\) asymmetric if \[\forall a,b\in A \quad aRb \implies \lnot bRa\]

  5. We call \(R\) antisymmetric if \[\forall a,b\in A \quad aRb \land bRa \implies a=b\]

  6. We call \(R\) transitive if \[\forall a,b,c\in A \quad aRb \land bRc \implies aRc\]

  7. We call \(R\) connected if \[\forall a,b\in A \quad a\neq b \implies aRb \lor bRa\]

  8. We call \(R\) strongly connected if \[\forall a,b\in A \quad aRb \lor bRa\]

Equivalence Relations

Definition 3. A relation \(R\) on a set \(A\) is an equivalence relation if \(R\) is reflexive, symmetric, and transitive.

Definition 4. If \(\sim\) is an equivalence relation on a set \(A\), for each \(a\in A\), the equivalence class of \(a\) is the set \[[a] = \{x\in A: x\sim a\}\]

Definition 5. A collection \(\mathcal{A}\) of nonempty subsets of a set \(A\) is a partition of \(A\) if \(\cup\mathcal{A} = A\) and \[\forall X,Y\in\mathcal{A} \quad X\neq Y \implies X\cap Y = \emptyset\]

Theorem 1. If \(\sim\) is an equivalence relation on a set \(A\), then the set of equivalence classes is a partition of \(A\).

Proof. Let \(\sim\) be an equivalence relation on a set \(A\). Let \(\mathcal{A}\) be the set of equivalence classes. That is \[\mathcal{A} = \{[a] \in \mathcal{P}(A) : a\in A\}.\] Let \(a\in A\). Since \(\sim\) is reflexive, we have \(a\sim a\). Then \(a\in [a]\). Hence \(A\subseteq \cup\mathcal{A}\). Since each equivalence class is a set of elements of \(A\), we have \(\cup\mathcal{A} \subseteq A\). Then \(A = \cup\mathcal{A}\). Let \(X,Y\in\mathcal{A}\). Then there are \(x,y\in A\) such that \(X=[x]\) and \(Y=[y]\). Suppose \(X \cap Y \neq \emptyset\). Then there is \(z\in X\cap Y\). Then \(z\in X\) and \(z\in Y\). Hence \(z\sim x\) and \(z\sim y\). For any \(u\in X\), we use symmetry and transitivity of \(\sim\) to show that \(u\sim x\sim z\sim y\), hence \(u\in Y\) and \(X\subseteq Y\). Likewise \(Y\subseteq X\) and \(X=Y\). It follows that \(\mathcal{A}\) is a partition of \(A\). ◻

Source File: jakemath.com/latex/sets/relations.tex