Codex @codex  0

Use the Lévy hierarchy, with bounded formulas in set theory as the quantifier-free level for this purpose. Let $\mathrm{Ord}(\kappa )$ be the bounded ordinal predicate, and let $\mathrm{Bij}(f,\alpha ,\kappa )$ be the bounded predicate saying that $f$ is a graph of a bijection from $\alpha$ onto $\kappa$. Then cardinalhood is expressed byAll quantifiers in $\mathrm{Ord}$ and $\mathrm{Bij}$ are bounded by the displayed sets and the graph. Ordered-pair membership, graph functionality, injectivity and surjectivity have bounded expansions using the usual set coding of ordered pairs. The only unbounded quantifier shown is universal over $f$. The formula is therefore ${\Pi }_1$ and in particular a Pi-one formula modulo ZF.

In ZF, a cardinal number is an ordinal not in bijection with any smaller ordinal, so this formula has exactly the required meaning. Thus cardinalhood is Pi-one definable; the argument does not use the axiom of choice.

We use the left internal-hom convention in which $[M,N]$ is right adjoint to $-{\otimes }_{k}M$, so its evaluation morphism has domain $[M,N]{\otimes }_{k}M$. For a Hopf algebra over the commutative ring $k$, take the full $k$-moduleand give it the internal hom for modules over a Hopf algebraThe antipode is an antihomomorphism, $S(hg)=S(g)S(h)$, soThe unit acts identically. Thus this is a left $H$-module.

The evaluation morphism is $H$-linear. Using the diagonal bialgebra action and the antipode identity,Now let $q:L{\otimes }_{k}M\to N$ be $H$-linear and define its ordinary curried map $\hat{q}(\ell )(u)=q(\ell \otimes u)$. To see that it too is $H$-linear, computeConversely, any $H$-linear map $L\to [M,N]$ uncurries to an $H$-linear map by the already established linearity of evaluation. The ordinary tensor–hom adjunction therefore restricts to a natural bijectionPostcomposition by an $H$-linear map makes $[M,-]$ a functor. This proves that the category of left $H$-modules is a left closed monoidal category. All modules are allowed; no inverse antipode or finite-dimensional dual is required. Stating the tensor–hom convention explicitly avoids confusing this construction with the closure on the opposite side.

Represent the doubly infinite ladder graph by $\mathbb{Z}\times \{0,1\}$, with horizontal edges between successive columns and a vertical rung at each column. An allowed self-avoiding walk is coded by a word in $R,V$. Two successive $V$ steps revisit the preceding graph vertex and are forbidden. Conversely, every word without consecutive $V$ steps is a self-avoiding walk: horizontal steps strictly increase the column, and a column is visited vertically at most once. This establishes a bijection, not merely an upper bound.

For the directed ladder self-avoiding walk count, ${\sigma }_0=1$, ${\sigma }_1=2$, and for $n\ge 2$ a word either ends in $R$, or ends in $RV$. Removing that final block givesLet $\phi =(1+\sqrt{5})/2$ be the golden ratio, and $\psi =(1-\sqrt{5})/2$. The Binet formula for the Fibonacci number yieldsSince $|\psi |<\phi$, taking $n$th roots gives ${\lim }_{n\to \infty }{\sigma }_n^{1/n}=\phi$. This use of the golden-ratio symbol is independent of the connection rate in Question 1.

Use the Riemann sphere convention for evaluating a Möbius transformation at a pole and at infinity. When the three prescribed points are finite, takeIts zero is $w_2$, its pole is $w_1$, and substitution at $w_3$ gives one. The remaining three cases areAll coefficient determinants are nonzero because the points are distinct. There is only one such Möbius transformation: the composite of any two candidate maps, one inverted, fixes $\infty ,0,1$; fixing infinity makes it affine, and fixing zero and one makes it the identity.

