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

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