Set Theory/Review
Appearance
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