For this question use the cross-ratio normalizationIn the finite case this is $(w_3-w_1)(w_4-w_2)/[(w_3-w_2)(w_4-w_1)]$, with the corresponding limits if a point is infinite. It is finite and distinct from zero and one, since $w_4$ is distinct from the other three points and $f$ is a bijection. Ordering conventions for the cross-ratio differ; the definition here is fixed by the specified images, rather than by importing another ordering formula.

A generalized circle means either a circle or a straight line completed by infinity. Let $K$ be the unique generalized circle through the first three points. Its image under $f$ is the unique generalized circle through $\infty ,0,1$, namely $\mathbb{R}\cup \{\infty \}$. Therefore $w_4\in K$ exactly when $f(w_4)$ is real. Conversely a real $f(w_4)$ lies on that extended real line, whose inverse image is $K$. This proves the real cross-ratio criterion for a generalized circle in both directions.

For a group action, the orbit of a group action of $x$ is $Gx=\{gx:g\in G\}$, and its stabilizer subgroup is $G_x=\{g:gx=x\}$. The orbit-stabilizer theorem gives $|Gx||G_x|=|G|$: the map $g{G}_x\mapsto gx$ is a well-defined bijection from stabilizer cosets to the orbit.

Within one orbit, the stabilizer subgroups are conjugate, since $G_{hx}=h{G}_x{h}^{-1}$. Their sizes are therefore equal. Summing stabilizer sizes over a single orbit gives $|Gx||G_x|=|G|$, and summing over all $n$ orbits yieldsNow count the pairs $(g,x)$ fixed by the action in two ways. Holding $x$ fixed gives $|G_x|$ choices of $g$, whereas holding $g$ fixed gives $|\mathrm{Fix}(g)|$ choices of $x$. ThusCombining the two identities proves Burnside lemma:The finiteness hypotheses justify these cardinality sums. If $X$ is empty, every sum and the orbit count are zero, so the formula still applies.

A set $A$ is a countable set if there exists an injective function $A\to \mathbb{N}$, with $\mathbb{N}=\{0,1,2,\dots \}$. Equivalently, it is a finite set or has a bijection with $\mathbb{N}$. An infinite countable set is called a countably infinite set.

The empty set is included: the empty function into $\mathbb{N}$ is injective. This convention distinguishes “countable” from “countably infinite” and will also cover the finite threshold sets in the last part.

For each positive integer $n$, the positive elements of $A_n$ form an infinite set, and the preceding increasing enumeration gives a bijection $f_n:\mathbb{N}\to A_n$ on these positive elements. The positive integers have a unique decomposition $10^{n-1}q$ with $10\nmid q$, so these sets are disjoint and exhaust the positive integers.

The printed natural numbers include $0$. The trailing-zero count of the representation of $0$ is not needed: shift the positive partition down by one and putUniqueness of the trailing-zero count proves the injective function property, and the decomposition of $N+1$ proves the surjective function property. An explicit decimal trailing-zero pairing function, using the increasing enumeration from the previous part, isIndeed, the bracket enumerates $1,2,\dots ,9,11,12,\dots$, exactly the positive integers not divisible by $10$. This handles both the positive index $n$ and the element $0$ without silently changing the PDF's convention.

To enumerate the rational numbers, first enumerate the integers by $e(0)=0$, $e(2r-1)=r$, $e(2r)=-r$ for $r\ge 1$. The function $(i,j)\mapsto e(i)/(j+1)$ maps ${\mathbb{N}}^2$ onto $\mathbb{Q}$, and composing with $g^{-1}$ gives a surjective function from $\mathbb{N}$. Choosing the first index representing each rational number gives an injective function $\mathbb{Q}\to \mathbb{N}$. Thus $\mathbb{Q}$ is countably infinite; its infinitude follows because it contains all integers.

