5
$\begingroup$

The following question was asked in a comment by Joel David Hamkins in Graph on the set of all functions $f:\mathbb{N}\to\mathbb{N}$.

Let $V$ be the set of all functions $f:\mathbb{N}\to\mathbb{N}$. Let $$E:=\big\{\{f,g\}: f, g \in V \land f\neq g\land \exists k\in \mathbb{N} \text{ }\forall n\in\mathbb{N}\setminus\{k\} (f(n) = g(n))\big\}.$$

Let $G=(V,E)$. This graph is Borel. Can there be a Borel $\mathbb{N}$-coloring?

$\endgroup$
10
$\begingroup$

I claim that there can be no Borel $\mathbb{N}$-coloring of this graph.

To see this, suppose toward contradiction that there is such a Borel coloring. Consider the forcing to add a generic Cohen real, in the form of a function $g:\mathbb{N}\to\mathbb{N}$. So the forcing conditions are finite partial functions from $\mathbb{N}\to\mathbb{N}$, ordered by extension. Since the coloring has a Borel code, we may interpret this code in the forcing extension $V[g]$ (where I use $V$ here as usual to denote the original set-theoretic universe, rather than your use to denote the underlying set of the graph $\mathbb{N}^{\mathbb{N}}$). Furthermore, the interpretation of that coloring is still a coloring of the corresponding graph as defined in the forcing extension $V[g]$, since the assertion that a given Borel code codes a coloring for that graph is a $\Pi^1_1$ assertion and hence absolute between the universe $V$ and the forcing extension $V[g]$. So the generic function $g$ gets some color, say $k$. This fact must be forced by some finite piece of the generic function $p=g\upharpoonright n$. That is, condition $p$ forces that the generic function gets color $k$. But now let us modify $g$ to form a new function $g'$ by making a single change beyond $p$. So $g'$ is also generic, and furthermore extends $p$, and the corresponding forcing extensions are the same $V[g]=V[g']$. It follows that $g'$ must also get color $k$, since this was forced by $p$, and this contradicts the fact that $g$ and $g'$ are adjacent in the graph. So there can be no such coloring. QED

This argument is similar to an argument showing that almost-equality has no Borel selector, and a similar idea appears in [this MO question}(https://mathoverflow.net/a/47191/1946) concerning the non-existence of a Borel diagonalization against countable sets of reals.

$\endgroup$
2
  • $\begingroup$ Since you mentioned absoluteness of the property that a real codes a Borel coloring, it seems appropriate to mention that you also use, at the end of the proof, the absoluteness of the property that changing one value of a function changes its color. $\endgroup$ – Andreas Blass May 22 '15 at 20:57
  • 1
    $\begingroup$ Yes, I agree, although actually that is part of what I meant when I said that it is a coloring of that graph, so that adjacent vertices get different colors. $\endgroup$ – Joel David Hamkins May 22 '15 at 22:27
9
$\begingroup$

No. Otherwise there is a Borel non meager set $B$ such that for every $k$, $B + e_k$ is disjoint with $B$. $B$ is comeager in some basic clopen set $C$. Choose $k$ larger than the support of $C$, then $B, B + e_k$ are both comeager in $C$. Contradiction.

$\endgroup$
2
  • 1
    $\begingroup$ +1 Very nice. Despite first appearances, this answer and mine are actually rather close, using the same underlying idea, and one can view this as an instance of the connection of Cohen genericity with comeager sets: a function is $V$-generic just in case it is in every ground-model comeager set. So the clopen set here corresponds to the condition $p$ in my answer, with $B$ the set of functions having the color that $g$ gets, and $B+e_k$ corresponds to my argument with $g'$, which made a change to $g$ outside $p$. $\endgroup$ – Joel David Hamkins May 21 '15 at 16:26
  • 1
    $\begingroup$ But meanwhile, of course, the forcing-free proof is obviously easier to grasp for those who don't know forcing! I think of the situation as analogous to the difference in perspective between using non-standard analysis and arguing with actual nonstandard infinitesimals versus arguing with epsilons and deltas and sets in an ultrafilter. Sometimes it is clarifying to have the actual infinitesimal or the actual generic object, even in cases where the need for it is eliminable. $\endgroup$ – Joel David Hamkins May 21 '15 at 21:32
5
$\begingroup$

It's worth pointing out that in the context of Borel chromatic numbers, there is a canonical reason for a graph to not have countable chromatic number. Kechris, Solecki, and Todorcevic showed that there is a graph $\mathcal G_0$ such that a Borel graph $\mathcal G$ has $\chi_B(\mathcal G)\leq \aleph_0$ iff there is no continuous (graph) homomorphism from $\mathcal G_0$ to $\mathcal G$.

Proving $\mathcal G_0$ has uncountable Borel chromatic number normally goes via a simple category argument such as in Guest's answer, but as Joel pointed out, this can be seen through a forcing lens if you like. Proving the dichotomy is normally done using the Gandy-Harrington topology on $2^\mathbb{N}$ (part of an area known as effective descriptive set theory), which doesn't quite admit category arguments. However, the topology is what's known as strong Choquet (a property based on a certain infinite game), which allows one to carry out something very similar to category arguments. (It assures you that certain intersections of nonempty open sets are nonempty.) And of course one can talk instead about the Gandy-Harrington forcing. More recently, Ben Miller wrote a proof of the $\mathcal G_0$-dichotomy which doesn't use effective descriptive set theory or forcing.

As for $\mathcal G_0$ itself, here's a definition. Fix a sequence $(t_n)$ of binary sequences such that $|t_n|=n$ and the sequence is dense, meaning for any binary sequence $t$ there is some $n$ such that $t_n$ extends $t$. (In other words, the basic open sets of $2^\mathbb{N}$ defined by the $t_n$ intersect every open set of $2^\mathbb{N}$.) Then define $\mathcal G_0$ on $2^\mathbb{N}$ by

$$ x \mathcal G_0 y \Leftrightarrow \exists n [x\restriction n = y\restriction n = t_n \text{ and } x(n)=1-y(n) \text{ and } \forall m>n (x(m)=y(m)) ]$$

I'll note that this is clearly very similar to the graph $G$ in the question, and leave it as an exercise to find a homomorphism from $\mathcal G_0$ to $G$. I'll also note that while the definition of $\mathcal G_0$ does depend on your choice of $(t_n)$, the KST dichotomy (actually, a slight strengthening of it also due to KST) assures us that any two versions are homeomorphic to subgraphs of each other.

I highly recommend reading the Kechris-Solecki-Todorcevic paper if you have any interest in this topic. Not only is it the first systematic look at Borel chromatic numbers, it is very readable. If you'd prefer something more up-to-date, Kechris and Marks have a survey on Borel combinatorics coming soon. The preprint is available on either of their websites.

$\endgroup$
1
  • 1
    $\begingroup$ I meant to also point out that the connected components of $\mathcal G_0$ are precisely the equivalence classes of almost-equality on $2^\mathbb{N}$, so the connection that Joel noted there is not coincidental. $\endgroup$ – Jay Williams May 22 '15 at 18:30

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.