# Independent families of functions on $\omega$ of size continuum

In Hausdorff's article "Über zwei Sätze von G. Fichtenholz und L. Kantorovich''(1935) one can find the (simplified) proofs of the following two theorems:

1) There are continuum many essentially different functions (in the original version they are called wesentlich verschieden) from $\omega$ to $\omega$: i.e. there is some $H \subseteq {^\omega \omega}$ such that $|H|=2^{\aleph_0}$ and for every finitely many different $f_0, \dots, f_l \in H$ there is a position $a \in \omega$ such that $f_i(a) \neq f_j(a)$ for $i<j \leq l$.

2) There is an independent family of subsets of $\omega$ of size continuum: i.e. there is a family $F \subseteq P_{=\omega}(\omega)$, of infinite subsets of $\omega$, such that $|F|=2^{\aleph_0}$ and for every finitely many pairwise different $x_1, \dots, x_l, y_1, \dots, y_m \in F$ the intersection $x_1 \cap \dots \cap x_l \cap (\omega \setminus y_1) \cap \dots \cap (\omega \setminus y_m)$ is infinite.

I found in Blass and Irwin's paper "Special families of sets and Baer-Specker Groups" that

3) There is an independent family of functions on $\omega$ of size continuum: i.e. there is a family $G \subseteq {^\omega}{\omega}$, such that $|G|=2^{\aleph_0}$ and for every pairwise different $f_0, \dots, f_l \in G$ and every (not necessarily distinct) $n_0, \dots, n_l \in \omega$ there is some $a \in \omega$ such that $f_0(a)=n_0, f_1(a)=n_1, \dots, f_l(a)=n_l.$

Blass writes that the proof of 3) is generated by 1) or 2). I cannot see it and I can't find any explicit proof of 3). So I tried (apparently without using directly points 1) and 2)) to find a function $G: 2^{\aleph_0} \times \omega \rightarrow \omega$ such that for every finitely many $(\alpha_0,n_0), \dots, (\alpha_i,n_i) \in 2^{\aleph_0} \times \omega$ with different first coordinates, there is some $k \in \omega$ such that $G(\alpha_j,k)=n_j$ for all $j \leq i$ (the existence of such a $G$ is mentioned by Blass in a discussion in Mathoverflow about iterations of $\sigma$-centered forcings).

Actually I can construct a perfect tree $T\subseteq {^{<\omega}\omega}$ where every natural number appears infinitely many times in each branch and I define $F: [T] \times fin({^{<\omega}}\omega, \omega) \rightarrow \omega$ such that for every $i \in \omega$, for finitely many different branches $f_0, \dots, f_i \in [T]$ and every $n_0, \dots, n_i \in \omega$ there is a $g \in fin({^{<\omega}}\omega, \omega)$ such that $F(f_j, g) = n_j$ for $j \leq i$. (Elements of $fin({^{<\omega}}\omega, \omega)$ are finite functions from finite sequences of $\omega$ to $\omega$. The function $F$ is defined as $F(f,g):= f(min\{l: g(f \upharpoonright l) = f(l)\})$ if $\{l \in \omega: g(f \upharpoonright l)=f(l)\} \neq \emptyset)$ )

I will skip the details because my questions are more related to the following perspective:

a) Why (a modification of) the words essentially different functions is not used in 3)?

b) The terminologies independent family of functions and independent family of subsets are very similar. So can an independent family of subsets generate an independent family of functions of the same size?

c) Is there a reference (book or paper) where one can find an explicit proof of point 3)?

d) Is there a short way to see that 1) or 2) generate 3), as Blass and Irwin claim?

• I think this follows from a universal b-sequence with zero initial state, as defined in Rinot's blog here: blog.assafrinot.com/?p=3346
– Eran
Jun 3, 2017 at 8:11

The following is Theorem 3 in Some theorems of set theory and their topological consequences by Engelking and Karlowicz (Fund. Math. 57, 1965):

For any infinite set $A$ there is a family $G \subseteq {^A}{A}$ such that $|G|=2^{|A|}$ and for every pairwise different $f_0, \dots, f_l \in G$ and every (not necessarily distinct) $n_0, \dots, n_l \in A$ there is some $a \in A$ such that $f_0(a)=n_0, \dots, f_l(a)=n_l$.

They explicitly construct the independent family of functions from the independent family of subsets.

As for your question a), note that an independent family of subsets corresponds exactly to an independent family of functions from $A$ to $2$.

• Thank you Ramiro de la Vega for your precise answer. Engelking and Karlowicz wrote a nice construction. I am happy to see the explicit contructions from one familty to another.
– flos
Jun 1, 2017 at 19:01

For (d) maybe the following was meant:

Take your independent family $F$ and partition it into continuum many families of size $\omega$:

$F = \{ I_{\alpha,n} : \alpha< \mathfrak{c},n \in \omega \}$

Now construct functions $f_\alpha$, so that $f_\alpha (k) = n$ if $k \in \bigcap_{i<n} (\omega \setminus I_{\alpha,i}) \cap I_{\alpha,n}$ (these sets are pairwise disjoint for $n\in\omega$). For $k$ which is not an element of such a set define $f_\alpha (k)$ arbitrarily.

It is not too dificult to see that this works using the independence of the family $F$.

• Thank you Jonathan for you answer, which is indeed very immediate.
– flos
Jun 1, 2017 at 19:21