[FOM] A "clear understanding" of P(N)

[Todd Wilson]

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