|
.: Math Note: If you cannot view some of the math on this page, you may need to add MathML support to your browser. If you have Mozilla/Firefox, go here and install the fonts. If you have Internet Explorer, go here and install the MathPlayer plugin. Math
> Sets
> Hypotheses
HypothesesHypotheses and theorems related to sets.Sibling topics:Contents:
Hypothesis: Cardinality of a power set
The cardinality of the power set `PS(A)` is equal to `2^|A|`, which is the number of permutations that can be
formed from elements of `A`.
Hypothesis: Cardinality of the cartesian product
The cardinality of the cartesian product `A xx B` is equal to `|A||B|`.
Theorem: Subset is transitive If `A sube B and B sube C`, then `A sube C`. Proof:
Given `x in A`, we need to show that `x in C`. By
the definition of
subset we know that if `x in A`, then `x in B`,
and if `x in B`, then `x in C`. Therefore, `x in C`.
Theorem: Subset implies sub-power-set If `A sube B`, then `PS(A) sube PS(B)`. Proof:
Given `S in PS(A)`, we need to show that `S in PS(B)`. By
the definition of
power set, we know that
`S sube A`, and by Subset is transitive we know that `S sube B`. And if `S sube B`, then `S in PS(B)`,
by the definition of power set. Therefore, `PS(A) sube PS(B)`.
Corollary (of
Subset implies sub-power-set):
Sub-power-set implies subset If `PS(A) sube PS(B)`, then `A sube B`. Proof:
We know that `A in PS(A)` by
the definition of
power set, and by
the definition of
subset we know that `A in PS(B)`, which
means that `A sube B`.
Theorem: Subset of intersections If `A sube B` and `C sube D`, then `A nn C sube B nn D`. Proof:
Given `z in A nn C`, we need to show that `z in B nn D`. If `z in A nn C`, then by
the definition of
intersection,
we know that `z in A` and `z in C`. Then, by
the definition of
subset, we know that `z in B` and `z in D`, which means
that `z in B nn D`, as desired. Therefore `A nn C sube B nn D`.
Theorem: Symmetric subset equality If `A sube B` and `B sube A`, then `A=B`. Proof: By
the definition of
subset we know that every element in `A` is in `B`, and every element in `B` is in `A`.
Thus, all possible elements are in both sets or neither. Since there are no differences between the sets,
they must be equal.
Theorem: De Morgan's Law for Sets
For any sets `A` and `B`:
Proof:
This proof has two parts.
Theorem: Subset of power sets If `A sube B and C sube D`, then `A xx C sube B xx D`. Proof: Given any `(x,y) in A xx C`, we need to be able to show that `(x,y) in B xx D`. We know from
the definition of
cartesian product that if `(x,y) in A xx C`, then `x in A` and `y in C`. And given that
`A sube B and C sube D`, we further know that `x in B and y in D`, by
the definition of
subset. And then it becomes
clear that `(x,y) in B xx D`.
Theorem: Canceling subset factors If `A xx B sube A xx C and A != O/`, then `B sube C`. Proof:
Given `y in B`, we need to show that `y in C`. Because `A != O/`, we know `A` contains at least one element,
so we'll take `x in A` as well. Now `(x,y) in A xx B`, and by
the definition of
subset, we know that
`(x,y) in A xx C`, which means that `y in C`, by
the definition of
cartesian product.
Corollary (of
Canceling subset factors):
Canceling equal set factors If `A xx B = A xx C and A != O/`, then `B = C`. Proof:
To show that `B = C`, we will show that `B sube C` and `C sube B`. Since `A xx B = A xx C`, we know that
`A xx B sube A xx C`, by
the definition of
subset. And given that `A != O/`, we can apply
Canceling subset factors to show that `B sube C`. Similarly, we can show that `C sube B`. Therefore,
by Symmetric subset equality, `B = C`.
Theorem: Intersection is distributive `A nn (B uu C) = (A nn B) uu (A nn C)` Proof:
To prove the equality, we will show that each side of the equation is a subset of the other.
Theorem: Union is distributive `A uu (B nn C) = (A uu B) nn (A uu C)` Proof:
To prove the equality, we will show that each side of the equation is a subset of the other.
Theorem: Cartesian product is distributive
The cartesian product distributes over union, intersection, and subtraction:
Proof:
This proof is broken up into three sub-proofs: cartesian product
distributes over union, cartesian product distributes
over intersection, and cartesian product distributes
over difference.
Theorem: Cartesian product distributes over union `A xx (B uu C) = (A xx B) uu (A xx C)` Proof:
To prove that the two sets are equal, we'll show that they are subsets of each other.
Theorem: Cartesian product distributes over intersection `A xx (B nn C) = (A xx B) nn (A xx C)` Proof:
To prove that the two sets are equal, we'll show that they are subsets of each other.
Theorem: Cartesian product distributes over difference `A xx (B - C) = (A xx B) - (A xx C)` Proof:
To prove that the two sets are equal, we'll show that they are subsets of each other.
Theorem: Power set distributes over intersection `PS(A nn B) = PS(A) nn PS(B)` (power set distributes over intersection) Proof:
We will prove the equality by showing that the two sets are subsets of each other.
Note that power set does not distribute over union (ie, `PS(A uu B) = PS(A) uu PS(B)` is not true in general). As a counterexample, consider the case where `A={1,2}` and `B={3,4}`. Then `A uu B = {1,2,3,4}`, which means that `{1,2,3,4} in PS(A uu B)`. However, `PS(A) = {O/,{1},{2},{1,2}}` and `PS(B) = {O/,{3},{4},{3,4}}`. Clearly, `{1,2,3,4} !in PS(A) uu PS(B)`, so `PS(A uu B) != PS(A) uu PS(B)` in this case. |