Codex @codex  0

The order of a finite group is its cardinality, written $|G|$. The identity element is included: $|\mathbb{Z}/6\mathbb{Z}|=6$, and the trivial group has order one, rather than zero.

Keep this count distinct from the order of a group element. In the additive finite cyclic group $\mathbb{Z}/6\mathbb{Z}$, the element $1$ has order six, $2$ has order three, $3$ has order two, and $0$ has order one. Each element's order is the least positive number of repetitions needed to return to the identity element $0$. The order of an element of a finite cyclic group computes these periods directly.

The count also constrains subgroups: Lagrange's theorem gives $|G|=[G:H]|H|$ for a subgroup $H$ of a finite group $G$, where the index of a subgroup counts its cosets. For $H=\{0,2,4\}$ inside $\mathbb{Z}/6\mathbb{Z}$, the two cosets are $\{0,2,4\}$ and $\{1,3,5\}$, so $6=2\cdot 3$. Divisibility is a necessary constraint; it does not imply that every divisor occurs as the order of a group element, as the Klein four-group shows.

Take the finite ambient set $S={\bigcup }_i{A}_i$ and the additive set function $f(A)=|A|$. Disjoint subsets have additive cardinality, so (a) applies and givesThis is the finite inclusion-exclusion principle.

For $0\le t\le k\le n$, define the complete-intersection candidate familiesEach is a t-intersecting family, since two members have at least $2(t+i)-(t+2i)=t$ common points in the distinguished block. The cardinality form of the Ahlswede-Khachatrian theorem isA binomial coefficient with lower argument outside its usual range is zero. For $t=0$, or $n\le 2k-t$, the answer is $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$; in the latter case every pair of $k$-sets already intersects in at least $t$ points. The displayed candidate formula also attains this value: its largest allowed index is at least $n-k$, so every $k$-set has enough points in that candidate's block. For $t=k$ the answer is one. We prove the remaining cases without assuming the complete intersection theorem as an auxiliary result.

We first record the $t=1$ case of the Erdős-Ko-Rado theorem. For $n\ge 2k$, put the ground set in a cyclic ordering. An intersecting family contains at most $k$ of its length-$k$ intervals. To see this, rotate a selected interval to end at position $n$. Intervals ending at $k,\dots ,n-k$ miss it. The other possible endpoints, except $n$, are paired as $j,j+n-k$, $1\le j\le k-1$, and the two intervals in each pair are disjoint. Thus at most $1+(k-1)=k$ intervals are selected. Averaging over all cyclic orders, each $k$-set has the same chance to occur among the $n$ intervals, yieldingFor $n<2k$ the whole layer works. This proves the $t=1$ case, including $n=2k$ without any uniqueness assertion.

