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

1. Image of Subset under Mapping is Subset of Image

   Let $f: S \to T$ be a mapping from $S$ to $T$ and $A, B \subseteq S$ such that $A \subseteq B$.

   Then $A \subseteq B \implies f \sqbrk A \subseteq f \sqbrk B$

2. Inverse of Mapping is One-to-Many Relation

   Let $f$ be a mapping.

   Then its inverse $f^{-1}$ is a one-to-many relation.

3. Preimage of Mapping equals Domain

   The preimage of a mapping is the same set as its domain: $\Preimg f = \Dom f$

4. Null Relation is Mapping iff Domain is Empty Set

   Let $S$ and $T$ be sets.

   The null relation $\mathcal R = \varnothing \subseteq S \times T$ is a mapping iff $S = \varnothing$.

5. Mapping is Constant iff Image is Singleton

   A mapping is a constant mapping if and only if its image is a singleton.

6. Identity Mapping is Left Identity

   Let $f: S \to T$ be a mapping.

   Then $I_T \circ f = f$

7. Identity Mapping is Right Identity

   Let $f: S \to T$ be a mapping.

   Then $f \circ I_S = f$

Injections

1. Equivalence of Definitions of Injection

   $\forall x_1, x_2 \in \Dom f: \map f {x_1} = \map f {x_2} \implies x_1 = x_2$

   $\forall x_1, x_2 \in \Dom f: x_1 \ne x_2 \implies \map f {x_1} \ne \map f {x_2}$

   An injection is a relation which is both one-to-one and left-total.

   $f^{-1} {\restriction_{\Img f} }: \Img f \to \Dom f$ is a mapping

   $\forall y \in \Img f: \card {\map {f^{-1} } y} = \card {\set {f^{-1} \sqbrk {\set y} } } = 1$

   $\exists g: T \to S: g \circ f = I_S$

   $f$ is an injection if and only if $f$ is left cancellable

2. Injection iff Left Cancellable

   A mapping $f$ is an injection if and only if $f$ is left cancellable.

3. Identity Mapping is Injection

   On any set $S$, the identity mapping $I_S: S \to S$ is an injection.

4. Composite of Injections is Injection

   #: If $g$ and $f$ are injections, then so is the composite $g \circ f$.

5. Injection if Composite is Injection

   Let $f$ and $g$ be mappings such that their composite $g \circ f$ is an injection.

   Then $f$ is an injection.

6. Injection iff Left Inverse

   A mapping $f: S \to T, S \ne \O$ is an injection if and only if: $\exists g: T \to S: g \circ f = I_S$

   That is, if and only if $f$ has a left inverse.

7. Inclusion Mapping is Injection

   The inclusion mapping $i_S: S \to T$ defined as: $\forall x \in S: i_S \left({x}\right) = x$ is an injection

8. Restriction of Injection is Injection

Surjections

1. Equivalence of Definitions of Surjection

   $f: S \to T$ is a surjection if and only if $\forall y \in T: \exists x \in \Dom f: \map f x = y$ (that is, if and only if $f$ is right-total).

   $f: S \to T$ is a surjection if and only if: $f \sqbrk S = T$ (that is, $f$ is a surjection if and only if its image equals its codomain: $\Img f = \Cdm f$)

2. Surjection iff Right Cancellable

   A mapping $f$ is a surjection if and only if $f$ is right cancellable.

3. Identity Mapping is Surjection

   On any set $S$, the identity mapping $I_S: S \to S$ is a surjection.

4. Composite of Surjections is Surjection

   If $g$ and $f$ are surjections, then so is the composite $g \circ f$.

5. Surjection iff Right Inverse

   A mapping $f: S \to T, S \ne \O$ is a surjection if and only if: $\exists g: T \to S: f \circ g = I_T$

   That is, if and only if $f$ has a right inverse.

6. Surjection if Composite is Surjection

   Let $f: S_1 \to S_2$ and $g: S_2 \to S_3$ be mappings such that $g \circ f$ is a surjection.

   Then $g$ is a surjection.

Bijections

1. Identity Mapping is Bijection

   The identity mapping $I_S: S \to S$ on the set $S$ is a bijection.

2. Identity Mapping is Permutation

   The identity mapping $I_S: S \to S$ on the set $S$ is a permutation.

3. Equivalence of Definitions of Bijection

   $f$ is both an injection and a surjection.

   $f$ has both a left inverse and a right inverse.

   The inverse $f^{-1}$ of $f$ is a mapping from $T$ to $S$.

   For each $y \in T$ there exists one and only one $x \in S$ such that $\tuple {x, y} \in f$.

   For each $x \in S$ there exists one and only one $y \in T$ such that $\left({x, y}\right) \in f$ and for each $y \in T$ there exists one and only one $x \in S$ such that $\left({x, y}\right) \in f$.

