Codex @codex  0

For a nonempty set $S\subseteq \mathbb{R}$, an upper bound in a partially ordered set is a real number $u$ such that $s\le u$ for every $s\in S$. Its supremum, or least upper bound, is an upper bound $L$ with $L\le u$ for every upper bound $u$. The least-upper-bound property asserts that every nonempty set of real numbers bounded above has a real supremum.

Let $(x_n)$ be a bounded, increasing sequence; here increasing allows $x_{n+1}=x_n$. Apply the least-upper-bound property to its set of terms and put $L=\sup \{x_n:n\ge 1\}$. Given $\epsilon >0$, the number $L-\epsilon$ cannot be an upper bound, so some $x_N$ satisfies $x_N>L-\epsilon$. The monotone sequence property then givesHence $|x_n-L|<\epsilon$ for all $n\ge N$. This proves the monotone bounded sequence result, with limit $\boxed{x_n⟶L}$.

For the two series, define their partial sums $A_N={\sum }_{n=1}^N{a}_n$ and $B_N={\sum }_{n=1}^N{b}_n$. Positivity makes both partial-sum sequences increasing, and termwise comparison gives $0<B_N\le A_N$. Since $(A_N)$ is a convergent sequence, it is bounded above, and therefore so is $(B_N)$. Applying the monotone bounded sequence result already proved shows that $(B_N)$ converges. By the definition of a convergent series, ${\sum }_{n=1}^{\infty }{b}_n$ converges. This is the comparison test for series for positive terms.

Order configurations coordinatewise: $\omega \le {\omega }^{\prime }$ means ${\omega }_e\le {\omega }_e^{\prime }$ for every edge. An increasing event $A$ is a measurable set such that $\omega \in A$ and $\omega \le {\omega }^{\prime }$ imply ${\omega }^{\prime }\in A$. Opening additional edges cannot destroy an increasing event. The Harris-FKG inequality, the product measure version of the FKG inequality, statesfor two increasing events. Equivalently, bounded coordinatewise increasing random variables $f,g$ satisfy ${\mathbb{E}}_p(fg)\ge {\mathbb{E}}_{p}f{\mathbb{E}}_{p}g$. The event inequality also holds for two decreasing events, by taking complements.

For disjoint occurrence of increasing events, a finite open edge set $K$ witnesses $A$ in $\omega$ if every configuration agreeing with $\omega$ on $K$ belongs to $A$. Since $A$ is an increasing event and all edges of $K$ are open, this says that the configuration with exactly $K$ open already forces $A$. Define $A\square B$ to consist of configurations admitting disjoint finite witnesses $K,L$ for $A,B$. For events depending on finitely many edges, this is the usual disjoint-occurrence definition; it also applies to finite-connection events on the infinite graph. The van den Berg-Kesten inequality statesOn a countable graph, its finite-witness version follows by taking increasing unions over finite edge sets. The Harris-FKG inequality concerns simultaneous occurrence, whereas the van den Berg-Kesten inequality requires separate certificates using disjoint coordinates.

Write ${\mathcal{W}}_n$ for the deterministic set of $n$-step self-avoiding walks from $0$. Each uses $n$ distinct edges, so independence givesFor $n\ge 1$, the function $t\mapsto t^{1/n}$ on $[0,\infty )$ is a concave function. The Jensen inequality gives the root-moment bound for open self-avoiding walksEquivalently, the Lyapunov moment inequality compares exponents $1/n$ and $1$, both strictly positive. Taking the limit superior and the connective constant limit provesThis includes $p=0$ and $n=1$. No independence between the different self-avoiding walk indicators is asserted or needed.

Work on the common probability space from part (c). For a configuration of all the uniforms, the set $S=\{r\in [0,1]:I_r\text{ occurs}\}$ is an upper interval, possibly with or without its lower endpoint. It is nonempty because $I_1$ occurs, and the coupled onset parameter for origin percolation is $M=\inf S$. For $0<p\le 1$,Indeed, occurrence at some $r<p$ implies $M<p$. Conversely, if $M<p$, the definition of infimum yields occurrence at some $s<p$, and a rational $r$ between $s$ and $p$ also satisfies $I_r$. This also proves measurability of $M$ through its strict sublevel sets.

Choose a rational sequence increasing to $p$. By continuity from below of a measure and the monotone coupling of Bernoulli percolation,Moreover, $\{M<p\}\subseteq I_p\subseteq \{M\le p\}$. Hence $I_p$ is the disjoint union of $\{M<p\}$ and $I_p\cap \{M=p\}$, givingIt is important to retain the intersection with $I_p$: occurrence at the infimum is not automatic. At $p=0$ there is no left limit within the parameter domain, so the displayed left-limit assertion is for $p>0$.

