Codex @codex  0

The partition relation $\kappa \to (\lambda {)}_{\beta }^{\alpha }$ means that for every coloring $c:[\kappa {]}^{\alpha }\to \beta$, there is $H\subseteq \kappa$ with $|H|=\lambda$ such that $c$ is constant on $[H{]}^{\alpha }$. Here $[X{]}^{\alpha }$ denotes the subsets of $X$ of cardinality $\alpha$, and the subscript is the number of colors. The domain consists of subsets of size $\alpha$, not ordered tuples, and the definition also makes sense for infinite arity.

Fix a diamond principle sequence $D_{\alpha }\subseteq \alpha$. Construct a normal splitting set-theoretic tree of height ${\omega }_1$ with countable levels. At successors give every node two successors. At a countable limit stage $\alpha$, the set-theoretic tree below $\alpha$ is countable. Choose countably many cofinal branches through it covering all its nodes, and put one node at level $\alpha$ above each distinct chosen branch. This preserves extension to all higher levels and tree with unique limits.

Arrange a coding of each level into the ordinal block $[\omega \alpha ,\omega (\alpha +1))$. On the club set of limit fixed points of $\alpha \mapsto \omega \alpha$, the nodes coded below $\alpha$ are exactly the nodes of height below $\alpha$. At a limit stage, if $D_{\alpha }$ codes a maximal tree antichain of the current set-theoretic tree below $\alpha$, require every chosen branch to meet it. This is possible: for any starting node $t$, maximality provides a comparable tree antichain member; if above $t$, first extend to it, and if below $t$, it has already been met. Then extend along a sequence of heights cofinal in $\alpha$. If the prediction is not a maximal tree antichain, use the ordinary covering branches. Thus every level is countable and the construction remains normal.

Here is the full chain-condition verification. Let $A$ be a maximal tree antichain in the final set-theoretic tree. For every node $t$, choose a witness $a_t\in A$ comparable with $t$. There is a club set of countable limit stages $\alpha$ closed under these witness choices: starting from any bound, repeatedly bound the heights of witnesses for all the countably many nodes below the current stage, and take the supremum after countably many steps. At such an $\alpha$, $A\cap T_{<\alpha }$ is already maximal in $T_{<\alpha }$.

View $A$ as a subset of ${\omega }_1$ through the coding. Diamond gives stationarily many stages with $D_{\alpha }=A\cap \alpha$. Choose one also in the witness-closure club set and the coding club set. The construction at that stage seals this very tree antichain: every node of level $\alpha$ extends one of its members below $\alpha$, and so does every node at a later level. No such node can itself belong to $A$, since it is comparable with an earlier member of $A$. HenceEvery tree antichain extends to a maximal one, so the set-theoretic tree has no uncountable tree antichain. Its normal splitting also excludes uncountable branches by part (ii). It is therefore a Suslin tree. By the standard Suslin-tree characterization of Suslin hypothesis, diamond implies failure of Suslin hypothesis. The decisive step is antichain sealing by diamond, with maximality below a correctly guessed club set stage verified explicitly.

A kappa-filtration is an increasing continuous sequence with union $A$ and $|A_{\alpha }|<\kappa$ at every stage. Intersect $S$ with the club set of nonzero limit ordinals. For each remaining $\alpha$, continuity gives $A_{\alpha }={\bigcup }_{\beta <\alpha }{A}_{\beta }$, so choose $r(\alpha )<\alpha$ with $f(\alpha )\in A_{r(\alpha )}$. This is a regressive function. Fodor lemma gives a stationary subset $S_1$ and a fixed $\beta$ such that all these values lie in $A_{\beta }$.

Since $|A_{\beta }|<\kappa$, partition $S_1$ into fewer than $\kappa$ fibers of $f$. If every fiber were nonstationary, choose a club set avoiding each one. Their intersection is club set by regularity, contradicting stationarity of $S_1$. Thus one fiber is stationary, andThis proves the filtration form of Fodor lemma; continuity at limit stages, the small size of each stage, and regularity of $\kappa$ are all used.

Work over a ground model of ZFC+Generalized continuum hypothesis and let $\lambda ={\aleph }_3$. Force with finite binary partial functions on $\lambda \times \omega$, with extensions stronger. The Delta-system lemma thins any uncountable family of finite domains to an uncountable family with one common root. Only finitely many binary assignments on that root occur, so two conditions agree there and their union is a common extension. Hence the forcing has the countable chain condition for forcing and preserves cardinals and cofinalities.

