Codex @codex  0

Choose disjoint subsets $K_1,K_2\subseteq [n]$ of size $k$ and let $R=[n]\setminus (K_1\cup K_2)$. The two-block extremisers for the cross-Sperner inequality areFor $A\in \mathcal{A}$ and $B\in \mathcal{B}$, some point of $K_1$ belongs to $A$ but not $B$, so $A⊈B$. Some point of $K_2$ belongs to $B$ but not $A$, so $B⊈A$. Thus these form a cross-Sperner family pair.

An element of $\mathcal{A}$ fixes its intersections with both blocks and freely chooses its subset of $R$. An element of $\mathcal{B}$ chooses any proper subset of $K_1$, any nonempty subset of $K_2$, and any subset of $R$. HenceThe hypotheses ensure that the blocks exist and both set families are nonempty, including when $n=2k$. Moreover,so this construction attains equality in the Cross-Sperner inequality.

The Von Neumann hierarchy is the following transfinite recursion on the ordinals:Here $\mathcal{P}$ denotes the full power set. The levels are increasing transitive sets, and the construction is continuous at limit ordinals. Transfinite induction proves these properties: transitivity at a successor follows because a member of a subset of $V_{\alpha }$ already belongs to $V_{\alpha }\subseteq \mathcal{P}(V_{\alpha })$; at a limit it follows from the set union of increasing transitive sets. In ZF, Axiom of foundation and Axiom schema of replacement ensure that every set belongs to some $V_{\alpha }$. In terms of the rank of a set, $x\in V_{\alpha }$ exactly when $\mathrm{rank}(x)<\alpha$.

Use the standard convention that a strongly inaccessible cardinal is uncountable, regular and strong limit. The printed explanatory definition omits uncountability: literally it also admits $\kappa =\omega$, for which no finite cardinal is a worldly cardinal. Thus that omission makes the requested conclusion false under the literal abbreviated definition. The proof below applies to the usual, intended strongly inaccessible cardinal convention $\kappa >\omega$.

First $|V_{\gamma }|<\kappa$ for every $\gamma <\kappa$. At successor stages this follows from the strong limit cardinal property, and at limits from the regular cardinal property. Consequently $V_{\kappa }\models \mathsf{ZFC}$. In particular, for Axiom schema of replacement, a domain $a\in V_{\kappa }$ has size less than $\kappa$, so its functional image has fewer than $\kappa$ elements, so the supremum of the rank of a set over its elements is below $\kappa$ by regular cardinal structure. All other axioms, including axiom of choice, have their witnesses at bounded ranks below $\kappa$; uncountability supplies axiom of infinity.

Enumerate the first-order formulas as ${\phi }_0,{\phi }_1,\dots$. For each finite collection, reflection inside the set structure $V_{\kappa }$ gives a closed unbounded subset of $\kappa$ of agreeing ranks. To see why the witness bounds stay below $\kappa$, there are fewer than $\kappa$ parameter tuples at each $V_{\gamma }$, and the supremum of their least witness ranks remains below $\kappa$ by regular cardinal structure. Closing under these bounds and taking increasing countable limits gives the usual reflection theorem for definable hierarchies argument. The countable intersection of these closed unbounded subsets is still closed unbounded because $\kappa$ is regular and uncountable. At each resulting $\alpha$,The infinite cardinal numbers below $\kappa$ also form a closed unbounded subset: they are unbounded because ${\lambda }^{+}\le 2^{\lambda }<\kappa$ for infinite $\lambda <\kappa$, and a supremum of increasing cardinal numbers is a cardinal number. Intersect the two closed unbounded subsets. Every member of the intersection is a worldly cardinal, and an unbounded subset of a regular cardinal $\kappa$ has size $\kappa$. HenceIn fact this proves the stronger worldly cardinals below an inaccessible cardinal result that these worldly cardinals contain a closed unbounded subset of $\kappa$.

Fix the base convention $L_0(X)=X$. For a transitive set $X$, the relative constructible hierarchy isHere the definable power set isThe satisfaction for a set structure in this definition is a definable set-theoretic relation, obtained by finite syntax coding and recursion on a first-order formula. The transfinite recursion therefore defines a class in ZF.

