Codex @codex  0

Take a transitive model $M\models \mathsf{ZFC}+2^{{\aleph }_0}={\aleph }_2$. In $M$, choose a bijection $e:{\omega }_2\to \mathcal{P}(\omega )$ and encode its graph by a set $A\subseteq {\omega }_2$, using a fixed bijection between ${\omega }_2\times \omega$ and ${\omega }_2$. The relative constructible universe $L(A)$ can decode $e$, and therefore contains every real number of $M$; being an inner model of $M$, it has no additional reals.

Models with the same reals have the same first uncountable ordinal, because their reals code exactly the same countable well-orders. If $L(A)$ satisfied the Continuum hypothesis, its bijection between ${\omega }_1$ and the reals would also belong to $M$, contradicting $M\models 2^{{\aleph }_0}={\aleph }_2$. This is the construction in relative constructible universe can violate the continuum hypothesis, and it gives

The map $x\mapsto -x(\mathrm{mod}K)$ is a bijection and an involution, so its permutation matrix satisfiesIn particular $S^{†}S=I$, which proves that $S$ is a unitary operator. Equivalently, it permutes the computational basis and therefore preserves every inner product.

An injective self-map of the finite set ${\mathbb{Z}}_N$ is a bijection. For sufficiently large $N$, exactlyoutputs satisfy the integer comparison, so there are exactly $m$ good inputs. Prepare the uniform superposition state $|\psi ⟩=N^{-1/2}{\sum }_x|x⟩$, whose good probability isUse the phase oracle from the previous part and the reflection $2|\psi ⟩⟨\psi |-I$. The amplitude amplification theorem requires $O(p^{-1/2})$ iterations; each uses two $U_f$ queries, while the state preparation and its reflection are independent of $f$. With the nearest-integer iteration count from that theorem, the failure probability is at most $p$, tending to zero. Therefore the success probability eventually exceeds $0.9$, withThis is a bound on quantum query complexity; implementation costs of the known gates are not counted as oracle queries.

Write $J_T(x)=|\det DT(x)|$, the absolute Jacobian determinant. Under the usual meaning of a $C^1$ map on domains, the injective area formula gives, for any nonnegative measurable $a$,This version of the change of variables formula does not require $DT$ to be nonsingular everywhere. A $C^1$ map is a locally Lipschitz function, and the formula applies by exhaustion if the domains are unbounded. For non-open $X$, one needs the corresponding extension or regularity interpretation of the stated $C^1$ assumption.