The essential fact is absoluteness of cardinalhood in limit ranks. Let $\alpha \le \beta$ be limit ordinals and $x\in V_{\alpha }$. Being an ordinal is absolute between these transitive sets, so a non-ordinal is a cardinal number in neither structure. For an ordinal $\delta \in V_{\alpha }$, we have $\delta <\alpha$.

If $\delta$ is not an ambient cardinal number, there is an ordinal $\gamma <\delta$ and a bijection $f:\gamma \to \delta$. With Kuratowski ordered pairs, its graph has rank of a set at most $\delta +3$. Since $\alpha$ is a limit ordinal, $\delta +3<\alpha$, so $f\in V_{\alpha }$. The assertion that $f$ is such a bijection is a bounded formula in set theory and is therefore evaluated correctly by each rank. Conversely, any internal bijection witnessing failure of cardinal number status is an actual one by the same set-theoretic absoluteness. ConsequentlyUnlike arbitrary transitive models, these rank-initial structures contain every sufficiently low-rank witness. That witness availability is what upgrades the usual downward absoluteness of cardinalhood to agreement in both directions.

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.

The reference kernel printed in the hint has total mass $1/n+\left(\genfrac{}{}{0ex}{}{n}{2}\right)/\left(\genfrac{}{}{0ex}{}{n}{2}\right)=1+1/n$, so it is not a Markov kernel. We explicitly replace it by the normalized random transposition shuffle: choose two positions independently and uniformly and swap them. Its probabilities areThese sum to one, and its ordinary spectral gap is $\tilde{\gamma }=2/n$, the value intended in the hint. This value can also be certified by the Aldous spectral gap theorem: the single-label generator has rate $2/n^2$ between distinct positions, so on centered functions it acts as multiplication by $-2/n$. Both shuffles have the same uniform distribution on a finite set as stationary distribution.

We use the Canonical paths comparison theorem in the following precise form. For two finite reversible Markov chains with the same positive stationary distribution $\pi$, route each directed transition $(x,y)$ of $\tilde{P}$ along a positive-capacity path ${\eta }_{xy}$ of $P$. Ifthen $\tilde{\mathcal{E}}(f,f)\le A\mathcal{E}(f,f)$ and $\gamma \ge \tilde{\gamma }/A$. Indeed, telescope each difference along its path, apply the Cauchy-Schwarz inequality, and sum with weights $\pi (x)\tilde{P}(x,y)/2$. The load definition gives the Dirichlet form of a Markov chain inequality; the common variance denominator then gives the spectral gap inequality. Identity transitions use empty paths.

Put $s_k=(k,k+1)$. A transposition $(i,j)$ is routed using the wordof length $L_{ij}=2(j-i)-1\le 2n$. Each generator occurs at most twice; write its occurrence count as $N_k(i,j)\le 2$. For a fixed directed adjacent edge $(\sigma ,\sigma s_k)$ and each occurrence of $s_k$ in a word, there is exactly one starting permutation whose translated word crosses this edge at that occurrence. This follows because right multiplication by the prefix is a bijection of the symmetric group. Hence the uniform stationary factors cancel in the comparison load, leavingThe crude bounds $L_{ij}\le 2n$, $N_k(i,j)\le 2$, and $\left(\genfrac{}{}{0ex}{}{n}{2}\right)\le n^2/2$ imply $A\le 4n^2$. ThereforeOnly pairs with $i\le k<j$ contribute, and there are $k(n-k)\le n^2/4$ of these. Keeping this restriction gives the stronger $A\le 2n^2$ and $\gamma \ge 1/n^3$. Neither comparison bound needs the exact adjacent-shuffle spectral gap; the normalization repair of the reference kernel is essential.

First require $x\ne 0$. A discrete logarithm to a generator of a group of ${\mathbb{Z}}_p^{\ast }$ exists only for nonzero $x$; the printed membership $x\in {\mathbb{Z}}_p$ inadvertently also permits zero, for which $x^{-b}$ is undefined. Zero can be rejected before any quantum circuit.

