Set Theory/Review

Need help creating math symbols?

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 \ne 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

$\empty$

• $\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 R
• Transitive: A relation R is transitive iff for all a, b, and c if <a, b> in R and 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

If and only If

Prove x iff y

suppose x

...

...

so, y

suppose y

...

...

so, x

Equality

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