As we have seen, sequences are ordered lists of items. They are fundamental building blocks in mathematics. Another such fundamental object is a collection of items that in unordered is called a set.
We can extend the language of mathematics we have developed thus far by including a new constant $\in$ which is called “is an element of” (or “is a member of” or “is in”) and a new variable and constant type called a set. The expression $x\in A$ is a statement is read “$x$ is an element of $A$” where $A$ is a set and $x$ can have any type. The set containing no elements is called the empty set. Many of the definitions below are informal definitions that are sufficient for our purposes.
Basic Set Notation and Operations
| Name | Definition |
|---|---|
| Finite set notation | $x\in\Set{ x _ {1},\ldots,x _ {n} } \iff x=x _ {1}\xor\cdots\xor\,x=x _ {n}$ |
| Set builder notation | $x\in\Set{ y : P(y) } \iff P(x)$ |
| Subset | $A\subseteq B\iff\forall x.x\in A\implies x\in B$ |
| Set equality | $A=B\iff A\subseteq B\xand B\subseteq A$ |
| Empty set | $A=\Set{}\iff\forall x.x\notin A$ |
| Nonempty | $A$ is nonempty $\iff\, \exists c.c\in A$ |
| Power set | $\mathscr{P}\left(A\right)=\Set{ B : B\subseteq A } $ |
| Intersection | $x\in A\cap B\iff x\in A\xand x\in B$ |
| Union | $x\in A\cup B\iff x\in A\xor x\in B$ |
| Relative Complement | $x\in B-A\iff x\in B\xand x\notin A$ |
| Complement | $x\in A’\iff x\notin A$ |
| Indexed Union | $x\in\bigcup\limits _ {i\in I}A _ {i}\iff\exists i.i\in I\xand x\in A _ {i}$ |
| Indexed Intersection | $x\in\bigcap\limits _ {i\in I}A _ {i}\iff\forall i.i\in I\implies x\in A _ {i}$ |
| Cartesian Product [see 1] | $A\times B=\Set{ \left\langle x,y\right\rangle : x\in A\xand y\in B } $ |
| Cartesian Product [see 1] | $A _ {1}\times\cdots\times A _ {n}=\Set{ \left\langle x _ {1},\ldots,x _ {n}\right\rangle : x _ {1}\in A _ {1}\xand\cdots\xand,x _ {n}\in A _ {n} } $ |
| Cartesian Product | $A^n=\underbrace{A\times \cdots \times A}_n$ where $A$ is a set and $1\leq n$ |
| Two convenient abbreviations | $\left(\forall x\in A.P\left(x\right)\right)\iff\forall
x.x\in A\implies P (x)$ $\left(\exists x\in A.P\left(x\right)\right)\iff\exists x.x\in A\xand P(x)$ |
Remarks:
As usual, in addition to using the above definitions in our proofs, we can also derive many useful rules of inference from them.
Basic Set Theory
Declare $\in$, nonempty, $\subseteq,\cap, \cup,\, ', \setminus, \mathscr{P}, \times,$ set, Union, Intersect and setbuilder to be constants.
Empty Set $x \notin \Set{}$
Nonempty $A$ is nonempty $\equiv \exists x.x \in A$
Set Builder $x \in \Set{ z : \mc{P}(z) } \equiv \mc{P}(x)$
Finite Sets
$x \in \Set{a}$ $\equiv$ $x=a$
$x \in \Set{a,b}$ $\equiv$ $x=a\xor x=b$
$x \in \Set{a,b,c}$ $\equiv$
$\qquad x=a\xor x=b\xor x=c$
$x \in \Set{a,b,c,d}$ $\equiv$
$\qquad x=a\xor x=b\xor x=c\xor x=d$
Useful trivial theorems
$a \in \Set{a}$,
$a \in \Set{a,b}$,
$b \in \Set{a,b}$,
$a \in \Set{a,b,c}$,
$b \in \Set{a,b,c}$,
$c \in \Set{a,b,c}$,
$a \in \Set{a,b,c,d}$,
$b \in \Set{a,b,c,d}$,
$c \in \Set{a,b,c,d}$ and
$d \in \Set{a,b,c,d}$
Set Relations
Subset+
Given
Let $x \in A$
$x\in B$
Conclude $A\subseteq B$
Set equality
Given
Let $x \in A$
$x\in B$
Let $x \in B$
$x\in A$
Conclude $A=B$
Subset- If $A\subseteq B$ and $x\in A$ then $x\in B$.
Set from other sets
Power set $A\in \mathscr{P}(B) \equiv A\subseteq B$
Intersection $x\in A\cap B \equiv x\in A , x\in B$
Union $x\in A\cup B \equiv x\in A \xor x\in B$
Relative Complement $x\in A\setminus B \equiv x\in A \xor x\notin B$
Complement $x\in B’ \equiv x\notin B$
Cartesian product
Binary $\times$ If $z\in A\times B$ then $z=\langle a,b\rangle$, $a\in A$, $b\in B$ for some $a$ and $b$.
Binary $\times$
$\langle a,b\rangle \in A\times B$ $\equiv$ $a\in A$, $b\in
B$.
Ternary $\times$ If $z\in A\times B\times C$ then $z=\langle a,b,c\rangle$, $a\in A$, $b\in B$, $c\in C$ for some $a$, $b$, and $c$.
Ternary $\times$
$\langle a,b,c\rangle \in A\times B\times C$ $\equiv$ $a\in
A$, $b\in B$, $c\in C$
Indexed Union and Intersection
Indexed Union+
If $x\in A_j$ and
$j\in I$ then
$\displaystyle x\in\bigcup_{i\in I} A_i$.
Indexed Union-
If $\displaystyle x\in\bigcup_{i\in I} A_i$
then $x\in A_j$ for some $j\in I$.
Indexed Intersection+
Given
Let $j\in I$
$x\in A_j$
Conclude $\displaystyle x\in\bigcap_{i\in I} A_i$
Indexed Intersection-
If $\displaystyle x\in\bigcap_{i\in I} A_i$
and $j\in I$ then
$x\in A_j$.
In addition to set builder notation, $\Set{ x : P(x) }$ where $P$ is a predicate, it is quite common practice in mathematics to write sets in the form $$\Set{ E(x _ 0,\ldots,x _ n) : P(x _ 0,\ldots,x _ n) }$$ where $E(x _ 0,\ldots,x _ n)$ is an expression containing the free variables $x _ 0,\ldots,x _ n$ and $P$ is a predicate. This is defined to be a shorthand for $$\Set{ x : \exists x _ 0,\ldots,x _ n, x=E(x _ 0,\ldots,x _ n) \xand P(x _ 0,\ldots,x _ n) }.$$
Example
When we write $$\bbC = \Set{ a+bi : a,b\in\bbR}$$ this is an
abbreviation for $$\bbC = \Set{ x : \exists a.b.x=a+bi \xand
a,b\in\bbR }$$ or equivalently $$\bbC = \Set{ x : \exists
a.b\in\bbR.x=a+bi }$$
Thus, if you need to pick an arbitrary element of $\bbC$ in your proof you should do it like this.
Let $z\in \bbC$
$z = a+bi \forsome a\in\RR \xand b\in\RR$
$\qquad\vdots$
The derived rules do this for you automatically.
In the following problems, capital letters represent sets which are all subsets of a universal set $\mathcal{U}$.
easy warmup If $x\in\Set{a}$ and $y\in\Set{a}$ then $x=y$
Order doesn’t matter $\Set{a,b} = \Set{b,a}$
Order does matter $\langle a,b\rangle = \langle b,a\rangle$ if and only if $a=b$
excluded middle $x\in A\cup A’$
double negative $A’'=A$
ordered pair inequality $x\neq y$ if and only if $\langle x,y\rangle \neq\langle y,x\rangle$
A set of sets $\Set{1,2} \in \Set{ A : \Set{1} \subseteq A }$
Cartesian calculation $\Set{2} \times \Set{ 3,5 } = \Set{ \langle 2,3\rangle, \langle 2,5\rangle }$
Subset is reflexive $A\subseteq A$
alternate definition of subset $A\subseteq B$ if and only if for all $x$, either $x\notin A$ or $x\in B$
Transitivity of $\subseteq$ $A\subseteq B\xand B\subseteq C \implies A\subseteq C$
Double negative $A - (B - A) = A$
Substraction lessens $A - B \subseteq A$
Contravariance of complement $A \subseteq B \iff B’ \subseteq A’$
Idempotency of $\cap$ $A \cap A = A$
Idempotency of $\cup$ $A \cup A = A$
Commutativity of $\cap$ $A \cap B = B\cap A$
Commutativity of $\cup$ $A \cup B = B\cup A$
Associativity of $\cap$ $(A \cap B) \cap C = A\cap (B\cap C)$
Associativity of $\cup$ $(A \cup B) \cup C = A\cup (B\cup C)$
Relative complement is not associative If $x\in A\cap B\cap C$ then $x\in A-(B-C)$ and $x\notin (A-B)-C$.
Distributivity of $\cap$ over $\cup$ $A \cap (B \cup C) = (A\cap B) \cup (A\cap C))$
Distributivity of $\cup$ over $\cap$ $A \cup (B \cap C) = (A\cup B) \cap (A\cup C))$
De Morgan $(A \cap B)’ = A’\cup B’$
De Morgan $(A \cup B)’ = A’\cap B’$
More De Morgan $A-(B \cap C) = (A-B)\cup (A-C)$
More De Morgan $A-(B \cup C) = (A-B)\cap (A-C)$
Even more De Morgan $$\left(\bigcap _ {i\in I} A _ i\right)’ = \bigcup _ {j\in I} A _ j’$$
Even more De Morgan $$\left(\bigcup _ {i\in I} A _ i\right)’ = \bigcap _ {j\in I} A _ j’$$
Not a subset If $\neg(A\subseteq B)$ then $\exists x.x\in A\cap B’$
Always in the power set $\emptyset\in\mathcal{P}(A)$
Always in the power set $A\in\mathcal{P}(A)$
Power sets of subsets $A\subseteq B\implies \mathcal{P}(A)\subseteq\mathcal{P}(B)$
Power sets of complements $A\subseteq B\implies \mathcal{P}(B’)\subseteq\mathcal{P}(A’)$
$\times$ is not commutative If $A\times B$ is non-empty, then $A\times B=B\times A$ if and only if $A=B$
Subsets are contagious $A\subseteq C \xand B\subseteq D\implies A\times B\subseteq C\times D$
Alternate definition of subset $A \subseteq B$ if and only if $\forall x. x\notin A \xor x\in B$
Power set and union $\mathcal{P}(A)\cup\mathcal{P}(B)\subseteq\mathcal{P}(A\cup B)$
Power set and intersection $\mathcal{P}(A)\cap\mathcal{P}(B) = \mathcal{P}(A\cap B)$
