Are there $\omega_1$-many binary sequences with this property?

Question

Is there a family $$\{f_\alpha:\alpha<\kappa\}\subseteq 2^\omega$$ of size $\mathfrak c$ or $\omega_1$ such that for any $n\in\omega$, $\{\alpha_i:i<n\}\subseteq \kappa$, and $n\times n$ binary matrix $\textbf M\in 2^{n\times n}$, there exists $k\in\omega$ such that $$(f_{\alpha_i} (k+j))_{ij}=\textbf M.$$

Hopefully I explained it well. It is easy to picture in your mind:

(1) think of the binary sequences ($f_\alpha$'s) going from left to right

(2) pick $n$ of them ($n$ rows) and let a matrix $\textbf M$ be given as above

(3) now imagine an $n\times n$ box sliding over the selected sequences

I want the $f_\alpha$'s to be chosen (beforehand) so that if I slide the box enough, I get $\textbf M$.

If it is too hard to get uncountably many, what about countably many? It seems like you could use some arithmetic to stagger the finite binary sequences or something.

Answer 1

One can at least get countably infinitely many by a straightforward recursive construction. Suppose that for some $n,m_n\in\omega$ we’ve defined $f_k(i)$ for $k<n$ and $i<m_n$ so that:

1. $f_k\upharpoonright m_n\ne f_\ell\upharpoonright m_n$ whenever $k<\ell<n$, and
2. for each $d\le n$, $S=\{s_0,\ldots,s_{d-1}\}\in[n]^d$ with $s_0<\ldots<s_{d-1}$, and $\mathbf{M}\in{^{d\times d}2}$ there is an $i\le m_n-d$ such that the $d\times d$ matrix whose ($0$-indexed) $\langle p,q\rangle$ entry is $f_{s_p}(i+q)$ is $\mathbf{M}$.

For $i<n$ let $f_n(i)=1-f_i(i)$. Let $f_n(n)=0$ and $f_n(n+1)=1$. Let $m_n'=\max\{m_n,n+2\}$. If $m_n<n+2$, let $f_k(i)=0$ for $k<n$ and $m_n\le i<n+2$; if $m_n>n+2$, let $f_n(i)=0$ for $n+2\le i<m_n$. We’ve now defined $f_k(i)$ for $k\le n$ and $i<m_n'$.

For $2\le d\le n+1$ let $\mathscr{F}_n(d)$ be the family of finite subsets of $n+1$ that contain $n$ and have cardinality $d$. For each such $d$, each $S\in\mathscr{F}_n(d)$, and each $\mathbf{M}\in{^{d\times d}2}$ in turn extend by $d$ the domains on which the $f_k$ for $k\le n$ are defined so that (2) is satisfied for $S$ and $\mathbf{M}$. This is a finite number of finite extensions; when they have all been performed, there is some $m_{n+1}\in\omega$ such that $f_k(i)$ is defined for all $k\le n$ and all $i<m_{n+1}$ in such a way that (1) and (2) hold with $n$ replaced by $n+1$. Thus, the construction goes through to $\omega$.

Added:

Theorem $3$ of R. Engelking and M. Karłowicz, Some theorems of set theory and their topological consequences, Fund. Math. $57$ ($1965$), $275$-$285$, which I present in slightly different form, allows the construction of a family of $2^\omega$ functions from a countably infinite set to itself that code something similar to what you want without actually giving what you want.

Definition. Let $I$ be an infinite set. A family $\mathscr{F}$ of functions from $I$ to $I$ is independent if for each finite $\{f_1,\ldots,f_n\}\subseteq\mathscr{F}$ and $i_1,\ldots,i_n\in I$ there is a $j\in I$ such that $f_k(j)=i_k$ for $k=1,\ldots,n$.

Theorem. If $|I|=\kappa\ge\omega$, there is an independent $\mathscr{F}\subseteq{^II}$ such that $|\mathscr{F}|=2^\kappa$.

Now let $I={^{<\omega}2}$, the set of finite binary sequences; $|I|=\omega$, so by the theorem there is an independent family $\mathscr{F}=\{f_\xi:\xi<2^\omega\}\subseteq{^II}$ of cardinality $2^\omega$. Let $n\in\Bbb Z^+$, $\{\xi_0,\ldots,\xi_{n-1}\}\subseteq 2^\omega$ with $\xi_0<\ldots<\xi_{n-1}$, and $\mathbf{M}\in{^{n\times n}2}$. Each row of $\mathbf{M}$ is a binary sequence of length $n$ and hence an element of $I$, so let the rows be $i_0,\ldots,i_{n-1}$. Then there is a $j\in I$ such that $f_{\xi_k}(j)=i_k$ for each $k<n$.

Indexing $I$ by $\omega$ allows us to view the functions $f_\xi$ as sequences of finite binary sequences, but as yet I see no way to modify this to get actual binary sequences.

Because it may be of use in thinking about the problem, I include a brief sketch of the proof of the theorem above:

Let $\{\langle F_i,\varphi_i\rangle:i\in I\}$ be an enumeration of $$\left\{\langle F,\varphi\rangle:F\subseteq I\text{ is finite and }\varphi\in{^{\wp(F)}I}\right\}\;.$$ For each $A\subseteq I$ let $f_A:I\to I:i\mapsto\varphi_i(A\cap F_i)$, and let $\mathscr{F}=\{f_A:A\subseteq I\}$. Suppose that $f_{A_1},\ldots,f_{A_n}\in\mathscr{F}$ and $i_1,\ldots,i_n\in I$. For each pair $\{k,\ell\}$ of distinct elements of $\{1,\ldots,n\}$ there is a $j(k,\ell)\in I$ that is in exactly one of the sets $A_k$ and $A_\ell$. Let $$F=\{j(k,\ell):1\le k<\ell\le n\}\;,$$ and let $\varphi$ be any function from $\wp(F)$ to $I$ such that $\varphi(A_k\cap F)=i_k$ for $k=1,\ldots,n$. Then $\langle F,\varphi\rangle$ is $\langle F_j,\varphi_j\rangle$ for some $j\in I$, and $F_{A_k}(j)=i_k$ for $k=1,\ldots,n$. $\dashv$