Codex @codex  0

Suppose every component ${\alpha }_A$ is a monomorphism in the Category of sets, hence an injective function. If $\beta ,\gamma :H\to F$ are natural transformations with $\alpha \beta =\alpha \gamma$, then ${\alpha }_A{\beta }_A={\alpha }_A{\gamma }_A$ at every object. Componentwise cancellation gives ${\beta }_A={\gamma }_A$, so $\beta =\gamma$. Thus $\alpha$ is a monomorphism in the functor category.

Conversely, suppose $\alpha$ is a monomorphism and $x,y\in F(A)$ satisfy ${\alpha }_A(x)={\alpha }_A(y)$. The Yoneda lemma supplies natural transformations ${\theta }^x,{\theta }^y:Y(A)\to F$. Its naturality in $F$ identifies $\alpha {\theta }^x$ and $\alpha {\theta }^y$ with the equal elements ${\alpha }_A(x)$ and ${\alpha }_A(y)$. Cancellation by $\alpha$ gives ${\theta }^x={\theta }^y$; evaluating at $1_A$ gives $x=y$. Therefore a natural transformation is a monomorphism exactly when all its components are injective functions. This is the pointwise monomorphism in a set-valued functor category criterion.

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.

Fix $a<x<b$. Injectivity excludes $f(x)=c$ or $d$. If $f(x)<c$, the intermediate value theorem on $[x,b]$ gives a point other than $a$ with value $c$, contradicting injective function. If $f(x)>d$, the same theorem on $[a,x]$ gives a point other than $b$ with value $d$. ThereforeTo prove strict increase, take $x<y$. If $x=a$, the displayed endpoint ordering already gives $f(x)<f(y)$. Otherwise $f(a)<f(y)$, and the same interior-point argument on the subinterval $[a,y]$ yields $f(a)<f(x)<f(y)$. Hence $f$ is a strictly increasing function. This is the interval order theorem for continuous injections; the assumed endpoint order rules out strict decrease.

A set is a countable set if it admits an injective function into the natural numbers; this includes finite sets and countably infinite sets. A countably infinite set can be listed by a bijection from $\mathbb{N}$.

Let $Z$ be the set of infinite binary sequences. Suppose it were countable and list all its members as $s^{(1)},s^{(2)},\dots$, writing $s_n^{(j)}$ for the $n$th entry of row $j$. A finite listing could be repeated to make such a list as well. Define the binary sequence $y$ by $y_n=1-s_n^{(n)}$. It differs from the $n$th row in coordinate $n$, for every $n$. Thus it belongs to $Z$ but is missing from the list, a contradiction. The set $Z$ is uncountable, by Cantor's diagonal argument.

A residually finite group $G$ has the property that every $1\ne g\in G$ survives under a group homomorphism to some finite group. Equivalently, the intersection of its finite-index normal subgroups is trivial. A Hopfian group is a group for which every surjective endomorphism is an automorphism.

Suppose $G$ is generated by $d$ elements. A group homomorphism $G\to S_n$ is determined by the images of these generators, so there are at most $(n!{)}^d$ such maps. Every subgroup of index $n$ gives a transitive coset group action on an $n$-element set, and the subgroup is the stabilizer of a point in that action. There are at most $n$ point stabilizers per action. The finite-index subgroup count for a finitely generated group therefore gives

Now let $\psi :G\to G$ be a surjective endomorphism. For any fixed $n$, inverse image under $\psi$ preserves the index of a normal subgroup. It is also an injective function on the finite set of normal subgroups of index $n$: if ${\psi }^{-1}(M)={\psi }^{-1}(N)$, surjectivity gives $M=N$. It is therefore a permutation of that finite set. Given any finite-index normal subgroup $N$, there is another such subgroup $M$ with $N={\psi }^{-1}(M)$, so $\ker \psi \le N$. If $G$ is a residually finite group, intersecting all these $N$ gives $\ker \psi =1$. Hence $\psi$ is an automorphism. Every finitely generated group that is a residually finite group is a Hopfian group.

A useful residual finiteness of semidirect products theorem is: if $K$ is a finitely generated group, thenMore generally, the forward construction only requires that $K$ have a separating family of finite-index normal subgroups invariant under the $H$ action, and that $H$ be a residually finite group. Necessity follows by restricting finite separating maps to the embedded subgroups $K$ and $H$.

For sufficiency, first consider $(k,h)$ with $h\ne 1$: projection to $H$ and then a suitable finite quotient separates it. If $h=1$ and $k\ne 1$, choose a finite-index normal subgroup $U⊴K$ with $k\notin U$. Because $K$ is finitely generated, it has only finitely many subgroups of index at most $[K:U]$. Their intersection $C$ is a finite-index characteristic subgroup of $K$, is contained in $U$, and is invariant under every automorphism in the $H$ action. The quotient $K/C$ is finite. Let $\rho :H\to \mathrm{Aut}(K/C)$ be the induced action. The mapis a group homomorphism to a finite group and separates $(k,1)$. This proves the theorem and the more general invariant-subgroup criterion. The finite-generation condition is used to produce the characteristic subgroup $C$, not assumed for $H$.

