Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 5 down vote accepted

$$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.$$

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.