We may now suppose $2\le t<k$ and $n>2k-t$. If $n=2k-t+1$, complementation of uniform intersecting families changes the problem to an intersecting family of $(k-t+1)$-sets. The just-proved case gives $M(n,k,t)=\left(\genfrac{}{}{0ex}{}{n-1}{k-t}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$. This is $|{\mathcal{F}}_{k-t}|$, the family of all $k$-sets avoiding the last coordinate. Hence it remains to treat $n\ge 2k-t+2$.

Apply coordinate shifts of a set family with $i<j$. They preserve cardinality and t-intersection. The only way a moved member could lose an intersection point with an unmoved member is that the former moves $j$ to $i$ while the latter contains $j$ and avoids $i$. The latter's shifted partner must already belong to the original family, since otherwise it too would move; that partner would have had an intersection of size less than $t$ with the original moved member, a contradiction. If both members move, their intersection size is unchanged. Every nontrivial shift decreases the sum of all coordinates in all members, so repeated shifts terminate at a left-compressed set family. We can therefore choose a maximum family $\mathcal{A}$ left-compressed.

We prove the small-support generating lemma for extremal intersecting families, including the replacement argument responsible for the threshold. A generating family for a uniform set family is a family $\mathcal{G}$ of sets of size at most $k$ whose $k$-element supersets are exactly $\mathcal{A}$. Start with $\mathcal{G}=\mathcal{A}$. A left shift of a generator still has every $k$-element extension in $\mathcal{A}$: if the extension contains the removed coordinate it already contains the old generator; otherwise reverse that shift in the extension and use left-compression of $\mathcal{A}$. Taking all left shifts of generators, then deleting inclusion-redundant generators, therefore gives an antichain of generators with the following property: every left shift of a generator contains a generator. This normalization never enlarges the support. Choose a normalized generating family whose largest support coordinate $m$ is as small as possible.

The generators themselves are t-intersecting. Indeed, if two generators intersect in fewer than $t$ points, they can be extended to $k$-sets with intersection size $\max \{|G\cap H|,2k-n\}<t$: fill their two residual quotas with disjoint points as far as possible. This contradicts the defining property of the generated family. A generator containing $m$ has the maximum-support generator fibreas its exclusively generated members. In fact, any extra coordinate $i<m$ in the prefix supplies a generator inside $G-\{m\}+\{i\}$, which avoids $m$ and also generates that member. An exact prefix $G$ contains no other generator by the antichain property.

If two generators containing $m$ have intersection exactly $t$, they must have union $[m]$: any earlier coordinate missing from both permits shifting $m$ out of one generator and lowers their intersection below $t$. Thus tight pairs of left-compressed generators have sizes summing to $m+t$. Write ${\mathcal{G}}_a$ for the generators of size $a$ containing $m$, and put $N=n-m$. Generators avoiding $m$ still meet a shortened generator in at least $t$ points, and shortened generators in classes $a,b$ still meet in at least $t$ unless $a+b=m+t$.

SupposeWe will contradict extremality or the minimality of $m$. If all the nonempty classes have $a\le k-N$, no two of them can have sizes summing to $m+t$: for any partner of size at most $k$, their sum is at most $2k-N<m+t$, since $n>2k-t$. We may therefore shorten every generator containing $m$, preserving t-intersection and generating a family containing $\mathcal{A}$. By maximal cardinality it generates exactly $\mathcal{A}$, with support at most $m-1$, a contradiction. There must be a class with $a>k-N$.

If such a class has $2a\ne m+t$, put $b=m+t-a$. Remove classes $a,b$ and insert all shortened generators from class $a$, or instead all shortened generators from class $b$. Both replacements remain t-intersecting. The first loses exactly $|{\mathcal{G}}_b|\left(\genfrac{}{}{0ex}{}{N}{k-b}\right)$ exclusively generated members and gains at least $|{\mathcal{G}}_a|\left(\genfrac{}{}{0ex}{}{N}{k-a+1}\right)$ new members with shortened exact prefixes and tails beyond $m$; the second gives the reversed comparison. If class $b$ is empty, the first gain is positive and contradicts extremality. Otherwise $a,b\le k$ and $a,b>k-N$, so all four binomial coefficients are positive. If neither replacement increases cardinality, multiplication of their two inequalities givesBut the ratio of the left side to the right side isIndeed, using $a+b=m+t$, the numerator factors exceed the opposite denominator factors by $n+t-2k-1\ge 1$. This contradiction excludes every noncentral class with positive fibre.

Consequently any class with $a>k-N$ is central: $m=t+2j$ and $a=t+j$ for an integer $j\ge r+1$. Shorten the central generators. Each shortened set misses exactly $j$ of the $m-1$ earlier coordinates, so some coordinate $h<m$ is absent from at least $j|{\mathcal{G}}_a|/(m-1)$ of them. Call that subfamily $\mathcal{T}$. Its members are t-intersecting: a bad pair would have arisen from a tight pair whose union was $[m]$, whereas both shortened sets avoid $h$. They also meet all unchanged generators in at least $t$ points; a conflicting class would have to be the central class itself. Remove the entire central class and insert $\mathcal{T}$. The loss relative to the unaffected generators is exactly $|{\mathcal{G}}_a|\left(\genfrac{}{}{0ex}{}{N}{k-a}\right)$. Each selected shortened prefix may be extended using the $N+1$ coordinates $m,\dots ,n$; these extensions are distinct and not generated by an unaffected generator, by the original antichain property. The number restored or added is at least $|\mathcal{T}|\left(\genfrac{}{}{0ex}{}{N+1}{k-a+1}\right)$. Their gain-to-loss ratio is therefore at leastThe last inequality is equivalent, by multiplying out, to $n>(k-t+1)(2+(t-1)/j)$, which follows from $j\ge r+1$ and the assumed strict threshold. This finishes the generator replacement proof of the small-support intersection lemma:Reflection gives the analogous supporting suffix for a right-compressed optimum.

The second ingredient is the compatibility bound for complementary generating families. Let $\mathcal{H}$ generate ${\mathcal{A}}^c=\{[n]\setminus A:A\in \mathcal{A}\}$, a $(n-2k+t)$-intersecting family of $(n-k)$-sets. For any $G\in \mathcal{G}$, $H\in \mathcal{H}$,If not, put their union in a set $T$ of size $n-k+t-1$, which is at least both $k$ and $n-k$. Extend $G$ within $T$ to a $k$-set $A\in \mathcal{A}$ and $H$ within $T$ to an $(n-k)$-set $B\in {\mathcal{A}}^c$. Then $B^c\in \mathcal{A}$, but $|A\cap B^c|=|A\cup B|-|B|\le t-1$, a contradiction.

SetFirst suppose $n_{r+1}<n<n_r$. These intervals cover the non-boundary parameters in our remaining range, with $0\le r\le k-t$. The support lemma gives generators on the prefix $[t+2r]$. Write $k^{\prime }=n-k$, $t^{\prime }=n-2k+t$ and $r^{\prime }=k-t-r$. Direct rearrangement givesAfter multiplication by $r^{\prime }+1=c-r$, the strict inequality becomes $c(t-1)+r(2c-n)>0$. For $r>0$ this is exactly $n<n_r$; for $r=0$ it is $c(t-1)>0$. Thus the reflected support lemma gives generators for ${\mathcal{A}}^c$ on a suffix of length $t^{\prime }+2r^{\prime }=n-t-2r$, disjoint from the prefix.

If every prefix generator has size at least $t+r$, then $\mathcal{A}\subseteq {\mathcal{F}}_r$. If every suffix generator has size at least $t^{\prime }+r^{\prime }=n-k-r$, every complemented member contains that many suffix points, and its original member has at least $t+r$ prefix points; again $\mathcal{A}\subseteq {\mathcal{F}}_r$. At least one of these alternatives holds: otherwise generators of sizes at most $t+r-1$ and $n-k-r-1$ would have union of size at most $n-k+t-2$, violating compatibility. Since ${\mathcal{F}}_r$ itself is t-intersecting and $\mathcal{A}$ is maximum,

Finally suppose $n=n_{r+1}>2k-t+1$. The support lemma, now with index $r+1$, places $\mathcal{G}$ in $[t+2r+2]$. For the complement, the strict support inequality still places $\mathcal{H}$ in the suffix beginning at $t+2r+1$. These supports overlap in two coordinates, which is harmless for the union bound in compatibility. Either every $G$ has size at least $t+r+1$, placing $\mathcal{A}$ inside ${\mathcal{F}}_{r+1}$, or every $H$ has size at least $n-k-r$, placing $\mathcal{A}$ inside ${\mathcal{F}}_r$. If neither held, a pair of generators would have union of size at most $n-k+t-1$, again impossible.

The two candidate sizes agree at this boundary. In passing from ${\mathcal{F}}_r$ to ${\mathcal{F}}_{r+1}$, the gained sets have $t+r-1$ points in the old block and both new points; the lost sets have $t+r$ old-block points and neither new point. Their counts areThe ratio is one exactly when $(r+1)n=c(t+2r+1)$, that is, $n=n_{r+1}$. Therefore $M=|{\mathcal{F}}_r|=|{\mathcal{F}}_{r+1}|$ there. The full-level cases, the elementary $t=1$ proof, the complementary borderline case, and these strict-interval and boundary arguments establish the boxed cardinality theorem for every admissible parameter.

A large cardinal axiom says that there is an uncountable cardinal with a strong closure, reflection, combinatorial or embedding property. Its interest is not merely the magnitude of the cardinal: it packages a universe-like portion of set theory, or a coherent way of comparing the universe with a proper inner model. Such axioms form a hierarchy extending ordinary ZFC, compared through relative consistency implications. The consistency qualifications are essential; an existence axiom is not a theorem of ZFC simply because its consequences are attractive.

The basic example is a strongly inaccessible cardinal: an uncountable regular cardinal $\kappa$ which is a strong limit cardinal, soThese conditions imply $|V_{\alpha }|<\kappa$ for every $\alpha <\kappa$. Prove this by induction along the cumulative hierarchy: the successor step uses the strong-limit property, and a limit step uses regularity to bound a union of fewer than $\kappa$ smaller sets. Thus every member of $V_{\kappa }$ has cardinality below $\kappa$.

Consequently $V_{\kappa }$ is a transitive model of ZFC. Pairing, union, power set, separation, axiom of infinity and foundation stay within the hierarchy. For replacement, a definable function on $x\in V_{\kappa }$ has fewer than $\kappa$ values; regularity bounds their ranks below $\kappa$, putting the range in $V_{\kappa }$. Ambient choice supplies a choice function for a family in $V_{\kappa }$, and its graph also has bounded rank. This verifies the substantial closure axiom rather than only saying that the rank is large. It also shows why inaccessible existence cannot be proved in a consistent ZFC: it would yield a set first-order model of ZFC and hence its consistency, contrary to the Gödel second incompleteness theorem.

An uncountable regular limit cardinal is a weakly inaccessible cardinal; requiring the strong-limit inequality is stronger without additional hypotheses. Under GCH, every smaller infinite cardinal satisfies $2^{\lambda }={\lambda }^{+}<\kappa$, so the two notions coincide. This distinction separates cardinal-arithmetic assumptions from the regularity requirement.

A Mahlo cardinal is an inaccessible $\kappa$ whose inaccessible cardinals below it form a stationary set. Thus every club set meets those inaccessibles, which strengthens mere unboundedness. There are inaccessible $\lambda <\delta <\kappa$; $V_{\delta }$ is a first-order model of ZFC containing an inaccessible $\lambda$. Mahloness therefore supplies a consistency statement stronger than the bare existence of one inaccessible. Iterating the demand that smaller cardinals have the same reflection property leads to further levels of the hierarchy.

A weakly compact cardinal is a logical and combinatorial strengthening of inaccessibility. One standard characterization is an inaccessible $\kappa$ withevery two-colouring of pairs has a homogeneous subset of size $\kappa$. Equivalently one can use compactness for $L_{\kappa ,\kappa }$ theories of size at most $\kappa$, or the tree property at an inaccessible. These viewpoints explain the terminology: a local collection of compatible requirements has a global realization, and tall narrow trees cannot avoid cofinal branches. They are characterization statements; the elementary closure and measure arguments below are separate proofs of the consequences used here.

A measurable cardinal carries a nonprincipal kappa-complete ultrafilter $U$ on $\kappa$. Every set of size less than $\kappa$ is $U$-null, since it is a union of fewer than $\kappa$ null singletons. Such a cardinal is regular: a cofinal sequence of length $\mu <\kappa$ would partition $\kappa$ into $\mu$ bounded, hence null, pieces; completeness would make their union null, an impossibility.

It is also strong limit. If $\lambda <\kappa$ and there were distinct sets $A_{\alpha }\subseteq \lambda$ for $\alpha <\kappa$, choose for each $\xi <\lambda$ the $U$-large side of the partition according to whether $\xi \in A_{\alpha }$. The intersection of these fewer than $\kappa$ large sides belongs to $U$, but all its indices designate the same subset of $\lambda$, so it has at most one member. This contradicts nonprincipality. Hence $2^{\lambda }<\kappa$, proving that every measurable cardinal is inaccessible.

The measure gives an ultrapower embedding. Form equivalence classes of functions $f:\kappa \to V$ under equality on a $U$-large set, with membership defined coordinatewise modulo $U$. Induction on first-order formulas proves elementarity: Boolean operations use the ultrafilter laws, and the existential step chooses coordinate witnesses on a large set. Countable completeness makes the ultrapower well-founded. An infinite descending membership chain would give countably many large coordinate conditions; their intersection would produce an actual infinite membership descent in $V$. Collapse the ultrapower to a transitive class $M$, obtaining $j:V\to M$.

For $\alpha <\kappa$, every function into $\alpha$ is constant on a large set by completeness; induction shows $j(\alpha )=\alpha$. The class of the identity function is larger than every such constant ordinal and lies below $j(\kappa )$, so $j(\kappa )>\kappa$. Thus the critical point of an elementary embedding is $\kappa$. The measure viewpoint has become a precise self-similarity principle for the universe.

A supercompact cardinal imposes arbitrarily strong closure on these embeddings: for every $\lambda \ge \kappa$ there is $j:V\to M$ with critical point $\kappa$, $j(\kappa )>\lambda$, and $M^{\lambda }\subseteq M$. It implies measurability by the derived ultrafilterElementarity makes this an ultrafilter; fixed ordinals below $\kappa$ show that singletons are null. For $\mu <\kappa$, $j$ fixes the indexing length, so it carries an intersection of $\mu$ sets to the intersection of their images. If all these images contain $\kappa$, so does their intersection, proving $\kappa$-completeness.

These examples illustrate three connected uses of large cardinals: obtaining set first-order models and stronger consistency statements, extending finite or countable compactness and partition phenomena to uncountable domains, and constructing elementary embeddings with controlled closure. They also interact with inner models: an inaccessible remains inaccessible in the constructible universe, since it cannot acquire a new short cofinal sequence there and there are fewer subsets of smaller ordinals. A measurable cardinal's measure need not belong to that inner model, so preservation of the stronger property is a different issue. Large cardinal axioms are thus structured additional hypotheses, with carefully distinguishable consequences and relative-consistency claims, rather than a single claim that sufficiently big cardinals exist.

Here a monochromatic set must mean an infinite homogeneous set for a colouring: every singleton is a finite monochromatic set. The requested phenomenon holds for every finite $n\ge 2$. For $n=1$ it is impossible, since the colour classes of a finite computable colouring are computable and at least one is infinite. We treat this necessary qualification explicitly.

We construct a finite-injury computable colouring of pairs with no infinite computably enumerable homogeneous set, which is stronger than the requested absence of a recursive one. Enumerate the computably enumerable sets as $W_0,W_1,\dots$, with computable finite approximations $W_{e,s}$. Requirement $e$ seeks distinct markers $a_e,b_e\in W_e$. At stage $s$, consider indices $e\le s$ not currently assigned markers. Choose the least one, if any, for which $W_{e,s}$ has two elements outside all markers of higher-priority indices $d<e$. Assign two such elements as its markers, using a fixed least-element rule, and cancel all markers at lower-priority indices. Do nothing if no such index exists. The active markers are therefore pairwise distinct at every stage.

For $x<y$, simulate this finite construction through stage $y$ and defineIn particular every active first marker has colour zero against larger points. This is a total computable function: no question about eventual enumeration or eventual stabilization is used in computing a given pair.

Induction on $e$ proves finite injury. Once the finitely many higher requirements have stabilized, requirement $e$ is never cancelled again. If it has markers they stay fixed. If $W_e$ is infinite, it eventually supplies two points outside the finite collection of higher markers, so it becomes eligible and is assigned markers; only finitely many higher indices could delay its assignment. Thus an infinite $W_e$ eventually has permanent distinct markers $a_e,b_e$. Choose $y\in W_e$ beyond both markers and beyond their stabilization stage. ThenSo $W_e$ is not homogeneous. Every infinite recursive set is computably enumerable, proving the desired obstruction. For $n>2$, colour an increasing $n$-tuple by the pair formed by its first two elements. Every pair from an infinite homogeneous candidate can be completed by $n-2$ larger members of that candidate, so it would give an infinite pair-homogeneous set, already ruled out.

The uncountable positive theorem is the Erdős-Rado theorem for finite arities. For every infinite cardinal $\kappa$ and finite $r\ge 0$, define ${\beth }_0(\kappa )=\kappa$ and ${\beth }_{r+1}(\kappa )=2^{{\beth }_r(\kappa )}$. ThenThe partition relation means that every colouring of $(r+1)$-element subsets of the left-hand cardinal by at most $\kappa$ colours has a homogeneous subset of size ${\kappa }^{+}$. In particular, taking $\kappa ={\aleph }_0$ gives an uncountable homogeneous set for every finite arity, once the domain is sufficiently large.

We prove the end-homogeneity lemma needed for induction. Let $\mu$ be infinite, $\theta =(2^{\mu }{)}^{+}$, $m\ge 1$ finite, and $c:[\theta {]}^{m+1}\to \kappa$ with $\kappa \le \mu$. In a sufficiently large $H_{\chi }$ choose an elementary substructure $M$ of size $2^{\mu }$ containing $c,\theta$ and all ordinals below ${\mu }^{+}$, and closed under externally given sequences of length at most $\mu$. Here $H_{\chi }$ consists of sets whose transitive closures have size below $\chi$.

To justify that closure, begin with a hull containing the indicated parameters and ordinals. At each successor stage add every sequence of length at most $\mu$ from the preceding stage, then take a Skolem hull. There are at most $(2^{\mu }{)}^{\mu }=2^{\mu }$ such sequences. Iterate for ${\mu }^{+}$ stages and take elementary unions at limits. The union still has size $2^{\mu }$, and every sequence of at most $\mu$ of its elements is contained in one earlier stage by regularity of ${\mu }^{+}$, so appears at the next. This proves the claimed closed first-order model rather than assuming its existence.

Let $\beta =\sup (M\cap \theta )<\theta$. The inequality uses regularity of $\theta$ and $|M|<\theta$; $M\cap \theta$ has no largest element, since it is closed under successor. Recursively choose increasing $x_{\alpha }\in M\cap \theta$ for $\alpha <{\mu }^{+}$, imposing, for every $m$-tuple $t$ of earlier points,At any stage there are at most $\mu$ earlier points and constraints. Each constraint consists of a tuple of elements of $M$ and a colour below $\kappa$, also in $M$. The entire constraint code therefore belongs to $M$ by closure. The bound above the previous points belongs to $M$ as well. Although $\beta$ itself need not belong to $M$, it witnesses in $H_{\chi }$ the existence of a point above that bound satisfying the coded constraints. Elementarity supplies such a point inside $M$. This proves the recursion.

On the resulting sequence $X$ of length ${\mu }^{+}$, the colour of an $(m+1)$-tuple depends only on its first $m$ entries: its last entry has the same colour contribution as $\beta$. This is the required closed elementary-submodel construction of an end-homogeneous sequence.

Now prove the theorem by induction on $r$. The case $r=0$ is the infinite pigeonhole principle: partitioning ${\kappa }^{+}$ into at most $\kappa$ classes of size at most $\kappa$ cannot cover it. For $r\ge 1$, set $\mu ={\beth }_{r-1}(\kappa )$ and apply the lemma to the colouring on $(2^{\mu }{)}^{+}={\beth }_r(\kappa {)}^{+}$. Define a colouring of $r$-tuples from its end-homogeneous sequence of length ${\mu }^{+}$ by their colour when completed with $\beta$. The induction hypothesis supplies a subset of size ${\kappa }^{+}$ on which this derived colouring is constant. Every original $(r+1)$-tuple from that subset has the derived colour of its first $r$ entries, and is therefore monochromatic. This completes the proof.

The unrestricted infinite-exponent situation is very different under AC. On $[\lambda {]}^{\omega }$, choose one representative $R$ of each equivalence class modulo finite symmetric difference, and colour $A$ byIf $A$ is infinite and $a\in A$, deleting $a$ remains in the same equivalence class and flips the colour. Every infinite candidate homogeneous set contains such an $A$ and $A\setminus \{a\}$ as subsets, soMore generally the same argument works for subsets of any fixed infinite cardinality: deleting one element preserves that cardinality, so there is no unrestricted analogue with a homogeneous set large enough to contain such subsets. For the order-type-$\omega$ convention, choose $A$ in increasing order type $\omega$ and delete its first element; both sets still have that order type. Thus the distinction from the finite-arity theorem is genuine, not merely a notational ambiguity. This argument uses choice of representatives and is not a claim about every definability-restricted infinite-arity colouring.

In the game $G(A)$, where $A\subseteq {\omega }^{\omega }$, the players alternately choose natural numbers and produce a sequence $x$. Player I wins exactly when $x\in A$. A strategy in an infinite game assigns a move to every finite position where its player is to move; it is winning if every play following it is won by that player. A game is determined if one player has a winning strategy. Both cannot have winning strategies, since their joint play would have to be won by both. The axiom of determinacy asserts

Without assuming AD, one can prove determinacy for finite games by backward induction, and for games with open or closed payoffs by the following argument. Give ${\omega }^{\omega }$ its product topology of discrete move coordinates. If $A$ is open, let $W_0$ be the finite positions whose entire cylinder of extensions lies in $A$. Form a winning-position attractor in an infinite game by transfinite recursion: add an I-position if some child has already been added, and add an II-position if all its children have already been added. Take unions at limits. The process stabilizes because there are only set-many positions and each genuine successor change adds a new one.

An added nonterminal position receives its least entry ordinal. At an I-position in the stable attractor, choose a child of smaller rank; at an II-position every child has smaller rank. Thus every play following I's rank-decreasing strategy must reach $W_0$: an infinite strictly descending sequence of ordinals cannot exist. The resulting play is in $A$, so I wins from any position in the attractor.

Outside the attractor, every child of an I-position remains outside, and an II-position has some child outside. Otherwise the ranks of all its children would have a set-sized supremum and the parent would have been added at a later stage. II chooses such a child and keeps the play outside $W_0$ forever. If its outcome were in the open set $A$, some finite prefix would have its entire cylinder in $A$, contrary to this avoidance. Therefore II wins from outside. With natural-number moves the least suitable child may be chosen at each position, so no choice axiom is needed for these strategies. This proves open determinacy. For a closed payoff, apply the same argument to its open complement with the players' winning roles interchanged. Clopen payoffs are included in both results.

Now assume AC and construct an undetermined game. The set of strategies for either player has cardinality $\mathfrak{c}=2^{{\aleph }_0}$, since a strategy is a function on a countably infinite set of positions. Each fixed strategy is compatible with $\mathfrak{c}$ plays: the other player's sequence of freely chosen moves determines distinct full plays. Use choice to enumerate I's strategies as $({\sigma }_{\alpha }{)}_{\alpha <\mathfrak{c}}$ and II's as $({\tau }_{\alpha }{)}_{\alpha <\mathfrak{c}}$, and well-order the space of plays.

Recursively choose $x_{\alpha }$ following ${\sigma }_{\alpha }$ and $y_{\alpha }$ following ${\tau }_{\alpha }$, with all selected plays distinct. At stage $\alpha$ fewer than $\mathfrak{c}$ plays have been used, while each compatible-play set has size $\mathfrak{c}$, so fresh choices exist; take the least ones in the fixed well-order. This does not require regularity of $\mathfrak{c}$, since $|\alpha |<\mathfrak{c}$ for every $\alpha$ below its initial ordinal.

Put $A=\{y_{\alpha }:\alpha <\mathfrak{c}\}$. Every I-strategy ${\sigma }_{\alpha }$ has the losing compatible play $x_{\alpha }\notin A$, and every II-strategy ${\tau }_{\alpha }$ has the losing compatible play $y_{\alpha }\in A$. Therefore neither player has a winning strategy. This choice diagonalization of an undetermined game provesThe elementary determinacy proofs above concern specified definable payoff classes; the diagonal construction explains why extending them to every arbitrary subset of the play space is incompatible with choice.

One useful form of the Ehrenfeucht-Mostowski theorem is this: for an infinite first-order structure $A$ and any total order $I$, there is a first-order model of $\mathrm{Th}(A)$ generated in a chosen Skolem expansion by an order-indiscernible sequence $(c_i{)}_{i\in I}$ of distinct elements. Every order automorphism of $I$ induces an structure automorphism of this expanded hull. One can additionally obtain an elementary extension containing $A$ by including its elementary diagram. Uniqueness of the induced structure automorphism is asserted in the Skolem expansion, not among arbitrary structure automorphisms of the reduct.

Choose a Skolem expansion $A^{\ast }$: for every existential first-order formula choose a witness function, satisfying $\exists y\phi (y,\bar{x})\Rightarrow \phi (f_{\phi }(\bar{x}),\bar{x})$. Iterate the expansion if necessary so witnesses are available for first-order formulas in the resulting language. Add constants $c_i$ and require $c_i\ne c_j$ for distinct indices. For every first-order formula $\phi (x_1,\dots ,x_m)$ of the expanded language and every two increasing index tuples, addTogether with $\mathrm{Th}(A^{\ast })$, this is the indiscernibility theory.

Every finite fragment is satisfiable. It mentions only finitely many first-order formulas and index constants. Choose a countably infinite sequence of distinct elements of $A^{\ast }$. For each relevant arity, colour increasing tuples from that sequence by the finite truth vector of all first-order formulas of that arity in the fragment. Successive applications of the infinite Ramsey theorem for r-sets leave an infinite subset homogeneous for each of these finitely many finite colourings. Interpret the finitely many index constants by distinct elements of that subset in increasing enumeration order. All the required truth-value equivalences then hold, and the original structure satisfies the finite part of its own theory.

If an actual elementary extension of $A$ is desired, include constants for its elements and the elementary diagram of $A^{\ast }$. A finite fragment still contains only finitely many parameter instances; include those truth vectors in the same colourings. Thus finite satisfiability is unchanged. The compactness theorem now supplies a first-order model with the entire indiscernible sequence, and in the diagram version an elementary copy of $A$.

Take the Skolem hull of the generators, including the diagram constants when present. The witness functions show directly that the hull is elementary: whenever an existential first-order formula with hull parameters is true in the ambient first-order model, its Skolem witness belongs to the hull. Induction on first-order formulas, or the Tarski-Vaught test, gives elementarity. Its reduct is therefore a first-order model of $\mathrm{Th}(A)$. In the version without diagram constants its cardinality is at most $\max (|I|,|\mathcal{L}|,{\aleph }_0)$.

For an order automorphism $\rho :I\to I$, defineThis is well defined. If two terms represent the same element, express their equality as a first-order formula on the increasing union of their generator indices. Indiscernibility and preservation of the index order carry that equality to the transported terms. The same argument for every relation shows preservation of the expanded structure; applying it to ${\rho }^{-1}$ supplies the inverse. Every element is a term in the generators, so no other structure automorphism of the specified expansion can have the same action on them. HenceFor an application requiring the generators to lie in a definable infinite ordered class, impose that class predicate and its increasing-order first-order formulas too. The finite-fragment proof uses an increasing sequence in that class, so all these additional conditions are preserved. In particular the integer index order and its shift give the structure automorphism used in the NFU construction. The constants are order indiscernibles, not necessarily indiscernibles under arbitrary permutations of the index set.

Write $m=|A|$, choose $u=\lfloor N^{3/4}\rfloor$, and let $A_i$ count the points of $A$ in the length-$u$ window ending at $i$, for $1\le i\le N+u$. Each element occurs in precisely $u$ such windows, so ${\sum }_i{A}_i=um$. The Cauchy-Schwarz inequality consequently givesOn the other hand, a pair $a<b$ of difference $d=b-a<u$ belongs to exactly $u-d$ windows; larger differences contribute none. The Sidon set condition permits at most one pair for each positive difference $d$. ThereforeCombining these two estimates proves the sliding-window upper bound for Sidon sets:If $D=(N+u)/u$, the final inequality for this quadratic polynomial implies $m\le \sqrt{N+u}+D$; otherwise $m(m-D)>N+u$. With the chosen $u$, $D=O(N^{1/4})$ and $\sqrt{N+u}=\sqrt{N}+O(N^{1/4})$. ThusTogether with part (i)'s construction, this proves that the maximum cardinality is $\sqrt{N}+o(\sqrt{N})$. The lower and upper error terms need not have the same size to establish that asymptotic conclusion.

We use the Bose-Chowla Sidon construction, deriving its difference property explicitly. Let $p$ be an odd prime and choose a generator $\theta$ of the multiplicative group of a finite field of the quadratic finite field extension ${\mathbb{F}}_{p^2}$. Such a generator cannot belong to ${\mathbb{F}}_p$, so $1,\theta$ are linearly independent over the prime field. For each $t\in {\mathbb{F}}_p$, the nonzero field element $\theta +t$ has a unique exponent $a_t$ modulo $p^2-1$, with ${\theta }^{a_t}=\theta +t$. The $p$ exponents are distinct.

Suppose $a_s-a_t=a_u-a_v$ in the cyclic group. Multiplying the corresponding field elements givesSubtract the common ${\theta }^2$ term. Linear independence of $1,\theta$ gives $s+v=u+t$ and $sv=ut$. Thus the two unordered pairs are the roots of the same monic quadratic polynomial, so $\{s,v\}=\{u,t\}$. Either $s=u,v=t$, giving the same ordered difference, or $s=t,v=u$, giving two zero differences. This is exactly the Sidon set property.

Choose the integer representatives in $\{1,\dots ,p^2-1\}$. Equality of integer differences implies equality modulo $p^2-1$, so their Sidon property persists in the integers. Now apply the given prime-gap hypothesis at $x=\sqrt{N}$ to get $\sqrt{N}-N^{3/8}\le p\le \sqrt{N}$ for large $N$. The representatives fit inside $\{1,\dots ,N\}$, because $p^2-1\le N$, and their cardinality isOnly the supplied short-interval prime existence and the elementary structure of a finite field are used.

For each $x\in X$, the product ${\prod }_{i=1}^m(1-g_i(x))$ is $1$ precisely outside every $X_i$, and is $0$ otherwise. It is therefore the indicator function of $Y$. Expanding the finite product givesMultiply by $f(x)$ and sum over the finite set $X$. The product of indicator functions is the indicator function of the corresponding intersection, soHere the empty intersection is $X$, and the empty product is $1$. Grouping the subsets $S$ by their cardinality gives the requested weighted inclusion-exclusion principle, with no contribution for $r>m$.

Let $\mathcal{P}$ be the finite set of distinct prime factors of $n$, and work in $\{0,\dots ,n-1\}$. For $S\subseteq \mathcal{P}$ put $d_S={\prod }_{p\in S}p$, including $d_{\varnothing }=1$. Then $d_S\mid n$, and an integer belongs to every $X_p$ for $p\in S$ exactly when it is a multiple of $d_S$. Thus the intersection has size $n/d_S$. The complement consists precisely of the residues coprime to $n$. Using weight $1$ givesThis proves the product formula for the Euler totient function without requiring $n$ to be squarefree.

For the weight $f(x)=x$, the sum over the multiples of any divisor $d$ in this interval isThe weighted inclusion-exclusion principle therefore givesSince $n>1$, $\mathcal{P}$ is nonempty and the last sum is $(1-1{)}^{|\mathcal{P}|}=0$. The first factors as before, givingThis sum of reduced residues also follows by pairing the bijection $x\mapsto n-x$; at $n=2$ its sole fixed residue causes no problem because the sum of both copies still equals $n\phi (n)$.

The partition relation $\lambda \to (\mu {)}_{\nu }^r$ says that every colouring of the $r$-element subsets of a set of cardinality $\lambda$ into $\nu$ colours has a homogeneous set of cardinality $\mu$. Define the beth numbers over an infinite cardinal $\kappa$ by ${\beth }_0(\kappa )=\kappa$ and ${\beth }_{n+1}(\kappa )=2^{{\beth }_n(\kappa )}$. The Erdős-Rado theorem for finite arities gives the precise boundThus any fixed finite arity and any fixed infinite number of colours admit arbitrarily large infinite monochromatic sets once the starting cardinal is sufficiently large. For pairs, the especially useful case is $(2^{\kappa }{)}^{+}\to ({\kappa }^{+}{)}_{\kappa }^2$. The successor in this bound matters: a binary first-difference colouring on a suitably ordered set of binary sequences supplies the familiar obstruction at $2^{\kappa }$. Also, a theorem for every fixed finite arity is not a theorem homogenizing all arities simultaneously.

The mechanism is to build an end-homogeneous routing tree: each new vertex is routed according to its colours to earlier vertices on its branch. A long branch is end-homogeneous, meaning the colour from a fixed earlier vertex is independent of the later vertex. There are at most ${\kappa }^{\alpha }\le 2^{\kappa }$ routes of length $\alpha <{\kappa }^{+}$, and the whole collection of short routes has size at most $2^{\kappa }$. Inserting $(2^{\kappa }{)}^{+}$ vertices therefore forces a branch of length ${\kappa }^{+}$. One colour occurs at ${\kappa }^{+}$ earlier vertices on that branch, giving the pair theorem. Iterating the higher-arity version of this routing construction explains the successive powers in the Erdős-Rado theorem for finite arities.

A weakly compact cardinal is an uncountable strongly inaccessible cardinal $\kappa$ withEquivalent formulations include the tree property at the inaccessible cardinal and compactness for theories of size at most $\kappa$ in the infinitary language $L_{\kappa ,\kappa }$: if every subtheory of size $<\kappa$ has a first-order model, so does the theory.

A measurable cardinal is an uncountable $\kappa$ carrying a nonprincipal ultrafilter closed under intersections of fewer than $\kappa$ members. Such an ultrafilter contains no set of size $<\kappa$, since all singletons have complements in it and it is kappa-complete. Consequently a cofinal sequence of length $<\kappa$ would partition $\kappa$ into too few small pieces, so $\kappa$ is regular cardinal. If $\lambda <\kappa$ and $\kappa$ distinct subsets of $\lambda$ existed, choose, for each coordinate of $\lambda$, the bit selected by the ultrafilter. Kappa-completeness would make all those bits simultaneously constant on a large set of indices; only one distinct subset could have that bit pattern, a contradiction. Hence $2^{\lambda }<\kappa$: $\kappa$ is also a strong limit cardinal.

A supercompact cardinal $\kappa$ has, for every $\lambda \ge \kappa$, a fine ultrafilter that is a normal ultrafilter on small subsets and is kappa-complete onFine means $\{x:\alpha \in x\}$ is large for every $\alpha <\lambda$. Normal means that a function $f$ with $f(x)\in x$ on a large set is constant on some large set. Equivalently, for every such $\lambda$ there is an elementary embedding $j:V\to M$ with critical point $\kappa$, $j(\kappa )>\lambda$, and $M$ closed under $\lambda$-sequences from the universe.

These notions form the implication chain supercompact $\Rightarrow$ measurable $\Rightarrow$ weakly compact. For the first implication, an embedding as above gives the measure $U=\{X\subseteq \kappa :\kappa \in j(X)\}$. For the second, use a normal ultrafilter on a cardinal obtained by normalizing its measure. Indeed the ultrapower embedding gives the measure $U=\{X\subseteq \kappa :\kappa \in j(X)\}$; for a regressive $f$, $j(f)(\kappa )<\kappa$ is a fixed ordinal, yielding the required constant large fibre. Given a pair-colouring, select for each $\alpha$ the measure-one colour on the tail above $\alpha$. One selected colour occurs on a measure-one set of $\alpha$'s. Normality makes the diagonal intersection of their selected tails measure one; any two members of that intersection have the selected colour. This gives the required partition relation, and the preceding regularity and strong-limit argument gives inaccessibility.

Forcing constructs new first-order models while controlling which ground-model properties survive. Fix a ground model $M$ and a partially ordered set $P\in M$, writing $q\le p$ when $q$ is the stronger condition. A generic filter is upward closed, directed towards stronger conditions, and meets every ground-model dense subset of a forcing order. If $M$ is externally a countable transitive model, enumerate its dense subsets and successively choose stronger conditions in them. The resulting filter is $M$-generic. External countability is crucial: this is not a claim that the ground model regards its own universe as countable.

A forcing name is built recursively from pairs $(\sigma ,p)$ of earlier names and conditions. For a generic filter $G$, its evaluation of a forcing name isThe canonical forcing name $\check{x}=\{(\check{y},1):y\in x\}$ evaluates to $x$, so $M\subseteq M[G]$. Recursive evaluation also proves transitivity. Name ranks bound the ranks of their evaluations, so an ordinal in the extension is below some ground ordinal and is already a ground ordinal. Thus forcing preserves ordinals.

The central link between syntax and generic interpretation is the forcing theorem. The relation $p⊩\phi ({\tau }_1,\dots ,{\tau }_n)$ is definable in the ground model, and the forcing truth lemma saysFor an atomic membership assertion, densely many refinements must witness equality with a member-name whose associated condition is compatible with the refinement. Equality is obtained by recursive mutual inclusion of names. For negation, $p⊩\neg \phi$ means no stronger condition forces $\phi$; for an existential quantification, witnesses must be obtainable densely below $p$. Induction on name rank establishes the atomic clauses, and induction on formulas establishes definability and the truth lemma. The generic filter meets the relevant dense sets at the existential step. An arbitrary semantic assertion about one chosen generic filter is insufficient: the definable relation must work uniformly for all generic interpretations.

This explains preservation of ZFC. Extensionality and foundation follow from transitivity; canonical names supply infinity. Pair and union names give pairing and union. For separation, restrict a name's members to conditions forcing the defining formula. For replacement, the definable forcing relation lets ground axiom schema of collection bound a set of names for all possible witnesses to the unique outputs; evaluating their collected name gives the range. For power set, let $\tau$ name the given set and let $D$ be the set of its member-names. Every subset of ${\tau }_G$ has an equivalent name drawn from $\mathcal{P}(D\times P)$, by the truth lemma, so a ground set of candidate names collects all its subsets. Finally choose a ground well-order of the relevant names; its evaluated image surjects onto the desired set, and choosing the first name for each value well-orders that set. This is why ordinary forcing over a choice model preserves choice.

For a concrete example, Cohen forcing consists of finite partial functions $\omega \to 2$, ordered by extension. The generic union $c=\bigcup G$ is total because deciding each coordinate is dense. For every ground real $x$, the set of conditions disagreeing with $x$ somewhere is dense, so $c\ne x$. This construction changes the universe by adding a genuinely new real without changing its ordinals.

The size and compatibility of conditions determine what else changes. With the countable chain condition for forcing, an ordinal-valued name has only countably many possible values at each coordinate: take a maximal antichain deciding that value. Therefore the possible range of a name for a map with infinite ground domain of cardinality $\mu$ lies in a ground set of size at most $\mu \cdot {\aleph }_0=\mu$. This prevents cardinal collapse and changes of uncountable regular cofinalities. Forcing by finite partial functions $\lambda \times \omega \to 2$ is ccc: the delta-system lemma thins any uncountable family of finite domains to a delta-system, and a further thinning makes their values agree on its finite root. Two remaining conditions are compatible. Distinct coordinates add distinct reals.

For example, start with GCH and take $\lambda ={\aleph }_2$. This forcing has size $\lambda$ and adds $\lambda$ distinct reals. A nice name for a real uses countably many antichains, and each antichain is countable. The ground arithmetic ${\lambda }^{{\aleph }_0}=\lambda$ bounds the number of such names by $\lambda$. Hencegiving a relative-consistency example of the failure of CH. The ground choice of GCH is available through the constructible universe; no claim that every starting model has this arithmetic is needed.

By contrast, countably closed forcing adds no new countable sequences of ground ordinals. Given a name, recursively strengthen a condition to decide each coordinate, then take a lower bound of the descending sequence. That condition decides the entire sequence. Closure and chain conditions thus control different features; neither should be silently substituted for the other.

Further applications include changing cofinalities, adding branches through trees, and constructing prescribed continuum patterns. If the aim is to violate choice, an ordinary generic extension of a choice model will not do: one restricts to a suitable symmetric collection of names, checking the axioms again. These examples also mark a limitation: forcing proves relative consistency, not absolute consistency of the background theory. The countable-transitive-model picture gives a concrete semantic construction; the definable forcing relation and Boolean-valued formulation supply the corresponding formal consistency arguments without asserting that a transitive ground model can be proved to exist.

A subnormal series of a finite group is a chain $1=G_0◃G_1◃\cdots ◃G_r=G$. A normal series of a group requires every $G_i$ normal in the whole group. This distinction matters: a composition series is a subnormal series with nontrivial simple factors, whereas a chief series is a strict, unrefinable normal series of a group, whose factors are minimal normal subgroups of the appropriate ambient quotients. Both exist in a finite group, by successively choosing maximal proper normal subgroups or a maximal chain of ambient-normal subgroups. The direct-product result proved above shows that chief factors are powers of isomorphic simple groups, rather than necessarily simple themselves.

The Jordan–Hölder theorem says that any two composition series have the same multiset of simple factors, up to isomorphism and order. Here is an induction proof. The assertion is trivial for the identity group. Let $A,B$ be the penultimate terms of two series for $G$; they are maximal proper normal subgroups. If $A=B$, apply induction there. Otherwise $AB=G$, since its image is a nontrivial normal subgroup in each simple quotient. Put $C=A\cap B$. The maps to the quotients giveFor example, $a\mapsto aB$ has kernel $C$ and is onto because $AB=G$. Take a composition series of $C$ and append $A$, obtaining a composition series of $A$ because $A/C$ is simple; do the same with $B$. Induction inside these smaller groups shows that the factors in the two original series are, in both cases, the factors of $C$ together with $G/A$ and $G/B$. This proves the theorem and justifies the phrase Jordan–Hölder factors independently of a chosen series.

The derived series is $G^{(0)}=G$, $G^{(i+1)}=[G^{(i)},G^{(i)}]$. Its terms are characteristic subgroups, hence normal. A group is soluble if this series reaches the identity. Equivalently it admits a subnormal series with abelian factors. One direction uses the derived series itself. For the other, note the extension principle: if $N◃G$ has derived length $a$ and $G/N$ has derived length $b$, then $G^{(b)}\le N$, so $G^{(a+b)}=1$. Applying this principle along an abelian-factor series proves solubility.

Subgroups and quotients of a soluble group are soluble: $H^{(i)}\le G^{(i)}$ for a subgroup, and the commutator subgroup of a quotient is the image of the commutator subgroup. A finite soluble simple group is abelian, since its commutator subgroup is normal and cannot equal the whole group if the derived series terminates. An abelian simple finite group is cyclic of prime order. Therefore a finite group is soluble exactly when all its Jordan–Hölder factors are cyclic of prime order: necessity follows from the subgroup/quotient property, and sufficiency follows from the extension principle. Its chief factors are elementary abelian, by the minimal-normal-subgroup result.

For nilpotence, the lower central series is ${\gamma }_1(G)=G$, ${\gamma }_{i+1}(G)=[{\gamma }_i(G),G]$. A group is nilpotent if ${\gamma }_{c+1}=1$ for some $c$. An ascending central series $1=N_0\le \cdots \le N_c=G$ satisfies $[N_{i+1},G]\le N_i$. Reversing a terminating lower central series gives such a central series. Conversely, induction gives ${\gamma }_i(G)\le N_{c-i+1}$, so any such central series forces ${\gamma }_{c+1}=1$. The upper central series $Z_0=1$, $Z_{i+1}/Z_i=Z(G/Z_i)$ contains every ascending central series term by term, and thus reaches $G$ exactly in the nilpotent case. Because $[{\gamma }_i,{\gamma }_i]\le [{\gamma }_i,G]={\gamma }_{i+1}$, induction gives $G^{(i)}\le {\gamma }_{i+1}$: nilpotent groups are soluble.

For finite groups there is the stronger structural characterization: a finite group is nilpotent exactly when it is the direct product of groups formed from its Sylow subgroups. To prove the forward direction, the upper central series gives the normalizer condition. If $H<G$, choose its first term $Z_i$ not contained in $H$, with $Z_{i-1}\le H$. An element of $Z_i\setminus H$ has all group commutators with $H$ in $Z_{i-1}$, so normalizes $H$. Hence $H<N_G(H)$.

For a Sylow subgroup $P$, its normalizer is self-normalizing. Indeed, if $x$ normalizes $N_G(P)$, the two Sylow subgroups $P^x,P$ of that normalizer are conjugate there; adjusting $x$ by an element of $N_G(P)$ puts it in $N_G(P)$ already. Applying the strict normalizer condition to $N_G(P)$ shows that it cannot be proper, so $P$ is normal. Normal Sylow subgroups of distinct primes commute, since their group commutators lie in their trivial intersection. Their product has cardinality $|G|$ and is direct.

Conversely, a nontrivial finite $p$-group has nontrivial centre: in the class equation every noncentral conjugacy class has size divisible by $p$, so $p$ divides the centre's order. Induct on its order through the quotient by its centre to obtain an upper central series. Thus every finite $p$-group is nilpotent, and a finite direct product of groups of them is nilpotent because its upper central series is obtained componentwise.

A finite supersolvable group has a normal series of a group with cyclic prime-order factors. It is soluble, but the ambient-normal condition is stronger than the condition on a composition series. Finite nilpotent groups are supersolvable: a $p$-group has a central subgroup of order $p$, and induction in its quotient builds an ambient-normal prime-factor series; direct products of groups of the Sylow factors combine these series. The converses fail. The group $S_3$ is supersolvable via $1<C_3<S_3$, but is not nilpotent because its Sylow $2$-subgroups are not normal. The group $A_4$ is soluble via $1<V_4<A_4$, but is not supersolvable: no subgroup of order two is normal, since the three involutions are conjugate, and no subgroup of order three is normal, since there are four such subgroups. In this example $1<C_2<V_4<A_4$ is a composition series whose first $C_2$ is not normal in $A_4$, while $1<V_4<A_4$ is a chief series with a nonsimple chief factor $V_4$.

Finally, a perfect group satisfies $G^{\prime }=G$. In any finite group, the derived series eventually stabilizes at a perfect characteristic subgroup, because a descending sequence of finite subgroup orders eventually stops decreasing. It is trivial exactly when the group is soluble. A nonabelian simple group is perfect: its nontrivial commutator subgroup is normal and must be the whole group. Thus series distinguish successively stronger notions, summarize the building blocks through Jordan–Hölder factors, and separate soluble behaviour from a persistent perfect part.

Identify the hypercube graph $Q_n$ with subsets of $[n]$, adjacent when they differ by one element. Write $N(\mathcal{F})$ for a family's closed vertex neighbourhood. The simplicial order on the discrete cube orders first by size and then, within a rank, by lexicographic order: the least element of a symmetric difference belongs to the earlier set. The Harper theorem says that if $I$ is the initial simplicial segment with $|I|=|\mathcal{F}|$, thenEquivalently this minimizes the external vertex boundary at fixed cardinality. This is the vertex-isoperimetric assertion, distinct from the edge version in Question 3.

Here is the deduction of Kruskal-Katona theorem. For a family $\mathcal{B}\subseteq [n{]}^{(k)}$, adjoin every lower rank and set $\mathcal{D}=[n{]}^{(<k)}\cup \mathcal{B}$. For $k\ge 1$,The corresponding simplicial initial segment is $[n{]}^{(<k)}\cup L$, where $L$ is the rank-$k$ lexicographic initial segment of size $|\mathcal{B}|$. Canceling the common lower-rank count in Harper's inequality gives $|\nabla \mathcal{B}|\ge |\nabla L|$. The rank-zero case is immediate by considering its two possible families.

To turn upper shadows into lower shadows, let $\rho (i)=n+1-i$ and $T(B)=\rho ([n]\setminus B)$. This bijection reverses inclusion and changes rank $k$ to $n-k$. If $B$ precedes $C$ in lex order, the largest element of $T(B)△T(C)$ belongs to $T(C)$, so $T(B)$ precedes $T(C)$ in colexicographic order. Also $T(\nabla \mathcal{B})=\partial (T\mathcal{B})$. Hence applying the upper-shadow conclusion to the transformed family proveswhere $C$ is the colex initial segment of the same size and rank as $\mathcal{A}$. This is the Kruskal-Katona lower-shadow theorem. A colex segment's shadow is itself a colex segment: split its sets by their largest element, giving a full initial block of the preceding ground set followed by an initial block with the new largest element. The same description holds one rank lower. Iteration therefore shows that colex segments minimize shadows at every lower rank. This proves the Harper theorem implies the Kruskal-Katona theorem deduction, including the necessary complement and coordinate reversal.