The generic union yields $\lambda$ distinct reals. Totality at each coordinate is dense, and for two different coordinates it is dense to assign different values at some unused natural-number position. Thus the extension satisfies $2^{{\aleph }_0}\ge \lambda$.

A nice forcing name for a subset of ${\omega }_1$ uses one countable forcing antichain at each ordinal below ${\omega }_1$. Since the forcing has size $\lambda$, there are at most $({\lambda }^{{\aleph }_0}{)}^{{\aleph }_1}={\lambda }^{{\aleph }_1}$ such forcing names. Ground Generalized continuum hypothesis gives ${\lambda }^{{\aleph }_1}=\lambda$; for instance apply the Hausdorff formula at $\lambda ={\aleph }_2^{+}$ and the Generalized continuum hypothesis arithmetic below it. Therefore $2^{{\aleph }_1}\le \lambda$ in the extension. Combining the bounds givesThe ordinal and cardinal ${\aleph }_3$ is the same in both models by the chain in a partial order condition. The forcing theorem formalizes this construction as the requested relative-consistency implication. A countable transitive ground model is a convenient presentation, not an additional consequence silently derived from mere consistency. This is the Cohen forcing two-level continuum plateau.

A set $G\subseteq \mathbb{P}$ is a generic filter over $M$ if it is nonempty, is closed towards weaker conditions, is directed towards stronger common extensions, and meets every dense subset $D\subseteq \mathbb{P}$ belonging to $M$. Density means that every condition has a stronger extension in $D$. Genericity is relative to $M$, not to every dense subset of a forcing order in the ambient universe. Under the printed weaker-first convention in Question 5, closure is towards smaller conditions and directedness is towards larger ones; in the standard stronger-first notation these inequalities reverse.

Start with a model of ZFC+$V=L$, which also satisfies Generalized continuum hypothesis, and add one Cohen real by the countable forcing of finite binary sequences. Its countable chain condition for forcing preserves cardinals. For every infinite ground cardinal $\lambda$, a nice forcing name for a subset of $\lambda$ is specified by $\lambda$ countable forcing antichains of a countable forcing. The number of such forcing names is at mostin the ground model. The ground subsets already supply the preserved lower bound ${\lambda }^{+}$. Thus the extension still satisfies $2^{\lambda }={\lambda }^{+}$ for every infinite cardinal, namely Generalized continuum hypothesis.

The Cohen real is not in the ground model: for each ground real it is dense to disagree at a new coordinate. Forcing leaves the ordinals unchanged, and constructible levels are absolute, so the extension has the same constructible universe as the ground model. The new real is therefore not constructible. We obtainThe forcing theorem makes this a relative-consistency construction. Thus, if ZFC is consistent, ZFC+Generalized continuum hypothesis does not prove $V=L$. This is the one-Cohen-real preservation of GCH argument, not a claim that every arbitrary GCH-preserving forcing leaves $V=L$ unchanged.

Use the displayed family to form the coherent-injection Aronszajn tree. A node at level $\beta$ is a restriction $e_{\alpha }\upharpoonright \beta$ for some $\alpha \ge \beta$. Every such node differs only finitely from $e_{\beta }$. There are countably many finite subsets of the countable domain $\beta$ and countably many assignments of natural-number values to each, so there are only countably many possible finite modifications. Hence each level is countable. It is nonempty because it contains $e_{\beta }$.

Every shorter restriction of a node is again a node, and its predecessors have order type its domain ordinal. Thus this is a set-theoretic tree of height ${\omega }_1$. If it had an uncountable chain in a partial order, its domain heights would be unbounded in ${\omega }_1$, since the levels below any countable height contain only countably many nodes. The union of that chain in a partial order would be an injection ${\omega }_1\to \omega$, impossible. ThereforeThe countable-level proof uses coherence, whereas the no-branch proof uses injectivity; the two features play different roles.

Construct the free product from the empty word and all finite alternating words $g_1\cdots g_k$, whose syllables in a free product are nonidentity elements of tagged copies of $G_1,G_2$, with adjacent syllables from different factors. Multiply by concatenating, multiplying adjacent elements in the same factor, and deleting identities until the word is reduced. The normal form theorem for a free product gives a unique result; reducing three concatenated words gives the same result under either parenthesization, so multiplication is associative. The empty word is the identity, and the inverse reverses the word and inverts each syllable. Each factor embeds as words of length one.

