2 - Sets, Functions, Cardinality

A collection of object is called a set. We will denote sets by capital letters $A, B \dots$

When an object $a$ is in set $A$ , we write $a \in A$ , otherwise, we write $a \notin A$ . let $A, B$ he sets. If every $a \in A$ is also in $B$ , we say that $A$ is a subset of $B$ , and write $A \subset B$ . Vacuously, the empty set $ϕ$ is a subset of any set.
If $A \subset B$ and $A \neq B, A \neq ϕ$ , then $A$ is a proper subset of $B$ , written $A \subseteq B$ .

If $P (x)$ is a predicate, then there is a set $S$ that collects all objects $x$ for which $P (x)$ is true. We write $S = {x : P (x)}$ .

The set of elements that belong to both $A$ and $B$ , is called the intersection of $A$ and $B$ , dented $A \cap B$ .

the set of elements that belong to $A$ or $B$ , is called the union of $A$ and $B$ , denoted $A \cup B$ .

Properties of union and intersection

(i) identities:- $A \cap A = A, A \cup A = A$ .
(ii) interaction with the empty set

A \cap ϕ = ϕ, A \cup ϕ = A .

(iii) Symmetry:- $A \cup B = B \cup A, A \cap B = B \cap A$ .
(iv) Associativity:- $A \cup (B \cup C) = (A \cup B) \cup C$ , $A \cap (B \cap C) = (A \cap B) \cap C$ .

(y) Distribution:- $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$

(Vi) Existence of Arbitrary unions and intersections. let $J$ be an index set (Probably infinite at any Cardinal), then $⋂_{α \in J} A_{α}$ and $⋃_{α \in J} A_{α}$ exist.

Difference of sets

if $A$ and $B$ an sets, $A - B$ is the set that contains all objects in $A$ , which are not in $B$ , written $A - B = {x \in A ∣ x \notin B}$ .

Properties of difference

(i)) $A \cap B = ϕ$ , then $A - B = A, B - A = B$ . if $A = B = A$ , then $A \cap B = ϕ$ .
(ii) $A - B = ϕ$ if and andy if $A \subset B$ .
(ii) $A - C = A - B$ if and and if $A \cap C = A \cap B$ .
(iv) $A - A = ϕ, A - ϕ = A$ .

\begin{aligned} De-morgan laws: A - (B \cap C) = (A - B) \cup (A - C) . \\ A - (B \cup C) = (A - B) \cap (A - C) . \end{aligned}

Contesian Products

let $S_{1}, S_{2} \dots S_{n}$ he sets, $X_{i = 1}^{n} S_{i}$ is the set of ordered $n$ -tuples $(x_{1}, \dots x_{n})$ with $x_{i} \in S_{i}$ .

A property of cartesian products

Let $A, C \subseteq S$ , and $B, D \subseteq T$ . Then,$$(A \times B) \cap(C \times D)=(A \cap C) \times(B \cap D)$$

$* p r o o f * :$

Let $(x, y) \in (A \times B) \cap (C \times D)$ . Then, $(x, y) \in (A \times B)$ . hence $x \in A$ and $y \in B$ . Similarly, $(x, y) \in (C \times D)$ hence $x \in C$ and $y \in D$ . Therefore, $x \in A \cap C$ and $y \in B \cap D$ .

$◻$

Functions

Functions, Image, Pre-image

$f : X \to Y$ is a function if for each $x \in X$ , we associate exactly one $f x \in Y$ .

Let $A \subseteq X$ , then the image of $A$ under $f$ is $f A = {y \in Y : y = f x, x \in A}$ .
Let $B \subseteq Y$ , then the pre-image of $B$ under $f$ is $f^{- 1} B = {x \in X : f x = y, y \in B}$ .
$f$ is injective if the pre-image of any singleton $y \in Y$ has at most one element.
$f$ is surjective if $f X = Y$ . $f$ is bijective if it is both injective and surjective, in which case, $f^{- 1}$ exists, and is a bijection from $Y$ to $X$ .

Interaction of images and pre-images of functions with set operators

For the following discussion, let $f : X \to Y$ , $A, B \subseteq X$ , $C, D \subseteq Y$ .

$f (A \cup B) = f (A) \cup f (B)$ , $f^{- 1} (C \cup D) = f^{- 1} (C) \cup f^{- 1} (D)$
$f (A \cap B) = f (A) \cap f (B)$ only if $f$ is injective.
$f (A - B) = f (A) - f (B)$ only if $f$ is injective.
$f^{- 1} (C - D) = f^{- 1} (C) - f^{- 1} (D)$ , $f^{- 1} (C \cap D) = f^{- 1} (C) \cap f^{- 1} (D)$ .

$* p r o o f * :$ Left for the reader.

$◻$

Cardinality

Set isomorphisms

A set $A$ is isomorphic to set $B$ , denoted $A \sim B$ , if there exists a bijection $f : A \to B$ , in which case we say that $A$ and $B$ have the same cardinality, sometimes written $| A | = | B |$ . The described relation is an equivalence, meaning that sets can be partitioned into classes, all of whose cardinality is the same.

Finite sets, countable sets, uncountable sets

let $J_{n} = {1, 2, \dots n}$ , where $n \in N$ . A set $X$ is finite if $X \sim J_{n}$ , for some $n \in N$
A set $X$ is countable, if $X \sim N$ , otherwise it is uncountable

A set, and its power set

let $X$ be any set, then $X ≁ 2^{X}$ where $2^{X}$ is the power set of $X$

$* p r o o f * :$ Suppose there exists a bijection $f: X \rightarrow 2{#X}$ . collect all $x \in X$ such that $x$ is mapped to a subset of $X$ that doesn't contain $x$ . $A = {x \in X : x \notin f (x)}$ , $A$ could be empty too. Then, notice that $A$ is a subset of $X$ , and since $f$ is surjective, we have $a \in X$ for which $f (a) = A$ . if $a \in A$ , then $a \notin f (a) = A$ , a contradiction. if $a \notin A$ , then $a \notin f (a)$ , hence $a \in A$ , also a contradiction.

$◻$

The reals are uncountable

There exists no bijection $f : N \to R$ .

$* p r o o f * :$ Suppose There exists a bijection $f : N \to R$ , write the real numbers, as infinite decimal digits, for example $4.999999 \dots = 5.000000 \dots$ pick the one with infinite zeros. write $f (i) = x_{i 1}, x_{i 2}, . . . . .$ then make $K = {\bar{x}}_{11}, {\bar{x}}_{22}, \dots$ Here, ${\bar{x}}_{i i} \neq x_{i i}$ . Then $K \in R$ , but $K \notin f (N$ ) . Contradicting the Surjectivity of the map $f$ .

$◻$

Every Infinite subset of a countable set is countable

Let $A$ be a countable set, $E$ an infinite subset of $A$ . Then, $E$ is countable.

$* p r o o f * :$ Use the bijection from $N \to A$ , to index $A$ as $a_{1}, a_{2}, \dots$ . Now, consider the following algorithm, find $e^{*} \in E$ with the smallest index in $A$ , that is $e^{*} = a_{j}$ for the smallest $j$ . set $e^{*} = e_{1}$ , delete $e^{*}$ from $E$ , and repeat this process (use a proof by induction), to show that $E$ is indexable.

$◻$

The union of countable sets, is countable

let

$* p r o o f * :$

$◻$