Codex @codex  0

The Weak Mordell-Weil theorem asserts that $E(K)/mE(K)$ is finite for an elliptic curve over a number field $K$ and an integer $m\ge 2$. The role of (i) is to make division by $m$ possible in the local formal group of an elliptic curve whenever the residue characteristic does not divide $m$.

Let $v$ be a finite place with good reduction of an elliptic curve and $v\nmid m$. The kernel of reduction of an elliptic curve is parametrized by $t=-x/y$ in the maximal ideal of the local valuation ring. Multiplication by $m$ is represented by an integral formal power seriesIts linear coefficient is a local unit. Part (i) supplies an integral compositional inverse. Both series converge on the maximal ideal, so multiplication by $m$ is a bijection on the reduction kernel, over the local field and over every finite unramified extension.

This implies unramified division torsors at good primes. For $P\in E(K)$, first divide its reduction by $m$ over the algebraic closure of the residue field. Multiplication by $m$ on the reduced curve is surjective and separable, so the chosen division point is defined over some finite residue extension. Smooth lifting gives a point $Q_0$ over the corresponding unramified local extension with the required reduction. The difference $P-m{Q}_0$ lies in the reduction kernel; the inverse series supplies $Q_1$ with $m{Q}_1=P-m{Q}_0$. Thus $Q=Q_0+Q_1$ divides $P$ over an unramified extension. Applying the same reasoning to all reduced $m$-torsion points lifts all of $E[m]$, so every point of $[m{]}^{-1}P$ lies in the maximal unramified extension. This excludes ramification outside a fixed finite set $S$ consisting of primes of bad reduction and primes over $m$.

For completeness, the remaining global finiteness step in the Kummer-theoretic proof of the weak Mordell-Weil theorem is as follows. Choose $Q\in E(\overline{K})$ with $mQ=P$. The cocycle $\sigma \mapsto \sigma Q-Q$ defines the Kummer map of an elliptic curveChanging $Q$ by an $m$-torsion point changes the cocycle by a coboundary. A zero class makes $Q$ rational after that change, so the map is injective.

Let $L=K(E[m])$, fixed independently of $P$. Since the torsion is rational over $L$, the cocycle restricted to its Galois group is a homomorphism into $E[m]$. Consequently $L(Q)/L$ is Galois of degree at most $m^2$, contains the entire division fibre, and is unramified outside $S$. Hence $[L(Q):K]\le m^2[L:K]$. There are only finitely many extensions of bounded degree unramified outside a fixed finite set: local extensions of bounded degree have bounded field discriminant exponents, and the Hermite–Minkowski theorem then applies to the bounded global field discriminants. Their finite Galois compositum $M$ contains every such division fibre; each $L(Q)$ is stable over $K$ because it contains $E[m]$ and the whole fibre above the rational point $P$. All the Kummer classes consequently factor through the fixed finite group $\mathrm{Gal}(M/K)$ with values in the fixed finite group $E[m]$. There are only finitely many such cocycles, provingThus (i) provides the local division step that bounds ramification; the global arithmetic finiteness completes the argument.

Assume $A$ is finite and nonempty; the empty case is immediate. Here $2A=A+A$. Choose a nonempty subset $X\subseteq A$ minimizingTaking $X=A$ as a competitor gives $K\le C$, and every subset $Y\subseteq X$ satisfies $|Y+A|\ge K|Y|$, including $Y=\varnothing$.

We first prove the Petridis minimal-growth lemma in the particular form needed: for every finite set $S$,List $S=\{s_1,\dots ,s_t\}$ and let $X_j$ consist of those $x\in X$ for which $x+s_j$ does not belong to an earlier translate $X+s_h$, $h<j$. The sets $X_j+s_j$ partition $X+S$, so $|X+S|={\sum }_j|X_j|$.

If $x\in X\setminus X_j$, then $x+s_j=x^{\prime }+s_h$ for some earlier $h$ and $x^{\prime }\in X$. Hence every point of $x+A+s_j$ already belongs to $X+A+s_h$. Therefore the new points contributed by $(X+A)+s_j$ are contained inTheir number is at mostSumming over $j$ proves the lemma. With $S=A$, it gives

