# 08.01.07

## 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 |

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

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.

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.

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.

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]