# User:Ascii/ProofWiki Sampling Notes for Theorems/Relation Theory

### Images

1. Image of Singleton under Relation
$\forall s \in S: \mathcal R \left({s}\right) = \mathcal R \left[{\left\{{s}\right\}}\right]$
2. Image of Subset under Relation is Subset of Image
$A \subseteq B \implies \mathcal R \left[{A}\right] \subseteq \mathcal R \left[{B}\right]$
3. Image of Element is Subset
$s \in A \implies \mathcal R \left({s}\right) \subseteq \mathcal R \left[{A}\right]$
4. Image is Subset of Codomain
$\forall A \subseteq \operatorname{Dom} \left ({\mathcal R}\right): \mathcal R \left({A}\right) \subseteq T$
5. Image of Empty Set is Empty Set
$\mathcal R \left[{\varnothing}\right] = \varnothing$

### Composition

1. Domain of Composite Relation
$\operatorname{Dom} \left ({\mathcal R_2 \circ \mathcal R_1}\right) = \operatorname{Dom} \left ({\mathcal R_1}\right)$
2. Composition of Relations is Associative
$\paren {\mathcal R_3 \circ \mathcal R_2} \circ \mathcal R_1 = \mathcal R_3 \circ \paren {\mathcal R_2 \circ \mathcal R_1}$
3. Inverse of Inverse Relation
$\left({\mathcal R^{-1}}\right)^{-1} = \mathcal R$
4. Preimage of Relation is Subset of Domain
$\operatorname{Im}^{-1} \left({\mathcal R}\right) \subseteq S$
5. Inverse of Composite Relation
$\left({\mathcal R_2 \circ \mathcal R_1}\right)^{-1} = \mathcal R_1^{-1} \circ \mathcal R_2^{-1}$
6. Image of Union under Relation
$\mathcal R \sqbrk {S_1 \cup S_2} = \mathcal R \sqbrk {S_1} \cup \mathcal R \sqbrk {S_2}$
7. Image of Intersection under Relation
$\mathcal R \sqbrk {S_1 \cap S_2} \subseteq \mathcal R \sqbrk {S_1} \cap \mathcal R \sqbrk {S_2}$
8. Image of Set Difference under Relation
$\mathcal R \sqbrk A \setminus \mathcal R \sqbrk B \subseteq \mathcal R \sqbrk {A \setminus B}$
9. Preimage of Union under Relation
$\mathcal R^{-1} \left[{T_1 \cup T_2}\right] = \mathcal R^{-1} \left[{T_1}\right] \cup \mathcal R^{-1} \left[{T_2}\right]$
10. Preimage of Intersection under Relation
$\mathcal R^{-1} \left[{C \cap D}\right] \subseteq \mathcal R^{-1} \left[{C}\right] \cap \mathcal R^{-1} \left[{D}\right]$
11. Preimage of Set Difference under Relation
$\mathcal R^{-1} \left[{C}\right] \setminus \mathcal R^{-1} \left[{D}\right] \subseteq \mathcal R^{-1} \left[{C \setminus D}\right]$
12. Image of Subset is Image of Restriction
Let $f: S \to T$ be a mapping, $X \subseteq S$, and $f \restriction_X$ be the restriction of $f$ to $X$.
Then $f \left[{X}\right] = \operatorname{Im} \left({f \restriction_X}\right)$
13. Inverse of Many-to-One Relation is One-to-Many
The inverse of a many-to-one relation is a one-to-many relation, and vice versa.
14. Image of Intersection under One-to-Many Relation
Let $S$ and $T$ be sets and $\mathcal R \subseteq S \times T$ be a relation.
Then $\forall S_1, S_2 \subseteq S: \mathcal R \left[{S_1 \cap S_2}\right] = \mathcal R \left[{S_1}\right] \cap \mathcal R \left[{S_2}\right]$

if and only if $\mathcal R$ is one-to-many.

1. One-to-Many Image of Set Difference
Let $\mathcal R \subseteq S \times T$ be a relation and $A$ and $B$ be subsets of $S$.
Then $\quad \mathcal R \left[{A}\right] \setminus \mathcal R \left[{B}\right] = \mathcal R \left[{A \setminus B}\right]$

if and only if $\mathcal R$ is one-to-many.

### Properties