Each level is a transitive set. For transitive $A$, every $a\in A$ is a subset of $A$ definable using the parameter $a$, so $A\subseteq \mathrm{Def}(A)$; also $A\in \mathrm{Def}(A)$ using the always-true first-order formula. Thus the levels increase and $X\in L_1(X)$. Starting instead with $X\cup \{X\}$ is another common indexing convention, but it is not the convention used here. The relative universe need not satisfy axiom of choice: arbitrary $X$ need not have an internally available well-order.

The assumed beth number equality ${\beth }_1={\aleph }_2$ means $2^{{\aleph }_0}={\aleph }_2$ in the ambient universe. Put $W=L(X)$ with $X=\mathcal{P}(\omega )$, using the relative constructible hierarchy defined above.

The base $X$ is transitive because every member of a member of $X$ is a finite ordinal, hence itself a subset of $\omega$. Moreover $X\subseteq W$ and $X\in W$, and $W$ is an inner model of ZF. The latter standard fact follows from the hierarchy and reflection: bounded-rank witnesses give pairing and union; reflection gives separation and replacement; ambient replacement bounds the stages of all relatively constructible subsets of any fixed set, giving power set. It does not require axiom of choice inside $W$. Since no new subsets of $\omega$ can appear in an inner class,

Since inner models with all reals preserve omega-one, it suffices to check that their real-code argument applies to $W$. Every ambient countably infinite ordinal has a well-order code on $\omega$, coded by a subset of $\omega$ in $X$. Finite ordinals and $\omega$ are already shared. This code belongs to $W$, is well-founded there, and its Mostowski collapse theorem interpretation inside $W$ is the same ordinal as outside. Hence the ordinal is countable in $W$. Conversely, any countability witness in $W$ remains a witness in the ambient universe. Thus ${\omega }_1^W={\omega }_1$.

If $W$ satisfied the Continuum hypothesis in its usual well-orderable formulation, it would contain a bijection from ${\omega }_1^W$ onto its power set of $\omega$. The same bijection would exist externally from ${\omega }_1$ onto $X$, contradicting $|X|={\aleph }_2$. ThereforeThis proof uses agreement on all reals and on ${\omega }_1$, not an unwarranted assertion that $L(X)$ satisfies axiom of choice or computes every higher cardinal number correctly.

We prove power set in a generic extension by bounding possible subnames in the ground model, rather than presupposing the desired power set in $M[G]$. Let $x={\tau }^G$, and let $S=\{\rho :\exists r((\rho ,r)\in \tau )\}$. In $M$ formEvery $\nu \in B$ is a forcing name. Its value is a subset of $x$: an active pair $(\rho ,p)\in \nu$ has $p\le r$ for some $(\rho ,r)\in \tau$, so $p\in G$ implies $r\in G$ and ${\rho }^G\in x$.

Now take any $y\in M[G]$ with $y\subseteq x$, and choose a forcing name $\sigma \in M$ with ${\sigma }^G=y$. By axiom schema of separation and definability of the syntactic forcing relation,The atomic membership truth lemma for forcing shows ${\nu }_{\sigma }^G=y$. One inclusion follows immediately from its soundness direction. For the other, if $a\in y\subseteq x$, choose $(\rho ,r)\in \tau$ with $r\in G$ and ${\rho }^G=a$. The truth direction supplies $p\in G$ forcing $\rho \in \sigma$; strengthen within $G$ below $p$ and $r$ to obtain an active pair in ${\nu }_{\sigma }$ representing $a$.

Finally the ground-model forcing nameexists by Axiom schema of replacement and the ground-model power set axiom. Since $G$ is nonempty, all $\nu \in B$ contribute their values, andThis set belongs to $M[G]$ by the definition of a generic extension. The construction uses all conditions in the outer pairs and therefore does not require a greatest condition in $\mathbb{P}$.

We prove mutual genericity for product forcing. Let $D\in M[G_0]$ be a dense subset of $\mathbb{Q}$, and take a forcing name $\dot{D}\in M$ evaluating to $D$. By the forcing theorem, some $p_0\in G_0$ forces that $\dot{D}$ is a dense subset of the canonical forcing name for $\mathbb{Q}$.

