6
$\begingroup$

Let $\kappa\le 2^{\aleph_0}$ be an infinite cardinal. We have a collection of functions $\{f_i|i<\kappa\}$ such that $f_i:i\rightarrow \omega$ and the collection is "triangle-free", i.e. there are not $i<j<k<\kappa$ such that $$f_j(i)=f_k(i)=f_k(j).$$

Is it always possible to extend this collection by adding one more function $f_\kappa:\kappa\rightarrow\omega$ so that the collection $\{f_i|i\le\kappa\}$ remains triangle-free?

$\endgroup$
10
  • $\begingroup$ Do you have an example of a triangle-free family when $\kappa$ is uncountable? $\endgroup$ Feb 19, 2016 at 20:29
  • $\begingroup$ For $\kappa$ countable it is very easy to cook up an example. Just make every $f_i$ constantly equal to some $n_i$ and $n_i\neq n_j$ for $i\neq j$. $\endgroup$ Feb 19, 2016 at 21:27
  • $\begingroup$ I just saw that you mentioned uncountable $\kappa$. There are examples where $\kappa$ is uncountable too. $\endgroup$ Feb 19, 2016 at 21:30
  • $\begingroup$ Here is an example: Let $\kappa=2^{\aleph_0}=P(\omega)$. Each element of $\kappa$ codes a subset of $\omega$. Let $f_j(i)$ be the least $n\in\omega$ that belongs to $j$ but does not belong to $i$. If $f_j(i)=f_k(i)=n$, then $n$ belongs both to $j,k$, but not to $i$. Then $f_k(j)$ can not be equal to $n$, and the collection is trangle-free. $\endgroup$ Feb 19, 2016 at 21:35
  • 1
    $\begingroup$ You have to take an antichain of subsets of $\omega$ which has size $2^{\aleph_0}$ and $j\subset i$ never happens. $\endgroup$ Feb 19, 2016 at 21:56

1 Answer 1

4
$\begingroup$

No, it is not always possible.

I find it helpful to translate the problem slightly. Note that, if $\alpha$ is an ordinal (not necessarily $\leq 2^{\aleph_0}$), a sequence of functions $\langle f_i \mid i < \alpha \rangle$ as specified is the same as a single function $f:[\alpha]^2 \rightarrow \omega$ (where $[\alpha]^2$ is the set of 2-element subsets of $\alpha$), and the requirement that $\langle f_i \mid i < \alpha \rangle$ is triangle-free precisely the same as requiring $f$ to be triangle-free (i.e. there is no $i < j < k < \alpha$ such that $f(\{i,j\}) = f(\{i,k\}) = f(\{j,k\})$).

Suppose that, for every $\alpha < (2^{\aleph_0})^+$ and every triangle-free coloring $f:[\alpha]^2 \rightarrow \omega$, $f$ can be extended to a triangle-free coloring $g:[\alpha+1]^2 \rightarrow \omega$ with $g \restriction [\alpha]^2 = f$. Then we can recursively build a sequence $\langle g_\alpha \mid \alpha < (2^{\aleph_0})^+ \rangle$ such that $g_\alpha:[\alpha]^2 \rightarrow \omega$ and, for $\alpha < \beta$, $g_\beta$ extends $g_\alpha$. Then, letting $g = \bigcup_{\alpha < (2^{\aleph_0})^+}g_\alpha$, we have that $g:[(2^{\aleph_0})^+]^2 \rightarrow \omega$ is a triangle-free coloring, contradicting the Erdos-Rado theorem. There thus must be some $\alpha < (2^{\aleph_0})^+$ and $f:[\alpha]^2 \rightarrow \omega$ such that $f$ is triangle-free and cannot be extended to a triangle-free coloring with domain $[\alpha+1]^2$. Taking a bijection between $\alpha$ and its cardinality, we can assume $f$ is actually a triangle-free coloring $f:[\kappa]^2 \rightarrow \omega$ that cannot be extended to a triangle-free coloring on $[\kappa+1]^2$, where $\kappa \leq 2^{\aleph_0}$ is a cardinal. Translating back to your formulation, we get $\langle f_i \mid i < \kappa \rangle$ by letting, for $i < j < \kappa$, $f_j(i) = f(\{i,j\})$. This sequence cannot be extended by a function $f_\kappa$.

As a side note, there is a very natural triangle-free coloring of size continuum that cannot be extended. Let ${^\omega}2$ denote the set of functions $F:\omega \rightarrow 2$, and define $f:[{^\omega}2]^2 \rightarrow \omega$ by letting $f(F,G)$ be the least $n$ such that $F(n) \neq G(n)$. $f$ is obviously triangle-free, and there's a nice argument showing that it cannot be extended.

$\endgroup$
8
  • $\begingroup$ Thank you for the answer. Although it does not follow from your argument, it seems to me that any counterexample will have size continuum. Can you think of any counterexample of size less than continuum that can not be extended? $\endgroup$ Feb 23, 2016 at 13:47
  • 1
    $\begingroup$ @IoannisSouldatos: I was thinking about this problem a bit yesterday, and it seems to me that you can get an example of size $\aleph_1$ after adding lots of Cohen reals (as many as you like). $\endgroup$
    – Will Brian
    Feb 23, 2016 at 14:32
  • $\begingroup$ @WillBrian: This is what I understand. Start with a model of CH. There is an example of size continuum that can not extend. Then use Cohen forcing to blow up continuum. Since continuum equals $\aleph_1$ in the ground model and cardinals are preserved, you get a function of size $\aleph_1$ in the extension that does not extend. Since $\aleph_1$ is less than continuum in the extension, we get the result. $\endgroup$ Feb 23, 2016 at 15:30
  • $\begingroup$ @IoannisSouldatos: That's not quite what I had in mind, and I don't think it's that simple. To see why, consider Chris's example. If $V$ satisfies CH, then his example has size $\aleph_1$ and cannot extend (in $V$). But if we blow up the continuum by forcing, then in the forcing extension $V[G]$, the example does extend. This is because we've created new subsets of $\omega$: if $X$ is a subset of $\omega$ in $V[G]$ but not in $V$, then we can add $X$ as a new vertex to Chris's example (which only uses sets in $V$), and we can color the edges from $X$ according to the same rule . . . $\endgroup$
    – Will Brian
    Feb 23, 2016 at 16:13
  • 1
    $\begingroup$ @IoannisSouldatos: I take it back. I sat down this morning to write out my forcing argument, only to find that my plan did not quite work. I don't see how to force an example smaller than the continuum, but for what it's worth I think this is probably due to my lack of skill with forcing: it seems to me that such a thing should be possible. $\endgroup$
    – Will Brian
    Feb 25, 2016 at 16:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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