08.01.07

Exercise 8.9

Posted in Uncategorized at 10:19 pm by admin

Proof from axioms is something that takes great care: it is all too easy to skip a step that “obviously follows” from the axioms without proving that step. I’m not convinced this is all correct…

r
≡ r `Intersect` univ [Axiom 4]
≡ r `Intersect` (r `Union` Complement r) [Axiom 5](r `Intersect` r) `Union` (r `Intersect` Complement r) [Axiom 3](r `Intersect` r) `Union` Empty [Axiom 5](r `Intersect` r) [Axiom 4]
 
Lemma 1: r ≡ (r `Intersect` r)
 
r
≡ r `Union` Empty [Axiom 4]
≡ r `Union` (r `Intersect` Complement r) [Axiom 5](r `Union` r) `Intersect` (r `Union` Complement r) [Axiom 3](r `Union` r) `Intersect` univ [Axiom 5](r `Union` r) [Axiom 4]
 
Lemma 2: r ≡ (r `Union` r)
 
r `Union` univ
≡ r `Union` (r `Union` Complement r) [Axiom 5](r `Union` r) `Union` Complement r [Axiom 1]
≡ r `Union` Complement r [Lemma 2]
≡ univ [Axiom 5]
 
Lemma 3: r `Union` univ ≡ univ
 
r `Intersect` Empty
≡ r `Intersect` (r `Intersect` Complement r) [Axiom 5](r `Intersect` r) `Intersect` Complement r [Axiom 1]
≡ r `Intersect` Complement r [Lemma 1]
≡ Empty [Axiom 5]
 
Lemma 4: r `Intersect` Empty ≡ Empty
 
Let X = (r1 `Union` (r1 `Intersect` r2))
X `Intersect` Complement r1
≡ (r1 `Union` (r1 `Intersect` r2)) `Intersect` Complement r1
≡ (r1 `Intersect` Complement r1) `Union`
  ((r1 `Intersect` r2) `Intersect` Complement r1) [Axiom 3]
≡ Empty `Union` ((r1 `Intersect` r2) `Intersect` Complement r1) [Axiom 5](r1 `Intersect` r2) `Intersect` Complement r1 [Axiom 4](r2 `Intersect` r1) `Intersect` Complement r1 [Axiom 2]
≡ r2 `Intersect` (r1 `Intersect` Complement r1) [Axiom 1]
≡ r2 `Intersect` Empty [Axiom 5]
≡ Empty [Lemma 4]
∴ by Axiom 5, X = r1
 
Lemma 5: (r1 `Union` (r1 `Intersect` r2)) ≡ r1
 
r1 `Intersect` (r1 `Union` r2)(r1 `Union` r1) `Intersect` (r1 `Union` r2) [Lemma 2]
≡ r1 `Union` (r1 `Intersect` r2) [Axiom 3]
≡ r1 [Lemma 5]
 
Lemma 6: (r1 `Intersect` (r1 `Union` r2)) ≡ r1
 
Let X = Complement (Complement r)
X `Union` (Complement r)
≡ Complement (Complement r) `Union` (Complement r)
≡ univ [Axiom 5]
∴ by Axiom 5, X = r
 
Lemma 7: Complement (Complement r) ≡ r
 
Let X = Complement Empty
X `Union` Empty
≡ Complement Empty `Union` Empty
≡ univ [Axiom 5]
∴ by Axiom 4, X = univ
 
Lemma 8: Complement Empty ≡ univ
 
Complement univ
≡ Complement (Complement Empty) [Lemma 8]
≡ Empty [Lemma 7]
 
Lemma 9: Complement univ ≡ Empty
 
Let X = Complement (r1 `Union` r2)
(r1 `Union` r2) `Union` X
≡ (r1 `Union` r2) `Union` Complement (r1 `Union` r2)
≡ univ [Axiom 5]
 
Let Y = Complement r1 `Intersect` Complement r2
(r1 `Union` r2) `Union` Y
≡ (r1 `Union` r2) `Union` (Complement r1 `Intersect` Complement r2)((r1 `Union` r2) `Union` Complement r1) `Intersect`
  ((r1 `Union` r2) `Union` Complement r2) [Axiom 3]((r2 `Union` r1) `Union` Complement r1) `Intersect`
  ((r1 `Union` r2) `Union` Complement r2) [Axiom 2](r2 `Union` (r1 `Union` Complement r1)) `Intersect`
  ((r1 `Union` r2) `Union` Complement r2) [Axiom 1](r2 `Union` (r1 `Union` Complement r1)) `Intersect`
  (r1 `Union` (r2 `Union` Complement r2)) [Axiom 1](r2 `Union` univ) `Intersect` (r1 `Union` (r2 `Union` Complement r2)) [Axiom 5](r2 `Union` univ) `Intersect` (r1 `Union` univ) [Axiom 5]