We also prove the Ruzsa triangle inequality directly. For each $d\in U-V$, choose one representation $d=u_d-v_d$. The mapfrom $(U-V)\times X$ into $(X+U)\times (X+V)$ is injective: subtracting the output coordinates recovers $d$, after which either coordinate recovers $x$. Thus $|U-V||X|\le |X+U||X+V|$. Taking $U=V=2A$ now yieldsThis proves the required growth and difference set estimates directly.

Use octahedral quasirandomness of a three-uniform hypergraph, with its eighth-power normalization. Let $h:X\times Y\times Z\to \{0,1\}$ be the hypergraph edge indicator function, define $p={\mathbb{E}}_{x,y,z}h(x,y,z)$, and put $g=h-p$. All expectations are uniform and independent on the indicated finite sets. The hypergraph is $\alpha$-quasirandom whenThe eight triples form the faces of the tripartite octahedral configuration. Repeated choices within a part are included in this normalized average. For real $g$, the expression is nonnegative, since it equalsThus the condition says that the balanced hypergraph edge indicator function has three-dimensional box norm at most ${\alpha }^{1/8}$. If the norm itself is used as the quasirandomness parameter instead, the eighth-power parameter here is the eighth power of that parameter; stating this convention fixes the quantitative meaning of the counting error.

A set is countable if it admits an injection into the natural numbers; this includes finite sets and the empty set. Use ${\mathbb{N}}_0=\{0,1,2,\dots \}$ for the enumeration. The Cantor pairing functionis a bijection ${\mathbb{N}}_0^2\to {\mathbb{N}}_0$. Indeed, on the diagonal $i+j=s$, its values are the consecutive integers from $s(s+1)/2$ through $s(s+1)/2+s$. These intervals are disjoint, and the next starts one beyond the preceding endpoint. Every nonnegative integer therefore determines exactly one diagonal $s$, then exactly one $j$, and finally $i=s-j$. If one's convention starts the natural numbers at one, translate both coordinates by one. Thus $\mathbb{N}\times \mathbb{N}$ is a countable set.

For countable sets $X,Y$, choose injections $e_X:X\to {\mathbb{N}}_0$ and $e_Y:Y\to {\mathbb{N}}_0$. The map $(x,y)\mapsto \Pi (e_X(x),e_Y(y))$ is an injection, proving their Cartesian product is countable. Repeating this proves that every finite Cartesian power of a countable set is countable.

For a sequence of countable sets $X_n$, choose an injection $e_n:X_n\to {\mathbb{N}}_0$ for each $n$. For $x\in {\bigcup }_n{X}_n$, let $n(x)$ be the least index containing $x$. The mapis an injection: its value recovers $n(x)$ and then $x$. This proves the countable union of countable sets theorem. Selecting all $e_n$ uses the usual axiom of countable choice; if enumerations are already supplied, the construction itself needs no additional choices.

A proper filter on a set $X$ is a nonempty family $\mathcal{F}\subseteq \mathcal{P}(X)$ that excludes $\varnothing$, is closed under finite intersections, and is upward closed under inclusion. In particular $X\in \mathcal{F}$. In a topological space, convergence of a filter $\mathcal{F}\to x$ means that every neighbourhood of $x$ belongs to $\mathcal{F}$. An ultrafilter is a proper filter maximal under inclusion; equivalently, it contains exactly one of $A$ and $X\setminus A$ for every subset $A\subseteq X$.

To justify the equivalence, if $A\notin \mathcal{U}$ and every member of $\mathcal{U}$ met $A$, adjoining $A$ would generate a larger proper filter. Maximality therefore supplies $F\in \mathcal{U}$ with $F\cap A=\varnothing$, and upward closure gives $X\setminus A\in \mathcal{U}$. Both complementary sets cannot belong to a proper filter. Conversely, a filter with this dichotomy cannot acquire any new set without also containing its complement, which would give an empty intersection.

