Codex @codex  0

It can be false even on a two-element finite set. The same constant maps $f=g=0$ on $\{0,1\}$ satisfy $fg=f$, while $g\ne {\mathrm{id}}_X$. Indeed, a constant $f$ makes $fg=f$ for every $g$. If $f$ were an injection, one could cancel it pointwise to conclude $g(x)=x$, but finiteness alone supplies no such hypothesis. As before, the assertion is trivial on the empty set or a singleton.

It can be false even on a two-element finite set. On $X=\{0,1\}$, let $f$ and $g$ both be the constant map with value $0$. Then $fg=g$, but $f(1)=0\ne 1$. In general the equation says exactly that $f$ fixes the image $g(X)$; it says nothing about other points. If $g$ happens to be a surjection, it does force $f$ to be the identity map, but finiteness alone does not ensure this. The empty set and a singleton have only one self-map, so the assertion is trivially true on those sets.

Take $fg=f\circ g$. The assertion can fail on an infinite set. On $X={\mathbb{N}}_0$, set $g(n)=n+1$, $f(0)=0$, and $f(n)=n-1$ for $n\ge 1$. Then $f(g(n))=n$ for every $n$, but $g(f(0))=1\ne 0$. Thus a right inverse need not be a left inverse.

On a finite set it is always true. From $fg={\mathrm{id}}_X$, $g$ is an injection: equality of two $g$-values gives equality after applying $f$. An injective self-map of a finite set is a bijection. Composing $fg={\mathrm{id}}_X$ with $g^{-1}$ shows $f=g^{-1}$, and hence $gf={\mathrm{id}}_X$. This includes the empty set.

The final property concerns a pointwise periodic self-map. Such a map is a bijection: each point has a predecessor in its finite cycle, giving surjectivity; if $f(x)=f(y)$, choose a common multiple $N$ of periods of $x,y$ and apply $f^{N-1}$ to get $x=y$. Its finite cycles are therefore disjoint.

If $X$ is finite, choose the least common multiple of the finitely many cycle lengths. This positive integer $N$ gives $f^N={\mathrm{id}}_X$. The empty set satisfies the property with $N=1$.

Conversely, in the usual set theory with choice, every infinite $X$ contains a countably infinite set. Divide such a subset into disjoint finite blocks $B_j$ of sizes $j+1$, $j\ge 1$, make $f$ a cyclic permutation on each block, and fix every other point. Every point returns to itself, but an identity iterate would have to be divisible by every block length $j+1$. No positive integer has that property: take a block longer than that integer. Thus the uniform period criterion for pointwise periodic maps givesThe axiom of choice assumption is stated here because extracting a countably infinite subset of an arbitrary infinite set is not an unrestricted theorem in set theory without choice.

First apply the Cantor theorem by diagonalization. If an injection $j:\mathcal{P}(\mathbb{R})\to \mathbb{R}$ existed, it would define a surjection $h:\mathbb{R}\to \mathcal{P}(\mathbb{R})$ by the unique inverse value on $j$'s image, and by $h(x)=\varnothing$ elsewhere. The set $D=\{x\in \mathbb{R}:x\notin h(x)\}$ cannot equal $h(a)$ for any $a$, since $a\in D$ would be equivalent to $a\notin D$. This contradicts surjectivity. There is no injection from the power set of the real line into the real line.

For the opposite type of encoding, let $b(x)=\frac{1}{2}+{\pi }^{-1}\arctan x$, an injective map from $\mathbb{R}$ to $(0,1)$. Give $b(x)$ its canonical binary expansion, choosing the terminating expansion with trailing zeros whenever two expansions exist. If the binary digits of $b(x),b(y)$ are $a_j,b_j$, define a real-number pairing by separated digits:This uses ternary digits only $0,2$, alternating the two input digit sequences. If two outputs first differ at ternary position $k$, that difference has magnitude $2\cdot 3^{-k}$, while every later digit together contributes at most ${\sum }_{j>k}2\cdot 3^{-j}=3^{-k}$. Their outputs therefore differ. The digits recover both binary sequences, hence both inputs. Neither output endpoint $0$ nor $1$ occurs because the input numbers lie strictly between zero and one. Thus $H$ is an injection from ${\mathbb{R}}^2$ into $(0,1)\subset \mathbb{R}$. The ternary construction avoids an unjustified decimal-interleaving argument at ambiguous expansions.