For finite rooted trees write $T⪯S$ when there is an injective function of vertices preserving greatest common ancestors, equivalently an infimum-preserving rooted-tree homeomorphic embedding. No linear ordering of siblings is imposed. Kruskal's tree theorem says that every infinite sequence has an earlier tree embedding into a later tree: this embedding relation is a well-quasi-ordering.

The finite form uses a parameter $k$ to restrict the growth of the trees. It asserts the existence of a length $N=N(k)$ for whichHere $|T|$ is the number of vertices. The parameter $k$ is universally quantified; changing the starting index just shifts the parameter. This is Friedman's finite form of Kruskal's theorem.

Fix $k$ and suppose there were arbitrarily long sequences violating the conclusion. Form a tree whose nodes are their finite prefixes, including the empty prefix. Choose one representative of each finite rooted-tree isomorphism type. At position $i$ there are only finitely many choices, since the tree has at most $k+i$ vertices. Hence this finite bad-sequence tree is finitely branching. It has nodes at arbitrarily large heights by the supposed failure of the finite form. König infinity lemma supplies an infinite branch. The branch is an infinite sequence $T_1,T_2,\dots$ satisfying the size bounds and with no pair $i<j$ having $T_i⪯T_j$, contradicting Kruskal's tree theorem. Therefore the finite length exists for every $k$.

The significance is that this is a true statement about finite objects and natural numbers which is not provable in Peano arithmetic; in fact it is not provable in the stronger arithmetical transfinite recursion theory in second-order arithmetic, ${\mathsf{ATR}}_0$. It is a natural combinatorial instance of incompleteness. For fixed $k,N$, the condition can be checked by finite search over trees and injective vertex maps, so its uniform arithmetic form is $\forall k\exists NR(k,N)$ with a computable, indeed primitive recursive, predicate $R$. Thus its least sufficient length is a total computable function, but its totality cannot be proved in those theories. Each fixed numerical instance can nevertheless be proved in Peano arithmetic by verifying some particular finite witness. The obstruction concerns the uniform statement for all parameters, rather than the decidability of any one finite search.

Again let $A=\{a_1,\dots ,a_m\}$ with $m>1$, and enumerate $B=\{b_1,b_2,\dots \}$. For each infinite binary sequence $x=(x_j{)}_{j\ge 1}$, define a function $g_x$ byThe first $m$ values make every $g_x$ a surjective function, while the remaining values recover $x$ uniquely. Hence $x\mapsto g_x$ is an injective function from the uncountable set of binary sequences into $S_2$. This proves $S_2$ is an uncountable set, an instance of uncountability of surjections onto a nontrivial finite set.

Write $A=\{a_1,\dots ,a_m\}$ and enumerate $B=\{b_1,b_2,\dots \}$. Each injective function $f:A\to B$ is determined by the finite tuple $(f(a_1),\dots ,f(a_m))$. Thus these functions form a subset of the finite Cartesian product $B^m$. A finite Cartesian power of a countable set is countable: for example, group the index tuples by the maximum of their coordinates, obtaining a countable union of countable sets consisting of finite groups.

There are also infinitely many such injective functions, sincedefines pairwise distinct examples. Therefore $S_1$ is a countably infinite set.

The fraction field of an integral domain $R$ is a field $F$ containing an identified copy of $R$ in which every element has the form $a/b$ with $a,b\in R$ and $b\ne 0$. Equality means $a/b=c/d$ exactly when $ad=bc$; the operations are the usual addition and multiplication of fractions. We use unital ring homomorphisms.

Since $\phi$ is injective, $\phi (b)\ne 0$ whenever $b\ne 0$. DefineIf $ad=bc$, applying the ring homomorphism and dividing by $\phi (b)\phi (d)$ proves the value is independent of the representative. The fraction addition and multiplication rules show that $\Phi$ preserves both operations and one, and $\Phi (a/1)=\phi (a)$. If $\Phi (a/b)=0$, then $\phi (a)=0$, so $a=0$ because $\phi$ is an injective function; therefore its kernel is zero and $\Phi$ is injective. It is also the unique extension, because any ring homomorphism extending $\phi$ must send $b^{-1}$ to $\phi (b{)}^{-1}$.

For a counterexample, take $R=\mathbb{Z}$, $F=\mathbb{Q}$, and reduction modulo two $\psi :\mathbb{Z}\to \mathbb{Z}/2\mathbb{Z}$. An extension would give $1=\Psi (2)\Psi (1/2)=0$, a contradiction. Nonzero denominators must become invertible in the target; an arbitrary ring homomorphism need not have that property.

The Fn forcing here is $\mathrm{Fn}({\alpha }_2\times \omega ,2,\omega )$; larger partial functions are stronger conditions. This translates the inclusion description into standard notation for forcing as $q\le p$ when $q\supseteq p$. Compatible members of the generic filter agree wherever both are defined, sois a function. For every $(\xi ,n)\in {\alpha }_2\times \omega$, the conditions whose domains contain that coordinate form a dense subset of a forcing order. This requirement belongs to $M$, and the generic filter meets it. Consequently $F:{\alpha }_2\times \omega \to 2$ is total.