In $M$ defineThis set is dense in the product forcing order. Given $(p,q)$, the incompatible case is immediate. Otherwise first strengthen $p$ below $p_0$. The forced density assertion and the existential clause of syntactic forcing supply a further $r\le p,p_0$ and a ground-model $q^{\prime }\le q$ with $r⊩{\check{q}}^{\prime }\in \dot{D}$. To justify choosing a ground-model $q^{\prime }$, a name forced to lie in $\check{\mathbb{Q}}$ can densely be made equal to some ${\check{q}}^{\prime }$ by the atomic membership clause; strengthen to that equality and use the forced order comparison. Thus $(r,q^{\prime })\in E$ lies below $(p,q)$.

The generic filter $H$ meets $E$. It cannot meet the first part, because its first projection contains $p_0$ and is directed. Hence there is $(p,q)\in H$ with $p\in G_0$ and $p⊩\check{q}\in \dot{D}$. Soundness of the forcing theorem gives $q\in D$, and the projection gives $q\in G_1$. Since every such $D$ is met,This establishes the stronger property, rather than merely meeting dense ground-model subsets.

The Rasiowa–Sikorski lemma constructs a generic filter $G_i$ over each $M_i$. Every resulting generic extension remains a countable transitive model of ZFC: there are only countably many ground-model names externally. The order $\mathbb{P}$ has the same elements and ordering at every stage, and atomless forcing order structure is absolute because all its quantifiers are bounded to $\mathbb{P}$. Hence the generic filter for an atomless order is new result gives $G_i\notin M_i$ for every $i$.

The increasing union $N={\bigcup }_{i<\omega }{M}_i$ is transitive and contains $\mathbb{P}$. If it satisfied Axiom of power set for $\mathbb{P}$, there would be a set $A\in N$ withChoose $i$ with $A\in M_i$. The next-stage generic filter $G_i$ belongs to $M_{i+1}\subseteq N$ and is an actual subset of $\mathbb{P}$. This subset assertion is absolute for the transitive set $N$, so $G_i\in A$. Transitivity of $M_i$ and $A\in M_i$ then give $G_i\in M_i$, a contradiction. Thus the power-set failure in an increasing union of generic extensions occurs already at the fixed ground-model order:The stages form an increasing chain, not an elementary chain, so the elementary chain theorem does not assert ZFC for their union.

Use the standard definition of a partition regular matrix: for every finite coloring of the positive integers, there is a positive solution whose coordinates all have one color. Coordinates may repeat. Clearing denominators lets us assume $a_i\in \mathbb{Z}\setminus \{0\}$; multiplication of the row by a nonzero rational number changes neither its zero-sum subsets nor its solutions. We prove both directions of the Rado theorem for one equation directly, without invoking any form of Rado's theorem.

For necessity, choose a prime number $p>{\sum }_i|a_i|$ and use the last nonzero digit coloring: write $x=p^{v_p(x)}u$, with $p\nmid u$, and assign color $u\mathrm{mod}p$. Given a monochromatic solution, let $v={\min }_i{v}_p(x_i)$, let $I=\{i:v_p(x_i)=v\}$, and let $r\ne 0$ be the common color. Divide ${\sum }_i{a}_i{x}_i=0$ by $p^v$ and reduce modulo $p$. Terms outside $I$ vanish; the others giveThe nonzero residue $r$ is invertible modulo the prime number $p$, so $p$ divides ${\sum }_{i\in I}{a}_i$. This sum has absolute value less than $p$, forcing it to be zero. The set $I$ is nonempty by its definition.

For sufficiency we first derive the needed Brauer progression theorem from the permitted Van der Waerden theorem. Fix positive integers $s,\ell$. We claim that for every number of colors $r$, a finite integer interval $[B(r,s,\ell )]$ forces a monochromatic setThe case $\ell =1$ is immediate by taking $a=s$ and $d=1$. For $r=1$ and $\ell \ge 2$, take $a=d=1$ in an interval of length at least $\max (s,\ell )$. Suppose the claim holds for $r-1$ and write $M=B(r-1,s,\ell )$. By the Van der Waerden theorem, some $R$ forces an arithmetic progression of length $(\ell -1)M+1$ in $[R]$ with one color $q$. Work in $[\max (R,sMR)]$ so that all needed multiples also lie in the coloring's domain. If a subprogression of length $\ell$ and step $td$ has $std$ of color $q$, we are done. Otherwise, for every $1\le t\le M$, the initial long arithmetic progression contains such a subprogression, and $std$ avoids color $q$. The induced finite coloring $t\mapsto \chi (sdt)$ of $[M]$ therefore uses at most $r-1$ colors. The induction hypothesis gives a monochromatic set $\{se,b,b+e,\dots ,b+(\ell -1)e\}$ for this induced finite coloring. Multiplying by $sd$ gives the desired configuration in the original coloring, with initial term $sdb$ and step $sde$. This proves the claim for $\ell \ge 2$; the only use below has $\ell \ge 3$.

