# Universal locally countable partial order

Call a poset locally countable if the set of predecessors of every member of the poset is countable. Is the following consistent?

There is no locally countable poset $$P$$ of size continuum such that every locally countable poset of size continuum embeds into $$P$$?

Remark: under ZFC+CH, there is such a universal locally countable poset: the Turing degrees. This is due to Sacks.

• Out of curiosity, is the negation of this (i.e., the affirmative: there exists such universal $P$) consistent?
– YCor
May 28, 2019 at 15:58
• Yes. Under CH, the Turing degrees witness this. This is due to Sacks. May 28, 2019 at 16:20
• Do you want them to embed as initial segments? May 28, 2019 at 20:27

The answer to this question, at least in ZFC, is "no." It is provable in ZFC that there is a universal locally countable partial order of size continuum. In other words, it is provable in ZFC that there is a locally countable partial order of size continuum into which every other such partial order embeds. This is true even if the embedding is required to be an initial segment embedding. I'm not sure what happens in ZF though.

I will describe a locally countable partial order of size continuum and show that every locally countable partial order of size continuum has an initial segment embedding into it. (Edited to add: This example has been known for a while but I'm not sure if it's written up anywhere. As pointed out in a comment below, it is mentioned in the paper "Independence Results from ZFC in Computability Theory: Some Open Problems" by Marcia Groszek.)

Definition of the partial order: The partial order (one of several that works) is basically the "hereditarily a column of" partial order on reals. For convenience (and to make sure we can actually get an initial segment embedding), I will actually use a slight variation on this partial order.

To define the partial order, first pick your favorite bijection $$f \colon \omega\times \omega \to \omega$$. This lets us think of subsets of $$\omega$$ as being subsets of $$\omega \times \omega$$ and justifies us when we talk about the "columns" of a real $$x \in 2^\omega$$: the $$n^\text{th}$$ column of $$x$$ is the set $$\{m \mid f(n, m) \in x\} \subseteq \omega$$. It will be convenient for us to assume that $$f$$ has the property that for all $$(n, m)$$, $$m < f(n, m)$$ (which is easy to arrange). We will also assume that $$f(0, 0) = 0$$.

Next, define the "is a column of" relation, $$<_{col}$$ on $$2^\omega$$. This is the relation such that $$x <_{col} y$$ holds if there is some $$n$$ such that $$x$$ is the $$n^\text{th}$$ column of $$y$$. We will modify this in two ways: first, we'll require that $$n > 0$$. So we basically ignore column $$0$$ of $$y$$ when deciding if $$x$$ is a column of $$y$$. Second, we will not call $$x$$ a column of $$y$$ if $$x$$ is the empty set (i.e. the all zeros binary sequence). This basically gives us a way to ignore columns, so we can have reals which have no columns (or rather, reals which we pretend have no columns).

Now define the "hereditarily a column of" partial order, $$<_{hcol}$$, to be the transitive closure of $$<_{col}$$. In other words $$x <_{hcol} y$$ if there is a sequence $$x = x_0 <_{col} x_1 <_{col} \ldots <_{col} x_k = y$$. There is one problem: this relation is not necessarily irreflexive. We can fix this by simply deleting all elements $$x$$ such that $$x <_{hcol} x$$ (note that this means we automatically will ignore the all zeros sequence, so we didn't really need to specify that in the previous step). Let's call the resulting partial order $$(P, <_{hcol})$$.

This partial order is locally countable because it is a subset of the transitive closure of a binary relation with countable sections (namely, $$<_{col}$$). Hopefully it is obvious that it has size continuum.

Initial segment embedding: Let $$(Q, <_Q)$$ be a locally countable partial order of size continuum. We will show how to embed $$Q$$ as an initial segment of $$P$$.

First, let $$g \colon Q \to 2^\omega$$ be an injection (which we can find because $$Q$$ has size continuum). Also, for each element $$x$$ of $$Q$$, pick an enumeration of its predecessors in $$Q$$, $$x_1,x_2,\ldots$$ (this is the only part where we need to use choice). Now define the embedding $$\psi : Q \to P$$ as follows. For each $$x$$, let $$\psi(x)$$ be the real whose $$0^\text{th}$$ column is $$g(x)$$ and whose $$n^\text{th}$$ column is $$\psi(x_n)$$ (recall that $$x_n$$ is the $$n^\text{th}$$ predecessor of $$x$$ in $$Q$$). If $$x$$ has only finitely many predecessors then fill the remaining columns with all zeros.

This definition of $$\psi$$ probably looks circular. It's actually not! The point is that to decide the $$f(n, m)^\text{th}$$ bit of $$\psi(x)$$ we need to know the $$m^\text{th}$$ bit of $$\psi(x_n)$$. Since $$m < f(n, m)$$, this process is actually well-defined.

Here's another way to think about the definition of $$\psi$$. Imagine that every $$\psi(x)$$ is initially a sequence of blanks (rather than a binary sequence). We will fill in these blanks in a series of steps. In the first step, we fill in the bits in column $$0$$ of each $$\psi(x)$$, as well as the bits of columns that are supposed to be all zeros. In each subsequent step, we look at each pair $$x <_Q y$$ and fill in bits of $$y$$ corresponding to bits of $$x$$ that were filled in on the previous step. One can show by induction (using the special properties of $$f$$ that we assumed) that by the end of step $$n$$, the $$n^\text{th}$$ bit of every $$\psi(x)$$ has been filled in.

Note first that $$\psi$$ is an injective map from $$Q$$ into $$2^\omega$$ (because $$g$$ is injective and column $$0$$ of $$\psi(x)$$ is $$g(x)$$). Next, the columns of $$\psi(x)$$ are exactly the images of the predecessors of $$x$$ (except for the special column $$0$$ and the all zeros columns, both of which are ignored in the definition of $$<_{col}$$). This also shows that the "hereditary columns" of $$\psi(x)$$ are exactly the images of the predecessors of $$x$$. Since $$\psi$$ is injective, this shows that we never have $$\psi(x) <_{hcol} \psi(x)$$ and thus the image of $$\psi$$ actually lands in the partial order $$P$$. It also shows that $$\psi$$ is truly an initial segment embedding of $$Q$$ into $$P$$.

Note: I believe the arithmetic degrees are also a universal locally countable partial order of size continuum but I don't think it's written up anywhere. The proof is an amalgamation of the proof I gave above and the counterexample to Martin's conjecture on the arithmetic degrees proved by Slaman and Steel and written up in this paper. I'm not sure if you can always get an initial segment embedding into the arithmetic degrees though.

• Thanks. This example also appears here (page 175): ams.org/books/conm/257/4033/conm257-4033.pdf Feb 7, 2021 at 10:26
• Yeah, I think this example is reasonably well-known (and I did not come up with it myself, to be clear). One interesting point is that the proof I give above actually shows that locally countable Borel partial orders can be Borel embedded into the "hereditarily a column of" partial order. The one use of choice can be done in the Borel context by the Lusin-Novikov theorem. Feb 7, 2021 at 17:03