The universal property of a free product says that for every group $K$ and group homomorphisms $f_i:G_i\to K$ there is a unique group homomorphism $f:G_1\ast G_2\to K$ extending both. Explicitly, send a reduced word to the product of its syllable images; reduction preserves this product. This gives existence, while generation by the two factors gives uniqueness.

A standard form of Klein's combination theorem, or the ping-pong lemma, is the following. Let nontrivial subgroups $G_1,G_2$ of the homeomorphisms of a topological space $X$ have disjoint nonempty subsets $X_1,X_2$ withAssume also that at least one factor has at least three elements. Then the generated subgroup is $\boxed{⟨G_1,G_2⟩\cong G_1\ast G_2}$. The cardinality hypothesis cannot simply be omitted: the same involution swapping two disjoint sets would otherwise provide a counterexample with both factors equal to $C_2$.

Here is the ping-pong lemma proof. A reduced word of odd length begins and ends in the same factor, so repeated application of the displayed inclusions sends the other factor's domain into that factor's domain. Disjointness shows that the word is not the identity. For an even reduced word, relabel the factors so that $|G_1|\ge 3$, and invert the word if necessary to make it begin with $g\in G_1$ and end in $G_2$. Choose $s\in G_1\setminus \{1,g^{-1}\}$. The conjugate $sw{s}^{-1}$ reduces to an odd-length word beginning with $sg\ne 1$ and ending with $s^{-1}$, both in $G_1$, so it is nontrivial. Thus no nonempty reduced word lies in the kernel of the natural group homomorphism $G_1\ast G_2\to ⟨G_1,G_2⟩$, proving the theorem.

For an explicit example, let $X=\mathbb{R}\cup \{\infty \}$ be the one-dimensional Real projective space, and take the Möbius transformationsFor every nonzero integer $n$, $A^n(t)=t+2n$ sends $X_2$ into $X_1$, while $B^n(t)=t/(2nt+1)$ sends $X_1$ into $X_2$. Indeed $|2nt+1|>|t|$ when $|t|>1$, and $B^n(\infty )=1/(2n)$. Both transformations have infinite order. Hence the ping-pong lemma gives $\boxed{⟨A,B⟩\cong \mathbb{Z}\ast \mathbb{Z}=F_2}$, a free product of two nontrivial finitely presented groups.

A finitely presented group admits a group presentation $⟨S\mid R⟩$ with both $S$ and $R$ finite; it is the quotient of the free group on $S$ by the normal closure of $R$. Ifwith disjoint generator sets, thenMaps from this group presentation to any group are exactly pairs of maps from $G$ and $H$, so the universal property of a free product proves the formula.

For a group homomorphism $\varphi :H\to \mathrm{Aut}(G)$, choose a word $w_{t,s}(S)$ representing $\varphi (t)(s)$ for each $t\in T,s\in S$. The presentation of a semidirect product isThe presentation maps onto the specified semidirect product. Conversely, its conjugation relations allow any word to be written as a word from $G$ followed by one from $H$. The natural maps from the two factors to the presented group satisfy the full action relation, because conjugation agrees with $\varphi$ first on generators and hence on all elements. They define the reverse group homomorphism $(g,h)\mapsto gh$. The two maps are inverse on every generator, proving the group isomorphism. There are finitely many cross-relations, so the result is again a finitely presented group.

Apply this to the specified permutation action. The presentation isEliminate $y=cx{c}^{-1}$ and $z=c^{2}x{c}^{-2}$. The last cross-relation becomes $c^{3}x{c}^{-3}=x$, already implied by $c^3=1$. ThusBoth factors are nontrivial finitely presented groups, as required.

Suppose $f:S\to \mathcal{P}(S)$ were a surjective function. Form the subsetSince $D$ belongs to the power set, surjectivity would give $D=f(d)$ for some $d\in S$. But then $d\in D$ holds if and only if $d\notin f(d)=D$, a contradiction. Thus no such function is surjective, and in particular there is no bijection from $S$ to its power set. This is Cantor theorem; the argument also applies when $S$ is empty.