Put $M=p-1$ and write $x=g^y$. Since $g$ is a generator of a group of order $M$, the map $k\mapsto g^k$ is a bijection from ${\mathbb{Z}}_M$ to the multiplicative group of a finite field. Hence every nonzero $c$ has a unique $k\in {\mathbb{Z}}_M$ with $c=g^k$. Equality of powers of $g$ is equality of their exponents modulo $M$, givingThe fiber over $c$ is an affine coset of the subgroup $\{(yb,b):b\in {\mathbb{Z}}_M\}$, and contains exactly $M$ pairs. This identifies the hidden subgroup problem underlying discrete-logarithm Fourier sampling; knowing $k$ numerically is not needed to construct the coset state.

We use the core-quotient bijection for partitions: an ordered $p$-tuple $({\nu }_0,\dots ,{\nu }_{p-1})$ and a fixed $p$-core determine a unique partition of an integer, withThe irreducible characters in both $B$ and $C$ therefore correspond to the same ordered tuples of total size $w$. Replacing the empty core of a partition by $\gamma$ while keeping the quotient of a partition fixed gives a bijection ${\chi }^{\lambda }\mapsto {\chi }^{\mu }$ from $B$ to $C$. In particular $|B|=|C|$.

For such a pair, all levels of the core tower of a partition above level zero agree. At level zero, their sizes are $0$ and $m$, respectively. Put $D={\sum }_{r\ge 1}|T^C(\lambda {)}_r|={\sum }_{r\ge 1}|T^C(\mu {)}_r|$. When $0\le m<p$, the base-p digit sum satisfiesThe P-adic valuation of a symmetric-group character degree from the core tower then givesThus the same bijection preserves degree coprimality to $p$ and restricts to a bijection between the indicated sets of irreducible characters of degree coprime to p. ConsequentlyFor $m=0$, take $\gamma$ to be the empty partition; the construction becomes the identity.

A cardinal number is identified with an initial ordinal, namely an ordinal not in bijection with any smaller ordinal. An inaccessible cardinal, in the strong sense used here, is an uncountable regular cardinal that is also a strong limit cardinal. ThusA worldly cardinal is a cardinal number whose level of the Von Neumann hierarchy satisfies all of ZFC:Worldliness is this model-theoretic condition; regularity is not part of its definition. The original PDF asks for these two notions; the extra comma in the local TeX makes “cardinal” look like a separate requested item.

The Mostowski collapse theorem applies when $E$ is a well-founded relation and an extensional relation on the set $M$. Extensionality here means that different points have different sets of $E$-predecessors. There is then a unique transitive set $T$ and a unique bijection $\pi :M\to T$ such thatThe collapsing map is characterized by well-founded relation recursion:Thus $(M,E)$ is isomorphic to $(T,\in )$. Both well-foundedness and extensionality are hypotheses of the theorem; well-foundedness alone does not make the recursive map injective.

We construct the two transitive models together, taking care that the later collapse really retains the earlier model. First, a worldly cardinal $\kappa$ is greater than ${\omega }_1$: ZFC in $V_{\kappa }$ contains the full power set $\mathcal{P}(\omega )$, and the axiom of choice there gives a bijection between it and an ordinal $\gamma <\kappa$. That power set is externally uncountable by Cantor theorem, so $\gamma \ge {\omega }_1$. Infinity rules out the finite cardinals and $\omega$ before this argument is applied.

By the Downward Lowenheim-Skolem theorem, choose a countable elementary substructure $X\prec (V_{\kappa },\in )$. Its inherited membership is a well-founded relation, and elementarity transfers extensionality from $V_{\kappa }$. Apply the Mostowski collapse theorem to obtain a countable transitive model $M$ of ZFC. Because $M$ is a countable transitive set, it is a hereditarily countable set and its rank of a set is below ${\omega }_1$. In particular, $M\in V_{\kappa }$.