4. Composite of Bijection with Inverse is Identity Mapping

   Let $f: S \to T$ be a bijection.

   Then $f^{-1} \circ f = I_S$ and $f \circ f^{-1} = I_T$

5. Inverse of Inverse of Bijection

   Let $f: S \to T$ be a bijection.

   Then $\paren {f^{-1} }^{-1} = f$

6. Composite of Bijections is Bijection

   If $f$ and $g$ are both bijections, then so is the composite $f \circ g$.

7. Inverse of Composite Bijection

   Let $f$ and $g$ be bijections.

   Then $\left({g \circ f}\right)^{-1} = f^{-1} \circ g^{-1}$ and $f^{-1} \circ g^{-1}$ is itself a bijection.

8. Composite of Permutations is Permutation

   Let $f, g$ are permutations of a set $S$.

   Then their composite $g \circ f$ is also a permutation of $S$.

9. Inverse of Permutation is Permutation

   If $f$ is a permutation of $S$, then so is its inverse $f^{-1}$.

10. Left Inverse Mapping is Surjection

    Let $f: S \to T$ be an injection and $g: T \to S$ be a left inverse of $f$.

    Then $g$ is a surjection.

11. Right Inverse Mapping is Injection

    Let $f: S \to T$ be a mapping and $g: T \to S$ be a right inverse of $f$.

    Then $g$ is an injection.

12. Restriction of Mapping to Image is Surjection

    Let $f: S \to T$ be a mapping and $g: S \to \Img f$ be the restriction of $f$ to $S \times \Img f$.

    Then $g$ is a surjective restriction of $f$.

Images

1. Image of Union under Mapping

   Let $S$ and $T$ be sets, $f: S \to T$ be a mapping, and $A$ and $B$ be subsets of $S$.

   Then $f \sqbrk {A \cup B} = f \sqbrk A \cup f \sqbrk B$

2. Image of Intersection under Mapping

   Let $S$ and $T$ be sets, $f: S \to T$ be a mapping, and $A$ and $B$ be subsets of $S$.

   Then $f \sqbrk {A \cap B} \subseteq f \sqbrk A \cup f \sqbrk B$

3. Image of Intersection under Injection

   Let $S$ and $T$ be sets, $f: S \to T$ be a mapping, and $A$ and $B$ be subsets of $S$.

   Then $f \sqbrk {A \cap B} = f \sqbrk A \cup f \sqbrk B$ if and only if $f$ is an injection.

4. Preimage of Union under Mapping

   Let $S$ and $T$ be sets, $f: S \to T$ be a mapping, and $T_1$ and $T_2$ be subsets of $T$.

   Then $f^{-1} \sqbrk {T_1 \cup T_2} = f^{-1} \sqbrk {T_1} \cup f^{-1} \sqbrk {T_2}$

5. Preimage of Intersection under Mapping

   Let $S$ and $T$ be sets, $f: S \to T$ be a mapping, and $T_1$ and $T_2$ be subsets of $T$.

   Then $f^{-1} \sqbrk {T_1 \cap T_2} = f^{-1} \sqbrk {T_1} \cap f^{-1} \sqbrk {T_2}$

6. Image of Set Difference under Mapping

   Let $f: S \to T$ be a mapping and $S_1$ and $S_2$ be subsets of $S$.

   Then $f \sqbrk {S_1} \setminus f \sqbrk {S_2} \subseteq f \sqbrk {S_1 \setminus S_2}$

7. Image of Set Difference under Injection

   Let $f: S \to T$ be a mapping and $S_1$ and $S_2$ be subsets of $S$.

   Then $\forall S_1, S_2 \subseteq S: f \left[{S_1}\right] \setminus f \left[{S_2}\right] = f \left[{S_1 \setminus S_2}\right]$

8. Preimage of Set Difference under Mapping

   Let $f: S \to T$ be a mapping and $T_1$ and $T_2$ be subsets of $T$.

   Then $f^{-1} \sqbrk {T_1 \setminus T_2} = f^{-1} \sqbrk {T_1} \setminus f^{-1} \sqbrk {T_2}$

9. Quotient Mapping is Surjection

   Let $\mathcal R$ be an equivalence relation on $S$.

   Then the quotient mapping $q_{\mathcal R}: S \to S / \mathcal R$ is a surjection.

10. Relation Induced by Mapping is Equivalence Relation

    Let $f: S \to T$ be a mapping and $\mathcal R_f \subseteq S \times S$ be the relation induced by $f$.

    Then $\mathcal R_f$ is an equivalence relation.