≡ univ `Intersect` (r1 `Union` univ) [Lemma 3]
≡ univ `Intersect` univ [Lemma 3]
≡ univ [Lemma 3]
 
∴ X ≡ Y
 
Lemma 10: Complement (r1 `Union` r2) ≡ Complement r1 `Intersect` Complement r2
 
Let X = Complement (r1 `Intersect` r2)
(r1 `Intersect` r2) `Union` X
≡ (r1 `Intersect` r2) `Union` Complement (r1 `Intersect` r2)
≡ univ [Axiom 5]
 
Let Y = Complement r1 `Union` Complement r2
(r1 `Intersect` r2) `Union` Y
≡ (r1 `Intersect` r2) `Union` (Complement r1 `Union` Complement r2)(r1 `Union` (Complement r1 `Union` Complement r2)) `Intersect`
  (r2 `Union` (Complement r1 `Union` Complement r2)) [Axiom 3](r1 `Union` (Complement r1 `Union` Complement r2)) `Intersect`
  ((Complement r1 `Union` Complement r2) `Union` r2) [Axiom 2]((r1 `Union` Complement r1) `Union` Complement r2) `Intersect`
  ((Complement r1 `Union` Complement r2) `Union` r2) [Axiom 1]((r1 `Union` Complement r1) `Union` Complement r2) `Intersect`
  (Complement r1 `Union` (Complement r2 `Union` r2)) [Axiom 1](univ `Union` Complement r2) `Intersect`
  (Complement r1 `Union` (Complement r2 `Union` r2)) [Axiom 5](univ `Union` Complement r2) `Intersect`
  (Complement r1 `Union` (r2 `Union` Complement r2)) [Axiom 2](univ `Union` Complement r2) `Intersect` (Complement r1 `Union` univ) [Axiom 5](univ `Union` Complement r2) `Intersect` univ [Lemma 3]
≡ univ `Union` Complement r2 [Axiom 4]
≡ Complement r2 `Union` univ [Axiom 2]
≡ univ [Lemma 3]
 
∴ X ≡ Y
 
Lemma 11: Complement (r1 `Intersect` r2) ≡  Complement r1 `Union` Complement r2