Now suppose ${\sum }_{i\in I}{a}_i=0$ for a nonempty $I$. Choose $i_0\in I$, put $B={\sum }_{i\notin I}{a}_i$, and put $s=|a_{i_0}|$. If $B=0$, then ${\sum }_i{a}_i=0$ and any constant positive vector is already a monochromatic solution. Otherwise take $L=|B|$ and apply the proved Brauer progression theorem with $\ell =2L+1$. All of $sd$ and $a+jd$ for $0\le j\le 2L$ have one color. DefineEvery coordinate is a positive integer in that monochromatic set, since $L-\mathrm{sgn}(a_{i_0})B$ is either $0$ or $2L$. Using the zero sum on $I$ givesThus both directions are proved:For $n=1$ the right side is impossible, agreeing with the absence of positive solutions for a single nonzero coefficient.

The dynamical proof of Hindman's theorem gives the following result. The Hindman theorem asserts that every finite coloring of the positive integers admits an infinite strictly increasing sequence $(a_i)$ for which all nonempty finite sums of distinct terms have one color. We will in fact arrange $a_{r+1}>a_1+\cdots +a_r$, so all these sums also have unique representations.

Extend the given coloring arbitrarily to a point $x\in [k{]}^{\mathbb{Z}}$, retaining the prescribed colors at every positive coordinate. Let $X$ be its forward orbit closure under the left shift. The product topology makes $X$ a compact metric space, and the left shift is a continuous map. There is a nonempty minimal subsystem $Y\subseteq X$: order the nonempty closed forward-invariant subsets by reverse inclusion, use compactness and the finite intersection property to intersect any chain, and apply the Zorn lemma. Minimality also implies $\mathcal{L}(Y)=Y$. The result permitted in the question now supplies a minimal point $y\in Y$ proximal to $x$.

We need the joint return lemma for a proximal minimal pair, which we prove here. It suffices to consider an open neighborhood $U$ of $y$ in $X$. Choose an open neighborhood $V$ of $y$ with $\overline{V}\subseteq U$. Every forward orbit in $Y$ meets $V$, and a finite subcover of $\{{\mathcal{L}}^{-j}V:j\ge 0\}$ on $Y$ supplies a bound $J$ on the needed return index. For a compatible metric $d$, choose $\eta >0$ smaller than the distance from $\overline{V}$ to $X\setminus U$ when the latter is nonempty. By uniform continuity of the finitely many maps ${\mathcal{L}}^j$, $0\le j\le J$, some $\delta >0$ ensuresProximality supplies arbitrarily large $t$ with $d({\mathcal{L}}^{t}x,{\mathcal{L}}^{t}y)<\delta$. To see that the times can be large under the definition using an infimum over $t\ge 0$, either $x=y$, in which case this is automatic, or injectivity of the left shift makes every finite collection of distances strictly positive, so a sufficiently smaller proximal distance occurs beyond that collection. Some $j\le J$ has ${\mathcal{L}}^{t+j}y\in V$. Then ${\mathcal{L}}^{t+j}x\in U$ also. Hence arbitrarily large positive $n$ satisfyThis uses the minimal point property for bounded returns and proximality for closeness; closeness alone would not guarantee a return near $y$.

Put $q=y(0)$. Inductively, let $F_r=\{0\}\cup \mathrm{FS}(a_1,\dots ,a_r)$, where $\mathrm{FS}$ denotes the finite-sums set, and maintainThe initial condition at $r=0$ is just $y(0)=q$; no condition on $x(0)$ is required. The cylinder set $U_r=\{z:z(s)=q\text{ for every }s\in F_r\}$ is a neighborhood of $y$. Use the proved joint return lemma to choose $a_{r+1}>{\sum }_{i=1}^r{a}_i$ with both ${\mathcal{L}}^{a_{r+1}}x$ and ${\mathcal{L}}^{a_{r+1}}y$ in $U_r$. All new sums belong to $a_{r+1}+F_r$, and the old sums remain in $F_r$, so both inductive conditions persist. Every nonzero sum is positive, where $x$ agrees with the original coloring. ThereforeThis proves the Hindman theorem using only the permitted proximal-minimal existence result and the compactness and return arguments supplied above.