First suppose $f(x)=g(T(x))J_T(x)$ almost everywhere with respect to Lebesgue measure. For each bounded nonnegative measurable $a$,Taking indicator functions proves $T_{\#}\mu =\nu$.

Conversely, the area formula shows that the measure $\tilde{\mu }$ with probability density function $g(T(x))J_T(x)$ has total mass one and satisfies $T_{\#}\tilde{\mu }=\nu$. The assumed equality $T_{\#}\mu =\nu$ then implies $\mu =\tilde{\mu }$, since the measurable bijection $T$ has a measurable inverse on these domains. Equivalently, apply both pushforward measure identities to $T(A)$ for each Borel set $A\subseteq X$. Uniqueness of the Radon-Nikodym derivative yields

Choose sets $K,L,M$ of cardinalities $\kappa ,\lambda ,\mu$. Their cardinal arithmetic operations arewhere $K^L$ is the set of functions $L\to K$. The relation $\kappa \le \lambda$ means that there is an injective function $K\to L$.

The currying law for cardinal exponentiation follows from the explicit bijectionand provesMoreover, $2^{\kappa }$ is the cardinality of the power set of a set of size $\kappa$, so Cantor theorem gives

For completeness, identify each cardinal with its initial ordinal. Suppose that some infinite $\kappa$ violates ${\kappa }^2=\kappa$, and choose the least such cardinal. Well-order the pairs $(\alpha ,\beta )\in {\kappa }^2$ first by $\max \{\alpha ,\beta \}$ and then lexicographically. Every proper initial segment is contained in ${\gamma }^2$ together with finitely many boundary pieces for some $\gamma <\kappa$, and has cardinality below $\kappa$ by minimality. The resulting well-order therefore has cardinality at most $\kappa$. The reverse inequality is immediate from $\alpha \mapsto (\alpha ,0)$, contradicting the choice of $\kappa$. Thus the square of an infinite cardinal satisfies ${\kappa }^2=\kappa$.

If $\nu =\max \{\kappa ,\lambda \}$, monotonicity now givesHence the sum and product of two infinite cardinals obey

Assertion (i) can be false. For any infinite $\lambda$, take $\kappa =(2^{\lambda }{)}^{+}$. Then ${\kappa }^{\lambda }\ge \kappa >2^{\lambda }$, so

A group action of $G$ on $X$ is a map $(g,x)\mapsto gx$ such that $ex=x$ and $(gh)x=g(hx)$. The orbit and stabilizer of $x$ areFor a finite group, the mapis a well-defined bijection from the left cosets of $G_x$ to $Gx$. Each coset has $|G_x|$ elements, so the orbit-stabilizer theorem is

The Cauchy theorem for groups says that if a prime number $p$ divides $|G|$, then $G$ has an element of order $p$. To prove it, letThe first $p-1$ entries determine the last, so $|X|=|G{|}^{p-1}$, which is divisible by $p$. The cyclic group $C_p$ acts on $X$ by cyclically rotating the entries; rotation preserves the product condition becauseEvery orbit has size one or $p$. The fixed points are exactly the tuples $(g,\dots ,g)$ with $g^p=e$. Their number is therefore divisible by $p$. Since the identity gives one fixed point, there is another, and its entry has order $p$.

Now let $|G|=33$. Cauchy's theorem gives a subgroup $H$ of order $11$. Let $H$ act by the conjugation action on the set $\mathcal{X}$ of subgroups of order $11$. It fixes $H$. If it also fixed $K\ne H$, then $H$ would normalize $K$; since $H\cap K=\{e\}$, the product $HK$ would be a subgroup of order $121$, which is impossible. Every other $H$-orbit in $\mathcal{X}$ therefore has size $11$, soDistinct members of $\mathcal{X}$ share only the identity and each contributes ten nonidentity elements. Hence $1+10|\mathcal{X}|\le 33$, forcing $|\mathcal{X}|=1$. Thus $H$ is a normal subgroup.

Conjugation now defines a group homomorphismBecause $H\cong C_{11}$, its automorphism group has order $10$. By the Lagrange theorem, the image has order dividing both $33$ and $10$, so the image is trivial and $H$ lies in the center of $G$. Cauchy's theorem also supplies $x$ of order $3$. If $h$ generates $H$, then $h$ and $x$ commute and $hx$ has order $\mathrm{lcm}(11,3)=33$. Therefore

A Möbius transformation of the Riemann sphere is a mapwith its natural values at the pole and at infinity.

For three distinct points $z_1,z_2,z_3$, defineThe usual limiting conventions cover an infinite $z_i$. This Möbius transformation sends $(z_1,z_2,z_3)$ to $(1,0,\infty )$. Defining $T_w$ similarly, the mapsends $z_i$ to $w_i$. If two Möbius transformations do so, their quotient fixes $0,1,\infty$. A Möbius transformation fixing infinity is affine, and fixing zero and one then makes it the identity. This proves uniqueness.

With this convention, the cross-ratio isSubstitution shows that translations, nonzero scalings, and inversion preserve it; since these generate the Möbius group, every Möbius transformation preserves cross-ratios.

Conversely, suppose a bijection $f$ of the Riemann sphere preserves every cross-ratio. Let $m$ be the unique Möbius transformation agreeing with $f$ at three chosen points $z_1,z_2,z_3$. For any other $z$, preservation by $f$ and $m$ givesThe last coordinate in a cross-ratio with three fixed distinct entries is injective, so $f(z)=m(z)$. The equality already holds at the three base points, hence $f=m$ everywhere and $f$ is Möbius.

Finally, the map $z\mapsto a\overline{z}+b$ is constant when $a=0$ and therefore is not Möbius. If $a\ne 0$, it is bijective and fixes infinity. Were it Möbius, it would have the affine form $\alpha z+\beta$. Equality on real $z$ forces $\alpha =a$ and $\beta =b$, whereas equality at $z=i$ would require $ai=-ai$, contradicting $a\ne 0$. Thus

The set $S(\mathbb{N})$ consists of all bijections $\mathbb{N}\to \mathbb{N}$. The composition of two bijections is a bijection, composition is associative, the identity map is an identity, and every bijection has an inverse, so $S(\mathbb{N})$ is a group.

An element of $S_{\mathrm{fin}}(\mathbb{N})$ has finite support. The support of a composition is contained in the union of the two supports, and a permutation and its inverse have the same support. The identity has empty support. Hence $S_{\mathrm{fin}}(\mathbb{N})$ is a subgroup.

Let $\sigma$ be a cycle and choose $n$ that it moves. Because $\sigma$ has finite support, the sequencemust repeat. Since $\sigma$ is invertible, its first repetition returns to $n$; let the least positive return time be $l$. The cycle condition says that every moved point occurs in this orbit, so ${\sigma }^l$ fixes every point. No smaller positive power fixes $n$. Thereforewhich is finite.

For $\tau \in S_{\mathrm{fin}}(\mathbb{N})$, partition its finite support into the orbits of the cyclic group $⟨\tau ⟩$. On each orbit, let ${\sigma }_i$ agree with $\tau$ and fix every point outside that orbit. Then each ${\sigma }_i$ is a permutation cycle, their supports are pairwise disjoint, andDisjoint cycles commute because at every point at most one of them acts nontrivially.

Writing $l_i=\mathrm{ord}({\sigma }_i)$, a power ${\tau }^m$ is the identity exactly when every ${\sigma }_i^m$ is the identity, equivalently when every $l_i$ divides $m$. Thus

For $a\in U$, the function $f:U\to {\mathbb{R}}^n$ is differentiable at $a$ if there is a linear map $A:{\mathbb{R}}^m\to {\mathbb{R}}^n$ such thatThe linear map is unique and is the Frechet derivative $D{f}_a=A$. The function is continuously differentiable at $a$ if it is differentiable on a neighbourhood of $a$ and the map $x\mapsto D{f}_x$, with values in the space of linear maps equipped with the operator norm, is continuous at $a$.

If $T:{\mathbb{R}}^m\to {\mathbb{R}}^n$ is linear, thenConsequently $D{T}_a=T$ at every $a$. The derivative is a constant function of $a$, hence is continuous, so every linear map is continuously differentiable everywhere.

The mean value inequality says that if the line segment $[x,y]$ lies in $U$ andthenTo prove it, put $v=f(y)-f(x)$. The claim is immediate if $v=0$. Otherwise set $e=v/\Vert v\Vert$ and apply the one-dimensional mean value theorem to the real-valued functionFor some $c\in (0,1)$, the chain rule givesas required.

Now suppose that $U$ is open and connected and that $D{f}_a=0$ for every $a\in U$. Every point has an open ball contained in $U$. The mean value inequality with $M=0$ shows that $f$ is constant on each such ball, so $f$ is locally constant. Fix $a_0\in U$. The level setis nonempty and open in $U$; its complement is also open because $f$ is locally constant. Since $U$ is connected, $E=U$. This proves the zero derivative on a connected open set result: $f$ is constant.

The inverse function theorem states that if $f:U\to {\mathbb{R}}^m$ is continuously differentiable, $a\in U$, and $D{f}_a$ is an invertible linear map, then there are open neighbourhoods $V$ of $a$ and $W$ of $f(a)$ such that $f{|}_V:V\to W$ is a bijection whose inverse is continuously differentiable.

For the curve in the question, define the continuously differentiable functionThenThe implicit function theorem, which follows from the inverse function theorem applied to $(x,y)\mapsto (x,F(x,y))$, therefore gives an open interval $I$ containing $0$, an open neighbourhood $U_0$ of $(0,0)$, and a continuously differentiable, hence continuous, function $g:I\to \mathbb{R}$ such that

No. Letthe successor cardinal of $\kappa$ computed by $M$. Then $\alpha \in M$, and $M$ regards $\alpha$ as a cardinal number. Because $M$ is transitive, $\alpha \subseteq M$, so externallyOn the other hand $\kappa <\alpha$, hence $|\alpha |=\kappa$ in the ambient universe. A corresponding bijection belongs to $V_{\lambda }$ because its rank is below the inaccessible limit $\lambda$. Thus $V_{\lambda }$ regards $\alpha$ as equinumerous with $\kappa$ and therefore not as a cardinal. This is an instance of cardinal nonabsoluteness in a small transitive model.

Use a beta set $X$ on an $e$-runner partition abacus. A hook of length divisible by $e$ corresponds to a bead $x$ and a gap $x-eh$ on the same runner. Divide both runner positions by $e$. They become a bead and a gap at distance $h$ in the runner partition ${\lambda }^{(s)}$, and hence determine a hook there. This gives the required bijection, with $|H|=e|f(H)|$.

Removing $H$ replaces the bead $x$ by the gap $x-eh$. On its runner this is exactly the bead move that removes $f(H)$, while every other runner is unchanged. Thus hook removal commutes with the construction andThis is the abacus divisible-hook correspondence.

For each fixed $\alpha$, right multiplication by $x^{-\alpha }$ is a bijection of $G$, whose inverse is right multiplication by $x^{\alpha }$. Therefore $D_x$ permutes the displayed orthonormal basis of the tensor-product space. It is consequently a unitary operator, with

Since $\gcd (x,N)=1$, multiplication by $x$ modulo $N$ is a bijection of ${\mathbb{Z}}_N$, with inverse multiplication by the modular inverse $x^{-1}$. Hence $U_x$ permutes the standard orthonormal basis. It preserves all inner products and satisfiesso $U_x$ is a unitary operator.

Independence makesa Markov chain. The data processing inequality for mutual information therefore gives $I(X;X+Y+Z)\le I(X;X+Y)$. Translation by the known value of $X$ is a bijection, so conditional entropy and independence giveand $I(X;X+Y)=H(X+Y)-H(Y)$. Rearranging proves the stated entropy submodularity for three independent sums:

Because the Entropic Ruzsa distance depends only on marginal distributions, take $X,Y,Z$ independent with the required marginals. Since $X-Z=(X-Y)+(Y-Z)$ is a function of $(X-Y,Y-Z)$, the data processing inequality for mutual information yieldsThe map $(X,X-Y,Y-Z)\mapsto (X,Y,Z)$ is a bijection. Using independence and the chain rule for information entropy, the left side iswhereas the right side is $H(X-Z)-H(Z)$. Hencewhere the final step is subadditivity of information entropy. Substituting this inequality into the definition of $d_R$ gives the Entropic Ruzsa triangle inequality

A permutation of a set is a bijection from that set to itself.

A pointwise periodic self-map returns each point to itself after a positive number of iterates which may depend on the point. It is a bijection: each finite cycle supplies predecessors; equality of two images can be undone by an iterate with an exponent one below a common multiple of the two periods. The set consequently decomposes into disjoint finite permutation cycles. Pointwise periodicity does not imply that one iterate is the identity on an infinite set.

Map each real into $(0,1)$ by a fixed bijection, choose its canonical binary expansion, and alternate the two bit sequences as ternary digits $0$ and $2$. If two such outputs first differ at position $k$, the leading difference has size $2\cdot 3^{-k}$ and the remaining tail has size at most $3^{-k}$, so they are unequal. This gives an explicit injection pairing two reals. Iteration encodes every fixed finite real tuple without invoking ambiguous decimal expansions.

Insert the successive letters of a permutation by row insertion to obtain an insertion tableau $P$, recording the insertion times in the new boxes of $Q$. This is a bijection between permutations and pairs of standard Young tableaux of a common shape. Reverse insertion removes the box marked by the latest recording time. The first row of $P$ has length equal to the longest increasing subsequence.

The sign homomorphism sends an even permutation to $1$ and an odd permutation to $-1$; its kernel is the alternating group.

A symmetric group is the group of all bijections from a set to itself, with function composition as its operation.