MATH 302 Lecture 7

« previous | Monday, September 19, 2011 | next »

Sets

An unordered collection of objects called elements or members.

A set is said to contain its members.

Defining Sets

1. List (Roster)
   • $A=\{1,3,7\}$
   • $B=\{1,2,3,\dots \}$
2. Rule (Set builder)
   • $C=\{x\in U|P(x)\}$
3. Real intervals
   • $(2,5]=\{x\in \mathbb{ℝ}|2<x\le 5\}$

Common Sets

• natural numbers: $\mathbb{\mathbb{N}}=\{0,1,2,\dots \}$
• integers: $\mathbb{\mathbb{Z}}=\{\dots ,-1,0,1,\dots \}$
  • positive integers: ${\mathbb{\mathbb{Z}}}^{\mathbb{+}}$
  • multiples: $n\mathbb{\mathbb{Z}}=\{x\in \mathbb{\mathbb{Z}}|x=nk\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{o}\mathrm{m}\mathrm{e}k\in \mathbb{\mathbb{Z}}\}$
• rational numbers: $\mathbb{\mathbb{Q}}$
• complex numbers: $\mathbb{ℂ}$
• null set: $\mathrm{\varnothing }=\{\}=\{x\in U|\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{d}\mathrm{i}\mathrm{c}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\}$
• universe: $U=\{x\in U|\mathrm{t}\mathrm{a}\mathrm{u}\mathrm{t}\mathrm{o}\mathrm{l}\mathrm{o}\mathrm{g}\mathrm{y}\}$

Set Comparison

Equality

Two sets are equal if and only if every element in $A$ is an element in $B$ and every element in $B$ is an element in $A$.

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

Subsets

Set $A$ is a subset of $B$, denoted by $A\subseteq B$, if and only if every element in $A$ is an element in $B$.

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

"Element Chasing" Proof. To prove $A\subseteq B$, let $c$ be an arbitrary element of $A$. Then argue to show that $c$ is an element of $B$.

The empty set is a subset of every set, every set is a subset of itself, and every set is a subset of the universe.

$\mathrm{\varnothing }\subseteq S\subseteq S\subseteq U$

Proper Subset

Set $A$ is a proper subset of $B$ if and only if $A\subseteq B$ and $A\ne B$. Written $A\subset B$

Venn diagrams

Graphical version/representation of truth table/membership table for Propoitional logic

Cardinality

denoted by $|S|$ and represents the number of elements in $S$

Cartesian Product

$A\times B$ is the set of all possible ordered pairs between $A$ and $B$:

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

Relationships to Propositional Logic

Connectives

and (∧)	intersection (∩)
or (∨)	union (∪)
not (¬)	complement (A)
conditional (→)	subset (⊆)
biconditional (↔)	equality (=)

Laws

Law	Logical	Sets
distribution	$p\vee (q\wedge r)\equiv (p\vee q)\wedge (p\vee r)$	$A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$
deMorgan's	$\mathrm{\neg }(p\vee q)\equiv \mathrm{\neg }p\wedge \mathrm{\neg }q$	$\overline{A\cup B}=\bar{A}\cap \bar{B}$

To prove these laws, show that the left side is a subset of the right side and vice versa.

Example Proof of deMorgan's Law

Proposition: $\overline{A\cup B}=\bar{A}\cap \bar{B}$

Proof (direct). To prove the above, we need to prove the following:

1. $\overline{A\cup B}\subseteq \bar{A}\cap \bar{B}$
2. $\bar{A}\cap \bar{B}\subseteq \overline{A\cup B}$

Proof of (1). Let $x\in \overline{A\cup B}$ be an arbitrary element.

1. $x\in ̸A\cup B$ (definition of complement)
2. $\mathrm{\neg }(x\in A\cup B)$ (definiton of negation)
3. $\mathrm{\neg }(x\in A\vee x\in B)$ (definition of union)
4. $\mathrm{\neg }(x\in A)\wedge \mathrm{\neg }(x\in B)$ (deMorgan's law)
5. $x\in ̸A\wedge x\in ̸B$ (notation)
6. $x\in \bar{A}\wedge x\in \bar{B}$ (definition of complement)
7. $x\in \bar{A}\cup \bar{B}$ (definition of intersection)

Proving part (1).

Proof of (2). reverse the proof of part (1).

Q.E.D.

Note: Be careful! Not all proofs are reversible