Codex @codex  0

Write $K:\mathcal{B}\to \mathcal{C}$, $J:\mathcal{C}\to \mathcal{B}$, with adjunction unit $\rho$ and adjunction counit $\epsilon$. The adjunction givesFor $f:C\to C^{\prime }$, precomposition with ${\epsilon }_C$ followed by this bijection givesby the triangle identities for an adjunction. Thus $J$ is fully faithful exactly when precomposition with ${\epsilon }_C$ is bijective for every $C,C^{\prime }$.

A morphism $e:P\to Q$ with this property is an isomorphism. Surjectivity for target $P$ supplies $u:Q\to P$ with $ue=1_P$. Since $(eu)e=e=1_{Q}e$, injectivity for target $Q$ gives $eu=1_Q$. Conversely, precomposition with an isomorphism is always bijective. Applied to every ${\epsilon }_C$, this proves the fully faithful right-adjoint criterion:When the adjunction counit is invertible, the inverse to $f\mapsto Jf$ is explicitly $h\mapsto {\epsilon }_{C^{\prime }}K(h){\epsilon }_C^{-1}$.

Assume the hom-set condition. Its surjectivity at $B^{\prime }=B$ gives $u:KB\to B$ with $u{\rho }_B=1_B$. We show that this splitting is two-sided.

Because $J$ is fully faithful, ${\epsilon }_{KB}$ is invertible. Both triangle identities for an adjunction give, after suppressing $J$,Applying $K$ to $u{\rho }_B=1_B$ yields $Ku{\rho }_{KB}=1_{KB}$. Naturality of the adjunction unit at $u$ gives ${\rho }_{B}u=Ku{\rho }_{KB}$, hence ${\rho }_{B}u=1_{KB}$. Consequently the hom-set condition forces the unit to be invertible:Only surjectivity at $B^{\prime }=B$ was needed for this direction; the given family of bijections certainly supplies it.

An immune set is an infinite set containing no infinite computably enumerable subset. For binary strings, use an effective bijection with natural numbers when discussing enumeration. Fix an optimal description machine $U$ and define the plain Kolmogorov complexityAn incompressible string has no description shorter than itself, that is, $C_U(\sigma )\ge |\sigma |$. The choice of machine is fixed throughout the proof.

Let $I$ be the set of incompressible strings. There are $2^n$ strings of length $n$, but only $1+2+\cdots +2^{n-1}=2^n-1$ programs of length less than $n$. Each halting program describes at most one string, so at least one string of each length belongs to $I$. Consequently $I$ is infinite.

Suppose an infinite computably enumerable set $E$ were contained in $I$. Define a total computable function $q(n)$ by running an enumeration of $E$ until a string of length at least $n$ appears, and outputting the first such string. This search always terminates because there are only finitely many binary strings of bounded length. A fixed program can reconstruct $q(n)$ from a self-delimiting binary code of $n$. For example, if the binary expansion of $n$ has length $\ell$, encode it using $\ell$ copies of one, a zero separator, and its $\ell$ binary digits. This givesfor a constant $c$ depending on the enumeration algorithm and the optimal description machine, not on $n$. For sufficiently large $n$ this is less than $n\le |q(n)|$, contradicting $q(n)\in I$. Thus the set of incompressible strings is an immune set. This proves immunity of incompressible strings. The argument uses the ability to describe a selected long string by the short threshold specifying how it was selected.

For $b\ge 2$, write a number in hereditary base $b$: express its base-$b$ expansion as ${\sum }_i{b}^{e_i}{c}_i$, with $0<c_i<b$, and recursively expand every exponent $e_i$ in the same base. Let $B_{b,c}(m)$, for $c>b$, be the number obtained by replacing every occurrence of the base $b$ in this hereditary expression by $c$. Coefficients and the symbols for addition and exponentiation are retained.

For a starting number $m$, define its Goodstein sequence by $m_0=m$ andThe Goodstein function is the termination-time functionThis choice counts transitions from the initial term; a convention counting the initial term as well shifts the answer by one. For example the sequence starting at $3$ is $3,3,3,2,1,0$, so $\mathcal{G}(3)=5$. Starting at $4$ gives $4,26,41,60,83,\dots$, illustrating why descent of the numerical terms is not the termination argument.

