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
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.
Hypotheses
Hypotheses and theorems related to sets.Sibling topics:
Contents:
 Canceling equal set factors
 Canceling subset factors
 Cardinality of a power set
 Cardinality of the cartesian product
 Cartesian product distributes over difference
 Cartesian product distributes over intersection
 Cartesian product distributes over union
 Cartesian product is distributive
 De Morgan's Law for Sets
 Intersection is distributive
 Power set distributes over intersection
 Subpowerset implies subset
 Subset implies subpowerset
 Subset is transitive
 Subset of intersections
 Subset of power sets
 Symmetric subset equality
 Union is distributive
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 `AB`.
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 subpowerset
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 subpowerset):
Subpowerset 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.
 `(A uu B)' = A' nn B'`, and
 `(A nn B)' = A' uu B'`

To prove (1) above, we will show that the two sides of the equation are subsets of each other.
 First we'll show that `(A uu B)' sube A' nn B'`. Given `x in (A uu B)'`, we need to show that `x in A' nn B'`. We know that `x !in A uu B`, by the definition of set complement. Then, because `x !in A uu B`, we know that `x !in A and x !in B`, by the definition of union. If `x !in A`, then `x in A'`, by definition. Similarly, `x in B'`. Therefore, `x in A' nn B'`.
 Now we'll show that `A' nn B' sube (A uu B)'`. Given `x in A' nn B'`, we need to show that `x in (A uu B)'`. We know that `x in A'` and `x in B'`, by the definition of intersection. Then by the definition of set complement, we know that `x !in A` and `x !in B`. Then, `x !in A uu B`, which means that `x in (A uu B)'`, as desired.

To prove (2) above, we will show that the two sides of the equation are subsets of each other.
 First we'll show that `(A nn B)' sube A' uu B'`. Given `x in (A nn B)'`, we need to show that `x in A' uu B'`. We know that `x !in A nn B`, by the definition of set complement, which means that `x !in A and x !in B`. This means `x in A' and x in B'`, which means that `x in A' uu B'`, as desired.
 Now we'll show that `A' uu B' sube (A nn B)'`. Given `x in A' uu B'`, we need to show that `x in (A nn B)'`. We know that `x in A' or x in B'`, by the definition of union, which means that `x !in A or x !in B`, by the definition of set complement. This means that `x` is not in both `A` and `B`, so it's not in `A nn B`, which means it is in `(A nn B)'`.
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.
 Suppose `x in A nn (B uu C)`. We know that `x in A and x in B uu C`. The union gives two possibilities,
and we'll examine both:
 `x in B`. If `x in B`, then we know `x in A nn B`, and that `x in (A nn B) uu (A nn C)`, by the definition of intersection and the definition of union, respectively.
 `x in C`. By a parallel argument, if `x in C`, then `x in (A nn B) uu (A nn C)`.
 Now suppose `x in (A nn B) uu (A nn C)`. We need to show that `x in A nn (B uu C)`. The union gives two
cases, which we'll examine:
 `x in (A nn B)`. In this case `x in A` and `x in B`. Then it's clear that `x in B uu C`, and `x in A nn (B uu C)`.
 `x in (A nn C)`. By a parallel argument, `x in A nn (B uu C)`.
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.
 Suppose `x in A uu (B nn C)`. The union gives two possibilities, and we'll examine both:
 `x in A`. If `x in A`, then we know `x in A uu B and x in A uu C`, and that `x in (A uu B) nn (A uu C)`, by the definition of union and the definition of intersection, respectively.
 `x in (B nn C)`. We know that `x in B and x in C`. Then clearly `x in A uu B and x in A uu C`, and so then `x in (A uu B) nn (A uu C)`.
 Now suppose `y in (A uu B) nn (A uu C)`. We need to show that `y in A uu (B nn C)`. By
