Throughout, N refers to the set of natural numbers, {1, 2, 3, ...} , Z refers to the set of integers, and R refers to the set of real numbers. The symbol "∋" means "such that". The symbol " ∈" means "is an element of" or "in". Often, I just write "in" rather than " ∈" because "in" is so much easier and quicker to type.

Basic Set Operations

Question 1. Let A = {1, 5, 6, 8, 9}, B = {1, 3, 5, 7, 9}, and C = {2, 3, 4, 5, 6}.

Find each of the following sets. Use set notation with the elements listed { _, _, _, ... }.

(a) A ∩ B

(b) B ∪ C

(c) (A ∩ B) \ C

(d) C \ (A ∩ B)

Question 2. Consider the intervals [6, 9), (5, 8], and [4, 7) of real numbers. (No work required to be shown).

(a) State the union of these three intervals:

(b) State the intersection of these three intervals:

Remarks: Write your answers in interval notation, as simply as possible. To find the answers, it can be helpful to graph the intervals on a number line (no requirement to submit graph).

Question 3. Consider the collection of intervals of real numbers A_k=[-1+ 1/k, 1/k], where k ∈ N.
(No work required to be shown).

(a) State the intervals corresponding to A₁, A₂, and A₃.

(b) State the union of the whole collection of intervals _(k=1)?^∞[A]_k

(c) State the intersection of the whole collection of intervals ?_(k=1)^∞[A]_k

Basic Logic

Question 4. TRUE/FALSE. Determine the truth value of each sentence (no explanation required).

________(a) A statement is a sentence that is true.

________(b) If p is false, then ~p is true.

________(c) In mathematical logic, p ν q refers to the "inclusive or" and is true when either p or q but not both are true.

________(d) The phrase " not both p and q" means "not p and not q".

________(e) The conditional statement p ⇒ q is false if and only if p is true but q is false.

________(f) The negation of ~p ⇒ q is p ⇒ q.

Question 5. Write the negation of each of the following statements in a clearly worded English sentence.

(a) Amy's bus is late or Amy's watch is fast.

(b) If Mike is ill, then Mike stays home from work.

Question 6. Construct a truth table for the statement [~q ^ ( p ⇒ q )] ⇒ ~p Show intermediate steps, with appropriate column headings.

Quantifiers

Question 7. TRUE/FALSE. Determine the truth value of each sentence (no explanation required).

________(c) ∃ n in N ∋ n² = 8.

________(c) ∀x in R, x² ≠ - 4.

________(d) ∀k, m in N, k - m is in N.

________(e) ∀x in R, ∃ k in Z ∋ k ≥ x .

Question 8. For each statement,

(i) write the statement in logical form with appropriate variables and quantifiers,

(ii) write the negation in logical form, and (iii) write the negation in a clearly worded English sentence.

(a) All teachers have college degrees.

(b) Some real numbers are positive.

(c) No women have walked on the moon.

Quantifiers, Counterexamples, Disproof

Question 9. For each statement, decide if the statement is true or false. If false, explain; provide a counterexample as appropriate or a careful explanation. (If true, no explanation expected)

(a) ∀ n in N, 1/n ≤ n.

(b) ∀ nonzero x in R , 1/x ≤ x.

(c) ∀ n in N, 9 + 2ⁿ is prime.

(d) ∃ n in N ∋ ∀ k in N, k ≥ n.

(e) ∀ x, y in R, (x + y)² ≥ x² + y².

(f) ∃ m in Z ∋ ∀ n in Z, m + n is an odd integer.

(g) ∀ m in Z ∃ n in Z ∋ m + n is an odd integer.

Applications of logic; Proofs

Question 10. Write the converse, the inverse, and the contrapositive of the statement If Polly is a parrot, then Polly has feathers.

Definitions: A real number r is rational iff ∃ integers k and n such that r = k/n and n is nonzero. A real number s is irrational iff s is not rational.

Question 11. Consider the following statement:

For all real numbers x and y, if the product xy is irrational, then x is irrational or y is irrational.

(a) Carefully state the contrapositive.

(b) Is the contrapositive true or false? Explain.

