Last modified on 2 May 2009, at 15:48

Set Theory/Review

Need help creating math symbols?

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

If and only IfEdit

Prove x iff y

suppose x
...
...
so, y
suppose y
...
...
so, x

EqualityEdit

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