User:Ascii/ProofWiki Sampling Notes for Theorems/Relation Theory
Jump to navigation
Jump to search
Images
- Image of Singleton under Relation
- $\forall s \in S: \mathcal R \left({s}\right) = \mathcal R \left[{\left\{{s}\right\}}\right]$
- Image of Subset under Relation is Subset of Image
- $A \subseteq B \implies \mathcal R \left[{A}\right] \subseteq \mathcal R \left[{B}\right]$
- Image of Element is Subset
- $s \in A \implies \mathcal R \left({s}\right) \subseteq \mathcal R \left[{A}\right]$
- Image is Subset of Codomain
- $\forall A \subseteq \operatorname{Dom} \left ({\mathcal R}\right): \mathcal R \left({A}\right) \subseteq T$
- Image of Empty Set is Empty Set
- $\mathcal R \left[{\varnothing}\right] = \varnothing$
Composition
- Domain of Composite Relation
- $\operatorname{Dom} \left ({\mathcal R_2 \circ \mathcal R_1}\right) = \operatorname{Dom} \left ({\mathcal R_1}\right)$
- 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}$
- Inverse of Inverse Relation
- $\left({\mathcal R^{-1}}\right)^{-1} = \mathcal R$
- Preimage of Relation is Subset of Domain
- $\operatorname{Im}^{-1} \left({\mathcal R}\right) \subseteq S$
- Inverse of Composite Relation
- $\left({\mathcal R_2 \circ \mathcal R_1}\right)^{-1} = \mathcal R_1^{-1} \circ \mathcal R_2^{-1}$
- Image of Union under Relation
- $\mathcal R \sqbrk {S_1 \cup S_2} = \mathcal R \sqbrk {S_1} \cup \mathcal R \sqbrk {S_2}$
- 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}$
- Image of Set Difference under Relation
- $\mathcal R \sqbrk A \setminus \mathcal R \sqbrk B \subseteq \mathcal R \sqbrk {A \setminus B}$
- 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]$
- 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]$
- 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]$
- 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)$
- 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.
- Image of Intersection under One-to-Many Relation
if and only if $\mathcal R$ is one-to-many.
if and only if $\mathcal R$ is one-to-many.
Properties
- 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$
- 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}$
- 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$.
- Relation Reflexivity
- Every relation has exactly one of these properties: it is either: reflexive, antireflexive or non-reflexive.
- Relation Symmetry
- Every non-null relation has exactly one of these properties: it is either symmetric, asymmetric or non-symmetric.
- 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$.
- 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$
- Relation is Symmetric and Antisymmetric iff Coreflexive
- Asymmetric Relation is Antisymmetric
- Asymmetric Relation is Antireflexive
- Antireflexive and Transitive Relation is Asymmetric
- Antireflexive and Transitive Relation is Antisymmetric
- Antitransitive Relation is Antireflexive
- 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.
Inverse Relations
- Inverse of Reflexive Relation is Reflexive
- Inverse of Antireflexive Relation is Antireflexive
- Inverse of Non-Reflexive Relation is Non-Reflexive
- Inverse of Symmetric Relation is Symmetric
- Inverse of Antisymmetric Relation is Antisymmetric
- Inverse of Asymmetric Relation is Asymmetric
- Inverse of Non-Symmetric Relation is Non-Symmetric
- Inverse of Transitive Relation is Transitive
- Inverse of Antitransitive Relation is Antitransitive
- Inverse of Non-Transitive Relation is Non-Transitive
Restriction of Relation
- Restriction of Reflexive Relation is Reflexive
- Restriction of Antireflexive Relation is Antireflexive
- Restriction of Symmetric Relation is Symmetric
- Restriction of Antisymmetric Relation is Antisymmetric
- Restriction of Asymmetric Relation is Asymmetric
- Restriction of Transitive Relation is Transitive
- Restriction of Antitransitive Relation is Antitransitive
- Restriction of Connected Relation is Connected
- Restriction of Serial Relation is Not Necessarily Serial
- Restriction of Non-Reflexive Relation is Not Necessarily Non-Reflexive
- Restriction of Non-Symmetric Relation is Not Necessarily Non-Symmetric
- Restriction of Non-Transitive Relation is Not Necessarily Non-Transitive
- Restriction of Non-Connected Relation is Not Necessarily Non-Connected
- Inverse Relation Equal iff Subset
- 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.
- 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
- 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$
- Diagonal Relation is Equivalence
- The diagonal relation $\Delta_S$ on a set $S$ is always an equivalence in $S$.
- Trivial Relation is Equivalence
- The trivial relation on $S$: $\mathcal R = S \times S$ is always an equivalence in $S$.
- 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}$
- 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$
- Equivalence Class is not Empty
- Let $\mathcal R$ be an equivalence relation on a set $S$.
- Then no $\mathcal R$-class is empty.
- 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}$
- 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$
- 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$.
- 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}$.
- 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$.
- Intersection of Equivalences
- The intersection of two equivalence relations is itself an equivalence relation.
- Union of Equivalences
- The union of two equivalence relations is not necessarily an equivalence relation itself.
- 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}$.