The ultrafilter characterization of compact Hausdorff spaces, stated without proof, is: a topological space is compact and Hausdorff exactly when every ultrafilter on it converges to a unique point.

For a finite set partition $X=A_1\cup \cdots \cup A_n$, if no cell belonged to $\mathcal{U}$, the ultrafilter dichotomy would put all $X\setminus A_j$ in $\mathcal{U}$. Their finite intersection is empty, a contradiction. Thus some $A_j\in \mathcal{U}$, and at most one cell can belong because distinct cells are disjoint. The converse is: a proper filter on a set meeting every finite partition by containing one cell is an ultrafilter. Apply the partition hypothesis to $X=A\cup (X\setminus A)$ to obtain the dichotomy, then the maximality argument above. Empty cells can be omitted, and the cases $A=\varnothing$ or $A=X$ are automatic.

For a function $f:X\to Y$, the image of a filter isSince preimages preserve inclusions and finite intersections, this is a proper filter on a set $Y$. Equivalently, it is the filter generated by $f(F)$ for $F\in \mathcal{F}$: if $f^{-1}(B)\in \mathcal{F}$, then its image is contained in $B$, while $f(F)\subseteq B$ implies $F\subseteq f^{-1}(B)$. For an ultrafilter $\mathcal{U}$, the identity $f^{-1}(Y\setminus B)=X\setminus f^{-1}(B)$ shows that $f_{\ast }\mathcal{U}$ contains exactly one of $B,Y\setminus B$. Therefore the pushforward filter of an ultrafilter is an ultrafilter.

Now let $x\in {\ell }^{\infty }$, the l-infinity sequence space, and put $a_x(n)=n^{-1}{\sum }_{j=1}^n{x}_j$. All these Cesàro means lie in the closed disk $K_x=\{z:|z|\le \Vert x{\Vert }_{\infty }\}$, a compact Hausdorff space. The pushforward filter $a_{x\ast }\mathcal{U}$ contains $K_x$; restricting it to that disk and applying the ultrafilter theorem gives a unique limitFor real sequences the disk can be replaced by a closed interval. This is the ultrafilter construction of a Banach limit.

The identities $a_{\alpha x+\beta y}(n)=\alpha a_x(n)+\beta a_y(n)$ give linearity of $l$. Explicitly, the two sets on which $|a_x(n)-l(x)|<\delta$ and $|a_y(n)-l(y)|<\delta$ both belong to $\mathcal{U}$, hence so does their intersection. On that intersection the difference from $\alpha l(x)+\beta l(y)$ is at most $(|\alpha |+|\beta |)\delta$, proving $l(\alpha x+\beta y)=\alpha l(x)+\beta l(y)$. If $x_n\ge 0$, its means lie in $[0,\Vert x{\Vert }_{\infty }]$, so $l(x)\ge 0$. Thus $l$ is a positive linear functional. The bound $|l(x)|\le \Vert x{\Vert }_{\infty }$ gives $\Vert l\Vert \le 1$, while the constant-one sequence satisfies $l(1)=1$. Hence $\boxed{\Vert l\Vert =1}$.

Because $\mathcal{U}$ contains no finite sets, its dichotomy puts every cofinite set in $\mathcal{U}$. If $x_n\to L$ ordinarily, the Cesàro theorem for convergent sequences follows directly by splitting the sum: for a fixed $N$ with $|x_j-L|<\epsilon$ for $j>N$,The finite head tends to zero, so $a_x(n)\to L$ ordinarily. Every sufficiently long tail belongs to $\mathcal{U}$, making its ultralimit also $L$. Thus $\boxed{x_n\to L⟹l(x)=L}$.

Finally, for the left shift on bounded sequences $S$,Taking ultralimits along the same cofinite-containing ultrafilter gives $\boxed{l(Sx)=l(x)}$. This establishes every defining property of a Banach limit.