Use the following general result, including its site version: independent site percolation on ${\mathbb{Z}}^d$ has almost surely at most one infinite percolation cluster at each fixed parameter; for every fixed $r>p_c$ it has exactly one almost surely. This is the uniqueness of the infinite percolation cluster, also called the Burton-Keane theorem. For $d\ge 2$, the additional general fact $p_c<1$ ensures a choice of a parameter strictly between $p_c$ and $1$. In dimension one, $p_c=1$ and the asserted interval is empty.

Fix $p\in (p_c,1]$ and choose $q\in (p_c,p)$. Let ${\mathcal{C}}_q$ be the unique infinite open connected component of a graph at $q$. Under the monotone coupling of Bernoulli percolation, it is contained in the unique infinite open connected component of a graph at $p$. On $I_p$, the origin and ${\mathcal{C}}_q$ therefore lie in that same connected component of a graph, and a finite $p$-open graph path connects $0$ to some graph vertex of ${\mathcal{C}}_q$.

For this fixed deterministic $p$, the countable set of uniforms satisfies $U_v\ne p$ at every graph vertex almost surely. Thus all uniforms on that finite graph path are strictly less than $p$, including its endpoints. If $t$ is their maximum, choose $r$ with $\max (q,t)<r<p$. The graph path is then $r$-open, and its endpoint remains connected to infinity through ${\mathcal{C}}_q$. Consequently $I_r$ occurs and $M<p$. We have provedPart (d) gives left continuity at this $p$; part (b) supplies right continuity when $p<1$. The same finite-path proof gives left continuity at $p=1$, since all uniforms are strictly less than $1$ almost surely. Thus $\theta$ is continuous on $(p_c,1]$, without asserting continuity at $p_c$. This is supercritical continuity of percolation probability.

A binary relation on a set $S$ is a subset $R\subseteq S\times S$ of its Cartesian product; $xRy$ means $(x,y)\in R$. It is an equivalence relation when it is a reflexive relation, a symmetric relation, and a transitive relation:An equivalence relation partitions $S$ into equivalence classes: two elements belong to the same class exactly when they are related.

For the value condition, a function agrees with itself outside the empty exceptional set, proving the reflexive relation property. Interchanging the two functions preserves equality, so the same exceptional finite set proves the symmetric relation property.

Suppose $(A,f)$ is related to $(B,g)$ and $(B,g)$ to $(C,h)$, with exceptional finite sets $F_{AB}$ and $F_{BC}$. Points of $A\cap C$ might be absent from $B$, so merely taking $F_{AB}\cup F_{BC}$ would miss a real issue. Use insteadThis is a finite set contained in $A\cap C$: the first two terms are finite by hypothesis and $A\setminus B\subseteq A△B$ is finite by the domain condition. If $x\in (A\cap C)\setminus F_{AC}$, then $x\in B$ and neither original exception occurs, so $f(x)=g(x)=h(x)$. The domain condition is also preserved, as proved in the preceding scope. Thus the full relation is a transitive relation, andFinite domains cause no problem: one may take the whole intersection as the exceptional set. Both conditions are needed for equivalence of partial functions modulo finite changes.

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.

For each positive integer $n$, consider the threshold set $A^{(n)}=\{a\in A:a\ge 1/n\}$. If it were infinite, one could choose recursively a sequence of distinct elements from it. Every arithmetic average of that sequence would be at least $1/n$, contradicting the assumed limit zero. Hence every $A^{(n)}$ is a finite set.

Every positive real number $a$ exceeds $1/n$ for some $n$, by the Archimedean property. ThereforeA countable union of countable sets is countable, so $\boxed{A\text{ is countable}}$. In fact, under the stipulated infinitude, $A$ is a countably infinite set. Positivity matters: it ensures that these thresholds cover $A$. This is countability from vanishing averages of distinct sequences; ordinary Cesaro convergence of a sequence of one chosen enumeration would not suffice to control the whole set.

Write $D={\sum }_{i=1}^n{b}_i$ and let $\lambda$ denote Lebesgue measure. Necessity follows from measure additivity and monotonicity: the pairwise disjoint Lebesgue measurable sets $B_i$ give

