Let $B={\mathbb{F}}_2^n\setminus (A+A)$ have density $\beta$. Since $1_A\ast 1_A$ vanishes on $B$,The zero-frequency contribution is ${\alpha }^2\beta$, soPut $\Gamma ={\mathrm{Spec}}_{\alpha /2}(1_B)$. Outside $\Gamma$, Parseval identity bounds the contribution byThereforebecause $|\widehat{1_B}(t)|\le \beta$. Chang's theorem places $\Gamma$ in a subspace $W$ of dimensionSet $V=W^{\perp }$. Then $V$ has this codimension, $V^{\perp }=W$, and adding the zero-frequency term $|\widehat{1_A}(0){|}^2={\alpha }^2$ gives

Use normalized Fourier analysis on a finite abelian group. If $A\subseteq {\mathbb{F}}_2^n$ has density $\alpha$, its large spectrum at level $\rho >0$ isThe Chang theorem states that this spectrum is contained in a subspace of dimensionEquivalently, it is contained in the span of a dissociated set of that size.

Assume $|A+A|\le K|A|$ and putThis set is symmetric, contains zero, and the Plünnecke-Ruzsa inequality givesIt also contains $A-A$, so for every $x\in A$,

To control $H+H=4A-4A$, observe again by Plünnecke-Ruzsa thatApply the Ruzsa covering lemma with $S=H+H$ and $T=A$. There is a set $Y$ with $|Y|\le K^9$ such thatConsequently $H$ is a $K^9$-approximate group. Taking a sufficiently large absolute constant $C$ gives

Construct $X\subseteq B$ greedily. Begin with one element of $B$. While some $b\in B$ satisfiesadjoin $b$ to $X$. The first translate contributes $|A|$ points to $A+X$, and each later translate contributes at least $|A|/2$ new points. Thereforeand hence

When the process stops, every $b\in B$ satisfies $|(A+b)\cap (A+X)|>|A|/2$. Each point in this intersection has the formand therefore gives a triple $(x,a,a^{\prime })\in X\times A\times A$ with $b=a-a^{\prime }+x$. Distinct intersection points give distinct $a^{\prime }$, so there are more than $|A|/2$ such triples.

For $b,b^{\prime }\in B$, the corresponding sets of possible $a^{\prime }\in A$ both have size greater than $|A|/2$ and hence intersect. Using a common $a^{\prime }$ givesso $b-b^{\prime }=a-c+x-y$. Thus

The Plünnecke-Ruzsa inequality says that if $A,B$ are finite nonempty subsets of an abelian group andthen for all nonnegative integers $m,n$,

Choose a nonempty $X\subseteq A$ minimizingthen $K^{\prime }\le K$. We first prove the Petridis minimal-growth lemmafor every finite $C$, by induction on $|C|$. Remove $c\in C$, write $C^{\prime }=C\setminus \{c\}$, and letThe new points contributed to $X+C$ by $X+c$ are exactly $|X\setminus X^{\prime }|$. Moreover, $X^{\prime }+B+c\subseteq (X+B+c)\cap (X+B+C^{\prime })$, soThe induction hypothesis, the identity $|X+B|=K^{\prime }|X|$, and minimality, which gives $|X^{\prime }+B|\ge K^{\prime }|X^{\prime }|$, yieldIteration with $C=(r-1)B$ gives

Finally, the Ruzsa triangle inequality givesas required.

The Lévy reflection theorem states that for every finite collection $\Phi$ of formulas and every ordinal $\gamma$, there is an ordinal $\alpha >\gamma$ such that, for every $\phi \in \Phi$ and all parameters $\vec{a}\in V_{\alpha }$,Indeed, the ordinals $\alpha$ reflecting all formulas in $\Phi$ form a closed unbounded class.

Conditions in $G$ are compatible finite functions, so their union $F=\bigcup G$ is a function $({\omega }_1{)}^M\rightharpoonup ({\omega }_1{)}^M$. For each $\alpha <{\omega }_1$, the setis dense: choose a normal function extending $p$ and add its value at $\alpha$. Genericity makes $F$ total.

If $\alpha <\beta$, choose a condition in the filter extending conditions that decide both values. It is contained in a normal function on an ordinal, so $F(\alpha )<F(\beta )$. Thus $F$ is strictly increasing.

It remains to prove continuity. For every limit $\delta <{\omega }_1$ and $\gamma <{\omega }_1$, let $D_{\delta ,\gamma }$ contain the conditions $p$ such that $\delta \in \mathrm{dom}p$ and eitheror there is some $\alpha <\delta$ in $\mathrm{dom}p$ with $p(\alpha )>\gamma$. This set is dense. Given $p$, extend it to a normal function $f$ and add $(\delta ,f(\delta ))$; if $f(\delta )>\gamma$, continuity of $f$ supplies an $\alpha <\delta$ with $f(\alpha )>\gamma$, which may also be added.

