Can Proofs Involving the Empty Set Be Solved by Contradiction?

[Chicago_Boy1]

I am doing some non-homework exercises in preparation for my midterm, and am struggling with the following proofs:

First Prove

{} is a subset of {}, where {} refers to an empty set

My professor told me to do this by contradiction.

So I assume that {} is not a subset of {}. That would imply that there exists an element "x" in {} that is NOT in {}.

As far as I can tell, there are two contradictions in that statement. First, {} is, by definition, empty, so there cannot exist an element "x" in {}. Second, an element cannot both be and not be in a set.

So I am just wondering whether it's the first contradiction, the second one, or perhaps both (?) that allows me to claim that I've solved this via contradiction.

Second Proof

A union B = {} iff A = X and B = X

The way I see it, there are two parts to this problem:

Part #1:
Assume A union B = {} and prove that A = {} and B = {}

Part #2:
Assume A = {} and B = {} and prove that A union B = {}

Part #1 Proof:

Assume A union B = {}, prove that A = {} and B = {}
Let x be a part of A union B = {} <=> x is a part of {}, but that can't happen (empty set does not have elements by definition), so it has to follow that there are no elements in A or in B.

Part #2 Proof:

Assume A = {} and B = {}, A union B = {}

Let x be a part of A, which would imply that x is a part of {}, but that can't happen, so A is empty

Let x be a part of B, which would imply that x is a part of {}, but that can't happen, so B is empty

So since A and B are both empty, it must follow that A OR (i.e. union) B = Empty or empty = {}.

Basically, for this second proof, I just need to make sure that I am doing it right.

 

[ystael]

For the first one, either contradiction suffices. However, it is simpler not to use contradiction and instead learn to argue using the concept of vacuous truth. This is the logical principle that anything is true of the members of an empty set: it is equally true that all invisible pink unicorns are vegetarian, and that all invisible pink unicorns eat pork chops for dinner every day.

The definition of set inclusion is: [tex]A \subset B[/tex] means that for all [tex]x \in A[/tex], [tex]x \in B[/tex]. But any statement that begins "for all [tex]x \in \emptyset[/tex]" is vacuously true, so the empty set is a subset of every set, including itself.

 

[ystael]

The second proof has a lot of problems. First, don't use the word "part", as it's not clear whether you mean "element" or "subset". Always use one of those two, or symbols. Second, both directions of your implication seem to be argued circularly. I assume from the fact that you're working this exercise that you can't just take as known that [tex]\emptyset \cup \emptyset = \emptyset[/tex], which is exactly what you seem to do at the conclusion of each half.

For one direction, it is useful to observe that [tex]A \subset A \cup B[/tex] and [tex]B \subset A \cup B[/tex]. For the other direction, you may again try arguing by contradiction.

 

[Chicago_Boy1]

The second proof has a lot of problems. First, don't use the word "part", as it's not clear whether you mean "element" or "subset". Always use one of those two, or symbols. Second, both directions of your implication seem to be argued circularly. I assume from the fact that you're working this exercise that you can't just take as known that [tex]\emptyset \cup \emptyset = \emptyset[/tex], which is exactly what you seem to do at the conclusion of each half.

For one direction, it is useful to observe that [tex]A \subset A \cup B[/tex] and [tex]B \subset A \cup B[/tex]. For the other direction, you may again try arguing by contradiction.

Thanks for the tip. I'll be more careful with my terms next time!

I guess I am a little confused by your note that it is useful to observe that [tex]A \subset A \cup B[/tex] and [tex]B \subset A \cup B[/tex]. How exactly does it fit into the problem?

 

[ystael]

I guess I am a little confused by your note that it is useful to observe that [tex]A \subset A \cup B[/tex] and [tex]B \subset A \cup B[/tex]. How exactly does it fit into the problem?

List all the subsets of the empty set.

 

[Chicago_Boy1]

List all the subsets of the empty set.

Would that be for the first part or the second part?

Sorry, I am just a little confused...