Description
(8 points) Problem 2.1.1
Let A be any set. What are the direct products ∅ × A and A × ∅? If x is any thing, what are the direct products A × {x} and {x} × A? Justify your answers.
(10 points) Problem 2.1.5
Let n be a natural and let I(x) be a unary relation on the set {0, . . . , n − 1}. Let w be the binary string of length n that has 1 in position x whenever I(x) is true and 0 in position x when I(x) is false. (As in Java, we consider the positions of the letters in the string to be numbered starting from 0.) What is the string corresponding to the predicate I(x) meaning “x is an even number” in the case where n = 5? The case where n = 8? If w is an arbitrary string and I(x) the corresponding unary predicate, describe the set corresponding to the predicate in terms of w.
(12 points) Problem 2.3.2
Suppose that for any unary predicate P on a particular type T , you know that the proposition (∃x : P (x)) ↔ (∀x : P (x)) is true. What does this tell you about T ? Justify your answer – state a property of T and explain why this proposition is always true if T has your property, and not always true if T does not have your property.
(12 points) Problem 2.5.6
Suppose that A is a language such that λ ∈/ A. Let w be a string of length k. Show that there exists a natural i such that for every natural j > i, every string in Aj is longer than k. Explain how this fact can be used to decide whether w is in A∗.
(14 points) Problem 2.6.3
Heinlein’s second puzzle has the same form as in Problem 2.6.2. Here you get to figure out what the intended conclusion is to be, and prove it as above:
-
Everything, not absolutely ugly, may be kept in a drawing room;
-
Nothing, that is encrusted with salt, is ever quite dry;
-
Nothing should be kept in a drawing room, unless it is free from damp;
-
Time-traveling machines are always kept near the sea;
-
Nothing, that is what you expect it to be, can be absolutely ugly;
-
Whatever is kept near the sea gets encrusted with salt.
(10 points) Problem 2.8.1
Let A = {1, 2} and B = {x, y}. There are exactly sixteen different possible relations from A to B. List them. How many are total? How many are well-defined? How many are functions? How many are neither well-defined nor total?
(10 points) Problem 2.9.3
Let f : A → B and g : B → C be functions such that g ◦ f is a bijection. Prove that f must be one-to-one and that g must be onto. Give an example showing that it is possible for neither f nor g to be a bijection.
(12 points) Problem 2.9.7
Let A be a set and f a bijection from A to itself. We say that f fixes an element x of A if f(x) = x.
-
Write a quantified statement, with variables ranging over A, that says “there is exactly one element of A that f does not fix.”
-
Prove that if A has more than one element, the statement of part (a) leads to a contra-diction. That is, if f does not fix x, and there is another element in A besides x, then there is some other element that f does not fix.
(12 points) Problem 3.1.7
A Perfect number is a natural that is the sum of all its proper divisors. For example, 6 = 1 + 2 + 3 and 28 = 1 + 2 + 4 + 7 + 14. Prove that if 2n − 1 is prime, then (2n − 1)2n−1 is a perfect number. (A prime of the form 2n − 1 is called a Mersenne prime. Every perfect number known is of the form given here, but it is unknown whether there are any others.)
Extra credit:
(10 points) Problem 2.10.6
There is only one partial order possible on the set {a}, because R(a, a) must be true. On the set {a, b}, there are three possible partial orders, as R(a, a) and R(b, b) must both be true and either zero or one of R(a, b) and R(b, a) can be true. List all the possible partial orders on the set {a, b, c}. (Hint: There are nineteen of them.) How many are linear orders?
3
