University of Toronto CSC240 Midterm Test
Monday, March 2, 2020
11:10 am – 1pm
aids allowed: one 8.5”x11” single-sided aid sheet (one side must be blank)
1. [5] For which real numbers a ∈ R is the following formula true? ∃b ∈ R. ∀c ∈ R. abc = c
Don’t just translate every symbol into English: you must understand the formula. For example, the following answer would be worth 0 marks: “The formula is true if there exists a real number b such that for all real numbers c, abc = c”.
2. [10] Consider the following predicate logic formula: ∀x∈D.P(x)IFF∀y∈D. NOT(NOT(P(y)))
Is it is valid, unsatisfiable, or satisfiable but not valid? If it is valid or unsatisfiable, briefly explain why. If it is satisfiable but not valid, give an interpretation making it true and an interpretation making it false.
(Remember that the domain of an interpretation must be nonempty.)
3. [15] Let T ⊆ R be the smallest set of numbers such that:
• Base case: 1 ∈ T.
• Constructor cases: if x ∈ T , then 2 ∈ T and x + 1 ∈ T .
Prove ∀x ∈ T. x ≥ 1.
4. [20] Definitions for this question:
• For a finite subset of the natural numbers S ⊆ N, S is the sum of the elements of S. For example, {0,4,10} = 14. If S = φ, then S = 0.
• GivenasetA⊆Nandanumbers∈NsuchthatA≥s,asetB⊆Aisa“justbigenough subset of A to reach s” if both of the following properties are true:
(i) B ≥ s
(ii) ∀x ∈ B. ( B) − x < s
Prove that for every finite subset of the natural numbers A ⊆ N, and every s ∈ N, there exists a set B which is a “just big enough subset of A to reach s”.
Your proof should either use induction or the fact that ≤ is a well-ordering on N. Notes:
• If you like, you can use this fact about finite sets without proof: if A is finite, then there is some n ∈ N such that |A| = n.
• The “finite” part isn’t actually needed. If we replace “every finite subset” with “every subset”, the statement is still true (define A = ∞ when A is infinite). But it’s written as “every finite subset” here in case you find that useful in your proof.
5. [20] Suppose (A ⊆ R) is a set of real numbers with the following property: every nonempty subset of A has a smallest element and a largest element. (These will be the same element for subsets of size 1.)
Prove that the number of elements in A is finite.
(Two facts that might help: the empty set contains a finite number of elements, and if S contains a finite number of elements and x ∈ R, then S ∪ {x} contains a finite number of elements. You can use these facts without proof.)
x2
1