Use the product topology on $\mathcal{C}=[k{]}^{\mathbb{Z}}$, with $[k]$ discrete, and the left shift $(\mathcal{L}c)(j)=c(j+1)$. A basic cylinder set specifies finitely many coordinates. This is a compact metric space, and $\mathcal{L}$ is a homeomorphism. Write $Y=\overline{\{{\mathcal{L}}^{n}c:n\ge 0\}}$ for the forward orbit closure. A minimal point means that $Y$ is a minimal dynamical system, equivalently that every point of $Y$ has a dense forward orbit in $Y$; it need not be a fixed point.

There is a convention needed in the source: the bounded-gaps property concerns every finite integer interval $I$, hence every finite word over an alphabet. Literally allowing $I=\mathbb{Z}$ would make the displayed condition impossible for finite $U$, although a constant coloring is a minimal point. Under the standard finite-word interpretation, the property is precisely uniform recurrence.

Suppose first that $Y$ is a minimal dynamical system. Its nonempty compact forward-invariant subset $\mathcal{L}(Y)$ must equal $Y$. As the ambient left shift is invertible, all integer translates of $c$ belong to $Y$. Let $I=[a,b]\cap \mathbb{Z}$ have length $\ell =b-a+1$, and let $V=\{z\in Y:z{|}_I=c{|}_I\}$. This is a nonempty clopen set. Each forward orbit in $Y$ meets $V$, so $\{{\mathcal{L}}^{-n}V:n\ge 0\}$ covers $Y$. By compactness, finitely many suffice; let $D$ be the largest index in this finite cover. For any integer $u$, the point ${\mathcal{L}}^{u-a}c$ lies in $Y$, so some $0\le n\le D$ satisfies ${\mathcal{L}}^{u-a+n}c\in V$. The prescribed word therefore occurs at positions $[u+n,u+n+\ell -1]$, entirely inside $[u,u+D+\ell -1]$. Taking $M=D+\ell$ proves the bounded-gaps property for every interval of length at least $M$.

Conversely suppose $c$ is uniformly recurrent. Every finite word from any integer translate of $c$ occurs arbitrarily far to the right, so every such translate belongs to $Y$. Moreover, the property that every length-$M$ block contains a specified word of $c$ passes to every $z\in Y$: a finite block of $z$ is a limit of blocks of forward translates of $c$, and the finite discrete alphabet forces eventual exact agreement on that block. Given $I=[a,b]\cap \mathbb{Z}$, look for its word inside $z([a,a+M-1])$. An occurrence starts at $a+n$ for some $n\ge 0$, so ${\mathcal{L}}^{n}z$ agrees with $c$ on $I$. Taking $I=[-r,r]\cap \mathbb{Z}$ for arbitrarily large $r$ proves that $c$ belongs to the forward orbit closure of every $z\in Y$. That closure is a closed forward-invariant subset of $Y$, so it also contains every forward translate of $c$ and hence all of $Y$. Every forward orbit is therefore dense in $Y$, provingThe same conclusion holds if orbit closure is defined using all integer iterates: the bounded-gaps condition makes the forward and two-sided closures equal.

For each subset $J\subseteq \{1,\dots ,n\}$, take the Walsh character $f_J(x)={\prod }_{j\in J}{x}_j$, including $f_{\varnothing }\equiv 1$. Under the uniform distribution on a finite set these functions are an orthonormal basis: $f_J{f}_K=f_{J△K}$ has mean zero unless $J=K$, since the coordinates are independent fair signs. There are $2^n$ such functions, the full dimension of the function space.

Flipping a coordinate in $J$ changes the sign, while flipping one outside $J$ leaves the value unchanged. The total probability of a sign change is $|J|/(2n)$, soThe spectrum of lazy random walk on the hypercube is thereforeAll eigenvalues are nonnegative and the second largest is $1-1/n$. Hence both the ordinary spectral gap and the absolute spectral gap equal $\boxed{\gamma =1/n}$. The requested bound in part (c) is smaller than the exact gap by a factor $2n$; even the refined increasing-coordinate canonical paths Poincare bound loses a factor $(n+1)/2$. The true optimal Poincare inequality for a reversible Markov chain constant is $n$.