5 responses to “Exercise 8.9”

1. 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. 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. 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. Why write anything at all for Theorem 8:
   Complement Empty univ.

   By definition univ = Complement Empty.

5. 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]