Description
1. Cat On a Hot Tin Proof (8 points)
Let the domain of discourse be foods, pets (including Garfield and Odie), and days of the week. We define the
predicates Cat(x), Dog(x), and Lasagna(x) to mean that x is a cat, a dog, or a lasagna, respectively. We also
define the predicates Loves(x, y) and Hates(x, y) to mean that x loves y and x hates y, respectively.
Prove the following claim:
∀x (Lasagna(x) → ∃y (Cat(y) ∧ Loves(y, x) ∧ Hates(y, Monday) ∧ ¬∀z (Dog(z) → Hates(z, y))))
Common-knowledge facts about about Garfield and Odie do not require any proof and may simply be stated.
If you are unfamiliar with that comic, the Wikipedia article may be helpful.
2. Teacher’s Set (24 points)
Let A, B, and C be sets. Prove or disprove the following claims.
For the proofs, you may not cite the Meta Theorem. However, you should feel free to follow it as a template
for how to write your own proof.
(a) A ∩ (B ∩ A) = A
(b) (B \ A) ∩ (C \ A) = (B ∪ C) \ A
(c) (B ∪ A) ∩ (B ∪ C) = B ∪ (C ∪ A)
3. April Showers Bring May Powers (24 points)
Let S and T be sets. Prove or disprove the following claims.
(a) P(S ∪ T) = P(S) ∪ P(T) ∪ P(S ∩ T)
(b) P(S ∩ T) = {∅} ∪ (P(S) \ P(S \ T))
(c) P(S ∩ T) = P(S) ∩ P(T)
4. Keeping Up With the Cartesians (24 points)
Let A, B, and C be sets.
(a) [12 Points] Prove that, if B ⊆ ∅, then A × B = B × C.
(If it helps, recall that ∅ is defined by the fact that ∀x (x /∈ ∅) holds.)
(b) [12 Points] Prove that, if B 6⊆ ∅ and A × B ⊆ B × C, then A ⊆ B.
5. A Good Prime Was Had By All (20 points)
Prove that, if p > 2 is prime and p 6≡ 0 (mod 3), then p mod 12 ∈ {1, 5, 7, 11}.
Hint 1: Note that p mod 12 has only 12 possible values (0 . . . 11).
Hint 2: Consider the proof strategies discussed in lecture.
6. Extra Credit: Match-22 (0 points)
In this problem, you will show that given n red points and n blue points in the plane such that no three points lie
on a common line, it is possible to draw line segments between red-blue pairs so that all the pairs are matched
and none of the line segments intersect. Assume that there are n red and n blue points fixed in the plane.
A matching M is a collection of n line segments connecting distinct red-blue pairs. The total length of a
matching M is the sum of the lengths of the line segments in M. Say that a matching M is minimal if there
is no matching with a smaller total length.
Let IsMinimal(M) be the predicate that is true precisely when M is a minimal matching. Let HasCrossing(M)
be the predicate that is true precisely when there are two line segments in M that cross each other.
Give an argument in English explaining why there must be at least one matching M so that IsMinimal(M)
is true, i.e.
∃MIsMinimal(M))
Give an argument in English explaining why
∀M(HasCrossing(M) → ¬IsMinimal(M))
Then, use the two results above to give a proof of the statement:
∃M¬HasCrossing(M).
2