Now take the Skolem hull in $V_{\kappa }$ of the seedCall it $H$. The seed has external cardinality ${\aleph }_1$ and lies inside $V_{\kappa }$. The hull is an elementary substructure of $V_{\kappa }$ with $|H|={\aleph }_1$: closure under countably many finitary Skolem functions gives the upper bound, and ${\omega }_1\subseteq H$ gives the lower bound. Let $\pi :H\to N$ be its Mostowski collapse theorem map. Then $N$ is a transitive model of ZFC.

The transitive collapse fixes transitive subsets lemma gives $\pi (m)=m$ for every $m\in M$, since $M\subseteq H$ is transitive. Since also $M\in H$, the collapse sends that element to $M$ itself. Thus $M\in N$, and transitivity of $N$ yields the required inclusion:This is the construction of nested transitive models from a worldly cardinal; the next two parts verify its size and ordinal requirements.

For the model $M$ constructed in part (a), the collapsing map $X\to M$ is a bijection. The Downward Lowenheim-Skolem theorem supplied countable $X$, so $M$ is externally countable. It is infinite because it satisfies the axiom of infinity. ConsequentlyThis is external cardinality. A countable transitive model still regards many of its own sets and ordinals as uncountable, because external enumerations need not belong to it.

The collapse $\pi :H\to N$ is a bijection, so $|N|=|H|={\aleph }_1$. Every $\alpha <{\omega }_1$ and every element of $\alpha$ belong to $H$. The transitive collapse fixes transitive subsets lemma therefore gives $\pi (\alpha )=\alpha$, so every ambient countable ordinal belongs to $N$.

Moreover, $V_{\kappa }$ correctly regards each such $\alpha$ as countable. An injection $\alpha \to \omega$ has rank below $\max (\alpha ,\omega )+\omega <\kappa$, so a witness belongs to $V_{\kappa }$. Elementarity gives $H\models$ “$\alpha$ is a countable ordinal”. Transporting this statement across the collapse, which fixes $\alpha$, gives the same statement in $N$.

The collapse also fixes the element ${\omega }_1\in H$. No injection ${\omega }_1\to \omega$ exists externally, hence none belongs to $V_{\kappa }$; together with the countability witnesses below it, this shows that $V_{\kappa }$ correctly identifies ${\omega }_1$ as its first uncountable ordinal. Elementarity and the collapse preserve that identification. Thus the construction gives

Let $C(x)$ be the formula expressing cardinal number status:Ordinalhood and the assertion that a given set is a bijection between fixed sets are each expressible by a bounded formula in set theory. If $M$ regarded $x$ as a non-cardinal ordinal, a witnessing smaller ordinal and bijection would remain present and valid in $N$. Ordinalhood itself is absolute between the transitive models. Thus $N\models C(x)$ implies $M\models C(x)$: this is downward absoluteness of cardinalhood.

For failure in the other direction, put $\beta =({\omega }_1{)}^M$. This ordinal belongs to $M$, and $M\models C(\beta )$ with $\beta >\omega$. Externally $\beta$ is countable, since $\beta \subseteq M$ and $M$ is countable. By the construction of $N$, it contains a countability witness for $\beta$, and hence a bijection $\omega \to \beta$. Therefore $N\models \neg C(\beta )$. This formula is downward absolute and fails to be upward absolute.

For every $x\in X$, invariance givesThus $T^{-1}\{x\}$ is nonempty, so $T$ is a surjective function. A surjection from a finite set to itself is a bijection. ThereforeThis is the finite full-support measure-preserving map is bijective principle.

D. Downward absoluteness of cardinalhood holds because, if the larger transitive model sees no bijection with a smaller ordinal, neither can the smaller model, whose functions form only a subset of those in the larger model. Cardinalhood is not described by an upward absolute formula, because the larger model can contain a new bijection collapsing an ordinal that the smaller model regards as a cardinal number.