From Wikibooks, the open-content textbooks collection

< Set Theory

Current revision (unreviewed)

Jump to: navigation, search

Need help creating math symbols?

[edit] Definitions

[edit] 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.

[edit] Proper Subset

$A \subset B$

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

[edit] 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 \}$

[edit] 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\}$

[edit] Empty Set

$\empty$

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

[edit] Minus

$A - B$

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

[edit] Powerset

$\mathcal{P}(A)$

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

[edit] Ordered Pair

$\langle a, b \rangle$

${{a},{a, b}}$

[edit] 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 \}$

[edit] Relation

A set of ordered pairs

[edit] Domain

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

[edit] Range

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

[edit] Field

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

[edit] 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

[edit] Partial Ordering

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

[edit] Trichotomy

Exactly one of the following holds

x < y
x = y
y < x

[edit] Proof Strategies

[edit] If, then

Prove if x then y

Suppose x

...

so, y

[edit] If and only If

Prove x iff y

suppose x

...

so, y

suppose y

...

so, x

[edit] Equality

Prove x = y

show x subset y

and

show y subset x

[edit] Non-Equality

Prove x != y

x = {has p}

y = {has p}

a in x, but a not in y

Set Theory/Review