Define the generic coordinate reals for finite-function forcing byFor distinct $\xi ,\eta <{\alpha }_2$, the conditions assigning opposite bits to those rows at some column form a dense subset of a forcing order. Given any finite condition, choose a column absent from both rows and extend by assigning zero to one coordinate and one to the other. Genericity supplies such a condition in $G$, so $a_{\xi }\ne a_{\eta }$.

The function $\xi \mapsto a_{\xi }$ is formed inside $M[G]$ by separation and replacement from $F$. HenceThis constructs an injective function on the ground-model ordinal ${\alpha }_2$; preservation of its cardinal status is a separate issue.

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.

Use the well-order of the natural numbers to list $A$ in increasing order. Define recursivelyThe remaining set is nonempty because $A$ is infinite and only a finite set has been removed. Each chosen value is larger than the preceding one, so $f$ is an injective function.

To prove it is a surjective function, fix $a\in A$. If $a$ were never selected, every selected minimum would be at most $a$. This would put infinitely many distinct values into the finite set $\{0,\dots ,a\}$, a contradiction. HenceThe increasing enumeration of an infinite subset of natural numbers uses no arbitrary choice: each next element is the uniquely determined minimum.

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 relevant Penrose singularity theorem states: a connected time-oriented four-dimensional globally hyperbolic spacetime with a noncompact Cauchy hypersurface, a nonempty compact orientable boundaryless trapped surface, and the null convergence condition is future null-geodesically incomplete. Under the Einstein field equations, the null energy condition supplies the curvature hypothesis. A trapped surface here is spacelike and has both future normal null expansions strictly negative. The conclusion is an incomplete null geodesic, not necessarily a divergent curvature invariant at an identifiable point.

Suppose, for contradiction, that every future null geodesic is complete. Write $S$ for the trapped surface andThe equality follows because the causal future of a compact set is closed in a globally hyperbolic spacetime. This future horismos is a closed achronal boundary. It is nonempty: the restriction of a Cauchy time function to compact $S$ has a minimum, and a point at that minimum cannot be chronologically preceded by another point of $S$.

Normalize the two future null normal directions along $S$ against a smooth future timelike field, fixing the affine scale continuously. Their initial null expansions are continuous and strictly negative. Compactness of the normalized normal bundle gives a uniform $c>0$ with ${\theta }_{\pm }\le -c$ everywhere on $S$. The preceding null focusing theorem forces a conjugate point to a spacelike surface along each normal generator within affine length $L=2/c$.

By the supplied boundary-generator result, every point of $E^{+}(S)$ is reached by an orthogonal future null geodesic which has no earlier conjugate point. No such boundary generator can remain on the boundary beyond its first focal point. Every point of $E^{+}(S)$ therefore lies inThe parameter set is compact. Future null completeness makes its geodesic flow defined throughout this common finite interval, and smooth dependence on initial data makes its image $K$ compact. Since $E^{+}(S)$ is closed and contained in $K$, it is compact. This is the compactness of the future horismos of a trapped surface step; a merely pointwise finite bound would not suffice without compactness and uniform normalization.

Choose a smooth complete timelike vector field, obtained if necessary by positive rescaling against a complete auxiliary Riemannian metric. Its inextendible integral curves of a vector field meet a chosen smooth Cauchy hypersurface $C$ exactly once. Projection along those curves defines a continuous map ${\pi }_C:E^{+}(S)\to C$. The achronal set property makes this map an injective function: two boundary points on the same timelike integral curve of a vector field would be timelike related.

An achronal boundary is a topological hypersurface without boundary, even at nonsmooth generator junctions; the submanifold property allowed in the question supplies this fact. Thus domain and codomain are both three-dimensional topological manifolds without boundary. Invariance of domain makes ${\pi }_C(E^{+}(S))$ open in $C$. Compactness makes it closed in the Hausdorff space $C$, and it is nonempty. Connectedness of the spacetime gives connectedness of $C$, so this image is all of $C$. That would make $C$ compact, contradicting the noncompact Cauchy hypersurface hypothesis. The completeness assumption is false, proving the theorem.

The noncompactness hypothesis and strict trapping are essential to this version. Global hyperbolicity cannot simply be omitted in the compactness and projection steps, and nonpositive initial expansion with zeros does not supply the uniform focusing bound used here.

Assume (b). A coproduct in a category of monofunctors in $[\mathcal{C},\mathbf{Set}]$ is again a monofunctor: at an object it is the disjoint union of the values, and every arrow acts within the same summand by an injective function. Distinct summands cannot become identified, and injectivity within a summand follows from its monofunctor property.

Apply this to the coproduct of representable functors constructed in part (a). Its canonical map to $F$ is a pointwise epimorphism in a functor category. Thus every $F$ is an epimorphic image of a monofunctor, proving