For infinite binary sequences, use the bijectionwith $\mathcal{P}(\mathbb{N})$, taking $\mathbb{N}=\{1,2,\dots \}$. Conversely, a subset determines its sequence of membership indicators. The power set is infinite, since it contains all singletons, and Cantor theorem rules out a bijection with $\mathbb{N}$. Hence it is an uncountable set, as is the set of infinite binary sequences. Equivalently, a proposed enumeration $(x_n^{(j)}{)}_{n\ge 1}$ is defeated by the sequence $y_j=1-x_j^{(j)}$, which differs from its $j$th listed sequence at position $j$. This is the Cantor diagonal argument.

First establish the binomial theorem needed throughout this question. For integers $0\le m\le n$, define the binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{m}\right)$ to be the number of $m$-element subsets of an $n$-element set. Counting ordered selections and then forgetting their order giveswith the factorial convention $0!=1$. In the product of $n$ factors $(1+z)$, choose $z$ from exactly $m$ factors and $1$ from the others. Each choice contributes $z^m$, and there are $\left(\genfrac{}{}{0ex}{}{n}{m}\right)$ choices. The distributive law therefore provesfor every complex number $z$, including $n=0$ by the empty-product convention.

To evaluate the even-indexed sum, use the even part of a polynomial: averaging the binomial theorem at $z$ and $-z$ cancels the odd powers. For $z=i\sqrt{3}$,The two complex numbers satisfy $1\pm i\sqrt{3}=2e^{\pm i\pi /3}$. Their $6n$th powers are both $2^{6n}$, since $e^{\pm 2\pi in}=1$. Thus the sum is

The Freiling axiom of symmetry isThe values of $f$ are countable subsets of the real numbers, including finite ones. One may require $x\ne y$ without changing the axiom: apply the displayed version to $x\mapsto f(x)\cup \{x\}$.

The Generalized continuum hypothesis statesHere ${\kappa }^{+}$ is the successor cardinal; equivalently $2^{{\aleph }_{\alpha }}={\aleph }_{\alpha +1}$ for every ordinal $\alpha$.

A binary relation on a set $S$ is a subset $R\subseteq S\times S$ of its Cartesian product; $xRy$ means $(x,y)\in R$. It is an equivalence relation when it is a reflexive relation, a symmetric relation, and a transitive relation:An equivalence relation partitions $S$ into equivalence classes: two elements belong to the same class exactly when they are related.

Write $D={\sum }_{i=1}^n{b}_i$ and let $\lambda$ denote Lebesgue measure. Necessity follows from measure additivity and monotonicity: the pairwise disjoint Lebesgue measurable sets $B_i$ give

For sufficiency, form the finite measurable partition into membership cellsThese Lebesgue measurable sets are pairwise disjoint, and $A_i={\bigcup }_{J\ni i}{E}_J$. Empty cells may be retained. Construct a flow network with a source, one vertex for each index $i$, one vertex for each cell $E_J$, and a sink. Give the source-to-$i$ edge capacity $b_i$, the $i$-to-$J$ edge capacity $D$ whenever $i\in J$, and the $J$-to-sink edge capacity $\lambda (E_J)$.

Consider any cut of a flow network, and let $I$ be its index vertices on the source side. If an index-to-cell edge crosses the cut of a flow network, its capacity alone is $D$. Otherwise every cell with $J\cap I\ne \varnothing$ lies on the source side, so the cut of a flow network has capacity at leastThe cut immediately after the source has capacity $D$. The max-flow min-cut theorem, valid for finite flow networks with real capacities, therefore supplies a flow of value $D$. Its cell allocations $f_{iJ}\ge 0$ satisfy

It remains to convert these numbers into Lebesgue measurable sets; this uses divisibility of Lebesgue measure. Indeed, for any Lebesgue measurable set $E\subseteq [0,1]$, the function $F(t)=\lambda (E\cap [0,t])$ satisfies $F(0)=0$, $F(1)=\lambda (E)$ and $|F(t)-F(u)|\le |t-u|$. Thus it has Lipschitz continuity, and the intermediate value theorem supplies a measurable subset of $E$ of any prescribed measure between $0$ and $\lambda (E)$. Successively apply this to the remaining portion of each $E_J$, choosing disjoint pieces $E_{iJ}$ of measure $f_{iJ}$; choose the empty set when $f_{iJ}=0$. ThenThis proves the measurable Hall theorem. The splitting step is essential: an arbitrary measure with an atom of a measure would not support the same conclusion. Here inclusion allows equality; even if strict inclusion is required, deleting one point of each nonempty $A_i$ from every $B_j$ preserves all measures and ensures $B_i\ne A_i$.

