Definitions

Subset

$A\subseteq B$ • $\{x\mid x\in A{\hbox{ then }}x\in B\}$ Subset means for all x, if x is in A then x is also in B.

Proper Subset

$A\subset B$ • $\{x\mid x\in A{\hbox{ then }}x\in B{\hbox{ and }}A\neq B\}$ Union

$\bigcup A$ • $\{x\mid x\in \bigcup A{\hbox{ iff }}y\in A{\hbox{ s.t. }}x\in y\}$ $A\cup B$ • $\{x\mid x\in A{\hbox{ or }}x\in B\}$ Intersection

$\bigcap A$ • $\{x\mid {\hbox{for all }}a\in A,x\in a\}$ $A\cap B$ • $\{x\mid x\in A{\hbox{ and }}x\in B\}$ Empty Set

$\emptyset$ • ${\hbox{There is a set }}A{\hbox{ s.t. }}\{x\mid x\notin A\}$ Minus

$A-B$ • $\{x\mid x\in A{\hbox{ and }}x\notin B\}$ Powerset

${\mathcal {P}}(A)$ • $\{x\mid x\subseteq A\}$ Ordered Pair

$\langle a,b\rangle$ • $\{\{a\},\{a,b\}\}$ Cartesian Product

$A\times B$ • $A\times B=\{x\mid x=\langle a,b\rangle {\hbox{ for some }}a\in A{\hbox{ and some }}b\in B\}$ or

• $\{\langle a,b\rangle \mid a\in A{\hbox{ and }}b\in B\}$ Relation

A set of ordered pairs

Domain

$\{x\mid {\hbox{ for some }}y,\langle x,y\rangle \in R\}$ Range

$\{y\mid {\hbox{ for some }}x,\langle x,y\rangle \in R\}$ Field

${\hbox{dom(}}R{\hbox{)}}\cup {\hbox{ran(}}R{\hbox{)}}$ Equivalence Relations

• Reflexive: A binary relation R on A is reflexive iff for all a in A, <a, a> in R
• Symmetric: A rel R is symmetric iff for all a, b if <a, b> in R then <b, a> R
• Transitive: A relation R is transitive iff for all a, b, and c if <a, b> in R and <b, c> in R then <a, c> in R

Partial Ordering

• Transitive and,
• Irreflexive: for all a, <a, a> not in R

Trichotomy

Exactly one of the following holds

• x < y
• x = y
• y < x

Proof Strategies

If, then

Prove if x then y

Suppose x
...
...
so, y

Prove x iff y

suppose x
...
...
so, y
suppose y
...
...
so, x

Prove x = y

show x subset y
and
show y subset x

Non-Equality

Prove x != y

x = {has p}
y = {has p}
a in x, but a not in y