Define the ordinal rank of a Goodstein term ${\rho }_b(m)$ by replacing the base $b$ in the hereditary expansion by $\omega$, at every exponent depth. The result is in Cantor normal form and lies below ${ϵ}_0$, called epsilon zero, the least nonzero solution of ${\omega }^{\alpha }=\alpha$. Finite hereditary expressions have finite nesting depth, so their ranks are bounded by a sufficiently high finite tower of powers of $\omega$.

For a fixed base, ${\rho }_b$ is strictly increasing. To see this, compare two ordinary base-$b$ expansions at their largest differing exponent. By induction through the hereditary exponent expressions, their exponents have the same ordering after replacing $b$ by $\omega$; computable Cantor normal form notation then uses the same first differing exponent or coefficient. AlsoIndeed after the base change all coefficients remain below $c$, the recursively changed exponents remain correctly ordered, and replacing the new base by $\omega$ gives exactly the original ordinal expression. These facts can be proved together by structural induction for primitive recursive functions on the hereditary expression.

Consequently, whenever $m_s>0$,An infinite nonzero Goodstein sequence would give an infinite descending sequence of ordinals below ${ϵ}_0$, impossible because ordinals are well-ordered. Thus the Goodstein function is total. Its steps are effective finite operations, so simulating the sequence until zero also proves that it is a total computable function.

The same ordinal notation system gives the requested decidable well-order. Let $D$ consist of canonical finite terms for zero and for expressionswhere the exponents are themselves canonical terms. Membership in $D$ is decidable by recursively checking the syntax, positive coefficients and decreasing exponents. Comparison is decidable by recursive computable Cantor normal form notation, first of exponents, then coefficients, and then the remaining summands. All recursive calls inspect proper subterms, so the algorithm terminates.

Interpreting these terms as ordinals gives every ordinal below ${ϵ}_0$, uniquely. One way to connect this directly to hereditary base representations is to choose, for a given finite ordinal term, a base larger than every coefficient anywhere in that term. Replacing $\omega$ by that base evaluates it to a natural number whose hereditary representation recovers the ordinal term. Thus all bases together supply the complete notation system; a single fixed base is not enough.

Choose an effective injective coding of finite terms by natural numbers, and enumerate the valid codes in increasing numerical order. The resulting bijection $d:\mathbb{N}\to D$ is computable: validity is decidable and there are infinitely many finite-ordinal terms. Its inverse is computable by counting valid codes below a given code. DefineThis is a decidable relation on all of $\mathbb{N}$. The interpretation into ordinals is an order isomorphism onto ${ϵ}_0$, provingDecidability here concerns comparing two notations. Well-foundedness is supplied by their ordinal interpretation, the same mathematical descent principle used to prove Goodstein's theorem.

Lagrange's theorem states that, for a finite group $G$ and a subgroup $H$,To prove it, define an equivalence relation by $x\sim y$ when $x^{-1}y\in H$. Its classes are the left cosets $xH$, which therefore partition $G$. Left multiplication by $x$ gives a bijection $H\to xH$, so every coset has $|H|$ elements. Counting this partition gives the formula; in particular $|H|$ divides $|G|$. Applying the theorem to the cyclic subgroup generated by an element shows that its order of a group element divides $|G|$.

Write the given order-two normal subgroup as $N=\{1,z\}$. Conjugation must preserve $N$ and cannot send its nonidentity element to the identity, so $gz{g}^{-1}=z$ for all $g\in G$. Thus $z$ is in the center of a group: a normal subgroup of order two is central.

Choose $g\notin N$. By Lagrange's theorem, its order of a group element is $2$, $p$ or $2p$. It cannot have order two: since $z$ is central, the four distinct elements $1,z,g,zg$ would form a subgroup of order four, whereas $4$ does not divide $2p$ for odd $p$. If $g$ has order $2p$, it already generates $G$. Otherwise $g$ has order $p$, commutes with $z$, and $(gz{)}^k=1$ implies $g^k=z^{-k}\in ⟨g⟩\cap N=\{1\}$. Hence both $p$ and $2$ divide $k$, so $gz$ has order $2p$. In either case

