00 Sets and Relations

$$ \nonumber \newcommand{aster}{*} \newcommand{exist}{\exists} \newcommand{B}{\mathbb B} \newcommand{C}{\mathbb C} \newcommand{I}{\mathbb I} \newcommand{N}{\mathbb N} \newcommand{Q}{\mathbb Q} \newcommand{R}{\mathbb R} \newcommand{Z}{\mathbb Z} \newcommand{eR}{\overline {\mathbb R}} \newcommand{cD}{ {\mathbb D}} \newcommand{dD}{ {\part \mathbb D}} \newcommand{dH}{ {\part \mathbb H}} \newcommand{eC}{\overline {\mathbb C}} \newcommand{A}{\mathcal A} \newcommand{D}{\mathcal D} \newcommand{E}{\mathcal E} \newcommand{F}{\mathcal F} \newcommand{G}{\mathcal G} \newcommand{H}{\mathcal H} \newcommand{J}{\mathcal J} \newcommand{L}{\mathcal L} \newcommand{U}{\mathcal U} \newcommand{M}{\mathcal M} \newcommand{O}{\mathcal O} \newcommand{P}{\mathcal P} \newcommand{S}{\mathcal S} \newcommand{T}{\mathcal T} \newcommand{V}{\mathcal V} \newcommand{W}{\mathcal W} \newcommand{X}{\mathcal X} \newcommand{Y}{\mathcal Y} \newcommand{bE}{\symbf E} \newcommand{bF}{\symbf F} \newcommand{bD}{\symbf D} \newcommand{bI}{\symbf I} \newcommand{bX}{\symbf X} \newcommand{bY}{\symbf Y} \newcommand{nz}{\mathcal Z} \newcommand{bT}{\mathbb T} \newcommand{bB}{\mathbb B} \newcommand{bS}{\mathbb S} \newcommand{bA}{\mathbb A} \newcommand{bL}{\mathbb L} \newcommand{bP}{\symbf P} \newcommand{bM}{\symbf M} \newcommand{bH}{\mathbb H} \newcommand{dd}{\mathrm d} \newcommand{Mu}{\mathup M} \newcommand{Tau}{\mathup T} \newcommand{ae}{\operatorname{a.e.}} \newcommand{aut}{\operatorname{aut}} \newcommand{adj}{\operatorname{adj}} \newcommand{char}{\operatorname{char}} \newcommand{cov}{\operatorname{Cov}} \newcommand{cl}{\operatorname{cl}} \newcommand{cont}{\operatorname{cont}} \newcommand{e}{\mathbb E} \newcommand{pp}{\operatorname{primitive}} \newcommand{dist}{\operatorname{dist}} \newcommand{diam}{\operatorname{diam}} \newcommand{fp}{\operatorname{Fp}} \newcommand{from}{\leftarrow} \newcommand{Gal}{\operatorname{Gal}} \newcommand{GCD}{\operatorname{GCD}} \newcommand{LCM}{\operatorname{LCM}} \newcommand{fg}{\mathrm{fg}} \newcommand{gf}{\mathrm{gf}} \newcommand{im}{\operatorname{Im}} \newcommand{image}{\operatorname{image}} \newcommand{inj}{\hookrightarrow} \newcommand{irr}{\operatorname{irr}} \newcommand{lcm}{\operatorname{lcm}} \newcommand{ltrieq}{\mathrel{\unlhd}} \newcommand{ltri}{\mathrel{\lhd}} \newcommand{loc}{ {\operatorname{loc}}} \newcommand{null}{\operatorname{null}} \newcommand{part}{\partial} \newcommand{pf}{\operatorname{Pf}} \newcommand{pv}{\operatorname{Pv}} \newcommand{rank}{\operatorname{rank}} \newcommand{range}{\operatorname{range}} \newcommand{re}{\operatorname{Re}} \newcommand{span}{\operatorname{span}} \newcommand{su}{\operatorname{supp}} \newcommand{sgn}{\operatorname{sgn}} \newcommand{syn}{\operatorname{syn}} \newcommand{var}{\operatorname{Var}} \newcommand{res}{\operatorname{Res}} \newcommand{data}{\operatorname{data}} \newcommand{erfc}{\operatorname{erfc}} \newcommand{erfcx}{\operatorname{erfcx}} \newcommand{tr}{\operatorname{tr}} \newcommand{col}{\operatorname{Col}} \newcommand{row}{\operatorname{Row}} \newcommand{sol}{\operatorname{Sol}} \newcommand{lub}{\operatorname{lub}} \newcommand{glb}{\operatorname{glb}} \newcommand{ltrieq}{\mathrel{\unlhd}} \newcommand{ltri}{\mathrel{\lhd}} \newcommand{lr}{\leftrightarrow} \newcommand{phat}{^\widehat{\,\,\,}} \newcommand{what}{\widehat} \newcommand{wbar}{\overline} \newcommand{wtilde}{\widetilde} \newcommand{iid}{\operatorname{i.i.d.}} \newcommand{Exp}{\operatorname{Exp}} \newcommand{abs}[1]{\left| {#1}\right|} \newcommand{d}[2]{D_{\text{KL}}\left (#1\middle\| #2\right)} \newcommand{n}[1]{\|#1\|} \newcommand{norm}[1]{\left\|{#1}\right\|} \newcommand{pd}[2]{\left \langle {#1},{#2} \right \rangle} \newcommand{argmax}[1]{\underset{#1}{\operatorname{argmax}}} \newcommand{argmin}[1]{\underset{#1}{\operatorname{argmin}}} \newcommand{p}[1]{\left({#1}\right)} \newcommand{c}[1]{\left \{ {#1}\right\}} \newcommand{s}[1]{\left [{#1}\right]} \newcommand{a}[1]{\left \langle{#1}\right\rangle} \newcommand{cc}[2]{\left(\begin{array}{c} #1 \\ #2 \end{array}\right)} \newcommand{f}{\mathfrak F} \newcommand{fi}{\mathfrak F^{-1}} \newcommand{Fi}{\mathcal F^{-1}} \newcommand{l}{\mathfrak L} \newcommand{li}{\mathfrak L^{-1}} \newcommand{Li}{\mathcal L^{-1}} \newcommand{const}{\text{const.}} \newcommand{Int}{\operatorname{Int}} \newcommand{Ext}{\operatorname{Ext}} \newcommand{Bd}{\operatorname{Bd}} \newcommand{Cl}{\operatorname{Cl}} \newcommand{Iso}{\operatorname{Iso}} \newcommand{Lim}{\operatorname{Lim}} \newcommand{src}{\operatorname{src}} \newcommand{tgt}{\operatorname{tgt}} \newcommand{input}{\operatorname{input}} \newcommand{output}{\operatorname{output}} \newcommand{weight}{\operatorname{weight}} \newcommand{paths}{\operatorname{paths}} \newcommand{init}{\bullet} \newcommand{fin}{\circledcirc} \newcommand{advance}{\operatorname{advance}} \newcommand{di}[2]{\frac{\part}{\part {#1}^{#2}}} $$

Sets #

Subset #

A set $B$ is a subset of a set $A,$ denoted by $B \subseteq A$ or $A \supseteq B,$ if every element of $B$ is in $A$. The notations $B \subset A$ or $A \supset B$ will be used for $B \subseteq A$ but $B \neq A$.

If $A$ is any set, then $A$ is the improper subset of $A .$ Any other subset of $A$ is a proper subset of $A$.

Cartesian product #

Let $A$ and $B$ be sets. The set $A \times B=\{(a, b) \mid a \in A$ and $b \in B\}$ is the Cartesian product of $A$ and $B$.

  • Let $(B _ i) _ {i = 1}^n$ be sets, finite length cartesian product $\prod _ {i=1}^n B _ i$ exists.
  • Let $H$ be a function with domain $I$, $H(i) = H _ i$.
    • Such a function is also viewed as an indexed family of sets.
  • Let $H:= \cup H _ i$. Set theory guarantees the existence of $$ X = \prod _ {i \in I} H _ i = \{f \mid f:I \to H \land \forall i\in I: f(i) \in H _ i\} $$
    • If some $H(i)$ is empty, the product $\prod H _ i$ is $\varnothing$.
    • The axiom of choice guarantees that the product is non-empty when all $H _ i$ is non-empty.
    • For $x \in X$, $x _ \alpha = x(\alpha)$ is the $\alpha$-th coordinate of $x$.
    • Define the $\alpha$-th projection or coordinate map $\pi _ {\alpha}: X \rightarrow X _ {\alpha}$ by $\pi _ {\alpha}(x)=x(\alpha)$.
    • In the particular case where $\forall i \in I: H _ i = Y$ we write $\prod _ {i \in I} H _ i = Y^A$.
Number systems #
  • $\mathbb{Z}$ is the set of all integers (that is, whole numbers: positive, negative, and zero).
  • $\mathbb{Q}$ is the set of all rational numbers (that is, numbers that can be expressed as quotients $m / n$ of integers, where $n \neq 0$ ).
  • $\mathbb{R}$ is the set of all real numbers. $\overline \R$ is the extended real, $\overline \R = \R \cup \{\infty, -\infty\}$.
  • $\mathbb{Z}^{+}, \mathbb{Q}^{+},$ and $\mathbb{R}^{+}$ are the sets of positive members.
  • $\mathbb C$ is the set of all complex numbers.
  • $\mathbb{Z}^{ * }, \mathbb{Q}^{ * }, \mathbb{R}^{ * },$ and $\mathbb{C}^{ * }$ are the sets of nonzero members.
Set algebra #
  • Power set: $\mathcal P(X)$ is the set of all subsets of $X$.
  • Symmetric difference: $A \Delta B = (A \backslash B) \cup (B \backslash A)$.
    • $A\Delta C \subseteq A \Delta B \cup B \Delta C$.
  • Disjointization identity: $(P \times Q) \backslash (E \times F) = [P\times (Q \backslash F)] \cup [(P\backslash E) \times F]$.
  • DeMorgan's laws: $$ \left(\bigcup _ {\alpha \in A} E _ {\alpha}\right)^{c}=\bigcap _ {\alpha \in A} E _ {\alpha}^{c}, \quad\left(\bigcap _ {\alpha \in A} E _ {\alpha}\right)^{c}=\bigcup _ {\alpha \in A} E _ {\alpha}^{c} $$

Relations #

Relation #

$R \subseteq A \times B$ is a relation from $A$ to $B$. $\forall a \in A ,\forall b \in B:a R b \iff (a, b )\in R$.

  • Denote $R^{-1} := \c{(b, a): (a, b) \in R}$ as the inverse relation of $R$.
Composition of relations #

Suppose $R \subseteq A \times B$ and $S \subseteq B \times C$. The composition $R \circ _ r S$ is defined as: $$ R \circ _ r S := \c{(a, c) : (\exists b \in B: (a, b) \in R \land (b, c) \in S)} $$

This is different from function composition conventions, thus we use a new symbol $\circ _ r$.

Inverse of relations #
Function #

A function $\phi$ mapping $X$ into $Y$ is a relation between $X$ and $Y$ with the property that each $x \in X$ appears as the first member of exactly one ordered pair $(x, y)$ in $\phi$.

  • Such a function is also called a map or mapping of $X$ into $Y$.
  • We write $\phi: X \rightarrow Y$ and express $(x, y) \in \phi$ by $\phi(x)=y$.
  • The domain of $\phi$ is the set $X$ and the set $Y$ is the codomain of $\phi$.
  • The range of $\phi$ is $\phi[X]=\{\phi(x) \mid x \in X\}$.

For a function $f: X \to Y$:

  • $f$ is injective if $\forall a,b \in X:f(a) = f(b) \to a = b$.
  • $f$ is surjective if $Y = f[X]$.
  • $f$ is bijective if $f$ is both injective and surjective.
  • If and only if $\phi$ is both injective and surjective, $\phi$ is said to be bijective.
Binary operation #

$ * : S\times S \to S$ is called a binary operation on $S$.

  • For each $(a, b) \in$ $S \times S$, we will denote the element $ * (a, b)$ of $S$ by $a * b$.
  • $ * $ is called commutative if $a * b=b * a$ for all $a, b \in S$.
  • $ * $ is called associative if $(a * b) * c=a * (b * c)$ for all $a, b, c \in S$.
Image #

For function $f: A \to B$, $C \subseteq B$, $D \subseteq A$.

  • $f^{-1}[C] = \{a \in A \mid f(a) \in C\}$ is the inverse image of $C$.
  • $f[D] = \{b \in B \mid \exists a \in A :f(a) = b\}$ is the image of $D$.
  • $f^{-1}[\{b\}]$ is called the fiber of $f$ over $b \in B$.
Inverse function #

Suppose $f: A \to B$. Then:

  • $f$ has a left inverse if there is a function $g: B \rightarrow A$ such that $g \circ f: A \rightarrow A$ is the identity map.
  • $f$ has a right inverse if there is a function $h: B \rightarrow A$ such that $f \circ h: B \rightarrow B$ is the identity map.
  • The map $f$ is injective if and only if $f$ has a left inverse.
  • The map $f$ is surjective if and only if $f$ has a right inverse.
  • The map $f$ is a bijection if and only if $f$ is injective and surjective.

Define the inverse map $f^{-1}: \P(B) \to \P(A)$ as $f^{-1}[D]=\{a \in A: f(a) \in D\}$.

  • When $f$ is a bijection, $f^{-1}$ can also denote $f^{-1}(y) = \operatorname{elem}{f^{-1}\{y\}}$. And it is called the inverse function.
Restriction / extension of function #
  • If $A \subseteq B$ and $f: B \rightarrow C$, we denote the restriction of $f$ to $A$ by $\left.f\right| _ {A}$. If the context is clear, we can denote $f| _ A$ as $f$.
  • If $A \subseteq B$ and $g: A \rightarrow C$ and there is a function $f: B \rightarrow C$ such that $\left.f\right| _ {A}=g$, we shall say $f$ is an extension of $g$ to $B$.
Equivalence and partition #

Suppose $S$ is a nonempty set.

$P \subset \mathcal P(S)$ is a partition of $S$ if $P$ is disjoint and $\cup P = S$.

  • Elements of $P$ are called blocks / cells.
  • Denote $\bar{x}$, $[x]$ as the block containing the element $x$ of $S$.

$R \subseteq S \times S$ is an equivalence relation on $S$ if it is

  • (reflexive) $\forall a \in S: (a, a) \in R$.
  • (symmetric) $\forall a, b \in S: (a, b) \in R \to (b, a) \in R$.
  • (transitive) $\forall a, b, c \in S: (a, b) \in R \land (b, c) \in R \to (a, c) \in R$.

There is a bijection from all partitions to all equivalence relations on $S$.

  • Define $f: P \mapsto \{(a, b) \in S \times S \mid \exists B \in P, a \in B \land b \in B\}$.
  • Define $u: a \mapsto \{x \in S\mid a R x \}$, and $g: R \mapsto \{u(a) \mid a \in R\}$.
  • We can show that $g \circ f$ is the identity, and $f \circ g$ is the identity.
Inverse images of sets #

Consider mapping $f: X \to Y$. $f^{-1}: \mathcal{P}(Y) \rightarrow \mathcal{P}(X)$ has following properties:

  • $f^{-1}\left(\bigcup _ {\alpha \in A} E _ {\alpha}\right)=\bigcup _ {\alpha \in A} f^{-1}\left(E _ {\alpha}\right)$.
  • $f^{-1}\left(\bigcap _ {\alpha \in A} E _ {\alpha}\right)=\bigcap _ {\alpha \in A} f^{-1}\left(E _ {\alpha}\right)$
  • $f^{-1}\left(E^{c}\right)=\left(f^{-1}(E)\right)^{c}$.
  • $f^{-1}(A - B) = f^{-1}(A \cap B^c) = f^{-1}(A) - f^{-1}(B)$.