5 Comments »

  1. Wieslaw Poszewiecki said,

    April 23, 2008 at 10:55 pm

    IMHO proof of Lemma 4 is not complete.

    It is assumed that if

    X `Union` Complement r = univ (1)

    then X has to be r, because

    r `Union` Complement r = univ

    In fact to fullfill (1) it is enough that X contains r, not that it is equal.

    Proof has to be a bit longer
    Similarly as (1) we can proove

    X `Intersect` Complement r = Empty (2)

    then let us start with r

    r
    = r `Intersect` univ (because axiom 4)
    = r `Intersect` (X `Union` Complement r) (because 1)
    = (r `Intersect` X) `Union` (r `Intersect` Complement r) (because axiom 3)
    = (r `Intersect` X) `Union` Empty (because axiom 5)
    = (r `Intersect` X) `Union` (X `Intersect` Complement r) (because 2)
    = (X `Intersect` r) `Union` (X `Intersect` Complement r) (because axiom 2)
    = X `Intersect` ( r `Union` Complement r) (because axiom 3)
    = X `Intersect` univ (because axiom 5)
    = X (because axiom 4)
    = Complement (Complement r)

    Similar problem I see with proofs of lemmas 10 and 11

  2. fero said,

    July 22, 2008 at 11:47 am

    IMHO I don’t think you can do
    “In fact to fullfill (1) it is enough that X contains r, not that it is equal.”

    It is true but there is no axiom that states that. You can use only axioms.

  3. Jonathan said,

    January 8, 2009 at 1:12 pm

    Actually
    r1 `Union` (r1 `Intersect` r2)

    In the => notation follows from or-introduction. It is always the case that if a then a or b

    So start
    r1,
    therefore, r1 `union` (r1 `intersect` r2)

    Then for equivalence you need actually to go the other way too. There is a lot of abuse of notation going on in this section of the book, and I found this exercise to be a stretch.

    Start,
    r1 `Union` (r1 `Intersect` r2)
    Now, for or-elimination you have to handle both cases.
    Assume r1.
    Therefore r1.
    Assume (r1 `Intersect` r2).
    By and-elimination, conclude
    r1.
    Therefore, r1.

    Therefore r1 r1 `Union` (r1 `Intersect` r2).

    I know the author states to use the axioms alone, but if there are ways to prove things without making weird declarations, then I prefer them as they make for better habits.

  4. Jonathan said,

    January 8, 2009 at 1:30 pm

    Why write anything at all for Theorem 8:
    Complement Empty univ.

    By definition univ = Complement Empty.

  5. Julian said,

    April 14, 2010 at 12:13 am

    For simplicity and brevity, I will use somthing like standard
    set-theoretic notations as abbreviations for Intersection and Union,
    writing

    r1 u r2 for r1 `Union` r2

    and

    r1 n r2 for r1 `Intersection` r2

    Also, I will write r’ for Complement r, 0 for Empty and 1 for univ,
    and a simple = sign instead of the three-line equivalence notation.

    Then the five axioms, together with some simple corollaries, read:

    Axiom 1
    ——-

    r1 u (r2 u r3) = (r1 u r2) u r3
    r1 n (r2 n r3) = (r1 n r2) n r3

    Axiom 2
    ——-

    r1 u r2 = r2 u r1
    r1 n r2 = r2 n r1

    Axiom 3
    ——-

    r1 n (r2 u r3) = (r1 n r2) u (r1 n r3)
    r1 u (r2 n r3) = (r1 u r2) n (r1 u r3)

    Corollaries:

    (r2 u r3) n r1 = (r2 n r1) u (r3 n r1)
    (r2 n r3) u r1 = (r2 u r1) n (r3 u r1)

    Proof: Apply Axiom 2 to both sides.

    Axiom 4
    ——-

    r u 0 = r
    r n 1 = r

    Corollaries:

    0 u r = r
    1 n r = r

    Proof: Apply Axiom 2 to the left side.

    Axiom 5
    ——-

    r u r’ = 1
    r n r’ = 0

    Corollaries:

    r’ u r = 1
    r’ n r = 0

    Proof: Apply Axiom 2 to the left side.

    Now for the exercise at hand…

    Lemma 1
    ——-

    r n r = r
    r u r = r

    Proof:

    r = r n 1 [Axiom 4]
    = r n (r u r’) [Axiom 5]
    = (r n r) u (r n r’) [Axiom 3]
    = (r n r) u 0 [Axiom 5]
    = r n r [Axiom 4]

    The proof of the second statement is essentially identical, swapping
    n with u and 1 with 0:

    r = r u 0 [Axiom 4]
    = r u (r n r’) [Axiom 5]
    = (r u r) n (r u r’) [Axiom 3]
    = (r u r) n 1 [Axiom 5]
    = r u r [Axiom 4]

    Lemma 2
    ——-

    r u 1 = 1
    r n 0 = 0

    Proof:

    r u 1 = r u (r u r’) [Axiom 5]
    = (r u r) u r’ [Axiom 1]
    = r u r’ [Lemma 1]
    = 1 [Axiom 5]

    and again, the other is exactly parallel:

    r n 0 = r n (r n r’) [Axiom 5]
    = (r n r) n r’ [Axiom 1]
    = r n r’ [Lemma 1]
    = 0 [Axiom 5]

    Corollaries:

    1 u r = 1
    0 n r = 0

    Proof: Apply Axiom 2 to the left side.

    Lemma 3
    ——-

    r1 u (r1 n r2) = r1
    r1 n (r1 u r2) = r1

    Proof (the first step is sneaky):

    r1 u (r1 n r2) = (r1 n 1) u (r1 n r2) [Axiom 4]
    = r1 n (1 u r2) [Axiom 3, in reverse]
    = r1 n 1 [Lemma 2, corollary]
    = r1 [Axiom 4]

    And again, swapping n with u and 1 with 0 gives the corresponding
    result:

    r1 n (r1 u r2) = (r1 u 0) n (r1 u r2) [Axiom 4]
    = r1 u (0 n r2) [Axiom 3, in reverse]
    = r1 u 0 [Lemma 2, corollary]
    = r1 [Axiom 4]

    Alternatively, the latter can be deduced from the former as follows:

    r1 n (r1 u r2) = (r1 n r1) u (r1 n r2) [Axiom 3]
    = r1 u (r1 n r2) [Lemma 1]
    = r1 [first part of Lemma 3]

    Lemma 4
    ——-

    r” = r, where r” means (r’)’

    Proof:

    The idea of this proof is to show that r” u r = r and also r” u r = r”,
    so that r = r” u r = r”, or r” = r. It could be written in one
    long chain, but it is clearer to write it in two halves.

    We have

    r” u r = (r” u r) n 1 [Axiom 4]
    = (r” u r) n (r u r’) [Axiom 5]
    = (r u r”) n (r u r’) [Axiom 2]
    = r u (r” n r’) [Axiom 3, in reverse]
    = r u (r’ n (r’)’) [Axiom 2, and writing r”=(r’)’]
    = r u 0 [Axiom 5]
    = r [Axiom 4]

    Likewise, but this time writing 1 = r’ u (r’)’ instead of 1 = r u r’,
    we get:

    r” u r = (r” u r) n 1 [Axiom 4]
    = (r” u r) n (r’ u (r’)’) [Axiom 5]
    = (r” u r) n (r” u r’) [Axiom 2, and writing (r’)’=r”]
    = r” u (r n r’) [Axiom 3, in reverse]
    = r” u 0 [Axiom 5]
    = r” [Axiom 4]

    Therefore r = r”.

    Lemma 5
    ——-

    0′ = 1
    1′ = 0

    Well, the first is the definition of univ (as given just before Axiom
    3), and the proof the of second is trivial:

    1′ = (0′)’ [By definition: 1 = 0′]
    = 0 [Lemma 4]

    Lemma 6
    ——-

    (r1 u r2)’ = r1′ n r2′
    (r1 n r2)’ = r1′ u r2′

    These are the famous De Morgan’s Theorems, and their proof is tricky
    (and not due to me, either!). We prove a preliminary lemma first.

    Lemma 7
    ——-

    If r1′ n r2 = 0 and r1′ u r2 = 1, then r1 = r2.

    Proof:

    r1 = r1 u 0 [Axiom 4]
    = r1 u (r1′ n r2) [Hypothesis]
    = (r1 u r1′) n (r1 u r2) [Axiom 3]
    = 1 n (r1 u r2) [Axiom 5]
    = (r1′ u r2) n (r1 u r2) [Hypothesis]
    = (r2 u r1′) n (r2 u r1) [Axiom 2]
    = r2 u (r1′ n r1) [Axiom 3, in reverse]
    = r2 u 0 [Axiom 5, corollary]
    = r2

    Proof of Lemma 6
    —————-

    We want to show first that (r1 u r2)’ = r1′ n r2′, so we aim to show
    that ((r1 u r2)’)’ n (r1′ n r2′) = 0 and ((r1 u r2)’)’ u (r1′ n r2′)
    = 1, so that (r1 u r2)’ = r1′ n r2′ by Lemma 7.

    We note first that ((r1 u r2)’)’ = r1 u r2 by Lemma 4. We then have

    (r1 u r2) n (r1′ n r2′)

    = ((r1 u r2) n r1′) n r2′ [Axiom 1]
    = ((r1 n r1′) u (r2 n r1′)) n r2′ [Axiom 3, corollary]
    = (0 u (r2 n r1′)) n r2′ [Axiom 5]
    = (r2 n r1′) n r2′ [Axiom 4, corollary]
    = (r1′ n r2) n r2′ [Axiom 2]
    = r1′ n (r2 n r2′) [Axiom 1]
    = r1′ n 0 [Axiom 5]
    = 0 [Lemma 2]

    and

    (r1 u r2) u (r1′ n r2′)
    = ((r1 u r2) u r1′) n ((r1 u r2) u r2′) [Axiom 3]
    = ((r2 u r1) u r1′) n ((r1 u r2) u r2′) [Axiom 2]
    = (r2 u (r1 u r1′)) n (r1 u (r2 u r2′)) [Axiom 1]
    = (r2 u 1 ) n (r1 u 1) [Axiom 5]
    = 1 n 1 [Lemma 2]
    = 1 [Axiom 4]

    Thus, by Lemma 7, (r1 u r2)’ = r1′ n r2′.

    For the second part of Lemma 6, we can either argue identically, or as
    follows:

    We have

    (r1 n r2)’ = ( (r1′)’ n (r2′)’ )’ [Lemma 4]
    = ( ((r1′) u (r2′))’ )’ [Lemma 6, first part]
    = (r1′ u r2′)” [rewriting with fewer brackets]
    = r1′ u r2′ [Lemma 4]

Leave a Comment