23rd Putnam 1962

Problem B2

Let R be the reals, let N be the set of positive integers, and let P = {X : X ⊆ N}. Find f : R → P such that f(a) ⊂ f(b) (and f(a) ≠ f(b) ) if a < b.



Let Q be the rationals. Define g: Q → N as follows. For m/n where m and n are positive integers without any common factor, let g(m/n) = 2m3n and let g(-m/n) = 2m5n. Now define f: R → P by f(x) = { g(r) : r <= x is rational }. We claim that f has the required property.

Clearly g is injective. Now suppose x < y are reals. We can find a rational r such that x < r < y. So g(r) belongs to f(y) but not to f(x). But S belongs to f(x), then S = g(q) for some q in Q with q < x. So q < y and hence S belongs to f(y) also. So f(x) is a subset of f(y).



23rd Putnam 1962

© John Scholes
5 Feb 2002