# Exercise 8.9

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”

1. Wieslaw Poszewiecki says:

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)

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 says:

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 says:

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 says:

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

By definition univ = Complement Empty.

5. Julian says:

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,

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]