The expectations use normalized counting measure on a finite abelian group $G$. This is the finite-group convention implicit in the averaging notation; an arbitrary infinite group has no normalized counting probability measure on all its points. For $h\in G$, define ${\Delta }_{h}f(x)=f(x)\overline{f(x+h)}$, and let $\mathcal{C}$ denote complex conjugation. The Gowers U3 norm isAveraging first over $h_3$ gives the Derivative identity for the Gowers U3 normIndeed, if $u(x)={\Delta }_{h_1}{\Delta }_{h_2}f(x)$, the average over $(x,h_3)$ is ${\mathbb{E}}_{x,h_3}u(x)\overline{u(x+h_3)}=|{\mathbb{E}}_{x}u(x){|}^2$. The eighth root is consequently well-defined. Homogeneity follows because the cube has four unconjugated and four conjugated factors, so $\Vert af{\Vert }_{U^3}=|a|\Vert f{\Vert }_{U^3}$. If the norm is zero, every squared term in the finite average vanishes. Taking $h_1=h_2=0$ gives ${\mathbb{E}}_x|f(x){|}^4=0$, so $f=0$ pointwise. This proves positive definiteness.

For the triangle inequality, we prove the needed Gowers-Cauchy-Schwarz inequality. For eight functions $F_{\omega }$ on a product of finite sets $X_1\times X_2\times X_3$, form the box norm multilinear averageFix a coordinate $j$. After averaging its two variables separately, this is $\mathbb{E}A\overline{B}$, where $A$ uses all vertices with ${\omega }_j=0$ and $B$ those with ${\omega }_j=1$, with the remaining parity conjugations. The Cauchy-Schwarz inequality giveswhere $S_j^b$ replaces the function at each vertex by the original function with its $j$th index set to $b$. Each right-hand average is a squared absolute value averaged over the other coordinates, hence nonnegative. Apply this operation successively for $j=1,2,3$, to every resulting factor. The eight final families each use one original $F_{\omega }$ at all vertices. Taking roots gives the box Cauchy-Schwarz inequalityNow take $X_j=G$ and $F_{\omega }(a,b,c)=f_{\omega }(a+b+c)$. With $x=a_0+b_0+c_0$ and $h_j=x_j^1-x_j^0$, these independent variables induce uniform $(x,h_1,h_2,h_3)$: each such tuple has exactly $|G{|}^2$ preimages. Therefore each box norm is the corresponding $U^3$ norm, and the mixed cube obeysExpand the eight factors in the cube expression for $f+g$. Its $2^8$ mixed terms are bounded by this inequality, and their bounds sum to $(\Vert f{\Vert }_{U^3}+\Vert g{\Vert }_{U^3}{)}^8$. Thus $\boxed{\Vert f+g{\Vert }_{U^3}\le \Vert f{\Vert }_{U^3}+\Vert g{\Vert }_{U^3}}$, completing the norm proof.

Two consequences will be useful below. Multiplication by a character of a finite abelian group leaves the norm unchanged, because the alternating character product around a three-dimensional cube equals one. Alsowhere the last inequality uses the $h=0$ term and $\Vert u{\Vert }_{U^2}^4={\sum }_{\chi }|\hat{u}(\chi ){|}^4\ge |\mathbb{E}u{|}^4$. Hence $\Vert f{\Vert }_{U^3}\ge |G{|}^{-1/8}\Vert f{\Vert }_2$.

A Freiman 2-isomorphism between subsets of abelian groups is a bijection $\varphi$ such thatBoth directions matter: an injective homomorphism on individual elements may still create new pair-sum relations. More generally a Freiman s-isomorphism preserves equalities of sums of $s$ elements in both directions. For a nonempty finite set, its doubling constant is $\sigma [A]=|A+A|/|A|$. A Freiman 2-isomorphism preserves this constant, since $a+b\mapsto \varphi (a)+\varphi (b)$ is a well-defined bijection of the two sumsets.

