Eberhard Karls Universität Tübingen | Seminar für Sprachwissenschaft (SfS)
Methods I: Logic, WS 2024/25 | Prof. Dr. Michael Franke
Tutors: Seoha Lee, Aida Rostami, Shanshan Xu, Erik Zeiner
Exercise Sheet 2
Proofs
Submission by: 12 November 2024, 2:00pm
Please write your solutions on this exercise sheet. You can submit an annotated PDF or a
scanned sheet you filled out by hand; acceptable submissions must use this provided
exercise sheet.
The phrasing of the first exercise has been adjusted (8 Nov 2024).
Exercise: 1 [2 points] Bob, the novice logician, wants to prove the following proposition:
Proposition. For all n ≥ 2, if you have n non-empty, disjoint sets, the union of these sets will
always have at least n elements.
Bob’s Proof Attempt
Base Case
Bob chooses the base case n = 1. He claims that if you have 1 set, the union of that set will contain
at least 1 element. For example, if the set is A = {a}, then the union of A is {a}, which has 1
element.
He’s happy with this and moves to the inductive step.
Inductive Hypothesis
Bob assumes that for some k ≥ 2, the union of k distinct sets contains at least k elements.
Inductive Step
Bob now tries to prove that the union of k + 1 distinct sets contains at least k + 1 elements. He
reasons:
• Suppose we have k distinct sets, and by the inductive hypothesis, their union contains at least
k elements.
• Now, if we add one more distinct set Ak+1 , the union will include the elements of this new set,
so it must contain at least k + 1 elements in total.
Bob declares the proof complete.
Can you find any mistakes in Bob’s proof? If yes, write the correct answer and highlight what you
changed in the original text.
1/3
Eberhard Karls Universität Tübingen | Seminar für Sprachwissenschaft (SfS)
Methods I: Logic, WS 2024/25 | Prof. Dr. Michael Franke
Tutors: Seoha Lee, Aida Rostami, Shanshan Xu, Erik Zeiner
Exercise: 2 [2 points] Bob’s tutor gave him 0 points on his solution to the following question:
1. Prove whether the statement is true or false:
For any two sets A and B, if A ⊆ B, then A < B.
Feeling both sad and frustrated, Bob is convinced that his answer was completely correct. Now, he
turns to you for help. Can you examine Bob’s solution and if you believe Bob’s answer is wrong,
write the correct answer and also explain which part of his proof went wrong.
Bob’s Proof Attempt
1. Assume A ⊆ B.
2. This means every element of A is also in B.
3. Since A is a subset of B, it must have fewer elements than B.
4. Therefore, A < B is true.
Exercise: 3 [3 points] Consider the following proposition:
Proposition. There exists a set S that contains all sets, including itself.
Formulate an argument for or against the existence of such a set. If you believe this idea leads to a
contradiction, prove why.
2/3
Eberhard Karls Universität Tübingen | Seminar für Sprachwissenschaft (SfS)
Methods I: Logic, WS 2024/25 | Prof. Dr. Michael Franke
Tutors: Seoha Lee, Aida Rostami, Shanshan Xu, Erik Zeiner
Exercise: 4 [4 points] Let X and Y be be arbitrary sets over some universe U. Refute the following
claims by a counterexample.
(a) X ∪ Y = X ∪ Y
(b) If P (X) ∩ P (Y ) ≠ ∅ then X ⊆ Y
Exercise: 5 [4 points] Let X and Y be arbitrary, unspecified sets. Use reductio ad absurdum to prove
the following claim:
X ∪X =U
3/3