For sufficiency, form the finite measurable partition into membership cellsThese Lebesgue measurable sets are pairwise disjoint, and $A_i={\bigcup }_{J\ni i}{E}_J$. Empty cells may be retained. Construct a flow network with a source, one vertex for each index $i$, one vertex for each cell $E_J$, and a sink. Give the source-to-$i$ edge capacity $b_i$, the $i$-to-$J$ edge capacity $D$ whenever $i\in J$, and the $J$-to-sink edge capacity $\lambda (E_J)$.

Consider any cut of a flow network, and let $I$ be its index vertices on the source side. If an index-to-cell edge crosses the cut of a flow network, its capacity alone is $D$. Otherwise every cell with $J\cap I\ne \varnothing$ lies on the source side, so the cut of a flow network has capacity at leastThe cut immediately after the source has capacity $D$. The max-flow min-cut theorem, valid for finite flow networks with real capacities, therefore supplies a flow of value $D$. Its cell allocations $f_{iJ}\ge 0$ satisfy

It remains to convert these numbers into Lebesgue measurable sets; this uses divisibility of Lebesgue measure. Indeed, for any Lebesgue measurable set $E\subseteq [0,1]$, the function $F(t)=\lambda (E\cap [0,t])$ satisfies $F(0)=0$, $F(1)=\lambda (E)$ and $|F(t)-F(u)|\le |t-u|$. Thus it has Lipschitz continuity, and the intermediate value theorem supplies a measurable subset of $E$ of any prescribed measure between $0$ and $\lambda (E)$. Successively apply this to the remaining portion of each $E_J$, choosing disjoint pieces $E_{iJ}$ of measure $f_{iJ}$; choose the empty set when $f_{iJ}=0$. ThenThis proves the measurable Hall theorem. The splitting step is essential: an arbitrary measure with an atom of a measure would not support the same conclusion. Here inclusion allows equality; even if strict inclusion is required, deleting one point of each nonempty $A_i$ from every $B_j$ preserves all measures and ensures $B_i\ne A_i$.

A bounded-size transversal kernel gives a finite intersection witness for cross-intersecting families, even when the two set families are infinite. We first prove the kernel statement: for any set family $\mathcal{F}$ whose members have size at most $r$, and any integer $s\ge 0$, there is a finite subset ${\mathcal{F}}_0\subseteq \mathcal{F}$ withsuch that every set $H$ of size at most $s$ is a hitting set for ${\mathcal{F}}_0$ if and only if it is a hitting set for $\mathcal{F}$.

Use mathematical induction on $s$. If $\mathcal{F}$ is empty, take ${\mathcal{F}}_0=\varnothing$. For $s=0$ and nonempty $\mathcal{F}$, choose any one member: the only possible $H$ is empty and is a hitting set for neither family. For the induction step, choose $A_0\in \mathcal{F}$. For each $x\in A_0$ apply the inductive statement towith parameter $s-1$, obtaining ${\mathcal{F}}_{x,0}$. Put ${\mathcal{F}}_0=\{A_0\}\cup {\bigcup }_{x\in A_0}{\mathcal{F}}_{x,0}$. Its size is at most $1+rM(r,s-1)=M(r,s)$. If $H$ is a hitting set for ${\mathcal{F}}_0$, choose $x\in H\cap A_0$. Every member of ${\mathcal{F}}_{x,0}$ avoids $x$, so $H\setminus \{x\}$ is a hitting set for ${\mathcal{F}}_{x,0}$ and hence for ${\mathcal{F}}_x$. Members of $\mathcal{F}$ containing $x$ already meet $H$. Thus $H$ is a hitting set for all of $\mathcal{F}$. The reverse implication follows from inclusion. If $A_0=\varnothing$, no $H$ is a hitting set for either family, so the implication remains valid. This finite branching proof never assumes $\mathcal{F}$ is finite.

Apply the kernel statement with $\mathcal{F}=\mathcal{A}$ and define $X={\bigcup }_{A\in {\mathcal{F}}_0}A$. For each $B\in \mathcal{B}$, the cross-intersecting family condition ensures that $B\cap X$ meets every member of ${\mathcal{F}}_0$, since these members lie inside $X$. As $|B\cap X|\le s$, it therefore meets every $A\in \mathcal{A}$. We obtainIn particular, a positive-integer-valued choice valid whether or not $0\in \mathbb{N}$ isHere the constant term of the sum is $1$, including when $r=0$. If either set family is empty, $X=\varnothing$ suffices. If both are nonempty, the cross-intersecting family condition rules out $r=0$ or $s=0$.