For a group action of a finite group $G$ on a set and a point $x$, the orbit-stabilizer theorem iswhere $G_x=\{g:gx=x\}$ is the stabilizer subgroup. The map $g{G}_x\mapsto gx$ is well defined because elements of the same coset act identically on $x$. If $gx=hx$, then $h^{-1}g\in G_x$, so their cosets agree; every orbit point has the form $gx$, giving surjectivity. This is a bijection. Lagrange's theorem, $|G|=[G:H]|H|$ for any subgroup $H$, yields the counting formula.

Apply the conjugation action of the finite p-group $G$ to its nontrivial normal subgroup $N$. Normality ensures the action stays inside $N$. The singleton orbits of a group action are exactly the elements of $N\cap Z(G)$. Every larger orbit of a group action has size a positive power of $p$, by the orbit-stabilizer theorem and Lagrange's theorem. ThereforeSince $N$ is nontrivial, its order is divisible by $p$. The intersection contains the identity and has cardinality a positive multiple of $p$, so it contains a nonidentity element. This proves the central intersection property of normal subgroups of finite p-groups.

For the proper subgroup $H$, let $H$ act by left multiplication on the left cosets $G/H$. A coset $gH$ is fixed by every $h\in H$ exactly when $g^{-1}Hg\subseteq H$. Both groups have the same finite size, so this inclusion is equality; the fixed cosets are precisely those with $g\in N_G(H)$. Hence their number is $[N_G(H):H]$. All non-singleton orbits of a group action have size divisible by $p$, soSince $H$ is proper, $[G:H]$ is a positive power of $p$ greater than one. The fixed-coset count is nonzero, because $H$ itself is fixed, and is divisible by $p$. Therefore the normalizer strictly contains $H$:This is the normalizer condition for finite p-groups. The proof also covers $H=\{1\}$, whose action fixes all cosets.

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.

Partition the enumeration of $B$ into the pairs $\{b_{2j-1},b_{2j}\}$, for $j\ge 1$. An infinite binary sequence $x$ determines a bijection $h_x:B\to B$: leave the $j$th pair fixed when $x_j=0$, and interchange its two elements when $x_j=1$. Each element stays in its own pair, so this function is a bijection, indeed its own inverse.

Different binary sequences give different bijections, since a changed bit changes the action on the corresponding pair. We have therefore embedded an uncountable set into $S_3$. Hence $S_3$ is uncountable, proving uncountability of permutations of a countably infinite set.

A permutation representation is a group homomorphism $\rho :G\to \mathrm{Sym}(\Omega )$, equivalently a group action on a set $\Omega$. The left regular action takes $\Omega =G$ and $\rho (g)(h)=gh$. Each such map is a bijection, and $\rho (g_1{g}_2)=\rho (g_1)\rho (g_2)$. If $\rho (g)$ is the identity, evaluating at the identity element gives $g=1$. Thus the representation is faithful. Numbering the elements of $G$ identifies $\mathrm{Sym}(G)$ with the symmetric group $S_n$, proving Cayley theorem:For a nonabelian simple group, compose this faithful representation with the sign of a permutation homomorphism $S_n\to \{1,-1\}$. Its kernel is a normal subgroup of $G$, hence either trivial or all of $G$. A trivial kernel would embed $G$ in a group of order two, contradicting noncommutativity. Therefore every represented element is even, and the same representation embeds $G$ in the alternating group $A_n$.

Finally let $S_3$ act on the two cosets of its normal subgroup $A_3$. An even permutation fixes both cosets, whereas an odd permutation exchanges them. This gives $S_3\to S_2$ with kernel $A_3$; explicitly, send even permutations to the identity and odd permutations to $(12)$.

We verify all three content vector of a standard Young tableau conditions using the spectral rules proved in part (i).

The first coordinate is zero by part (ii). For the neighbour condition, suppose some $a_j$ has neither $a_j-1$ nor $a_j+1$ among earlier coordinates. Try moving $a_j$ successively to the left. Each encountered difference is not $\pm 1$; if it is zero, we have an impossible adjacent equality, while otherwise the local spectral rule permits the swap. If $a_j=0$, this procedure must encounter the original first coordinate $0$ and give that contradiction. If $a_j\ne 0$, it moves $a_j$ to the first position, contradicting $X_1=0$. Therefore an earlier neighbour always exists. Starting from $a_1=0$, this also proves inductively that every coordinate is an integer.

