MATH 582, INTRODUCTION TO SET THEORY, WINTER 1999

Answers to the First Midterm

Problem 1 To prove the left-to-right implication, assume that f : A → B is onto, and suppose g, h : B → X are functions such that g ∘ f = h ∘ f. We have to show that g = h. So consider any b ∈ B. Since f is onto, there exists some a ∈ A with f(a) = b. Therefore, g(b) = g(f(a)) = h(f(a)) = h(b). Since b was arbitrary, this implies g = h.

To prove the other implication, assume that f : A → B is not onto. It suffices to find a set X and two functions g, h : B → X such that g ∘ f = h ∘ f, but g ≠ h. Since f is not onto, there is some b ∈ B that is not in the range of f. Let X = {0, 1}, and define g, h : B → X by

g(x) = 0, for all x ∈ B,
f(x) = \{ \begin{matrix}0,  for x ≠ b, \\ 1,  for x = b. \end{matrix}

Then for all a ∈ A, f(a) ≠ b and thus g(f(a)) = h(f(a)) = 0, which implies g ∘ f = h ∘ f. On the other hand, g(b) = 0 ≠ 1 = h(b), thus g ≠ h.

Problem 2

(a) The requirement f(n^{+}) = n^{+} · f(n) is not of the form f(n^{+}) = F (f(n)), because the right-hand-side not only depends on f(n), but also on n. Thus, the recursion theorem, as stated, does not directly apply here.

(b) Define a function F : ω × ω → ω × ω by F (⟨n, k⟩) = ⟨n^{+}, n^{+} · k⟩. Then by the Recursion Theorem, there exists a unique function h : ω → ω × ω such that

\begin{matrix}h(0) = ⟨0, 1⟩, \\ h(n^{+}) = F (h(n)). \end{matrix}

Now let i : ω → ω and f : ω → ω be the unique functions such that ⟨i(n), f(n)⟩ = h(n) for all n ∈ ω. We claim that i(n) = n for all n, and that f is a factorial function. This is proved by induction on n. For the base case, we calculate ⟨i(0), f(0)⟩ = h(0) = ⟨0, 1⟩, thus i(0) = 0 and f(0) = 1. For the induction step, assume that i(n) = n. Then ⟨i(n^{+}), f(n^{+})⟩ = h(n^{+}) = F (h(n)) = F (⟨n, f(n)⟩) = ⟨n^{+}, n^{+} · f(n)⟩, thus i(n^{+}) = n^{+} and f(n^{+}) = n^{+} · f(n).

(c) Assume that f and f′ are factorial functions. We prove by induction on n that f(n) = f′(n) for all n ∈ ω. The base case: f(0) = 1 = f′(0). The induction step: f(n) = f′(n) implies n^{+} · f(n) = n^{+} · f′(n) implies f(n^{+}) = f′(n^{+}).

Problem 3 The axioms of Union, Power Set, and Infinity fail; all the others are true in this “universe”.

Problem 4 Reflexivity: For all x ∈ A, xRx, and thus x(R ∪ Q)x. Symmetry: Suppose x(R ∪ Q)y. Then either xRy or xQy. In the first case yRx by symmetry of R; in the second case, yQx by symmetry of Q. In any case, y(R ∪ Q)x. Transitivity: Suppose x(R ∪ Q)y and y(R ∪ Q)z. It suffices to show that xRz or xQz. If xRy and yRz, then this follows by transitivity of R, and similarly if xQy and yQz. Thus, without loss of generality, we may assume that xRy and yQz (the symmetric case where xQy and yRz is handled similarly). By hypothesis, we know that either [y]_{R} ⊆ [y]_{Q} or [y]_{Q} ⊆ [y]_{R}. In the first case, since x ∈ [y]_{R} ⊆ [y]_{Q}, we have xQy, and with yQz, this implies xQz by transitivity of Q. In the second case, since z ∈ [y]_{Q} ⊆ [y]_{R}, we have yRz, and thus xRz by transitivity of R. In all cases, we have proved x(R ∪ Q)z, and thus transitivity of R ∪ Q follows.