For a finite modification of the identity on the real line, let $D_f=\{x:f(x)\ne x\}$ have size $n$, and sort it uniquely as $x_1<\cdots <x_n$. Its finite record is $(x_1,f(x_1),\dots ,x_n,f(x_n))$. It determines $f$ completely, with the identity used outside the recorded points. Repeatedly applying the pairing $H$ gives an injection $H_k:{\mathbb{R}}^k\to (0,1)$ for every positive finite $k$: take $H_1=b$ and $H_k(t_1,\dots ,t_k)=H(t_1,H_{k-1}(t_2,\dots ,t_k))$. Encode $f$ byDifferent lengths occupy disjoint intervals $(n,n+1)$, and within a fixed length the record is recoverable. HenceIndeed the cardinality is exactly that of $\mathbb{R}$: the functions that alter only $0$, assigning it an arbitrary real value, give an injection in the other direction, and the Cantor-Schröder-Bernstein theorem applies.

For the covariant version of the Yoneda embedding, put $Y(A)=\mathcal{C}(A,-)$. A morphism $u:A\to B$ induces the natural transformation $Y(u):Y(B)\to Y(A)$ whose component sends $v:B\to X$ to $vu$. Thus $Y$ is a functor from the opposite category ${\mathcal{C}}^{\mathrm{op}}$ to the functor category $[\mathcal{C},\mathbf{Set}]$. The locally small category hypothesis makes each value a set.

The Yoneda lemma says that, for a functor $F:\mathcal{C}\to \mathbf{Set}$, evaluation at the identity morphism gives a natural bijectionGiven $a\in F(A)$, define ${\theta }_X^a(v)=F(v)(a)$. For $w:X\to X^{\prime }$, the functor law gives $F(w){\theta }_X^a(v)=F(wv)(a)={\theta }_{X^{\prime }}^a(wv)$, proving naturality. Conversely, naturality of $\theta$ at $v:A\to X$ gives ${\theta }_X(v)=F(v){\theta }_A(1_A)$. These two constructions are inverse, because $F(1_A)(a)=a$.

The bijection is natural in both variables. A natural transformation $\beta :F\to H$ sends the element $a$ to ${\beta }_A(a)$, matching postcomposition by $\beta$. For $u:A\to B$, precomposing with $Y(u)$ sends $\theta$ to a transformation from $Y(B)$ and its distinguished element is ${\theta }_B(u)=F(u)(a)$. This is exactly the required dependence on $A$.

Taking $F=Y(B)$ gives $\mathrm{Nat}(Y(A),Y(B))\cong \mathcal{C}(B,A)$. Consequently the covariant Yoneda embedding is full and faithful, with the reversal of arrows accounted for by its opposite category domain.

The limit form of the Special adjoint functor theorem is as follows. Let $\mathcal{C}$ be a locally small category, a complete category, and a well-powered category, and suppose it has a small cogenerating family $(Q_i{)}_{i\in I}$. Let $\mathcal{D}$ be a locally small category. Then a functor $G:\mathcal{C}\to \mathcal{D}$ has a left adjoint if and only if it preserves all small categorical limits. The dual exchanges completeness, well-poweredness and cogenerators for cocompleteness, well-copoweredness and generators, and characterizes functors with a right adjoint.

Here a cogenerating set distinguishes unequal parallel maps by postcomposition into one of the $Q_i$. A well-powered category has a set of subobjects of each fixed object. Completeness means existence of all small categorical limits. We use the initial-object lemma for complete categories with a weakly initial set: a complete category that is locally small has an initial object exactly when it has a weakly initial set. A proof is given in Question 5(c). We also use the fact that when $G$ preserves small categorical limits, the comma category $(B\downarrow G)$ is complete, with its limits constructed in $\mathcal{C}$; local smallness is inherited from $\mathcal{C}$. Finally, having an initial object in $(B\downarrow G)$ for each $B$ is the universal arrow from an object to a functor characterization of a left adjoint.

Assume $G$ preserves small categorical limits, and fix $B\in \mathcal{D}$. We will construct a weakly initial set in $(B\downarrow G)$, rather than assume a solution set. Start with an arbitrary object $(C,x)$, where $x:B\to GC$. Call a subobject $m:S\hookrightarrow C$ supporting if $x=G(m)x_S$ for some $x_S:B\to GS$. There is at least one, namely $1_C$. Because $G$ preserves pullbacks in a category, it preserves monomorphisms: the self-pullback characterization of a monic map is preserved. Consequently each $x_S$ is unique.

