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

From ProofWiki
Jump to navigation Jump to search

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.

Inverse Relations

  1. Inverse of Reflexive Relation is Reflexive
    Let $\mathcal R$ be a relation on a set $S$.
    If $\mathcal R$ is reflexive, then so is $\mathcal R^{-1}$.
  2. Inverse of Antireflexive Relation is Antireflexive
  3. Inverse of Non-Reflexive Relation is Non-Reflexive
  4. Inverse of Symmetric Relation is Symmetric
  5. Inverse of Antisymmetric Relation is Antisymmetric
  6. Inverse of Asymmetric Relation is Asymmetric
  7. Inverse of Non-Symmetric Relation is Non-Symmetric
  8. Inverse of Transitive Relation is Transitive
  9. Inverse of Antitransitive Relation is Antitransitive
  10. Inverse of Non-Transitive Relation is Non-Transitive

Restriction of Relation

  1. Restriction of Reflexive Relation is Reflexive
  2. Restriction of Antireflexive Relation is Antireflexive
  3. Restriction of Symmetric Relation is Symmetric
  4. Restriction of Antisymmetric Relation is Antisymmetric
  5. Restriction of Asymmetric Relation is Asymmetric
  6. Restriction of Transitive Relation is Transitive
  7. Restriction of Antitransitive Relation is Antitransitive
  8. Restriction of Connected Relation is Connected
  9. Restriction of Serial Relation is Not Necessarily Serial
  10. Restriction of Non-Reflexive Relation is Not Necessarily Non-Reflexive
  11. Restriction of Non-Symmetric Relation is Not Necessarily Non-Symmetric
  12. Restriction of Non-Transitive Relation is Not Necessarily Non-Transitive
  13. Restriction of Non-Connected Relation is Not Necessarily Non-Connected
  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}$.