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

$\forall x(x\in A\leftrightarrow x\in B)$

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

$\forall x(x\in A\rightarrow x\in B)$

Examples of Sets

• $\mathbb {N} _{0}=\{0,1,2,3,\ldots \}$ (set of all natural numbers starting with 0)
• $\mathbb {N} =\{1,2,3,4,\ldots \}$ (set of all natural numbers starting with 1)
• $\mathbb {Z} =\{\ldots ,-2,-1,0,1,2,\ldots \}$ (set of all integers)
• $\mathbb {R} ={\mbox{all real numbers}}$
• $\emptyset =\{\}$ (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):

${\mbox{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\},\emptyset \}$

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|$