the definition of
intersection, we know that `y in A uu B and y in A uu C`. Now either `y in A` or `y !in A`,
and we'll examine both cases.
 `y in A`. If `y in A`, then clearly `y in A uu (B nn C)`.
 `y !in A`. If `y !in A`, then in order for `y in A uu B and A in A uu C` to be true, `y in B and y in C` must be true. Therefore `y in B nn C`, and then clearly `y in A uu (B nn C)`.
Theorem: Cartesian product is distributive
The cartesian product distributes over union, intersection, and subtraction:
Proof:
This proof is broken up into three subproofs: cartesian product
distributes over union, cartesian product distributes
over intersection, and cartesian product distributes
over difference.
 `A xx (B uu C) = (A xx B) uu (A xx C)`
 `A xx (B nn C) = (A xx B) nn (A xx C)`
 `A xx (B  C) = (A xx B)  (A xx C)`
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.
 Given `(x,y) in A xx (B uu C)`, we need to show that `(x,y) in (A xx B) uu (A xx C)`. By
the definition of
cartesian product, we know that `x in A` and `y in B uu C`. This gives two cases:
 `y in B`. If `y in B`, then `(x,y) in A xx B`, and so `(x,y) in (A xx B) uu (A xx C)`.
 `y in C`. By a parallel argument, `(x,y) in (A xx B) uu (A xx C)`.

Given `(x,y) in (A xx B) uu (A xx C)`, we need to show that `(x,y) in A xx (B uu C)`. The union gives
two cases:
 `(x,y) in (A xx B)`. By the definition of cartesian product, we know that `x in A and y in B`. Therefore, `y in B uu C`, so `(x,y) in A xx (B uu C)`.
 `(x,y) in (A xx C)`. By a parallel argument, `(x,y) in A xx (B uu C)`.
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.
 Given `(x,y) in A xx (B nn C)`, we need to show that `(x,y) in (A xx B) nn (A xx C)`. By the definition of cartesian product, we know that `x in A` and `y in B nn C`, so clearly `(x,y) in (A xx B) and (x,y) in (A xx C)`. In other words, `(x,y) in (A xx B) nn (A xx C)`, so `A xx (B nn C) sube (A xx B) nn (A xx C)`.
 Given `(x,y) in (A xx B) nn (A xx C)`, we need to show that `(x,y) in A xx (B nn C)`. We know that `(x,y) in (A xx B) and (x,y) in (A xx C)`. By the definition of cartesian product, `x in A and y in B and y in C`. Therefore, `y in B nn C` and `(x,y) in A xx (B nn C)`, so `(A xx B) nn (A xx C) sube A xx (B nn C)`.
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.
 Given `(x,y) in A xx (B  C)`, we need to show that `(x,y) in (A xx B)  (A xx C)`. By the definition of cartesian product, we know that `x in A` and `y in B  C`, which means that `y in B and y !in C`, by the definition of set difference. That means `(x,y) in (A xx B)` but `(x,y) !in (A xx C)`, and so `(x,y) in (A xx B)  (A xx C)`. Therefore, `A xx (B  C) sube (A xx B)  (A xx C)`.
 Given `(x,y) in (A xx B)  (A xx C)`, we need to show that `(x,y) in A xx (B  C)`. We know that `(x,y) in (A xx B) and (x,y) !in (A xx C)`. By the definition of cartesian product, `x in A and y in B and y !in C`. Therefore, `y in B  C` and `(x,y) in A xx (B  C)`, so `(A xx B)  (A xx C) sube A xx (B  C)`.
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.
 Given `S in PS(A nn B)`, `S sube A nn B` by the definition of power set. Clearly, then, `S sube A` and `S sube B`. And this means that `S in PS(A)` and `S in PS(B)`, so `S in PS(A) nn PS(B)`, and `PS(A nn B) sube PS(A) nn PS(B)`.
 Given `T in PS(A) nn PS(B)`, we know that `T sube A and T sube B` by the definition of power set, and so `T sube A nn B`, which means `T in PS(A nn B)`, so `PS(A) nn PS(B) sube PS(A nn B)`.
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.