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,\ldots \}$
2. Rule (Set builder)
   • $C=\{x\in U|P(x)\}$
3. Real intervals
   • $(2,5]=\{x\in \mathbb {R} |2<x\leq 5\}$

Common Sets

• natural numbers: $\mathbb {N} =\{0,1,2,\ldots \}$
• integers: $\mathbb {Z} =\{\ldots ,-1,0,1,\ldots \}$
  • positive integers: $\mathbb {Z^{+}}$
  • multiples: $n\mathbb {Z} =\{x\in \mathbb {Z} |x=nk\ \mathrm {for\ some} \ k\in \mathbb {Z} \}$
• rational numbers: $\mathbb {Q}$
• complex numbers: $\mathbb {C}$
• null set: $\emptyset =\{\}=\{x\in U|\mathrm {contradiction} \}$
• universe: $U=\{x\in U|\mathrm {tautology} \}$

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

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

$\forall x\,\{x\in A\rightarrow 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.

$\emptyset \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\neq 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	$\neg (p\vee q)\equiv \neg p\wedge \neg q$	${\overline {A\cup B}}={\overline {A}}\cap {\overline {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}}={\overline {A}}\cap {\overline {B}}$

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

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

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

1. $x\not \in A\cup B$ (definition of complement)
2. $\neg (x\in A\cup B)$ (definiton of negation)
3. $\neg (x\in A\vee x\in B)$ (definition of union)
4. $\neg (x\in A)\wedge \neg (x\in B)$ (deMorgan's law)
5. $x\not \in A\wedge x\not \in B$ (notation)
6. $x\in {\overline {A}}\wedge x\in {\overline {B}}$ (definition of complement)
7. $x\in {\overline {A}}\cup {\overline {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