Now fix $\gamma <F(\delta )$. Since $G$ meets $D_{\delta ,\gamma }$, compatibility with the condition deciding $F(\delta )$ rules out the first alternative and gives $\alpha <\delta$ with $F(\alpha )>\gamma$. Therefore values below $\delta$ are cofinal in $F(\delta )$. Strict increase supplies the reverse bound, soHence $F$ is normal on $({\omega }_1{)}^M$ in $M[G]$.

Assume the forcing relation and the forcing theorem have been constructed for $\phi (x,\vec{y})$. Defineto mean thatis dense below $p$. This definition is first-order over $M$, so the definability lemma is preserved.

Suppose $p\in G$ forces the existential statement. Genericity below $p$ gives $q\in G\cap D_p$ and a name $\sigma$ with $q⊩\phi (\sigma ,\vec{\tau })$. The truth lemma for $\phi$ yieldsso the existential statement is true. Conversely, if $M[G]\models \exists x\phi (x,{\vec{\tau }}^G)$, choose a name $\sigma$ for a witness. The truth lemma for $\phi$ gives $q\in G$ with $q⊩\phi (\sigma ,\vec{\tau })$, and then $q⊩\exists x\phi (x,\vec{\tau })$. This proves both directions of the forcing theorem for the existential formula.

The forcing theorem has two parts. The definability lemma says that for every formula $\phi$, the relationis definable in $M$. The truth lemma says that if $G$ is generic over $M$, then

Let $c=\bigcup G$ and $d(n)=c(2n)$. DefineThis is a filter: restrictions of finite pieces of $d$ remain in $H$, and the union of two members is a common stronger condition.

To prove genericity, take a dense set $D\in M$. Let $E_D$ consist of conditions $q\in \mathrm{Fn}(\omega ,2)$ for which some $p\in D$ satisfiesThe set $E_D$ is dense. Indeed, given $q$, first read its finitely many assigned even coordinates as a condition $p_0$ on $\omega$. Choose $p\le p_0$ in $D$, and extend $q$ by setting $q(2n)=p(n)$ at the remaining coordinates of $p$. Since $E_D\in M$, the generic filter $G$ meets it. For $q\in G\cap E_D$, the corresponding $p\in D$ is a finite subfunction of $d$, so $p\in H\cap D$.

Thus $H$ meets every dense subset belonging to $M$. Moreover, each singleton $\{(n,d(n))\}$ belongs to $H$, and hence

Let $A\subseteq \mathrm{Fn}(I,J)$ be uncountable. Apply the Delta-system lemma to the finite sets $\mathrm{dom}p$ for $p\in A$. After passing to an uncountable subset $A^{\prime }$, there is a fixed finite root $R$ such thatfor distinct $p,q\in A^{\prime }$. Because $J$ is countable and $R$ is finite, there are only countably many functions $R\to J$. A further uncountable subset $A^{\prime \prime }\subseteq A^{\prime }$ therefore has the same restriction to $R$.

Any two conditions in $A^{\prime \prime }$ agree on the intersection of their domains, so their union is a common stronger condition. Thus every uncountable family contains two compatible conditions, and no uncountable antichain exists. Therefore

Suppose $V=L$. If $x\in L_{{\omega }_1}$, then $x\in L_{\alpha }$ for some countable ordinal $\alpha$. The set $L_{\alpha }$ is transitive and countable, so the transitive closure of $x$ lies in a countable set. Thus $x$ is hereditarily countable, proving

Conversely, let $x\in H_{{\aleph }_1}$ and choose a sufficiently large $L_{\theta }$ containing $x$. By the Downward Lowenheim-Skolem theorem, there is a countable elementary substructure $N\prec L_{\theta }$ that contains every member of $\mathrm{TC}(\{x\})$. The Mostowski collapse theorem gives a transitive collapse of $N$, and the condensation lemma for the constructible universe identifies it with $L_{\beta }$ for a countable ordinal $\beta$. Because $N$ contains the transitive closure of $x$ pointwise, the collapse fixes $x$. Thus $x\in L_{\beta }\subseteq L_{{\omega }_1}$. Hence

Work in the ambient universe and let $a,u\in L$. SupposeFor each $x\in a$, let $y_x$ be this unique witness. The relativization ${\phi }^L$ is a first-order formula, so the ambient Axiom schema of replacement collects the witnesses $y_x$ into a set. Every witness lies in the constructible hierarchy, hence there is an ordinal $\alpha$ such thatFor example, take the supremum of one constructible rank for each witness and then increase it by one.

The set $L_{\alpha }$ itself belongs to $L_{\alpha +1}\subseteq L$. Taking $b=L_{\alpha }$, every $x\in a$ has a witness $y\in b$ satisfying ${\phi }^L(x,y,u)$. Thereforewhich is the stated instance of Replacement.

First form the singleton set $\{b\}=F_1(b,b)$ and then use $F_2$ to take a set union:The unused second argument of $F_2$ may be any term. Since $x\cap c=x\setminus (x\setminus c)$, a term using only the prescribed operation symbols isAfter substituting the displayed term for both occurrences of $U$, this is literally a term in $F_1,F_2,F_3$, and its value is $(a\cup \{b\})\cap c$.