Can Proofs Involving the Empty Set Be Solved by Contradiction?

In summary, the conversation discusses two proofs involving the concept of subset and the empty set. The first proof is done by contradiction, where the speaker assumes that the empty set is not a subset of itself and then contradicts this statement using the definition of an empty set and the concept of vacuous truth. The second proof has several issues and the expert advises against using the term "part" and suggests using "element" or "subset" instead. The expert also mentions that it is useful to observe that any set is a subset of its union with another set, which can be helpful in proving the second part of the problem. The conversation ends with a question about listing the subsets of the empty set.
  • #1
Chicago_Boy1
6
0
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.
 
Physics news on Phys.org
  • #2
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.
 
  • #3
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.
 
  • #4
ystael said:
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?
 
  • #5
Chicago_Boy1 said:
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.
 
  • #6
ystael said:
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...
 

Related to Can Proofs Involving the Empty Set Be Solved by Contradiction?

1. What are the two basic proofs in set theory?

The two basic proofs in set theory are the membership proof and the subset proof. These proofs are used to show the relationship between elements and sets in a given set theory context.

2. How do you prove membership in a set?

To prove membership in a set, you must show that an element is included in a specific set. This can be done by using the notation "∈" to indicate that an element belongs to a set. For example, if we want to prove that the number 3 is a member of the set {1, 2, 3}, we can write 3 ∈ {1, 2, 3}.

3. What is a subset proof?

A subset proof is a type of proof that shows that one set is a subset of another set. This means that all the elements in the first set are also included in the second set. This can be shown using the notation "⊆". For example, if we want to prove that the set {1, 2} is a subset of the set {1, 2, 3}, we can write {1, 2} ⊆ {1, 2, 3}.

4. How do you prove two sets are equal?

To prove that two sets are equal, you must show that they have the same elements. This can be done by using the notation "=". For example, if we want to prove that the sets {1, 2, 3} and {3, 2, 1} are equal, we can write {1, 2, 3} = {3, 2, 1}.

5. What is the importance of these basic proofs in set theory?

These basic proofs are important because they form the foundation of set theory and are used to prove more complex theorems and concepts. They allow us to establish relationships between elements and sets, and to define important concepts such as equality and subsets. Additionally, these proofs are used in various fields of mathematics and in computer science to solve problems and develop new theories.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
592
  • Calculus and Beyond Homework Help
Replies
4
Views
560
  • Calculus and Beyond Homework Help
Replies
9
Views
502
  • Calculus and Beyond Homework Help
Replies
34
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
934
  • Calculus and Beyond Homework Help
Replies
6
Views
3K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
600
  • Calculus and Beyond Homework Help
Replies
24
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
636
Back
Top