Jump to content

Set Theory/Review

From Wikibooks, open books for an open world

Need help creating math symbols?

Definitions

[edit | edit source]

Subset

[edit | edit source]

Subset means for all x, if x is in A then x is also in B.

Proper Subset

[edit | edit source]

Union

[edit | edit source]


Intersection

[edit | edit source]

Empty Set

[edit | edit source]

Minus

[edit | edit source]

Powerset

[edit | edit source]

Ordered Pair

[edit | edit source]

Cartesian Product

[edit | edit source]

or

Relation

[edit | edit source]

A set of ordered pairs

Domain

[edit | edit source]

Range

[edit | edit source]

Field

[edit | edit source]

Equivalence Relations

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

[edit | edit source]
  • Transitive and,
  • Irreflexive: for all a, <a, a> not in R

Trichotomy

[edit | edit source]

Exactly one of the following holds

  • x < y
  • x = y
  • y < x

Proof Strategies

[edit | edit source]

If, then

[edit | edit source]

Prove if x then y

Suppose x
...
...
so, y

If and only If

[edit | edit source]

Prove x iff y

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

Equality

[edit | edit source]

Prove x = y

show x subset y
and
show y subset x

Non-Equality

[edit | edit source]

Prove x != y

x = {has p}
y = {has p}
a in x, but a not in y