Reading (~20 mins)

Review our previous readings on logic, sets, and quantified logic!

Videos (~20 mins)

Review our previous videos on logic, sets, and quantified logic!

Warmup (~60 mins)

Problem 1

Let \(P(x)\) be some predicate, and let \(D\) be some set. For each of the following statements below, determine whether the deduction is valid for any choice of the set \(D\) and explain why. You don’t have to write a formal mathematical proof, but a sentence or two would be appropriate. If there is some \(D\) for which the deduction is not valid, give an example.

\(\forall x \in D: P(x)\) implies that \(\exists x \in D: P(x)\).
\(\forall x \in D: P(x)\) implies that \((x \in D) \rightarrow P(x)\).
\(\exists x \in D : P(x)\) implies that \(|D| \geq 1\).
\((\forall x \in D: P(x)) \land (y \in D)\) implies that \(P(y)\).

Problem 2

Let \(P(x)\) and \(Q(x)\) be any predicates. Suppose further that you know that \(P(x)\rightarrow Q(x)\). Define the sets: \[ \begin{aligned} A &= \{x \in \mathbb{Z} : P(x)\} \\ B &= \{x \in \mathbb{Z} : Q(x)\} \end{aligned} \]

Use the element method to write a careful proof that \(A \subseteq B\).
Suppose further that \(P(x) \leftrightarrow Q(x)\). Use the element method to prove that \(A = B\).
- Note: to prove that two sets \(A\) and \(B\) are equal, it is sufficient to show that \(A \subseteq B\) and \(B \subseteq A\).

An example of this scenario: let \(P(x)\) be the predicate “\(x\) is a prime number larger than 2” and let \(Q(x)\) be the predicate “\(x\) is an odd number.” We could use your proof structure to show that the set of prime numbers larger than 2 is a subset of the set of odd numbers.

Problem 3

In his letter to a leading Roman agriculturist, the statesman and writer Marcus Tullius Cicero (106 BCE–43BCE) wrote:

If you have a garden and a library, then you have everything you need.

Let \(G\) be the set of all gardens, \(L\) be the set of all libraries, and \(N\) be the set of things that you need. Finally, let \(H(x)\) be the statement that you have \(x\).

Part A

Use quantifiers and logical operators to translate Cicero’s statement into symbols.

Part B

The contrapositive of the statement \(p \rightarrow q\) is the statement \(\lnot q \rightarrow \lnot p\). As you may remember, the contrapositive is logically equivalent to the original implication. Write the contrapositive of your translation from Part A. Simplify your answer so that negation symbols \(\lnot\) appear only directly in front of predicates.