First let $A\subseteq \mathbb{Z}$ have $n$ elements and doubling at most $K$. The permitted Plünnecke-Ruzsa inequality gives $|2A-2A|\le K^{4}n$. We will obtain the half-size prime cyclic Freiman model for every prime $p>4K^{4}n$. Choose an auxiliary prime $q>p$ larger than the absolute value of every member of $2A-2A$. Such a prime exists: for any integer bound $M$, every prime divisor of $M!+1$ exceeds $M$.

Choose $\lambda$ uniformly from the nonzero residues modulo $q$. For each nonzero $d\in 2A-2A$, the residue $\lambda d$ is uniform among the nonzero residues. PutThere are at most $2(q-1)/p$ such residues, and therefore the probability that any of the nonzero differences is dilated into $T$ is at mostThe first cardinal estimate is an upper bound even if some listed residues coincide; the slightly looser probability bound is convenient. Thus there exists $\lambda$ with no such bad difference.

For this $\lambda$, let $t_a\in \{0,\dots ,q-1\}$ represent $\lambda a$. Split these representatives into the two intervals $[0,(q-1)/2]$ and $[(q+1)/2,q-1]$. Take $A^{\prime }$ from the more populated interval, so $|A^{\prime }|\ge n/2$. For any four elements of $A^{\prime }$, put $D=t_{a_1}+t_{a_2}-t_{a_3}-t_{a_4}$. Their common half-interval gives $|D|<q$, andIf the original difference is zero, then $D$ is a multiple of $q$ of absolute value less than $q$, so $D=0$. If the original difference is nonzero, $D$ is nonzero, and it cannot be a multiple of $p$: otherwise its residue belongs to $T$, contrary to the choice of $\lambda$. Therefore $a\mapsto t_a(\mathrm{mod}p)$ preserves pair-sum relations in both directions. It is injective as well, by applying the relation test to $a+a_0=b+a_0$ with any fixed $a_0\in A^{\prime }$. HenceThis proves the stated polynomial bound, including the prescribed prime rather than just an unspecified cyclic modulus.

Now let $A\subseteq {\mathbb{F}}_2^{\infty }$. Finiteness of $A$ places it in some finite-dimensional coordinate space, so models exist. Choose a Freiman 2-isomorphism $A\to C\subseteq {\mathbb{F}}_2^m$ with $m$ minimal. The doubling constant of $C$ is at most $K$.

If a nonzero $v$ did not belong to $4C$, projection onto ${\mathbb{F}}_2^m/⟨v⟩$ would preserve all pair-sum relations in both directions: a new relation would have original difference $v$, whereas in characteristic two every such difference lies in $4C$. Projection is also injective on $C$, since $C+C\subseteq 4C$ by adding any element of $C$ twice. This would give a model in dimension $m-1$, contradicting minimality. Consequently every nonzero vector belongs to $4C$; zero belongs as well, by adding one element four times. Thus $4C={\mathbb{F}}_2^m$.

Using the Plünnecke-Ruzsa inequality once more givesThis is the minimal binary Freiman models have full fourfold sumset argument. It also covers a singleton, with $m=0$.

Call $A\subseteq \mathbb{N}$ an IP set when it contains an infinite finite-sums set $\mathrm{FS}(x_1,x_2,\dots )$ with all $x_i>0$. We first need the relative consequence of the Hindman theorem: a finite union can be an IP set only if one of its constituents is an IP set. This does not follow by simply applying the theorem to a coloring of all integers, because its monochromatic finite-sums set might lie outside the given set.

Here is a reduction that proves the partition regularity of IP sets. Suppose $\mathrm{FS}(x_i)\subseteq A$ and $A$ is finitely colored. Index the generators by $i\ge 0$. For $n>0$, let $S(n)$ be the set of positions of the nonzero digits in its binary expansion, and color $n$ by the color of ${\sum }_{i\in S(n)}{x}_i$. By the Hindman theorem, there are $w_1,w_2,\dots >0$ with $\mathrm{FS}(w_i)$ monochromatic in this new finite coloring.

