Hypotheses

One does not thank logic. -- Sarek, "Journey to Babel", stardate 3842.4

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

Hypotheses

Hypotheses and theorems related to sets.

Sibling topics:

Contents:

Hypothesis: Cardinality of a power set [tags: cardinality powerSet]
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 [tags: cardinality setProduct]
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 [tags: powerSet]
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 [tags: powerSet]
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`:
  1. `(A uu B)' = A' nn B'`, and
  2. `(A nn B)' = A' uu B'`
Proof: This proof has two parts.
  1. To prove (1) above, we will show that the two sides of the equation are subsets of each other.
    1. 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'`.
    2. 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.
    Since they are subsets of each other, we know that they are equal by Symmetric subset equality.
  2. To prove (2) above, we will show that the two sides of the equation are subsets of each other.
    1. 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.
    2. 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)'`.
    Since they are subsets of each other, we know that they are equal by Symmetric subset equality.
Theorem: Subset of power sets [tags: subset powerSet]
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 [tags: subset setProduct setFactor]
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 [tags: setProduct setFactor]
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.
  1. 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:
    1. `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.
    2. `x in C`. By a parallel argument, if `x in C`, then `x in (A nn B) uu (A nn C)`.
    Because `x in (A nn B) uu (A nn C)` in both cases, we know that `A nn (B uu C) sube (A nn B) uu (A nn C)`.
  2. 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:
    1. `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)`.
    2. `x in (A nn C)`. By a parallel argument, `x in A nn (B uu C)`.
    Because `x in A nn (B uu C)` in both cases, we know that `(A nn B) uu (A nn C) sube A nn (B uu C)`.
Because the two sets are subsets of each other, we know they are equal by Symmetric subset equality.
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.
  1. Suppose `x in A uu (B nn C)`. The union gives two possibilities, and we'll examine both:
    1. `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.
    2. `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)`.
    Because `y in (A uu B) nn (A uu C)` in both cases, we know that `A uu (B nn C) sube (A uu B) nn (A uu C)`.
  2. 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.
    1. `y in A`. If `y in A`, then clearly `y in A uu (B nn C)`.
    2. `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)`.
    Because `y in A uu (B nn C)` in both cases, we know that `(A uu B) nn (A uu C) sube A uu (B nn C)`.
Because the two sets are subsets of each other, we know they are equal by Symmetric subset equality.
Theorem: Cartesian product is distributive [tags: setProduct]
The cartesian product distributes over union, intersection, and subtraction:
  • `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)`
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.
  1. 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:
    1. `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)`.
    2. `y in C`. By a parallel argument, `(x,y) in (A xx B) uu (A xx C)`.
    In both cases, `(x,y) in (A xx B) uu (A xx C)`, so `A xx (B uu C) sube (A xx B) uu (A xx C)`.
  2. 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:
    1. `(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)`.
    2. `(x,y) in (A xx C)`. By a parallel argument, `(x,y) in A xx (B uu C)`.
    In both cases, `(x,y) in A xx (B uu C)`, so `(A xx B) uu (A xx C) sube A xx (B uu C)`.
Because each side of the equation is a subset of the other, they must be equal.
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.
  1. 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)`.
  2. 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)`.
Because each side of the equation is a subset of the other, they must be equal.
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.
  1. 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)`.
  2. 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)`.
Because each side of the equation is a subset of the other, they must be equal.
Theorem: Power set distributes over intersection [tags: set powerSet]
`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.
  1. 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)`.
  2. 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)`.
Thus, `PS(A nn B) = PS(A) nn PS(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.