Balogh countable restriction enumeration

A sequence of binary functions on $\omega$ is equivalent, by evaluation, to a binary function on $\omega \times \omega$. The map $(i,j)\mapsto 2^i(2j+1)-1$ is a bijection onto $\omega$: each positive integer has a unique power of two dividing it and a unique odd quotient. Thus ${\kappa }^{{\mathrm{\aleph }}_0}=\kappa$ by this coding and F2. A nonempty countable subset of $\kappa$ is the range of a sequence, so A1 selects enumerations and bounds the number of such subsets by $\kappa$; including the empty subset leaves the same bound by F3. For fixed countable $A$, each binary function on $A$ is coded by a binary sequence, so there are at most $\kappa$ of them. Countable subsets $B$ therefore have at most ${\kappa }^{{\mathrm{\aleph }}_0}=\kappa$ possibilities. The subset $a\subseteq A$ and each of the maps $p,q,r$ have at most $\kappa$ possibilities: finite trace subsets have at most $\kappa$ possibilities by F3, and a sequence of these is again bounded by ${\kappa }^{{\mathrm{\aleph }}_0}$. F3 bounds the finite tuple product by $\kappa$. Realizability only restricts the set of typed tuples; it adds no new coordinate, so $\mathrm{\mid }\mathcal{R}\mathrm{\mid }\le \kappa$.

Every countable subset of $\kappa$ is bounded in $\kappa$. To prove this without assuming regularity of the continuum, suppose $\kappa$ were the union of countably many sets of size below $\kappa$. Transfer them along a bijection with ${}^{\omega }2$ to sets $Z_n$. Partition $\omega$ into the infinite sets $D_n=\{2^n(2j+1)-1:j<\omega \}$. The restrictions to $D_n$ of members of $Z_n$ number less than $\kappa$, whereas $\mathrm{\mid }{}^{D_n}2\mathrm{\mid }=\kappa$ by the explicit enumeration of $D_n$. Choose $b_n\in {}^{D_n}2$ outside that restriction family using A1. Their union $b$ is a binary function on $\omega$ outside every $Z_n$, a contradiction. If a countable subset of the initial ordinal $\kappa$ were unbounded, its initial segments, each of cardinality below $\kappa$, would express $\kappa$ as just such a countable union. This proves the asserted boundedness.

Fix $T$. If $I_T$ is empty, the empty $J_T$ and empty function work. Otherwise enumerate its countable set of triples so each appears infinitely often, by listing longer and longer finite initial portions of an enumeration, with repetition in the finite nonempty case. At each finite stage consider the scheduled $t=(n,E,e)$. The sets $q(\gamma )\setminus E$ for distinct $\gamma \in K_T(t)$ are pairwise disjoint, by F1. Only finitely many trace functions and finitely many points have been used at earlier stages. Each used trace can belong to at most one of these petals, so only finitely many candidates are forbidden. The infinite $K_T(t)$ has a fresh remaining point whose petal misses all previous petals. Choose it and assign that petal as its $u_T$ value. A1 fixes choices and F4 performs the recursion. The different $H_T(t)$ are disjoint, since $p(\gamma )$, $q(\gamma )\cap B$ and its evaluation determine $t$; therefore no incompatible triple assignment arises. The selected points form $J_T$. Each triple's infinitely many scheduled stages give infinitely many distinct witnesses; every petal misses $B$ because its root is exactly $q(\gamma )\cap B$. An empty petal is allowed and excludes no later candidate.

By step 1.1 and A1 enumerate $\mathcal{R}$ without repetition with order type $\tau \le \kappa$. At stage $\xi <\tau$, its support $A$ is bounded by step 1.2. The tail above $A$ has cardinality $\kappa$: otherwise that tail and an initial segment of size below $\kappa$ would have union of size below $\kappa$ by F3, contrary to their union being $\kappa$. Fewer than $\kappa$ labels have been used at stage $\xi$, so some label $\beta$ above every member of $A$ is unused. Assign the least such $\beta$. F4 gives this recursion, and its range $P$ supplies an injective labeling with $A_{\beta }\subseteq \beta$. No monotonicity of the labels is claimed.

Step 2.1 gives the labeled enumeration, and step 1.3 gives its thinning data for each tuple. A1 selects those data simultaneously from the nonempty witness sets just proved, after the tuple counting, so their choices do not change the counting argument. These are all the asserted conclusions. QED.