# Proving Complement Laws

The problem I am working on is:

Proof the following: $A∪ \bar{A}=U$

As with all proofs, I commenced this proof by using the definition of a union:

$A∪ \bar{A} = \{x|x \in A \vee x \in \bar{A}\}$

Using the definition of the complement of A:

$A∪ \bar{A} = \{x|x \in A \vee ( x \in U \wedge x \notin A) \}$

I then proceeded to use the distributive law, then the domination law, until I noticed a pattern--I was going in circles. Have I started my proof incorrectly?

-
This is not provable in intuitionistic logic (which lacks the Law of Excluded Middle) so perhaps you are an intuitionist :) –  Trevor Wilson Mar 1 '13 at 18:39
Well, I am not familiar with intuitionistic logic, but I'll presume that being referred to as an intuitionist is a complement! –  Mack Mar 1 '13 at 19:05
Sure, what I meant was that there is a long history of certain mathematicians refusing to use $p \vee \neg p$, and not just because they forgot to. –  Trevor Wilson Mar 1 '13 at 19:16
Hmm, how interesting. I wonder what there apprehension was of toward using it. –  Mack Mar 1 '13 at 19:24
One reason is that they thought a proof of $p \vee q$ should consist of a proof of $p$ or a proof of $q$, just like a proof of $p \wedge q$ consists of a proof of $p$ and a proof of $q$. So if $p$ is something like the Riemann hypothesis then we wouldn't be justified in asserting $p \vee \neg p$ just yet. –  Trevor Wilson Mar 1 '13 at 20:22

$$A \cup \bar{A} = \{x|x \in A \vee ( x \in U \wedge x \notin A) \}$$

$$A \cup \bar{A} = \{x|(x \in A \vee x \in U) \land ( x \in A \lor \notin A) \}$$

$$\text{Note that}\;\; x \in A \lor x\notin A \iff x \in U.$$

-
This is true because A and not A always partition the universe? I could have proved this in one step, right? –  Mack Feb 28 '13 at 15:12
Yes, indeed! A and not A always partition the universe. –  amWhy Feb 28 '13 at 15:16
Thank you very much! –  Mack Feb 28 '13 at 15:17
You're welcome, Eli! –  amWhy Feb 28 '13 at 15:18