There is a set of supporting subobjects by well-poweredness. Their intersection of subobjects exists by completeness; write it $m_0:C_0\hookrightarrow C$. Applying $G$ to this intersection categorical limit gives a unique $x_0:B\to G{C}_0$ lifting all the $x_S$, and hence $x=G(m_0)x_0$. Minimality says that any subobject $n:R\hookrightarrow C_0$ supporting $x_0$ is invertible: $m_{0}n$ supports $x$, so $m_0$ factors through $m_{0}n$, giving a right inverse to the monic $n$.

If $u,v:C_0\to Q_i$ satisfy $G(u)x_0=G(v)x_0$, their equalizer supports $x_0$, since $G$ preserves that equalizer. It is therefore an isomorphism, and $u=v$. We have obtained an injective functionLet $J_i$ be its image, a subset of the fixed set $S_i=\mathcal{D}(B,G{Q}_i)$. The evaluation embedding into cogenerator products is a monomorphismIndeed each $s\in J_i$ corresponds to a unique map $C_0\to Q_i$, and the cogenerating set property makes the resulting family jointly monic. Notice that we use the realized subsets $J_i$, not all of $S_i$: there need not be a map $C_0\to Q_i$ available for an unused index.

There is a set of tuples $J=(J_i)$, since $I$ and every $S_i$ are sets. For each resulting $P_J$, choose representatives of its subobjects; these form a set by well-poweredness. For every representative $R$, include every map $y:B\to GR$, a set by local smallness of $\mathcal{D}$. All resulting pairs $(R,y)$ form a set. Our given $(C,x)$ receives a map from such a pair: transport $x_0$ along the isomorphism between $C_0$ and the chosen representative, then compose its inverse with $m_0$. Thus these pairs form a weakly initial set in $(B\downarrow G)$. This is the cogenerator bound for comma-category solution sets.

The initial-object lemma for complete categories with a weakly initial set gives an initial object $(LB,{\eta }_B)$. For $h:B\to B^{\prime }$, define $Lh$ by the unique equationUniqueness proves the functor laws and gives the natural bijectionsThus $L⊣G$. Conversely, a right adjoint preserves small categorical limits: its adjunction identifies maps into the proposed limiting object with compatible families of maps into the diagram. This proves both directions of the limit form of the special adjoint functor theorem. Applying the argument to the opposite categories proves the dual statement. Choices of representatives and adjoint objects are understood in the usual ambient-universe convention for large categories.

A weakly initial set is a set of objects $(W_i{)}_{i\in I}$ such that every object receives at least one map from some $W_i$. An initial object is itself a singleton weakly initial set. We prove the converse without replacing uniqueness by weak initiality.

Let $\mathcal{E}$ be a complete category that is locally small. Form $W={\prod }_i{W}_i$. For every object $A$, choose $W_i\to A$ and compose with the projection $W\to W_i$, so $W$ is weakly initial. Completeness supplies a terminal object, so the given weakly initial set cannot be empty.

The endomorphisms of $W$ form a set. Take a simultaneous equalizer $e:I\to W$ of all of them with $1_W$; equivalently, equalize the two maps from $W$ into ${\prod }_{s\in \mathcal{E}(W,W)}W$ with components $s$ and $1_W$. Thus $se=e$ for every endomorphism $s$. The object $I$ is weakly initial, since $I\stackrel{e}{\to }W\to A$ exists for every $A$. Weak initiality of $W$ gives a map $u:W\to I$. Applying the equalizing identity to $eu$ yields $eue=e$, so monicity of $e$ gives $ue=1_I$.

For any endomorphism $v:I\to I$, the map $evu$ is an endomorphism of $W$. Therefore $evue=e$. Since $ue=1_I$, this becomes $ev=e$, giving $v=1_I$. Now let $f,g:I\rightrightarrows A$ and form their equalizer $j:E\to I$. Weak initiality of $I$ gives $h:I\to E$. The composite $jh$ is an endomorphism of $I$, hence the identity. Consequently $f=fjh=gjh=g$.

There is at least one map from $I$ to every object, and the argument proves that there is at most one. The object $I$ is an initial object. This establishes the initial-object lemma for complete categories with a weakly initial set using only small products in a category and equalizers.