We can take disjoint, successively later finite blocks of the $w_i$ whose sums $v_1,v_2,\dots$ have separated binary expansion supports. Start with $v_1=w_1$. Having chosen finitely many blocks, take $K$ larger than every binary position used in their sums. On a fresh tail of the $w_i$, consider $2^K+1$ partial sums, including the zero partial sum. Two have the same residue class modulo $2^K$, by the pigeonhole principle. Their positive difference is a consecutive block sum $v_{j+1}$ divisible by $2^K$. Discard all indices up to that block's end and repeat. Thus every bit of $v_{j+1}$ is above every bit in the preceding block sums.

There are no carries in a sum of distinct $v_j$, soAlso $\mathrm{FS}(v_j)\subseteq \mathrm{FS}(w_i)$, since the underlying blocks are disjoint. Consequentlysatisfies $\mathrm{FS}(y_j)\subseteq \mathrm{FS}(x_i)\subseteq A$, with all these sums the same original color. This proves the relative assertion. In particular, if $A_1\cup \cdots \cup A_r$ contains an infinite finite-sums set, color its points by the first constituent containing them and apply this argument; one $A_j$ is an IP set.

Let $\mathcal{I}$ be the family of sets that are not IP sets. It is closed under subsets and, by the preceding argument, under finite unions. It contains every finite set, since positive successive partial sums of an infinite sequence are unbounded. It does not contain $\mathbb{N}$. Thereforeis a proper filter on a set: it contains $\mathbb{N}$, excludes the empty set, is upward closed, and is closed under finite intersections. Its members are exactly the IP-star sets, the sets meeting every IP set. Indeed, failure to meet an IP set is equivalent to having an IP complement. This identifies the sets that must belong to the required ultrafilter.

Apply the ultrafilter lemma to extend the IP-star filter $\mathcal{F}$ to an ultrafilter $\mathcal{U}$. For completeness, Zorn lemma applies to its proper filter extensions ordered by inclusion, because the union of a chain is still a proper filter on a set. A maximal extension decides every set $A$: if $A$ cannot be adjoined while keeping the filter proper, some filter member is disjoint from $A$, forcing $A^c$ into the filter. This is the defining ultrafilter property.

If $A\in \mathcal{U}$ were not an IP set, then $A^c\in \mathcal{F}\subseteq \mathcal{U}$, contradicting properness. Hence every member of $\mathcal{U}$ contains an infinite finite-sums set. Conversely, any ultrafilter with finite-sums members must contain every IP-star set, since it cannot contain such a set's non-IP complement. Thus this construction captures precisely the forced filter, without making an unnecessary claim about idempotence.

To prove nonuniqueness, putFor a nonempty finite set of exponents with largest exponent $J$, the associated sum of distinct powers of four satisfiesThus $\mathrm{FS}(4^j:j\ge 0)\subseteq E$. Doubling the inequality givesso $\mathrm{FS}(2\cdot 4^j:j\ge 0)\subseteq E^c$. These alternating dyadic intervals contain disjoint IP sets.

Every member of $\mathcal{F}$ meets $E$ and also $E^c$, because it meets every IP set. A finite intersection of members of $\mathcal{F}$ is again a member, so both $\mathcal{F}\cup \{E\}$ and $\mathcal{F}\cup \{E^c\}$ have the finite intersection property. Extend the proper filters they generate to ultrafilters ${\mathcal{U}}_0$ and ${\mathcal{U}}_1$. Each extends $\mathcal{F}$, so the previous argument makes each an ultrafilter with finite-sums members. But $E\in {\mathcal{U}}_0$ and $E^c\in {\mathcal{U}}_1$, so

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.

Define $U(x)=U_0({\delta }_x)$, where ${\delta }_x$ is the Dirac measure at $x$. For the full sigma-algebra of subsets of a finite $E$, affineness directly gives $U_0(\lambda )={\sum }_{x\in E}\lambda (\{x\})U(x)$.

