# Set

## set

• an unordered collection of elements

## subsets and proper subsets

• Subset notation: $\subseteq$

• Proper subset $\subset$

## Set Operations and Its Identities

• Union, Intersection, Difference, Symmetric difference, complement
• Commutative Law, Associative Law, Distributive law, Absorption, DeMorgan’s Law, Idempotent law

## Power Set

• $2^S$ = set of all subset of $S$

## Partition

A partition of nonempty set $A$ is a subset $\sqcap$ of $2^A$ such that

1. $\phi\notin \sqcap$
2. $\forall S,T \in \sqcap.$ and $S\neq T, S \cap T = \phi$
3. $\cup \sqcap = A$

# Relations and Functions

## Ordered Pair and Binary Relation

• Ordered Pair: $(a,b)$

• Cartesian Product: $A \times B$

• Binary Relation $A$ and $B$

• Inverse

• Composition

## Function

Definition: A function $f: A\rightarrow B$ must satisfy:

• $f \subseteq A \times B$
• $\forall a \in A, \exists$ exactly one $b \in B$ with $(a,b) \in f$

Note: We write $(a,b)\in f$ as $f(a) = b$

• one-to-one function: $\forall a,b \in A \land a \neq b \Rightarrow f(a) \neq f(b)$
• onto function: $\forall b \in B, \exists a\in A$ such that $f(a)=b$
• bijection function: one-to-one + onto

# Special Types of Binary Relations

## Representation of Relations

• Directed graph: node, edge, path

## Properties of Relations ($R \subseteq A\times A$)

• reflexive: $\forall a\in A \Rightarrow (a,a) \in R$
• symmetric: $(a,b) \in R \land a \neq b \Rightarrow (b,a)\in R$, antisymmetric: $(a,b) \in R \Rightarrow (b,a) \notin R$
• transitive: $(a.b)\in R, (b,c)\in R \Rightarrow (a,c)\in R$

## Equivalence Relation

• reflexive, symmetric, transitive

• equivalence classes

Theorem Let $R$ be an equivalence relation on a nonempty set $A$. Then the equivalence classes of $R$ constitute a partition of $A$.

## Partial Order

• reflexive, symmetric, transitive
• total order
• minimal element and maximal element

# Finite and Infinite sets

## Equinumerous

• Sets $A$ and $B$ equinumerous $\Leftrightarrow \exists$ bijection $f:A\rightarrow B$
• Cardinality and generalized Cardinality
• Finite and Infinite sets

## Countable and Uncountable Infinite

• A set is said to be countably infinite $\Leftrightarrow$ it is equinumerous with $\mathbb{N}$
• S is an uncountable set $\Leftrightarrow |S|>|\mathbb{N}|$
• The union of a countably infinite collection of countably infinite sets is countably infinite.

Example: Show that $\mathbb{N} \times \mathbb{N}$ is countably infinite.

Theorem: $|\mathbb{R}|>|\mathbb{N}|$ (diagonalization)

Question: Is $|\mathbb{R}| > |(0,1)|$?

## Continuum Hypothesis

$|\mathbb{N}|=\aleph_0, |\mathbb{R}|=\aleph_1$

$\aleph_0<\aleph_1$