1. Equivalence of Definitions of Reflexive Relation
$\mathcal R$ is reflexive if and only if $\forall x \in S: \tuple {x, x} \in \mathcal R$
$\mathcal R$ is reflexive if and only if it is a superset of the diagonal relation: $\Delta_S \subseteq \mathcal R$
2. Equivalence of Definitions of Symmetric Relation
$\tuple {x, y} \in \mathcal R \implies \tuple {y, x} \in \mathcal R$
$\mathcal R^{-1} = \mathcal R$
$\mathcal R \subseteq \mathcal R^{-1}$
3. Equivalence of Definitions of Transitive Relation
$\mathcal R$ is transitive if and only if $\tuple {x, y} \in \mathcal R \land \tuple {y, z} \in \mathcal R \implies \tuple {x, z} \in \mathcal R$.
$\mathcal R$ is transitive if and only if $\mathcal R \circ \mathcal R \subseteq \mathcal R$.
4. Relation Reflexivity
Every relation has exactly one of these properties: it is either: reflexive, antireflexive or non-reflexive.
5. Relation Symmetry
Every non-null relation has exactly one of these properties: it is either symmetric, asymmetric or non-symmetric.
6. Relation is Reflexive Symmetric and Antisymmetric iff Diagonal Relation
$\mathcal R$ is reflexive, symmetric and antisymmetric if and only if $\mathcal R$ is the diagonal relation $\Delta_S$.
7. Relation both Symmetric and Asymmetric is Null
Let $\mathcal R$ be a relation in $S$ which is both symmetric and asymmetric.
Then $\mathcal R = \varnothing$
8. Relation is Symmetric and Antisymmetric iff Coreflexive
9. Asymmetric Relation is Antisymmetric
10. Asymmetric Relation is Antireflexive
11. Antireflexive and Transitive Relation is Asymmetric
12. Antireflexive and Transitive Relation is Antisymmetric
13. Antitransitive Relation is Antireflexive
14. Symmetric Transitive and Serial Relation is Reflexive
Let $\mathcal R$ be a relation which is symmetric, transitive, and serial.
Then $\mathcal R$ is reflexive. Thus such a relation is an equivalence.

### Restriction of Relation

1. Inverse Relation Equal iff Subset
If a relation $\mathcal R$ is a subset or superset of its inverse, then it equals its inverse.
2. Composition of Relation with Inverse is Symmetric
Let $\mathcal R \subseteq S \times T$ be a relation.
Then the composition of $\mathcal R$ with its inverse $\mathcal R^{-1}$ is symmetric.
3. Many-to-One Relation Composite with Inverse is Transitive
Let $\mathcal R \subseteq S \times T$ be a relation which is many-to-one.
Then the composites (both ways) of $\mathcal R$ and its inverse $\mathcal R^{-1}$, that is, both $\mathcal R^{-1} \circ \mathcal R$ and $\mathcal R \circ \mathcal R^{-1}$, are transitive.

### Equivalence Relations

1. Equivalence of Definitions of Equivalence Relation
$\mathcal R$ is an equivalence relation if and only if it is reflexive, symmetric, and transitive.
$\mathcal R$ is an equivalence relation if and only if: $\Delta_S \cup \mathcal R^{-1} \cup \mathcal R \circ \mathcal R \subseteq \mathcal R$
2. Diagonal Relation is Equivalence
The diagonal relation $\Delta_S$ on a set $S$ is always an equivalence in $S$.
3. Trivial Relation is Equivalence
The trivial relation on $S$: $\mathcal R = S \times S$ is always an equivalence in $S$.
4. Element in its own Equivalence Class
Let $\mathcal R$ be an equivalence relation on a set $S$.
Then every element of $S$ is in its own $\mathcal R$-class: $\forall x \in S: x \in \eqclass x {\mathcal R}$
5. Equivalence Class of Element is Subset
Let $\mathcal R$ be an equivalence relation on a set $S$.
The $\mathcal R$-class of every element of $S$ is a subset of the set the element is in: $\forall x \in S: \left[\!\left[{x}\right]\!\right]_\mathcal R \subseteq S$
6. Equivalence Class is not Empty
Let $\mathcal R$ be an equivalence relation on a set $S$.
Then no $\mathcal R$-class is empty.
7. Equivalence Class holds Equivalent Elements
Let $\mathcal R$ be an equivalence relation on a set $S$.
Then: $\tuple {x, y} \in \mathcal R \iff \eqclass x {\mathcal R} = \eqclass y {\mathcal R}$
8. Equivalence Classes are Disjoint
Let $\mathcal R$ be an equivalence relation on a set $S$.
Then all $\mathcal R$-classes are pairwise disjoint: $\tuple {x, y} \notin \mathcal R \iff \eqclass x {\mathcal R} \cap \eqclass y {\mathcal R} = \O$
9. Fundamental Theorem on Equivalence Relations
Let $\mathcal R \subseteq S \times S$ be an equivalence on a set $S$.
Then the quotient $S / \mathcal R$ of $S$ by $\mathcal R$ forms a partition of $S$.
10. Equivalence Class is Unique
Let $\mathcal R$ be an equivalence relation on $S$.
For each $x \in S$, the one and only one $\mathcal R$-class to which $x$ belongs is $\eqclass x {\mathcal R}$.
11. Union of Equivalence Classes is Whole Set
Let $\mathcal R \subseteq S \times S$ be an equivalence on a set $S$.
Then the set of $\mathcal R$-classes constitutes the whole of $S$.
12. Intersection of Equivalences
The intersection of two equivalence relations is itself an equivalence relation.
13. Union of Equivalences
The union of two equivalence relations is not necessarily an equivalence relation itself.
14. Equivalence iff Diagonal and Inverse Composite
Let $\mathcal R$ be a relation on $S$.
Then $\mathcal R$ is an equivalence relation on $S$ iff $\Delta_S \subseteq \mathcal R$ and $\mathcal R = \mathcal R \circ \mathcal R^{-1}$.