Question 12. An eccentric uncle hid a small safe in his house. His family needed to retrieve some important documents from the safe. The uncle gave them a set of clues to the location of the safe (in fact, more clues than needed). Here are the five clues:

If the house is next to a lake, then the safe is in the kitchen.
If the safe is in the garage, then the house is not next to a lake.
If the tree in the front yard is a cherry tree, then the safe is not in the kitchen.
The house is next to a lake or the safe is in the basement.
The tree in the front yard is a cherry tree.

Let L, C, K, G, and B represent the following statements.

L = "The house is next to a lake." C = "The tree in the front yard is a cherry tree."
K = "The safe is in the kitchen." G = "The safe is in the garage."
B = "The safe is in the basement."

(a) Write the five clues as five statements in symbolic form, using symbols ⇒, ∨, ^, ~ as needed.
[Do not overcomplicate matters -- there are no quantifiers involved in this problem.]

(b) Using the clues, what do you conclude? Is the safe in the basement, kitchen, or garage? EXPLAIN carefully how you arrived at your conclusion. (space provided on next page)

Recall the definitions of even, odd, and multiple of a. (These are used in Question 13 and Question 14.)

An integer n is even iff n = 2k for some integer k.

An integer n is odd iff n = 2k + 1 for some integer k.

An integer n is a multiple of a iff n = ak for some integer k. (When a = 2, this is exactly the definition of even.)

Question 13. Prove carefully: For any integers p and q, if p is even and q is odd, then p + 6q - 5 is odd.

Question 14. Claim: For all integers p and q, if their product pq is a multiple of 4, then p and q are even.

Consider the following "proofs" of the claim.

Proof A:

Suppose p and q are integers and pq is a multiple of 4.

By definition of multiple of 4, ∃ integer k such that pq = 4k = (2m)(2n) for some integers m and n.

Then p = 2m and q = 2n for integers m and n.

By definition of even, p and q are even integers.

Proof B:

Suppose p and q are any even integers. By definition of even, ∃ integer k such that p = 2k and q = 2k.

Then pq = (2k)(2k) = 4k². Let m = k2, which is an integer.

Thus, pq = 4m for some integer m, and by definition of multiple, pq is a multiple of 4.

Proof C:

Suppose p and q are any even integers.

By definition of even, ∃ integer k such that p = 2k and ∃ integer n such that q = 2n.

Then pq = (2k)(2n) = 4(kn). Let m = kn, which is an integer.

Thus, pq = 4m for some integer m, and by definition of even, pq is a multiple of 4.

Proof D:

(By contraposition; i.e., proving the contrapositive)

Suppose p and q are any odd integers. We want to show that pq is not a multiple of 4.

By definition of odd, ∃ integer m such that p = 2m + 1 and ∃ integer n such that q = 2n + 1.

Then pq = (2m + 1)(2n + 1) = 4mn + 2m + 2n + 1 = 2(2mn + m + n) + 1.

Let k = 2mn + m + n, which is an integer.

So, pq = 2k + 1 for some integer k, and by definition of odd, pq is odd. Thus pq cannot be even and cannot be a multiple of 4 either.

INSTRUCTIONS:

(a) Critique each proof (A, B, C, D). For each proof, is it a logically valid argument proving the claim? What are the flaws, if any?

(b) Is the Claim true or false? Explain.

Question 15. Fill in the blanks to complete the proof of the following statement:

For all sets A, B, and C, if A ⊆ B and B ∩ C = Φ, then A ∩ C = Φ.

Proof (by contradiction):

Let A, B, and C be any sets.

Suppose ________________ and ______________ but A ∩ C ≠ Φ.

Since A ∩ C ≠ Φ, there exists x  ∈ ___________.

Since x  ∈ A ∩ C, x  ∈ ________ and x  ∈ _______.

Since x  ∈ A and A ⊆ B, we have x  ∈ ______.

Thus x  ∈ B and x  ∈ C, so x  ∈ ____________.

But this contradicts our hypothesis that ____________.

So, we conclude that A and C cannot have any elements in common, that A ∩ C = Φ.