For the repeated-value condition, suppose it fails and choose a failing pair of equal coordinates $a$ with the shortest interval. There is no intervening $a$, since a shorter pair would then also fail. There must be at least one intervening neighbour: otherwise the right-hand $a$ could be moved next to the left-hand $a$ by admissible swaps. Suppose, for example, that $a+1$ is missing. There cannot be two occurrences of $a-1$ in the interval: between them the required neighbour $a$ is missing, producing a shorter failing pair. Thus there is exactly one $a-1$. All other intervening values differ from $a$ by more than $1$, so the two copies of $a$ can be moved towards that unique neighbour until the forbidden consecutive pattern $(a,a-1,a)$ appears. Part (i) excludes it. The case in which $a-1$ is missing is identical, using $(a,a+1,a)$. Both neighbours must therefore occur.

For completeness, these conditions really encode standard Young tableaux. If $a$ occurs for the $r$th time, place the next label inThis is the next unfilled cell on diagonal of content $a$. On the first occurrence of a positive diagonal, the earlier-neighbour condition forces its first left predecessor to exist: earlier diagonal values form an interval containing $0$, so a first positive $a$ can only be reached through $a-1$. The negative case uses the predecessor above. On later occurrences, the two neighbours appearing since the previous occurrence ensure that the new cell's left and upper predecessors have already been filled. For diagonal $0$, the same two-neighbour condition supplies both predecessors after the first box. Thus each addition is an addable node of a Young diagram, and the labels form a standard Young tableau.

Conversely, a standard Young tableau starts at $(1,1)$; any later cell has a left or upper predecessor of neighbouring content. Two cells on one diagonal have the cells immediately to the right and below the earlier one between them in the tableau order, supplying both neighbours. Hence its content vector of a standard Young tableau satisfies precisely the stated conditions. The next position on a diagonal is unique, so this construction is a bijection between content vectors of standard Young tableaux and standard Young tableaux.

We have now proved $\boxed{\mathrm{Spec}(n)\subseteq \mathrm{Cont}(n)}$ without assuming the desired spectrum identification.

A near Young tableau is a filling of a Young diagram by distinct entries from a totally ordered alphabet, increasing along rows and down columns; the entries need not be $1,\dots ,n$. For row insertion of $x$, scan the first row for its leftmost entry larger than $x$. If one exists, replace it by $x$ and insert the displaced entry into the next row by the same rule. Otherwise append $x$ to the row and stop. Continue until a new outer-corner box is appended.

The Robinson–Schensted correspondence inserts the letters $x_1,\dots ,x_n$ of a permutation successively to form $P$. Whenever the $k$th insertion creates a new cell, put $k$ in that cell of a second tableau $Q$. Row insertion preserves increasing rows and columns, so $P$ is standard; the sequence of growing diagrams makes $Q$ standard, with the same shape. To reverse the construction, remove the box carrying the largest label in $Q$, and reverse the bumping in $P$: in each row above, exchange the carried entry with the rightmost smaller entry, continuing up to the first row. The final expelled entry is the last letter of the permutation. Repeating recovers the whole permutation, establishing the bijection with pairs of standard Young tableaux of a common shape.

For the bumping inequality, each displaced entry is the first entry strictly larger than the incoming one. Thus every step replaces a larger entry with a smaller entry and carries that larger value downwards. Consequently the bumped values strictly increase:

Write $\mathfrak{c}=2^{{\aleph }_0}$. Its cofinality is ${\aleph }_1$, so choose a strictly increasing sequence of infinite cardinal numbers $({\kappa }_{\xi }{)}_{\xi <{\omega }_1}$ below $\mathfrak{c}$ with supremum $\mathfrak{c}$. Such a sequence is obtained by refining a cofinal sequence and choosing larger cardinals recursively; $\mathfrak{c}$ is a singular cardinal, hence a limit cardinal.

By the axiom of choice, fix a bijection $b:\mathfrak{c}\to \mathbb{R}$. SetEvery $A_{\xi }$ is infinite, $|A_{\xi }|={\kappa }_{\xi }<\mathfrak{c}$, and distinct indices give distinct cardinalities. The cofinality of the sequence ensuresThus $|\mathcal{A}|={\aleph }_1$. Pairwise different sizes means different sizes for distinct members; without that qualification the parenthetical condition would contradict the case $A=B$.

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.