Definitions
edit
-
Subset means for all x, if x is in A then x is also in B.
Proper Subset
edit
-
-
-
Intersection
edit
-
-
Empty Set
edit
-
-
Powerset
edit
-
Ordered Pair
edit
-
Cartesian Product
edit
-
or
-
Relation
edit
A set of ordered pairs
Equivalence Relations
edit
- 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
- Transitive and,
- Irreflexive: for all a, <a, a> not in R
Trichotomy
edit
Exactly one of the following holds
Proof Strategies
edit
If, then
edit
Prove if x then y
- Suppose x
- ...
- ...
- so, y
If and only If
edit
Prove x iff y
- suppose x
- ...
- ...
- so, y
- suppose y
- ...
- ...
- so, x
Equality
edit
Prove x = y
- show x subset y
- and
- show y subset x
Non-Equality
edit
Prove x != y
- x = {has p}
- y = {has p}
- a in x, but a not in y