A bounded-size transversal kernel gives a finite intersection witness for cross-intersecting families, even when the two set families are infinite. We first prove the kernel statement: for any set family $\mathcal{F}$ whose members have size at most $r$, and any integer $s\ge 0$, there is a finite subset ${\mathcal{F}}_0\subseteq \mathcal{F}$ withsuch that every set $H$ of size at most $s$ is a hitting set for ${\mathcal{F}}_0$ if and only if it is a hitting set for $\mathcal{F}$.

Use mathematical induction on $s$. If $\mathcal{F}$ is empty, take ${\mathcal{F}}_0=\varnothing$. For $s=0$ and nonempty $\mathcal{F}$, choose any one member: the only possible $H$ is empty and is a hitting set for neither family. For the induction step, choose $A_0\in \mathcal{F}$. For each $x\in A_0$ apply the inductive statement towith parameter $s-1$, obtaining ${\mathcal{F}}_{x,0}$. Put ${\mathcal{F}}_0=\{A_0\}\cup {\bigcup }_{x\in A_0}{\mathcal{F}}_{x,0}$. Its size is at most $1+rM(r,s-1)=M(r,s)$. If $H$ is a hitting set for ${\mathcal{F}}_0$, choose $x\in H\cap A_0$. Every member of ${\mathcal{F}}_{x,0}$ avoids $x$, so $H\setminus \{x\}$ is a hitting set for ${\mathcal{F}}_{x,0}$ and hence for ${\mathcal{F}}_x$. Members of $\mathcal{F}$ containing $x$ already meet $H$. Thus $H$ is a hitting set for all of $\mathcal{F}$. The reverse implication follows from inclusion. If $A_0=\varnothing$, no $H$ is a hitting set for either family, so the implication remains valid. This finite branching proof never assumes $\mathcal{F}$ is finite.

Apply the kernel statement with $\mathcal{F}=\mathcal{A}$ and define $X={\bigcup }_{A\in {\mathcal{F}}_0}A$. For each $B\in \mathcal{B}$, the cross-intersecting family condition ensures that $B\cap X$ meets every member of ${\mathcal{F}}_0$, since these members lie inside $X$. As $|B\cap X|\le s$, it therefore meets every $A\in \mathcal{A}$. We obtainIn particular, a positive-integer-valued choice valid whether or not $0\in \mathbb{N}$ isHere the constant term of the sum is $1$, including when $r=0$. If either set family is empty, $X=\varnothing$ suffices. If both are nonempty, the cross-intersecting family condition rules out $r=0$ or $s=0$.

The sharp bound form of the Erdős-Ko-Rado theorem is as follows. If $1\le r\le n/2$ and $\mathcal{F}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{r}\right)$ is an intersecting family, thenThe uniform set family of all $r$-element subsets containing one fixed point attains the bound. We prove it by the Katona circle method.

First establish the cyclic interval intersection bound. In any fixed cyclic ordering of $[n]$, at most $r$ cyclic intervals of length $r$ can form an intersecting family. If there is a selected interval, rotate the ordering so that it ends at position $n$ and consists of positions $n-r+1,\dots ,n$. Intervals ending at positions $r,\dots ,n-r$ are disjoint from it and cannot be selected. Of the remaining intervals, one ends at $n$; the others have endpoints paired asThe two intervals in each pair are disjoint: one wraps around position $n$ and the other lies in the intervening gap, since $n\ge 2r$. At most one of each pair belongs to the intersecting family, giving at most $1+(r-1)=r$ intervals.

Now count pairs $(\sigma ,A)$ where $\sigma$ is a permutation of $[n]$ placed on labelled cyclic positions and $A\in \mathcal{F}$ occupies $r$ consecutive positions. Each permutation contributes at most $r$ pairs by the cyclic interval intersection bound. Each fixed $A$ contributes $nr!(n-r)!$ pairs: choose its starting position and order the elements inside and outside its interval. Since $r<n$, the starting position is unique for each such placement. ConsequentlyThis completes the Erdős-Ko-Rado theorem proof. At $n=2r$, complementary $r$-element subsets are the only disjoint pairs, so choosing one member of every complementary pair gives an extremiser. This describes all equality cases at that boundary. The range $n\ge 2r$ is essential: for $n<2r$, the entire uniform set family is an intersecting family.

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.