Set Theory/Review

Need help creating math symbols?

Definitions

Subset

$A\subseteq B$

• $\{x\mid x\in A\text{ 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\text{ then }x\in B\text{ and }A\ne B\}$

Union

$\bigcup A$

• $\{x\mid x\in \bigcup A\text{ iff }y\in A\text{ s.t. }x\in y\}$

$A\cup B$

• $\{x\mid x\in A\text{ or }x\in B\}$

Intersection

$\bigcap A$

• $\{x\mid \text{for all }a\in A,x\in a\}$

$A\cap B$

• $\{x\mid x\in A\text{ and }x\in B\}$

Empty Set

$\mathrm{\varnothing }$

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

Minus

$A-B$

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

Powerset

$𝒫(A)$

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

Ordered Pair

$⟨a,b⟩$

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

Cartesian Product

$A\times B$

• $A\times B=\{x\mid x=⟨a,b⟩\text{ for some }a\in A\text{ and some }b\in B\}$

or

• $\{⟨a,b⟩\mid a\in A\text{ and }b\in B\}$

Relation

A set of ordered pairs

Domain

$\{x\mid \text{ for some }y,⟨x,y⟩\in R\}$

Range

$\{y\mid \text{ for some }x,⟨x,y⟩\in R\}$

Field

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

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