[FOM] A "clear understanding" of P(N)
Todd Wilson
twilson at csufresno.edu
Fri Feb 24 12:07:17 EST 2006
Martin Davis wrote:
> I personally regard the marks on paper as a very fragile reed indeed,
> but on the other hand have convinced myself that I have a very clear
> understanding of P(N).
It is true that the elements of P(N) can be pictured in a number of
simple and appealing ways, and that these pictures lend themselves to
answering basic questions about the associated elements. For example, I
can picture an element of P(N) as a sequence of bits
b_0 b_1 b_2 b_3 ... (b_i in {0,1}),
with the associated set being { i | b_i = 1 }, and can imagine unions
and intersections as bitwise ORs and ANDs, etc. This perspective also
gives me a way to survey the whole of P(N), since I can imagine the
"space" of all such bit strings, and this may lead me to say that I have
a very clear understanding of P(N).
But I think this would be misleading. Elements of P(N) can be
determined by separation from N by formulas of arbitrary complexity,
involving as parameters not only P(N) itself, but much more complicated
sets, and this can lead, via coding, to structures of enormous
complexity living "within" P(N). To take one example, we can use a
standard pairing operation
<_,_> : N x N -> N
on the natural numbers to code binary relations on N as elements of
P(N). Some of these binary relations will be well-orderings, and
isomorphisms between these well-orderings are partial functions f : N ->
N, which are also sets of ordered pairs on N and hence can be coded as
elements of P(N). Using AC, we can choose one well-ordering from each
equivalence class and obtain a subset CO of P(N) that codes the
countable ordinals, with a definable ordering relation. Determining the
cardinality of this set CO is the Continuum Problem.
My point in rehearsing these well-known considerations is to illustrate
that, even though P(N) has an intuitively clear "surface structure", its
set-theoretic significance goes far beyond what these basic pictures
reveal, and to say that these pictures give us a "very clear
understanding" of P(N) is analogous to saying that the simple definition
of a Turing machine gives us a very clear understanding of the set of
computable functions, or that an understanding of ink and paper gives us
a similarly clear understanding of everything that might be printed
using them.
--
Todd Wilson A smile is not an individual
Computer Science Department product; it is a co-product.
California State University, Fresno -- Thich Nhat Hanh
More information about the FOM
mailing list