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 responses to “Exercise 8.9”

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

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.

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.

Why write anything at all for Theorem 8:

Complement Empty univ.

By definition univ = Complement Empty.

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]