Set Basics

What is a Set?

A set is an unordered collection of distinct objects called elements or members.

Notation

• $a \in A$ means "$a$ is an element of set $A$"
• $a \notin A$ means "$a$ is not an element of $A$"

Ways to Define Sets

Roster Method (Listing)

$A = \{1, 2, 3, 4, 5\}$ $B = \{a, e, i, o, u\}$

Set-Builder Notation

$A = \{x \mid x \text{ is a positive integer less than 6}\}$ $B = \{x \in \mathbb{R} \mid x^2 - 1 = 0\} = \{-1, 1\}$

Interval Notation (for real numbers)

$[a, b] = \{x \in \mathbb{R} \mid a \leq x \leq b\}$ $(a, b) = \{x \in \mathbb{R} \mid a < x < b\}$

Important Number Sets

Symbol	Name	Elements
$\mathbb{N}$	Natural numbers	$\{0, 1, 2, 3, \ldots\}$ or $\{1, 2, 3, \ldots\}$
$\mathbb{Z}$	Integers	$\{\ldots, -2, -1, 0, 1, 2, \ldots\}$
$\mathbb{Z}^+$	Positive integers	$\{1, 2, 3, \ldots\}$
$\mathbb{Q}$	Rational numbers	$\{\frac{p}{q} \mid p, q \in \mathbb{Z}, q \neq 0\}$
$\mathbb{R}$	Real numbers	All points on the number line
$\mathbb{C}$	Complex numbers	$\{a + bi \mid a, b \in \mathbb{R}\}$

Special Sets

Empty Set

The set with no elements: $\emptyset = \{\} = \{x \mid x \neq x\}$

Note: $\emptyset \neq \{\emptyset\}$ (empty set vs. set containing empty set)

Universal Set

The set $U$ containing all objects under consideration.

Set Equality

Two sets are equal if they have exactly the same elements: $A = B \iff \forall x (x \in A \leftrightarrow x \in B)$

Properties

• Order doesn't matter: $\{1, 2, 3\} = \{3, 1, 2\}$
• Repetition doesn't matter: $\{1, 1, 2\} = \{1, 2\}$

Subsets

$A$ is a subset of $B$ if every element of $A$ is in $B$: $A \subseteq B \iff \forall x (x \in A \rightarrow x \in B)$

$A$ is a proper subset of $B$ if $A \subseteq B$ and $A \neq B$: $A \subset B \iff A \subseteq B \land A \neq B$

Properties

• $\emptyset \subseteq A$ for any set $A$
• $A \subseteq A$ (reflexive)
• If $A \subseteq B$ and $B \subseteq A$, then $A = B$
• If $A \subseteq B$ and $B \subseteq C$, then $A \subseteq C$ (transitive)

Cardinality

The cardinality of a finite set is the number of elements: $|A| = n \text{ if } A \text{ has exactly } n \text{ elements}$

Examples

• $|\{1, 2, 3\}| = 3$
• $|\emptyset| = 0$
• $|\{a, \{b, c\}\}| = 2$

Power Set

The power set of $A$ is the set of all subsets of $A$: $\mathcal{P}(A) = \{S \mid S \subseteq A\}$

Example

If $A = \{1, 2\}$: $\mathcal{P}(A) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}$

Cardinality

If $|A| = n$, then $|\mathcal{P}(A)| = 2^n$

Cartesian Product

The Cartesian product of $A$ and $B$: $A \times B = \{(a, b) \mid a \in A \land b \in B\}$

Example

If $A = \{1, 2\}$ and $B = \{a, b\}$: $A \times B = \{(1, a), (1, b), (2, a), (2, b)\}$

Properties

• $A \times B \neq B \times A$ (unless $A = B$ or one is empty)
• $|A \times B| = |A| \cdot |B|$
• $A \times \emptyset = \emptyset$

n-tuples

$A_1 \times A_2 \times \cdots \times A_n = \{(a_1, a_2, \ldots, a_n) \mid a_i \in A_i\}$

$A^n = A \times A \times \cdots \times A \text{ (n times)}$

Russell's Paradox

Consider: $R = \{S \mid S \notin S\}$ (set of all sets that don't contain themselves)

Is $R \in R$?

• If $R \in R$, then by definition $R \notin R$ — contradiction!
• If $R \notin R$, then by definition $R \in R$ — contradiction!

This paradox shows naive set theory needs restrictions (resolved by axiomatic set theory).