# [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
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

```