Error recognition in the Cantor cube (Q6167837)

This paper is, as suggested by the title, primarily concerned with the Cantor cube \(2^\omega\). For binary strings \(x\) and \(y\) of equal length (finite or infinite), the Hamming distance between \(x\) and \(y\), the number of entries for which \(x\) and \(y\) differ, is denoted by \(\mathrm{hd}(x,y)\). Then \(x \sim y\) if \(\mathrm{hd}(x,y) < \infty\). Motivated by error detection and correction, given \(T \subseteq 2^p\) where \(p \in \{ 1 , 2 , \ldots \} \cup \{ \omega \}\), the minimum distance of \(T\) is defined to be \(d(T) = \inf \{ \mathrm{hd}(x,y) : x,y \in T, x \neq y \}\). For \(n \in \omega\), let \(\mathrm{pr}_n : 2^\omega \to 2^{\omega \setminus \{n\}}\) be the projection \(\mathrm{pr}_n(x) = x\restriction_{\omega\setminus\{n\}}\). A set \(T \subseteq 2^\omega\) is said to be thin if, for every \(n \in \omega\), the restriction \(\mathrm{pr_n}\restriction_T\) is injective. As demonstrated in this paper, a set \(T\) is thin if and only if \(d(T) \geq 2\). For a set \(T \subseteq 2^\omega\), the Banach-Mazur game \(\mathcal G(T)\) relative to \(T\) in this paper's context is defined as follows. Ego (the first player) and Alter (the second player) alternate playing finite binary strings which are concatenated together in order of play. Ego wins if the infinite binary string produced is in \(T\) and Alter wins otherwise. The usual notions of perfect-information strategies are used. One of the first major results is that, if \(T\) is thin, then Ego has no winning strategy in \(\mathcal G(T)\). The proof is accomplished by assuming that Ego has a winning strategy in \(\mathcal G(T)\) and then uses two iterations of the game where the auxiliary game stacks the plays in such a way that the two infinite strings produced are Hamming distance \(1\) apart. To supplement the result about Ego's strategies, it is shown that, if Alter has a winning strategy in \(\mathcal G(T)\), then there is an entire \(\sim\)-equivalence class that misses \(T\). The main idea in this proof is to play the game \(\omega\)-many times where Alter's strategy is stacked on itself in such a way in each of the games so that the sequence of strings \(\{r_n : n \in \omega \}\) created fills out a \(\sim\)-equivalence class. Part of this is to feedback entire initial plays as Ego's first move in the \(n^{\mathrm{th}}\) game where a finite number of bits are changed and the rest of the plays are then appropriately stacked to ensure coherence in the end. From the two results above about conditions in which strategies exist and the fact that maximal thin sets must intersect each \(\sim\)-equivalence class, it is concluded that, for maximal thin \(T \subseteq 2^\omega\), \(\mathcal G(T)\) is undetermined, and thus, that \(T\) is neither Borel nor meager. The remaining content of the paper is related to xor-sets and \(k\)-thin sets. In particular, it is shown that every xor-set is a maximal thin set and that the Cantor cube can be partitioned into two (necessarily non-Borel) thin sets. Such partitions are shown to necessarily consist of two complementary xor-sets. The final result is the generalization of the result about thin sets, that maximal \(k\)-thin sets are neither Borel nor meager.