CSCE 222 Lecture 9

« previous | Wednesday, February 9, 2011 | next »

Sets

A set is an unordered collection of unique objects, called elements.

Sets are equal ($A=B$) iff

$\mathrm{\forall }x(x\in A\leftrightarrow x\in B)$

Set $A$ is a subset of set $B$ ($A\subseteq B$) iff

$\mathrm{\forall }x(x\in A\to x\in B)$

Examples of Sets

• ${\mathbb{\mathbb{N}}}_0=\{0,1,2,3,\dots \}$ (set of all natural numbers starting with 0)
• $\mathbb{\mathbb{N}}=\{1,2,3,4,\dots \}$ (set of all natural numbers starting with 1)
• $\mathbb{\mathbb{Z}}=\{\dots ,-2,-1,0,1,2,\dots \}$ (set of all integers)
• $\mathbb{ℝ}=\text{all real numbers}$
• $\mathrm{\varnothing }=\{\}$ (empty set)
• $A=\{a,a,b\}=\{a,b\}$

Note: Properties of Sets

1. The empty/null set is a subset of all sets
2. Every set is a subset of itself

Cardinality

Let $S$ be a finite set (containing a finite number of elements):

$\text{number of elements}n=|S|$

Power Sets

Given a set $S$, $P(S)$ is the set of all subsets of $S$:

$P(\{1,2\})=\{\{1\},\{2\},\{1,2\},\mathrm{\varnothing }\}$

Note: If a finite set $S$ has $n$ elements, then $P(S)$ has $2^n$ elements.

Cartesian Products

A cartesian product between two finite sets $A$ and $B$ is the set of all unique tuples that can be created from the elements of $A$ and $B$:

$A\times B=\{(a,b)|a\in A,b\in B\}$

Note: $|A\times B|=|A|\cdot |B|$