An equivalence of categories consists of functors $F:\mathcal{C}\to \mathcal{D}$ and $G:\mathcal{D}\to \mathcal{C}$ together with invertible natural transformations $GF\cong 1_{\mathcal{C}}$ and $FG\cong 1_{\mathcal{D}}$. A strict isomorphism of categories instead requires a functor with an inverse whose composites are literally identity functors.

First suppose $F$ belongs to an equivalence of categories. The isomorphisms $FGD\cong D$ give essential surjectivity. If $Ff=Fg$, apply $G$ and conjugate by $GF\cong 1_{\mathcal{C}}$ to obtain $f=g$, so $F$ is a faithful functor. Similarly $G$ is a faithful functor. Writing $\alpha :GF\stackrel{\sim }{\to }{1}_{\mathcal{C}}$, any $h:FA\to FB$ has a preimageIndeed naturality of $\alpha$ gives $GF(f)=G(h)$, and faithfulness of $G$ gives $F(f)=h$. Thus $F$ is a full and faithful functor.

Conversely, assume $F$ is a full and faithful functor and has essential surjectivity. Using the axiom of choice, for each $D$ choose an object $GD$ and an isomorphism ${\theta }_D:F(GD)\to D$. Define $G$ on a morphism $h:D\to E$ by the unique liftThe full and faithful functor property makes $G$ preserve identities and composition, and makes $\theta :FG\cong 1_{\mathcal{D}}$ a natural transformation. For $A\in \mathcal{C}$, lift ${\theta }_{FA}:FGFA\to FA$ uniquely to ${\alpha }_A:GFA\to A$. Lifting its inverse shows that ${\alpha }_A$ is invertible. The naturality of $\theta$ and faithfulness of $F$ imply the naturality of $\alpha$. This provesFor large categories, this choice argument is understood in a fixed universe, or with the corresponding class-choice convention; ordinary set-sized axiom of choice suffices for small categories.

For the category of partial functions, let $X_{+}=X⨿\{\ast \}$, with a tagged new element as basepoint. Send a partial function $f:X\rightharpoonup Y$ to the basepoint-preserving total functionUndefined composition is sent to the basepoint, so this is a functor $(-{)}_{+}:\mathbf{Part}\to {\mathbf{Set}}_{\ast }$. Restriction away from the basepoint recovers each partial function uniquely; hence it is a full and faithful functor. Every pointed set $(Y,y_0)$ is isomorphic to $(Y\setminus \{y_0\}{)}_{+}$, so there is an equivalence of categories. This particular equivalence can also be constructed explicitly, without choice, by deleting and adjoining the basepoint.

These actual categories are equivalent but not isomorphic. In $\mathbf{Part}$ the empty set is the only zero object: if $X$ is nonempty, its identity differs from its nowhere-defined endomorphism, so it cannot be initial or terminal. In ${\mathbf{Set}}_{\ast }$ every singleton pointed set is a zero object, and distinct singleton underlying sets give distinct objects. An isomorphism of categories is a bijection on objects preserving zero objects; it cannot take one such object onto several. This uses the categories of all actual sets, as in the paper, rather than chosen skeletal categories of representatives.

A skeletal category has no distinct isomorphic objects. If an equivalence $F:\mathcal{C}\to \mathcal{D}$ joins two skeletal categories, essential surjectivity becomes surjectivity on objects. If $FA=FB$, lift the identity of that object and its inverse using full and faithful to obtain $A\cong B$, so $A=B$. Thus $F$ is bijective on objects and on every hom-set. Its inverse on objects and morphisms is a strictly inverse functor, proving that it is an isomorphism of categories.

Under the axiom of choice, choose one object from each isomorphism class of a small category. The full subcategory on those objects is a skeleton of a category, and its inclusion is a full and faithful functor with essential surjectivity, hence an equivalence of categories.

For the converse, form the small category which is a groupoid with objects $(i,a)$ for $a\in A_i$, and exactly one morphism $(i,a)\to (j,b)$ when $i=j$, with no morphisms when $i\ne j$. Suppose it is equivalent to a skeletal category $\mathcal{S}$, with quasi-inverse functors $H:\mathcal{C}\to \mathcal{S}$ and $K:\mathcal{S}\to \mathcal{C}$. For each $i$, the objects $H(i,a)$ for $a\in A_i$ are isomorphic, hence all equal to a uniquely determined $s_i$. The isomorphism $KH(i,a)\cong (i,a)$ ensures that $K(s_i)=(i,a_i)$ for some $a_i\in A_i$. The rule $i\mapsto a_i$ is a choice function. In particular, no representative in $A_i$ had to be chosen to define $s_i$, since it is unique. Consequently