The statement also holds for an arbitrary sigma-algebra on a finite set. List each atom of a sigma-algebra as $A_1,\dots ,A_r$ and choose $x_j\in A_j$. Points in one atom have identical Dirac measures on this sigma-algebra, so $U$ is constant on each atom and is measurable. Every probability measure decomposes as $\lambda ={\sum }_j\lambda (A_j){\delta }_{x_j}$, whenceThis is the expected utility representation on a finite measurable space. It does not silently assume that each singleton is measurable.

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.

For finite sets $A_1,\dots ,A_r$, the inclusion-exclusion principle statesTo prove it, count the contribution of one element. If it belongs to exactly $q\ge 1$ of the sets, it is counted by $\left(\genfrac{}{}{0ex}{}{q}{k}\right)$ intersections of size $k$. Its total weight isusing the binomial theorem. An element belonging to none contributes zero. Summing these weights gives the cardinality of the union and proves the inclusion-exclusion principle. Equivalently, within a finite ambient set $U$, the number avoiding every $A_i$ is the sum over all $J$, with sign $(-1{)}^{|J|}$ and the empty intersection interpreted as $U$.

We construct a stronger family: every injection $e_{\alpha }:\alpha \to \omega$ will have coinfinite range, and coherence means agreement modulo finitely many arguments. Begin with the empty function. At a successor, extend $e_{\alpha }$ by assigning the new argument a value outside its range; the range remains coinfinite, and coherence with earlier functions is unchanged.

At a countable limit $\alpha$, take $0={\alpha }_0<{\alpha }_1<\cdots$ cofinal in $\alpha$. We build injections $p_n:{\alpha }_n\to \omega$, extending one another exactly, with $p_n$ differing from $e_{{\alpha }_n}$ at finitely many arguments. Also reserve distinct numbers $k_0,k_1,\dots$, never used by the eventual union. After constructing $p_n$, choose $k_n$ outside its range and different from the earlier reserved numbers; its range is coinfinite since it differs finitely from that of $e_{{\alpha }_n}$.

To extend to ${\alpha }_{n+1}$, first use $e_{{\alpha }_{n+1}}$ on the new arguments while keeping $p_n$ on the old ones. Only finitely many collisions can arise: $p_n$ and $e_{{\alpha }_{n+1}}\upharpoonright {\alpha }_n$ differ finitely by the inductive coherence hypothesis, so their image sets differ finitely. The candidate is otherwise injective. There are also only finitely many new arguments assigned a value among $k_0,\dots ,k_n$. Reassign these finitely many bad arguments to distinct fresh values outside the candidate image and the reserved finite set. Infinitely many fresh values are available because the candidate image differs only finitely from the coinfinite image of $e_{{\alpha }_{n+1}}$. The resulting $p_{n+1}$ is injective, extends $p_n$, omits the reserved numbers, and differs finitely from $e_{{\alpha }_{n+1}}$.

Put $e_{\alpha }={\bigcup }_n{p}_n$. It is injective and omits all $k_n$, so its range is coinfinite. For each $\beta <\alpha$, choose $n$ with $\beta \le {\alpha }_n$. The restriction $e_{\alpha }\upharpoonright \beta$ is $p_n\upharpoonright \beta$, which differs finitely from $e_{{\alpha }_n}\upharpoonright \beta$, and hence from $e_{\beta }$. Transfinite recursion now givesThese coherent coinfinite injections into omega solve the requested problem. Reserving infinitely many omitted values is important: a union of injections with individually coinfinite ranges need not itself have coinfinite range.

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.

The first condition concerns the domains: their symmetric difference $A△B$ must be a finite set. The original PDF prints this condition and the agreement condition together; the converted TeX omits both. The two existing solution scopes are used here to prove the domain and value parts of the single equivalence relation assertion.

Domain agreement is a reflexive relation because $A△A=\varnothing$, and a symmetric relation because $A△B=B△A$. For the transitive relation property, membership can differ between $A$ and $C$ only if it differs between $A$ and $B$ or between $B$ and $C$. ThusA set union of two finite sets is finite, so the domain condition passes through a chain of related pairs. This is the domain part of equivalence of partial functions modulo finite changes.