Set

A set is an unordered collection of distinct elements.

Formal definition

According to Morse-Kelley set theory:

$$ \exists B: A \in B \iff A \text{ is a set} $$

Defining a set

Enumeration

A small finite set can be described by enumerating all its elements:

$$ S=\{\text{Apple, Banana, Peaches}\} $$

Some infinite sets following simple patterns can also be enumerated:

$$ S=\{0,1,2,\cdots\} \text{ (Set of natural numbers)} $$

To avoid ambiguity, reserve enumeration for simple patterns that most people can identify at first glance. Use #Set-builder notation elsewise.

Set-builder notation

A set that cannot be easily described by enumeration can often be described by rules that all elements of the set follow.

e.g.,

$$ S=\{x | x = 2^n, n \in N\ \land n \le 20\} $$

is the infinite set of all natural number powers of 2 up to $2^{20}$: $2,4,8,16,32,64,128,256...2^{20}$

Special sets

Set	Symbol	Note
Empty set	$\emptyset$
Universal set	$U$	Set of all elements relevant to a particular context

Set properties

Cardinality

The cardinality of a set $S$, denoted $|S|$, is its number of elements.

Example:

$S$	$|S|$
$\{1,2,3\}$	3
$\{a,b,c,\cdots,z\}$	26
$\{0,2,4,6,8,\cdots\}$	$\infty$

In everyday language, "size" is often used as an alternative term for cardinality.

If $|S|$ is finite, $S$ is known as an infinite set.

If $\exists f:\mathbb{Z} \to S$, $S$ is said to be countable.

All finite sets are countable. Infinite sets may be either countable (e.g., $\mathbb{N}$) or uncountable (e.g., $\mathbb{R}$).

Set relationships

Complement

Let $A$ be a set.

$$ x \in A^c \iff x \in U \land x \notin A \text{ (absolute complement)} $$

Intersection, union, symmetric difference

Let $A$, $B$ be sets.

$$\begin{gathered} x \in A \cap B \iff x \in A \land x \in B \text{ (intersection)} \\ x \in A\cup B \iff x \in A \lor x \in B \text{ (union)} \\ x \in A\triangle B \iff x \in A \oplus x \in B \text{ (symmetric difference)} \end{gathered}$$

If $A \cap B = \emptyset$, $A,B$ are said to be disjoint.

• 
  $A^c$
• 
  $A \cap B$
• 
  $A \cup B$
• 
  $A \triangle B$

Diagrams like this that visualise sets as circles and represent their relationship via relative positions are called Venn diagrams.

Subset

Let $A$, $B$ be sets.

$$\begin{gathered} A \subseteq B \iff \forall x \in A: x \in B \text{ (subset)} \\ A \subset B \iff (A \subseteq B) \land (A \neq B) \text{ (proper subset)} \end{gathered}$$

It can be therefore inferred:

$$\begin{gathered} A \not\subseteq B \iff \exists x \in A: x \notin B \\ A \subseteq A \\ \forall S: \emptyset \subseteq S \\ \end{gathered}$$

Direct product

See direct product (sets).

Power set

Let $A$ be a set, $X$ be some sets.

If:

$$ \mathcal{P}(A) = \{X |\forall X \subseteq A\}. $$

Then

$\mathcal{P}(A)$ is the power set of $A$.

Note the power set $\mathcal{P}(A)$ is a set of sets.

Example:

$$ \mathcal{P}(\{a, b\})= \{\emptyset, \{a\}, \{b\}, \{a,b\}\}. $$

It can be inferred:

$$ |\mathcal{P}(S)|=2^{|S|} $$

Proof by induction:

Let $S_n:|S_n|=n$ be sets.

By definition of #cardinality, $n \in N$.

If $n=0$:

$$\begin{gathered} \mathcal{P}(S_0)=\{\emptyset\} \\ |\mathcal{P}(S_0)|=1=2^n \end{gathered}$$

If $n=1$:

$$\begin{gathered} \mathcal{P}(S_1)=\{\emptyset\,A\} \\ |\mathcal{P}(S_1)|=2=2^n \end{gathered}$$

If $n>1$:

Given $|\mathcal{P}(S_n)|=2^n$

For any set $S_{n+1}: |S_{n+1}|=n+1$, identify an arbitrary element $s\in S_{n+1}$, then

$$ S_{n+1}=S_n+s $$ where set $S_n:|S_n|=n$.

As $|\mathcal{P}(S_n)|=2^n$, $S_n$ has $2^n$ subsets: $A_1=\emptyset,A_2,A_3,...A_{m}$, where $m=2^n$

Since

$$ A_m \subseteq S_n \subset S_{n+1} \Rightarrow A_m \subset S_{n+1} $$

which gives $m$ subsets of $S_{n+1}$

and

$$\begin{gathered} \because s \in S_{n+1} \\ \therefore A_m+s \subseteq S_{n+1} \end{gathered}$$

which gives $m$ more subsets of $S_{n+1}$

Therefore, $S_{n+1}$ has $2m=2 \cdot 2^n=2^{n+1}$ subsets,

i.e.,$|\mathcal{P}(S_{n+1})|=2^{n+1}$

$\therefore $ By induction,

$$ |\mathcal{P}(S)|=2^{|S|} $$