집합과 관계

 

Basic set theory

 

1. $X, Y$ : sets

product set : $X \times Y  = \left\{(x, y) \; | \; x \in X, y \in Y \right\}$

 

2. $X_{1}, \cdots, X_{n}$ : sets

$n$-tuple : $X_{1} \times \cdots \times X_{n} = \left\{(x_{1}, \cdots, x_{n}) \; | \; x_{i} \in X_{i}, \; 1 \leq i \leq n \right\}$

 

3. $B_{m} = \left\{1, 2, \cdots, m \right\}$, $X$ : set

①  $X$ is finite if there exists a $1-1$ correspondence $f : X \to B_{m}$ for some $m$

②  $X$ is infinite if $X$ is not finite

③  If there is a $1-1$ correspondence $X \to B_{m}$, the cordinality of $X$ is defined by

$\left|X \right| = n(X) = m$

 

 

 

(equivalence) relation on sets

 

Def 1

$S$ : set

A relation on $S$ is a subset $\mathcal{R}$ of $S \times S$

 

notation

$(a, b) \in \mathcal{R}$  $\Leftrightarrow$  $a \mathcal{R} b$  $\Leftrightarrow$  $a \sim b$

 

 

 

Def 2

An equivalence relation $\sim$ on $S$ is a relation satisfying the following

  $(\mathrm{i})$   (reflexive)   $\forall a \in S$,  $a \sim a$ 

 $(\mathrm{ii})$   (symmetric)   $a \sim b$  $\Rightarrow$  $b \sim a$

$(\mathrm{iii})$   (transitive)   $a \sim b$, $b \sim c$  $\Rightarrow$  $a \sim c$

 

 

 

Def 3

The equivalence class of $a$ under $\sim$ is 

$[a] = \left\{x \in S \; | \; a \sim x \right\}$

 

 

 

Thm 1

Let $\sim$ be an equivalence relation on $S$.  $\forall a, b \in S$, 

either  $[a] = [b]$     or     $[a] \cap [b] = \varnothing$

 

  Case 1 : $[a] \cap [b] = \varnothing$

  Clear!

 

  end

 

 

  Case 2 : $[a] \cap [b] \neq \varnothing$

  So there exists $x \in [a] \cap [b]$.

 

  - Show 1 : $[a] \subset [b]$

  Let $y \in [a]$.

  So $a \sim y$  $\Rightarrow$  $y \sim a$.

  Since $a \sim x$, so

  $y \sim x$.

  Since $b \sim x$  $\Rightarrow$  $x \sim b$, so

  $y \sim b$  $\Rightarrow$  $b \sim y$  $\Rightarrow$  $y \in [b]$

  $\therefore$  $[a] \subset [b]$

 

  - Show 2 : $[b] \subset [a]$

  Similarly, we can show $[b] \subset [a]$.

 

  end

 

  $\therefore$  $[a] = [b]$

 

 

 

Cor 1

Let $\sim$ be an equivalence relation on $S$.  $\forall a, b \in S$, 

$[a] = [b]$  $\Leftrightarrow$  $a \sim b$

( i.e. $\left\{(a, b) \in S \times S \; | \; [a] = [b] \right\} = \; \sim$ )

 

$\Rightarrow)$

  Since $b \in [b] = [a]$, so $a \sim b$

 

$\Leftarrow)$

  Since $a \sim b$,

  $b \in [a]$.

  Since $\sim$ is equivalence relation,

  $b \sim b$

  $\therefore$  $b \in [b]$

  $\therefore$  $[a] \cap [b] \neq \varnothing$

 

  By Thm 1, 

  $[a] = [b]$

 

 

 

Cor 2

If $\sim$ is an equivalence relation on $S$, then $S$ is a disjoint union of equivalence classes.

 

  By Thm 1, It is sufficient to show

  $\displaystyle \bigcup_{x \in S} [x] = S$

 

 

  Show 1 : $S \subset \displaystyle \bigcup_{x \in S} [x]$

  Let $y \in S$.

  Since $y \in [y]$,

  $y \in \displaystyle \bigcup_{x \in S} [x]$

  $\therefore$  $S \subset \displaystyle \bigcup_{x \in S} [x]$

 

  end

 

 

  Show 2 : $\displaystyle \bigcup_{x \in S} [x] \subset S$

  By defintion of $[x]$,

  $[x] \subset S$

  $\therefore$  $\displaystyle \bigcup_{x \in S} [x] \subset S$

 

  end

 

 

 

