It is well known that one can represent sets as digraphs. What is the proper digraph representation of $\mathscr P$($\omega$)? I ask this because $\mathscr P$($\omega$) is $\Pi_1$ in the Levy hierarchy and this is taken to mean that the value of |$\mathscr P$($\omega$)|, say, is not absolute, that is, it can change relative to the model of ZFC it is found in.

What does this mean, relative to $\mathscr P$($\omega$)'s representation as a digraph? It would seem that, if one takes the relativity of |$\mathscr P$($\omega$)| seriously, it would mean that $\mathscr P$($\omega$) is to be represented by a proper class of graphs ($\mathscr P$($\omega$) could not represent a set of such graphs, otherwise that set would itself be representable by a digraph, and a form of the Burali-Forti paradox would ensue) each element of the proper class formed by an addition of, say, a Cohen real to the previously formed digraph.

On the other hand, because each digraph representation of $\mathscr P$($ \omega$) for some model $\mathfrak M$ (where $\mathfrak M$ is a (proper) class of digraphs satisfying the graph-theoretical analogues of the ZFC axioms, if such exist....) is a unique mathematical object, it would seem that each digraph representing $\mathscr P$($\omega$) is an incomplete object because one can add (by a ccc forcing) to any $\mathscr P$($\omega$) in some model $\mathfrak M$ a Cohen real creating the forcing extension $\mathfrak M$[G] of $\mathfrak M$. Taking the digraph perspective of this situation, it would seem that an infinite digraph representing $\mathscr P$($\omega$) is determined in some sense by the class of digraphs $\mathfrak M$ in which it lies. If this is false, then it would seem that each digraph representation of $\mathscr P$($\omega$) is, in fact, incomplete. Is this a correct rendering of the situation?


In each model of set theory, there is a concrete set that is $\mathcal P(\omega)$, and this set can, if one wants, be represented as a directed graph.

Two different models will, in general, have their own $\mathcal P(\omega)$ sets, and each of these sets will have a graph representation. It is not the intention that there should be a single thing that, at once, represents the $\mathcal P(\omega)$s of every model graphically.

It is not fruitful to think of "$\mathcal P(\omega)$" as a single Platonic thing with different manifestations in different models. Rather, "being $\mathcal P(\omega)$" is merely a property an object in a model can have -- and incidentally the axioms of set theory imply that exactly one object in each model will have this property -- but it is the individual objects in particular models that have graph representations, not the property as such.

(If you want, you can say that there is a single Platonic $\mathcal P(\omega)$, namely the one in the "intended interpretation" of set theory, whatever that might mean. But even so, that "true" $\mathcal P(\omega)$ is just one set, and has nothing in particular to do with the $\mathcal P(\omega)$s that exist in other non-standard models of the axioms).

| cite | improve this answer | |
  • $\begingroup$ I don't think of $\mathscr P$($\omega$) as "a single Platonic thing with different manifestations in different models", rather, I think of $\mathscr P$($\omega$) as the proper class of all digraph representations of $\mathscr P$($\omega$) in the ground model $\mathtt L$ and all successive ccc-forcing extensions $\mathtt L$[G] formed by adding a Cohen real. The question is, for the digraph representation of $\mathscr P$($\omega$)$\cap$$\mathtt L$, what is the digraph representation for 'adding a Cohen real'? $\endgroup$ – Thomas Benjamin Nov 21 '14 at 8:01
  • $\begingroup$ That is, what are you adding to the digraph representation of $\mathscr P$($\omega$)$\cap$$\mathtt L$ to make it a digraph representation of $\mathscr P$($\omega$)$\cap$$\mathtt L$[G] where G is the generic filter for adding one Cohen real? $\endgroup$ – Thomas Benjamin Nov 21 '14 at 8:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.