User:Ascii/ProofWiki Sampling Notes for Theorems/Mapping Theory
Jump to navigation
Jump to search
- 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$
- Inverse of Mapping is One-to-Many Relation
- Let $f$ be a mapping.
- Then its inverse $f^{-1}$ is a one-to-many relation.
- Preimage of Mapping equals Domain
- The preimage of a mapping is the same set as its domain: $\Preimg f = \Dom f$
- 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$.
- Mapping is Constant iff Image is Singleton
- A mapping is a constant mapping if and only if its image is a singleton.
- Identity Mapping is Left Identity
- Let $f: S \to T$ be a mapping.
- Then $I_T \circ f = f$
- Identity Mapping is Right Identity
- Let $f: S \to T$ be a mapping.
- Then $f \circ I_S = f$
Injections
- 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
- Injection iff Left Cancellable
- A mapping $f$ is an injection if and only if $f$ is left cancellable.
- Identity Mapping is Injection
- On any set $S$, the identity mapping $I_S: S \to S$ is an injection.
- Composite of Injections is Injection
- #: If $g$ and $f$ are injections, then so is the composite $g \circ f$.
- Injection if Composite is Injection
- 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.
- 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
- Restriction of Injection is Injection
Surjections
- 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$)
- Surjection iff Right Cancellable
- A mapping $f$ is a surjection if and only if $f$ is right cancellable.
- Identity Mapping is Surjection
- On any set $S$, the identity mapping $I_S: S \to S$ is a surjection.
- Composite of Surjections is Surjection
- If $g$ and $f$ are surjections, then so is the composite $g \circ f$.
- 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.
- 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
- Identity Mapping is Bijection
- The identity mapping $I_S: S \to S$ on the set $S$ is a bijection.
- Identity Mapping is Permutation
- The identity mapping $I_S: S \to S$ on the set $S$ is a permutation.
- 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$.
- 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$
- Inverse of Inverse of Bijection
- Let $f: S \to T$ be a bijection.
- Then $\paren {f^{-1} }^{-1} = f$
- Composite of Bijections is Bijection
- If $f$ and $g$ are both bijections, then so is the composite $f \circ g$.
- 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.
- 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$.
- Inverse of Permutation is Permutation
- If $f$ is a permutation of $S$, then so is its inverse $f^{-1}$.
- 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.
- 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.
- 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
- Image of Union under Mapping
- Image of Intersection under Mapping
- 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.
- Preimage of Union under Mapping
- Preimage of Intersection under Mapping
- Image of Set Difference under Mapping
- Image of Set Difference under Injection
- Preimage of Set Difference under Mapping
- 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.
- 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.