Additional Instructions:

1. You may not define your own propositional operators, predicates, or sets for this problem set. Work with the symbols we have introduced in lecture, and any definitions provided in the questions.

2. You may not use any external facts about these definitions unless they are explicitly stated in the question.However, youmaymake statements about these definitions without proof when they concern only specific integers, e.g., 7 is odd or 13 is prime.

3. You are not required to submit translations of statements youre proving in predicate logic unless we explicitly ask for it. However, if you are doing a disproof, then you must submit a translation of the negation of the statement in predicate logic

1. (12 marks] Number theory. For this question, you may use any of the following definitions or facts without proof. In other words, you may refer to any of these definitions, and any of these facts may appear as a justification for some deduction in your proofs, but do NOT prove these facts as part of your justification. All definitions, facts, and statements proven in worksheets 1-8. Theorem 2.1 (Quotient-Remainder Theorem) from the Course Notes. Fact 1: Vr ER,0 9. (Hint: Try to find a lower bound for (:1 3)2 first.) (c) (4 marks] There exist odd functions g: R + R and h: R+R such that f(x) = g(2) - h(x) is a non-constant even function. (A function f: R+R is constant when 3k ER, VI ER, f(3) = k.) 2. (8 marks] Sets of real numbers. Consider the following predicates, defined for arbitrary sets ST CR: GO(S, T): VIES,VY ET, x >y G1(S,T): Vx E S,Ey E T, x > y G2(ST): 3x S, Vy E T,x > y G3(S, T): 32 SBY ET, x >y (a) [2 marks] For fixed (but arbitrary) non-empty sets S and T, do any of these predicates imply each other? To answer this question, for each predicate, write any true implications for which it can be the hypothesis. For example, you would write Go(S,T) G(S,T)" if G(S,T) was on the list and was true whenever Go(S,T) is true. For each implication you write, explain in 1-3 sentences why the implication is true. (Note: this will require you to consider all 16 possible implications between the four predicates.) (b) [6 marks] Prove or disprove each of the following statements. State clearly whether you are at- tempting a proof or a disproof. Go([3, 5), (0, 2)) GO(R, R) G1(0,1),(0,1)) G2(Z,(-0,0) G2({10}, ), where is the empty set. G3([0, 1] nQ, R Q) 1. (12 marks] Number theory. For this question, you may use any of the following definitions or facts without proof. In other words, you may refer to any of these definitions, and any of these facts may appear as a justification for some deduction in your proofs, but do NOT prove these facts as part of your justification. All definitions, facts, and statements proven in worksheets 1-8. Theorem 2.1 (Quotient-Remainder Theorem) from the Course Notes. Fact 1: Vr ER,0 9. (Hint: Try to find a lower bound for (:1 3)2 first.) (c) (4 marks] There exist odd functions g: R + R and h: R+R such that f(x) = g(2) - h(x) is a non-constant even function. (A function f: R+R is constant when 3k ER, VI ER, f(3) = k.) 2. (8 marks] Sets of real numbers. Consider the following predicates, defined for arbitrary sets ST CR: GO(S, T): VIES,VY ET, x >y G1(S,T): Vx E S,Ey E T, x > y G2(ST): 3x S, Vy E T,x > y G3(S, T): 32 SBY ET, x >y (a) [2 marks] For fixed (but arbitrary) non-empty sets S and T, do any of these predicates imply each other? To answer this question, for each predicate, write any true implications for which it can be the hypothesis. For example, you would write Go(S,T) G(S,T)" if G(S,T) was on the list and was true whenever Go(S,T) is true. For each implication you write, explain in 1-3 sentences why the implication is true. (Note: this will require you to consider all 16 possible implications between the four predicates.) (b) [6 marks] Prove or disprove each of the following statements. State clearly whether you are at- tempting a proof or a disproof. Go([3, 5), (0, 2)) GO(R, R) G1(0,1),(0,1)) G2(Z,(-0,0) G2({10}, ), where is the empty set. G3([0, 1] nQ, R Q)