# Proof help

• Apr 8th 2007, 11:44 AM
Possible actuary
Proof help
This is what I am given: Let A and B be sets. If A or B are not an empty set, then both A and B are nonempty.

I am thinking that this statement is not true and to do a proof by contradiction. But what I came up with does not sound complete.

Assume A or B are not an empty set and either A or B is an empty set. Let x be an element of A. Since A or B are not empty, then B is empty set. Let x be an element of B. Since A or B are not empty then A is empty set. Thus either A or B is an empty set and thus a contradiction.
• Apr 8th 2007, 11:53 AM
Jhevon
Quote:

Originally Posted by Possible actuary
This is what I am given: Let A and B be sets. If A or B are not an empty set, then both A and B are nonempty.

I am thinking that this statement is not true and to do a proof by contradiction. But what I came up with does not sound complete.

Assume A or B are not an empty set and either A or B is an empty set. Let x be an element of A. Since A or B are not empty, then B is empty set. Let x be an element of B. Since A or B are not empty then A is empty set. Thus either A or B is an empty set and thus a contradiction.

By "A or B" do you mean, AUB?

i guess it doesn't make much difference though.

a proof by contradiction is nice, but it is an overkill in this situation. we can easily find an example to illustrate the statement is false.

If A or B are not an empty set, then both A and B are nonempty.

The statement is false.

Solution (we say solution and not proof since we're giving an example)

Consider A = {1} and B = empty set

then AUB = {1} so it is not empty and since B is empty, the statement "both A and B are nonempty" is false

and so, we have a true claim implying a false claim, thus the overall statement is false
• Apr 8th 2007, 11:58 AM
Possible actuary
Yes, I did mean AUB. I don't know why I didn't just use an example that made it false. Thanks!
• Apr 8th 2007, 12:18 PM
Jhevon
Quote:

Originally Posted by Possible actuary
Let A and B be sets. If A or B are not an empty set, then both A and B are nonempty.

I am thinking that this statement is not true and to do a proof by contradiction. But what I came up with does not sound complete.

Assume A or B are not an empty set and either A or B is an empty set. Let x be an element of A. Since A or B are not empty, then B is empty set. Let x be an element of B. Since A or B are not empty then A is empty set. Thus either A or B is an empty set and thus a contradiction.

Let's try a proof by contradiction you started with. But first, let's think through it to make sure we are organized correctly.

Proof Analysis:

Let the statement "A or B are not an empty set" be P
Let the statement "both A and B are nonempty" be Q

then we are given implication P=>Q to test whether it is true or false.

to prove that an implication P=>Q is TRUE by Contradiction we must begin by assuming Pand~Q and show that this implies a contradiction. so since we want to show this statment is false, we can show that Pand~Q DOES NOT cause a contradiction.

However, this twisting of the definition gets confusing, so I'd probably use a direct proof of this (if i wanted to write a proof, which i wouldn't)

Proof:
Assume AUB is not empty.

since AUB is not empty, there is some x element of AUB. so x is an element of A or x is an element of B. thus there are three possiblities.

case 1: x is an element of A and not B
case 2: x is an element of B and not A
case 3: x is an element of both A and B

in cases 1 and 2, the statement "both A and B are nonempty" is false. and so the overall statement "If A or B are not an empty set, then both A and B are nonempty" is false

QED

we would proceed in a similar manner for a proof by contradiction, however, we'd end up showing that only one possibility is false, instead of two
• Apr 8th 2007, 12:24 PM
Possible actuary
so case 3 does not matter?
• Apr 8th 2007, 12:30 PM
Jhevon
Quote:

Originally Posted by Possible actuary
so case 3 does not matter?

yes it does actually. in case 3, the statement made is true. so we are not worried about it, we wanted to show it was false, so we point at the other two cases and say, "yeah, the statement is true in the third case, but lookie here, it is false these other two times, and so, if it is not true all the time, then it is not a true statement as far as logic is concened"