Partition on Sets

 

Def 4

$S$ : set

A partition of $S$ is a collection of subsets $S_{i}$ of $S$  s.t.  $S$ is a disjoint union of $S_{i}'s$.

The $S_{i}$ is called cell of the partition.

 

notation

For $x \in S$, the cell of $x$ is

$\overline{x} =$ the subset of the partition containing $x$

 

 

 

Thm 2

For the partition of $S$, $\forall a, b \in S$

$\overline{a} = \overline{b}$  $\Leftrightarrow$  $b \in \overline{a}$

( i.e. $\left\{b \in S \; | \; \overline{a} = \overline{b} \right\} = \overline{a}$ )

 

$\Rightarrow)$

  $b \in \overline{b} = \overline{a}$

 

$\Leftarrow)$

  Since $b \in \overline{b}$,

  $\overline{a} \cap \overline{b} \neq \varnothing$

  By Def 4, 

  $\overline{a} = \overline{b}$

 

 

 

Thm 3

For the partition of $S$, relation on S

$\sim \; = \left\{(a, b) \in S \times S \; | \; \overline{a} = \overline{b} \right\}$

is an equivalence relation.

 

  Show 1 : $\forall a \in S$,  $a \sim a$ 

  Since $\overline{a} = \overline{a}$,

  $a \sim a$

 

  end

 

 

  Show 2 : $a \sim b$  $\Rightarrow$  $b \sim a$

  Since $\overline{a} = \overline{b}$,

  $\overline{b} = \overline{a}$

  $\therefore$  $b \sim a$

 

  end

 

 

  Show 3 : $a \sim b$, $b \sim c$  $\Rightarrow$  $a \sim c$

  Since $\overline{a} = \overline{b}$ and $\overline{b} = \overline{c}$,

  $\overline{a} = \overline{c}$

  $\therefore$  $a \sim c$

 

  end

 

 

 

Thm 4

$S$ : set

$\sim_{S}$ : collection of equivalence relation on $S$

$P_{S}$ : collection of pratition of $S$

$f : \; \sim_{S} \; \to P_{S}$   by   $f(\sim) = \left\{[a] \; | \; a \in S \right\}$

$g : P_{S} \to \; \sim_{S}$   by   $g(P) = \left\{(a, b) \in S \times S \; | \; \overline{a} = \overline{b} \right\}$

 

1.  $g \circ f = I_{\sim_{S}}$

2.  $f \circ g = I_{P_{S}}$

 

# $f, g$ are well-defined by Cor 2, Thm 3 

 

pf)

   $\forall \sim \; \in \; \sim_{S}$

  $f(\sim) = \left\{[a] \; | \; a \in S \right\}$

  $\overline{a} =$ the subset of the partition containing $a$ $=$ $[a]$

 

  By Cor 1,

  $g(f(\sim)) = \left\{(a, b) \in S \times S \; | \; \overline{a} = \overline{b} \right\} = \left\{(a, b) \in S \times S \; | \; [a] = [b] \right\} = \; \sim$

 

  $\forall P \in P_{S}$

  $g(P) = \left\{(a, b) \in S \times S \; | \; \overline{a} = \overline{b} \right\}$

 

  By Thm 2,

  $[a] = \left\{b \in S \; | \; a \; g(P) \; b \right\} = \left\{b \in S \; | \; \overline{a} = \overline{b} \right\} = \overline{a}$

 

  $\therefore$  $f(g(P)) = \left\{[a] \; | \; a \in S \right\} = \left\{\overline{a} \; | \; a \in S \right\} = P$

 

 

 

Cor 3

$f, g$ is $1-1$ correspondence. So $X$ and $Y$ are equipotent.

 

# Thm 2