DefinitionsEdit

SubsetEdit

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

$A \subset B$

• $\{x \mid x \in A \hbox{ then } x \in B \hbox{ and } A \ne B\}$

UnionEdit

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

IntersectionEdit

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

$\empty$

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

MinusEdit

$A - B$

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

PowersetEdit

$\mathcal{P}(A)$

• $\{x \mid x \subseteq A \}$

Ordered PairEdit

$\langle a, b \rangle$

• $\{ \{a\}, \{a, b\}\}$

Cartesian ProductEdit

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

RelationEdit

A set of ordered pairs

DomainEdit

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

RangeEdit

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

FieldEdit

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

Equivalence RelationsEdit

• 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 OrderingEdit

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

TrichotomyEdit

Exactly one of the following holds

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

Proof StrategiesEdit

If, thenEdit

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

Prove x != y

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