note-math

composition (function composition)

Define proposition, parameter $𝑓:𝐴\to 𝐵$

• injective := $\forall 𝑎,{𝑎}^{\prime }\in 𝐴,𝑓\left(𝑎\right)=𝑓\left({𝑎}^{\prime }\right)⟹𝑎={𝑎}^{\prime }$. Notation $𝑓:𝐴\hookrightarrow 𝐵$
• surjective := $\forall 𝑏\in 𝐵,\exists 𝑎\in 𝐴,𝑓\left(𝑎\right)=𝑏$. Notation $𝑓:𝐴\twoheadrightarrow 𝐵$
• bijective := injective and surjective. Notation $𝑓:𝐴\leftrightarrow 𝐵$. At this time, there exists an inverse mapping ${𝑓}^{-1}:𝐵\leftrightarrow 𝐴$

cardinal_(tag)

• $\left|𝐴\right|=\left|𝐵\right|≔\text{bijective}\left(𝐴\to 𝐵\right)\ne \varnothing$. or there exists a bijection $𝑓:𝐴\leftrightarrow 𝐵$
• $\left|𝐴\right|\le \left|𝐵\right|≔\text{injective}\left(𝐴\to 𝐵\right)\ne \varnothing$. or there exists an injection $𝑓:𝐴\hookrightarrow 𝐵$
• $\left|𝐴\right|\ge \left|𝐵\right|≔\text{surjective}\left(𝐴\to 𝐵\right)\ne \varnothing$. or there exists a surjection $𝑓:𝐴\twoheadrightarrow 𝐵$

• Symmetry of injection and surjection

  $$\text{surjective}\left(𝐴\to 𝐵\right)\ne \varnothing ⟺\text{injective}\left(𝐵\to 𝐴\right)\ne \varnothing$$

  or there exists a surjection $𝑓:𝐴\twoheadrightarrow 𝐵$ <==> there exists an injection $𝑔:𝐵\hookrightarrow 𝐴$

cardinal-always-comparable_(tag) Trichotomy of element number order $<$ or order is always #link(<order-comparable>)[comparable]

$$\forall 𝐴,𝐵\in \text{ Set},\left(\left|𝐴\right|=\left|𝐵\right|\right)\oplus \left(\left|𝐴\right|<\left|𝐵\right|\right)\oplus \left(\left|𝐵\right|<\left|𝐴\right|\right)$$

finite_(tag) := $\exists 𝑛\in \mathrm{\mathbb{N}},\left|𝐴\right|=\left|\left\{0,1,\dots ,𝑛-1\right\}\right|$. also let $\left|\left\{0,1,\dots ,𝑛-1\right\}\right|=𝑛$

finite <==> $\left|𝐴\right|<\mathrm{\mathbb{N}}$

$𝐴$ is a finite set ==> ($𝑓:𝐴\to 𝐴$ is injective or surjective <==> $𝑓$ is bijective)

Example $\mathrm{\mathbb{N}}$ is an infinite set, $\begin{array}{ccccc}\mathrm{\mathbb{N}}& & ⟶& & \mathrm{\mathbb{N}}\\ 𝑛& & ⟿& & 2𝑛\end{array}$ is injective and not surjective, so not bijective

• countably infinite := $\left|𝐴\right|=\left|\mathrm{\mathbb{N}}\right|$
• uncountable_(tag) uncountable := $\left|𝐴\right|>\left|\mathrm{\mathbb{N}}\right|$
• countable_(tag) countable := $\left|𝐴\right|\le \left|\mathrm{\mathbb{N}}\right|$ i.e. finite or countably infinite

Operations that preserve countability. let $\forall 𝑖\in \mathrm{\mathbb{N}}$, ${𝐴}_{𝑖}$ is countable. The following sets are countable

• union: ${𝐴}_1\cup \cdots \cup {𝐴}_{𝑛}$, ${\bigcup }_{𝑖\in \mathrm{\mathbb{N}}}{𝐴}_{𝑖}$
• product: ${𝐴}_1\times \cdots \times {𝐴}_{𝑛}$, ${\prod }_{𝑖\in \mathrm{\mathbb{N}}}{𝐴}_{𝑖}$

range_(tag) $\text{Range}\left(𝑓\right)≔\left\{𝑏\in 𝐵:\exists 𝑎\in 𝐴,𝑏=𝑓\left(𝑎\right)\right\}$. alias image of $𝑓$, $\text{im}\left(𝑓\right)$, $𝑓\left(𝐴\right)$

codomain_(tag) $\text{co-domain}\left(𝑓\right)=𝐵$. alias range 值域

let $𝑆\subset 𝐴$

image_(tag) Image like $𝑓\left(𝑆\right)≔\left\{𝑏\in 𝐵:\exists 𝑎\in 𝑆,𝑏=𝑓\left(𝑎\right)\right\}$

let $𝑆\subset 𝐵$

inverse-image_(tag) Inverse image ${𝑓}^{-1}\left(𝑆\right)≔\left\{𝑎\in 𝐴:\exists 𝑏\in 𝑆,𝑏=𝑓\left(𝑎\right)\right\}$

$\begin{array}{ccc}𝑓\left(𝑎\right)\in 𝑆& ⟺& \exists 𝑏\in 𝑆,𝑏=𝑓\left(𝑎\right)\\ & ⟺& 𝑎\in {𝑓}^{-1}\left(𝑆\right)\end{array}$

==>

$\begin{array}{ccc}𝑓\left({𝑆}_{𝐴}\right)\subset {𝑆}_{𝐵}& ⟺& \forall 𝑎\in {𝑆}_{𝐴},𝑓\left(𝑎\right)\in {𝑆}_{𝐵}\\ & ⟺& \forall 𝑎\in {𝑆}_{𝐴},𝑎\in {𝑓}^{-1}\left({𝑆}_{𝐵}\right)\\ & ⟺& {𝑆}_{𝐴}\subset {𝑓}^{-1}\left({𝑆}_{𝐵}\right)\end{array}$

Inverse image ${𝑓}^{-1}$ maintains $\cup ,\cap ,\setminus$, e.g.

$${𝑓}^{-1}\left(𝑆\cup {𝑆}^{\prime }\right)={𝑓}^{-1}\left(𝑆\right)\cup {𝑓}^{-1}\left({𝑆}^{\prime }\right)$$

Image $𝑓$ only maintains $\cup$, for others

• $𝑓\left(𝑆\cap {𝑆}^{\prime }\right)\subset 𝑓\left(𝑆\right)\cap 𝑓\left({𝑆}^{\prime }\right)$
• $𝑓\left(𝑆\setminus {𝑆}^{\prime }\right)\subset 𝑓\left(𝑆\right)\setminus 𝑓\left({𝑆}^{\prime }\right)$

cardinal-increase_(tag) $\left|𝐴\right|<\left|\text{Subset}\left(𝐴\right)\right|$ (cf. #link(<cardinal>)[])

Partition $𝑋$. Directly $𝑋=⨆{𝑋}_{𝑖}$ or according to the inverse image of the image set of the mapping $𝑓:𝑋\to 𝑌$, ${⨆}_{𝑦\in 𝑌}{𝑓}^{-1}\left(𝑦\right)$

quotient_(tag) quotient $𝑥\sim {𝑥}^{\prime }$ := $𝑥,{𝑥}^{\prime }\in {𝑋}_{𝑖}$ or $𝑥,{𝑥}^{\prime }\in {𝑓}^{-1}\left(𝑦\right)$