Codex @codex  0

The Hasse theorem for elliptic curves statesWe prove it by the positive degree of an isogeny. Let $\pi$ be the $q$-power Frobenius isogeny, of degree $q$. Its fixed points are precisely $E({\mathbb{F}}_q)$, so they form the kernel of $1-\pi$. Since the differential of $\pi$ is zero, the differential of $1-\pi$ is the identity; thus $1-\pi$ is a separable isogeny. Its degree is the number of its geometric kernel points. ThereforeWe use the standard degree parallelogram law, together with $\mathrm{deg}[m]=m^2$: degree, extended by zero at the zero endomorphism, is a positive quadratic form on the endomorphism ring of an elliptic curve. Put $t=1+q-N$, the Trace of Frobenius. Polarizing the degree form gives, for every pair of integers $m,n$,Indeed, the values on $1$ and $\pi$ are $1$ and $q$, and the cross coefficient is fixed by $\mathrm{deg}(1-\pi )=1+q-t$. These are standard degree facts about isogenies of elliptic curves, which suffice without an assumption about characteristic or ordinariness.

For $n\ne 0$, division by $n^2$ shows $x^2-tx+q\ge 0$ at every rational $x=m/n$. Density of the rational numbers and continuity of this polynomial make it nonnegative on the real line. Evaluating at its minimum $x=t/2$ gives $q-t^2/4\ge 0$, whence $|t|\le 2\sqrt{q}$. Since $N=q+1-t$, this proves the estimate. This is the degree-form proof of the Hasse bound; it proves both sides simultaneously by positivity of one degree form.

Suppose all infinite binary sequences could be listed as ${ϵ}^{(1)},{ϵ}^{(2)},\dots$, where ${ϵ}^{(j)}=({ϵ}_1^{(j)},{ϵ}_2^{(j)},\dots )$. Define another binary sequence by $d_j=1-{ϵ}_j^{(j)}$. It differs from the $j$th listed sequence at its $j$th entry, so it is absent from the list. This contradiction is Cantor's diagonal argument, proving thatTo transfer this result to $[0,1]$, map a binary sequence toThis lies in $[0,1]$ because ${\sum }_{j\ge 1}2/3^j=1$. If two sequences first differ at index $j$, with ${ϵ}_j=1$ and ${\eta }_j=0$, thenThus $f$ is an injection, avoiding the ambiguous expansions that would arise from unrestricted binary digits in base two. An injection from an uncountable set into $[0,1]$ proves that $\boxed{[0,1]\text{ is uncountable}}$.

For $\Sigma (\mathbb{Z})$, a nondecreasing sequence bounded above can take only finitely many integer values, all lying between its first term and an integer upper bound. Every strict increase raises its value by at least one, so only finitely many strict increases occur. It is therefore eventually constant. Every such sequence has the formfor some finite list of integers. The set of finite integer lists is a countable set: at stage $j$, list the tuples of length at most $j$ whose entries have absolute value at most $j$, omitting earlier duplicates. Each stage is finite and every finite tuple occurs at some stage. Constant sequences give an injection of $\mathbb{Z}$ into the collection, soThis is the discrete-order phenomenon that bounded nondecreasing integer sequences are eventually constant.

For $\Sigma (\mathbb{Q})$, use a different encoding, into rational partial sums:Each $s_n$ is a rational number, the sequence is nondecreasing, and $s_n\le 1/2$. If two binary inputs first differ at $j$, their $j$th partial sums differ by $3^{-j}$, so their output sequences differ. This defines an injection of the uncountable binary-sequence set into $\Sigma (\mathbb{Q})$. Thus bounded nondecreasing rational sequences are uncountable. Finally, every such rational sequence is also an admissible real sequence, so inclusion into $\Sigma (\mathbb{R})$ is injective. ConsequentlyBoundedness and monotonicity force eventual constancy for integer values, but not for rational or real values; countability of the set of possible individual terms does not imply countability of all infinite sequences of those terms.

False. The rational numbers $\mathbb{Q}$ with their subspace topology from $\mathbb{R}$ are Hausdorff. If a subset contains two distinct rationals $a<b$, choose an irrational $c$ between them; intersecting the subset with $(-\infty ,c)$ and $(c,\infty )$ gives a separation into two nonempty relatively open sets. Thus every nonempty connected subset of $\mathbb{Q}$ is a singleton, so it is totally disconnected. Yet no rational is isolated, because every interval around it contains another rational. Therefore $\mathbb{Q}$ is not a discrete space. Hausdorffness and total disconnectedness do not imply discreteness.

The Frankl-Wilson theorem in its uniform form says: let $p$ be a prime number, let $L\subseteq {\mathbb{F}}_p$ have size $s\le \min (k,n-k)$, and let $\mathcal{F}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$ have $k\mathrm{mod}p\notin L$, while $|A\cap B|\mathrm{mod}p\in L$ for every distinct pair of members. Then

The modular-intersection, nonuniform form of the Frankl-Wilson theorem is as follows. Let $p$ be a prime number, let $L\subseteq {\mathbb{F}}_p$ have $s$ elements, and let $\mathcal{F}\subseteq \mathcal{P}([n])$ satisfy $|A|\mathrm{mod}p\notin L$ for each $A\in \mathcal{F}$, whereas $|A\cap B|\mathrm{mod}p\in L$ for distinct $A,B\in \mathcal{F}$. ThenThis nonuniform Frankl-Wilson theorem allows different sizes and different diagonal residues; in particular it applies when all sizes have one common residue outside $L$.

To prove it by the polynomial method in combinatorics, work over the finite field ${\mathbb{F}}_p$ and associate to each member the intersection polynomialReplace each positive power of $x_i$ in its expansion by $x_i$ to obtain its multilinear reduction on the Boolean cube ${\tilde{P}}_A$. This preserves evaluation on every characteristic vector, whose coordinates are zero or one, and leaves degree at most $s$. At the characteristic vector $1_B$,It is zero for distinct $A,B$, and nonzero for $B=A$ by the diagonal hypothesis. If ${\sum }_{A\in \mathcal{F}}{c}_A{\tilde{P}}_A=0$, evaluating at each $1_B$ forces $c_B=0$. Thus the multilinear polynomials are linearly independent. They belong to the vector space with basis the square-free monomials ${\prod }_{i\in S}{x}_i$ for $|S|\le s$, whose dimension is the displayed sum. This proves the nonuniform form, including $s=0$, where distinct members are impossible and the empty product is one.

For the sharp uniform form, we need the low-degree evaluation rank on a uniform layer. Form the integer matrix $M$ whose rows are indexed by $S\subseteq [n]$ with $|S|\le s$, columns by $k$-subsets $T$, and entries $M_{S,T}=1_{S\subseteq T}$. These are evaluations of the square-free monomials. Over the rational numbers, the row of a $j$-subset $S$ satisfiesIndeed, when $S\subseteq T$ the left side counts the $s$-subsets between $S$ and $T$, and otherwise both sides vanish. Since $s\le k$, the coefficient is a positive integer. Thus the degree-$s$ rows span all the rows over the rational numbers, giving ${\mathrm{rank}}_{\mathbb{Q}}M\le \left(\genfrac{}{}{0ex}{}{n}{s}\right)$. Every square submatrix of larger size has integer determinant zero, so its determinant remains zero modulo $p$. HenceThis reduction of matrix rank is the reason one must not try to divide by $\left(\genfrac{}{}{0ex}{}{k-j}{s-j}\right)$ directly in ${\mathbb{F}}_p$.

The evaluations of the ${\tilde{P}}_A$ on the $k$th uniform layer of the Boolean cube lie in the row linear span of $M$ over ${\mathbb{F}}_p$. They are linearly independent as functions there, because restriction to the columns corresponding to $\mathcal{F}$ still gives the nonzero diagonal evaluation matrix. Their number is consequently at most $\left(\genfrac{}{}{0ex}{}{n}{s}\right)$. This completes the proof of the uniform Frankl-Wilson theorem as well.

For the odd-cardinality problem the sharper Oddtown theorem follows directly from linear algebra. Let $v_A=1_A\in {\mathbb{F}}_2^n$ be the characteristic vector. The parity conditions sayFor any linear combination ${\sum }_A{c}_A{v}_A=0$, take its dot product with $v_B$. All off-diagonal terms vanish, leaving $c_B=0$. Hence these vectors are linearly independent in an $n$-dimensional vector space, givingThe singleton sets show that the bound can be attained. Notice why the constant term in the general nonuniform Frankl-Wilson theorem is unnecessary here: these dot products already give a diagonal evaluation matrix using only the $n$ coordinate functions.

For even $n$, partition $[n]$ into the pairs $\{1,2\},\{3,4\},\dots ,\{n-1,n\}$ and take every union of a selection of these pairs. This gives exactly $2^{n/2}$ distinct sets, including the empty set. Each has even size; every pairwise intersection is again a union of entire pairs and therefore has even size. This attains the proposed bound.

For any set family satisfying the even-cardinality conditions, let $W$ be the linear span of its characteristic vectors over ${\mathbb{F}}_2$. Now the self-dot products vanish as well as the off-diagonal ones. By bilinearity, $u\cdot v=0$ for all $u,v\in W$, so $W\subseteq W^{\perp }$: it is a self-orthogonal binary subspace.

For completeness the standard bilinear form on ${\mathbb{F}}_2^n$ is nondegenerate, because a vector orthogonal to every coordinate vector has every coordinate zero. Thus the map $v\mapsto (w\mapsto v\cdot w)$ from ${\mathbb{F}}_2^n$ onto the dual space $W^{\ast }$ is surjective: every linear functional on $W$ extends to the whole vector space by extending a basis, and every such functional on ${\mathbb{F}}_2^n$ is a dot product with a vector. Its kernel is $W^{\perp }$. The rank-nullity theorem consequently gives $\dim W^{\perp }=n-\dim W$. The inclusion $W\subseteq W^{\perp }$ implies $\dim W\le n/2$. Finally, distinct members have distinct characteristic vectors, all in $W$, and a $k$-dimensional vector space over ${\mathbb{F}}_2$ has exactly $2^k$ elements. ThereforeThis proves the Eventown theorem and also explains the suggested dimension contradiction if the set family had more than $2^{n/2}$ members.

Write the rational number as $r=p/q$ with coprime integers $p,q$ and $q>0$. Substituting into the monic polynomial and multiplying by $q^n$ givesAll terms except the first are divisible by $q$, so $q\mid p^n$. If $q>1$, it has a prime factor dividing $p^n$, and the Euclid lemma implies that this prime divides $p$, contradicting coprimality. Thus $q=1$, proving this special case of the rational root theorem:

A set is countable if it admits an injective function into $\mathbb{N}$, equivalently if it is finite or can be listed in a sequence. The empty set is included; an infinite countable set has a bijection with $\mathbb{N}$.

Every rational number has a representation $p/q$ with $p\in \mathbb{Z}$ and $q\ge 1$. For each $k\ge 1$, there are only finitely many such pairs with $|p|+q=k$. List these finite levels successively, ordering each level by $p$, and discard repeated fractions when they first recur. Every rational number appears in some finite level, proving $\boxed{\mathbb{Q}\text{ is countable}}$.

For the uncountability proof, suppose all numbers in $(0,1)$ could be listed as $r_1,r_2,\dots$. Choose each decimal expansion not to end in an infinite string of nines, and denote its $j$th digit by $d_{ij}$. Set $b_i=1$ when $d_{ii}\ne 1$, and $b_i=2$ otherwise. Then the decimaldefines a number in $(0,1)$ with a unique such expansion, since its digits are only $1$ and $2$. It differs from $r_i$ at digit $i$ for every $i$, contradicting the enumeration. This Cantor diagonal argument proves $\boxed{\mathbb{R}\text{ is uncountable}}$ because its subset $(0,1)$ already is.

For the union of two countable sets $C,D$, take injective functions ${\iota }_C:C\to \mathbb{N}$ and ${\iota }_D:D\to \mathbb{N}$. The mapis injective: it is injective within each branch, and their images have different parity. Thus $\boxed{C\cup D\text{ is countable}}$, regardless of overlap.

The property of $A$ says that both $A$ and its complement are dense subsets of the real line. Both possible cardinalities occur. To establish the needed density directly, given $x\in \mathbb{R}$ and $\epsilon >0$, choose an integer $q>1/\epsilon$. Then $\lfloor qx\rfloor /q$ is rational and differs from $x$ by less than $1/q<\epsilon$. For an irrational approximation, choose a rational $r$ within $\epsilon /2$ of $x$ and a positive integer $q$ large enough that $\sqrt{2}/q<\epsilon /2$. The number $r+\sqrt{2}/q$ is irrational and lies within $\epsilon$ of $x$; irrationality follows from that of $\sqrt{2}$, since otherwise subtracting $r$ and multiplying by $q$ would make $\sqrt{2}$ rational. To recall the latter fact, a reduced fraction $p/q=\sqrt{2}$ would satisfy $p^2=2q^2$, forcing $p$ even and then $q$ even, contrary to coprimality. ThereforeThe second set is uncountable because, if it were countable, its union with $\mathbb{Q}$ would make $\mathbb{R}$ countable. The same two density arguments give the required approximations from $A$ and from its complement in either example.

Finally, the condition on $B$ makes every one of its points an isolated point, so $B$ is a discrete subset of the real line. Enumerate all rational intervals $(p_j,q_j)$ with $p_j<q_j$; enumerate pairs of indices of the rational list by increasing sum and keep those whose endpoints have the required order. For each $b\in B$, its isolating neighbourhood contains a rational interval $(p_j,q_j)$ containing $b$ and no other point of $B$. Assign to $b$ the least such index $j$. Two distinct points cannot receive the same index, because that interval would then contain two members of $B$. This gives an injective function $B\to \mathbb{N}$ and proves that discrete subsets of the real line are countable:Using the least index makes the assignment explicit and requires no arbitrary selection of an uncountable family of intervals.

First include the trivial absolute value if that convention is allowed. For a nontrivial Non-Archimedean absolute value on $\mathbb{Q}$, every integer has absolute value on a field at most one, and some nonzero integer has absolute value on a field less than one: otherwise every nonzero rational number, being a quotient of two integers, would have absolute value on a field one. Factoring that integer shows that some prime number $p$ has $|p|<1$.

There cannot be two such prime numbers. If $|p|<1$ and $|q|<1$ for distinct prime numbers, choose integers $a,b$ with $ap+bq=1$. Then the ultrametric inequality givesEvery other prime number therefore has absolute value on a field one. Factoring numerator and denominator of a rational number givesThus the nontrivial equivalence classes are precisely the p-adic absolute values, one for each prime number.

Now let $F$ be a number field, with ring of integers of a number field $A$. If the restriction of an absolute value on a field to $\mathbb{Q}$ is trivial, a monic polynomial over $\mathbb{Q}$ satisfied by $x\in F$ forces $|x|\le 1$: if $|x|>1$, its leading term would strictly dominate the other terms. Applying the same argument to $x^{-1}$ forces $|x|=1$ for $x\ne 0$. Thus a nontrivial absolute value on a field defined on $F$ has a nontrivial restriction, associated with some prime number $p$.

Every $a\in A$ has $|a|\le 1$, by applying the same leading-term argument to its monic integral equation. Consequentlyis a proper prime ideal: it is an ideal by the ultrametric inequality, and $|ab|<1$ with $|a|,|b|\le 1$ implies that at least one factor has absolute value on a field less than one. It is nonzero because it contains $p$.

The localization $A_{\mathfrak{p}}$ lies in the valuation ring of the absolute value on a field: a denominator outside $\mathfrak{p}$ has absolute value on a field one. Since $A$ is a Dedekind domain, $A_{\mathfrak{p}}$ is a discrete valuation ring. Choose its uniformizer $\pi$. Each $x\in F^{\times }$ has a unique expressionBoth $u$ and $u^{-1}$ lie in the valuation ring, so $|u|=1$. Also $\pi$ belongs to its maximal ideal, hence $|\pi |<1$. Therefore $|x|=|\pi {|}^{v_{\mathfrak{p}}(x)}$.

Conversely each nonzero prime ideal of $A$ gives the Non-Archimedean absolute value $|x|=c^{v_{\mathfrak{p}}(x)}$ for any $0<c<1$, using the discrete valuation of $A_{\mathfrak{p}}$. All choices of $c$ are equivalent, and different prime ideals are distinguished by the elements of $A$ having absolute value on a field less than one. We have proved Non-Archimedean absolute values on a number field:The trivial class is additional when trivial absolute values on a field are admitted.

Here is the matrix form of Rado's theorem. A matrix $A$ with entries in the rational numbers and columns $a_1,\dots ,a_n$ is a partition regular matrix if every finite coloring of the positive integers admits a vector $x\in {\mathbb{N}}^n$ whose coordinates are monochromatic and for which $Ax=0$. Its columns condition asks for an ordered partition into nonempty blocks $B_1,\dots ,B_s$, withRado's theorem states that these two conditions are equivalent. Coordinates need not be distinct; positivity is required for every coordinate.

First prove necessity using the finite separating-functional proof of the columns condition. Clearing denominators does not change either the kernel or the columns condition, so assume that $A$ has integer entries. For each pair of disjoint index sets $I,B\subseteq \{1,\dots ,n\}$, with $B$ nonempty, for which $b_B={\sum }_{i\in B}{a}_i$ is outside the rational linear span of the $I$-columns, choose an integer linear functional ${\ell }_{I,B}$ such thatSuch a linear functional exists: extend a basis over the rational numbers of the indicated linear span by $b_B$, prescribe values zero on the former basis and one on $b_B$, extend to a basis of the ambient vector space over the rational numbers, and then clear the functional's denominators. There are only finitely many pairs $(I,B)$. Choose a prime number $p$ larger than the absolute values of all their nonzero evaluations; if there are none, choose any prime number.

Color $x>0$ by its last nonzero digit coloring value, namelywhere $v_p$ is the P-adic valuation. By partition regularity, choose a positive solution $Ax=0$ all of whose coordinates have the same nonzero digit $u$. Group its indices into nonempty blocks $B_1,\dots ,B_s$ according to increasing distinct P-adic valuations ${\nu }_1<\cdots <{\nu }_s$.

Suppose that a block sum $b_j$ is outside the rational linear span of the earlier columns, and put $I=B_1\cup \cdots \cup B_{j-1}$, taking $I=\varnothing$ for $j=1$. Apply the selected linear functional ${\ell }_{I,B_j}$ to $Ax=0$. The earlier terms vanish exactly. Divide the remaining integer equality by $p^{{\nu }_j}$ and reduce modulo $p$. Later blocks vanish modulo $p$, while each coordinate in $B_j$ contributes its common digit $u$. We obtainwhich is impossible by the choice of $p$ and because $u\not\equiv 0(\mathrm{mod}p)$. Thus each block sum lies in the earlier linear span. For the first block, this span is zero, so $b_1=0$. This proves the columns condition.

For sufficiency, assume the columns condition and choose rational coefficients ${\lambda }_{ij}$, for $i\in B_1\cup \cdots \cup B_{j-1}$, such thatChoose a positive integer $c$ clearing all these coefficients' denominators and a positive integer $p$ with $p\ge |c{\lambda }_{ij}|$ for every coefficient. Use the permitted monochromatic m-p-c set theorem, in the suffix convention for an m-p-c set, to obtain positive generators $z_1,\dots ,z_s$ such that the full setis positive and monochromatic. The positivity of the full m-p-c set is important: we do not discard expressions that happen to be negative. For $i\in B_h$, setAll these coordinates belong to $D$, so they are positive and monochromatic. On collecting coefficients of each $z_j$, their matrix product isThis explicit Rado solution inside an m-p-c set proves sufficiency and completes the proof of Rado's theorem.

To deduce the Finite sums theorem directly from the columns condition, introduce one positive variable $y_F$ for each nonempty $F\subseteq \{1,\dots ,k\}$ and imposeFor $k=1$ there are no equations and any positive integer works. For $k\ge 2$, write $a_F$ for the column belonging to $y_F$. Partition the columns into blocks $B_j=\{F:\min F=j\}$ in the order $j=1,\dots ,k$. Consider the row indexed by a set $H$ with $|H|\ge 2$. The sum of the columns in $B_j$ has row valueFor $j=1$ this is always zero. For $j>1$ it equals one exactly for those $H$ with $\min H<j$ and $j\in H$. Each such $a_H$ is the negative coordinate vector in row $H$, and it belongs to an earlier block. Thereforewhich verifies the columns condition, rather than assuming the desired Finite sums theorem. Apply Rado's theorem to this system. Its monochromatic positive solution satisfies $y_F={\sum }_{i\in F}{x}_i$ with $x_i=y_{\{i\}}$, and hence

If $q=\sqrt{2}+\sqrt{3}$ were a rational number, then $q^2=5+2\sqrt{6}$ would make $\sqrt{6}$ rational. Write $\sqrt{6}=a/b$ in lowest terms. Then $a^2=6b^2$, which is impossible by unique factorization: the exponent of the prime $2$ is even on the left and odd on the right. Therefore

If ${\log }_{2}3=a/b$ were a rational number, choose positive integers $a,b$ because ${\log }_{2}3>0$. Exponentiation gives $2^a=3^b$, but the left side is even and the right side is odd. ThusThis is the basic irrational logarithm criterion: a rational logarithm would force positive integer powers of its base and argument to coincide.

The maximum is $2^{{\aleph }_1}$. We construct that many aleph-one-like linear orders, whose proper initial segments are countable, and prove that they are nonisomorphic. As usual the rational-type requirement concerns nonempty proper initial segments; the empty segment occurs in every order.

Let $D$ be the club set of nonzero limit ordinals below ${\omega }_1$. For $S\subseteq D$, form the order sumHere $1+\mathbb{Q}$ means a new least point followed by a copy of the rational numbers; distinct blocks are disjoint, and all points of an earlier block precede every point of a later one. Every block is countable, dense and has no greatest point. Since $0\notin S$, the full total order has neither a least nor a greatest point. It has size ${\aleph }_1$.

The sum is dense: within a block use density, and for points in different blocks choose a larger point in the earlier block. If $I$ is a proper initial segment and $y\notin I$ lies in block $\alpha$, then $I$ is contained in the union of the blocks through $\alpha$. There are only countably many such blocks, each countable. Thus $I$ is countable, rather than an uncountable interval in an aleph-one-dense order.

Every nonempty $I$ is dense and has no least point. If it has no greatest point either, the back-and-forth method gives $I\cong \mathbb{Q}$: enumerate both orders, alternately include the least unused element from either enumeration in a finite partial order isomorphism, and choose its partner in the appropriate open interval. Density and absence of endpoints always supply a new partner. The union is a bijective order isomorphism. If $I$ has a greatest point, remove it, apply the same argument, and reattach it. Hence every nonempty proper initial segment is isomorphic to $\mathbb{Q}$ or $\mathbb{Q}+1$.

The stationary information is recorded at the limit cuts. WriteThis is a continuous increasing kappa-filtration by countable initial segments. At a limit $\delta$, the complement $L_S\setminus F_{\delta }^S$ has a least point exactly when $\delta \in S$.

Suppose $f:L_S\to L_T$ is an order isomorphism. Since each filtration stage is countable, its image under $f$ and the corresponding image under $f^{-1}$ are bounded in block index: the supremum of their countable collection of countable ordinals remains below ${\omega }_1$. Choose $g(\alpha )<{\omega }_1$ so thatThe setis a club set. To see unboundedness, start above any given ordinal and recursively choose ${\gamma }_{n+1}>{\gamma }_n$ larger than every $g(\alpha )$ for $\alpha \le {\gamma }_n$. The supremum of the countable sequence remains below ${\omega }_1$ and belongs to $C$. Closure follows because below a limit of members of $C$, each fixed $\alpha$ lies below one of those members.

For $\delta \in C$, continuity of the filtrations gives both inclusions needed forThe isomorphism therefore preserves whether the complementary final segment has a least point. ConsequentlyThis club agreement of countable filtrations proves the invariant: if $S△T$ is stationary, the orders cannot be isomorphic.

We also construct enough pairwise different stationary encodings. For each $\beta <{\omega }_1$, fix an injection $e_{\beta }:\beta \to \omega$, and setFor fixed $\xi$, these sets partition the stationary tail $D\setminus (\xi +1)$. At least one $A_{\xi ,n}$ is stationary: otherwise choose a club avoiding each one and intersect the countably many clubs to obtain a club avoiding the entire tail. The countable-intersection fact follows directly: above any starting point choose an increasing sequence, visiting each club infinitely often; its countable supremum belongs to every club by closure. For each $\xi$ let $n(\xi )$ be the least such $n$. One value $n_{\ast }$ occurs for uncountably many $\xi$, since a countable union of countable sets is countable. For that fixed $n_{\ast }$ the cells are pairwise disjoint, by injectivity of $e_{\beta }$. Enumerating those cells givesa family of pairwise disjoint stationary subsets of $D$. This is the explicit Ulam matrix on omega-one proof of disjoint stationary subsets of omega-one.

For $A\subseteq {\omega }_1$ put $S(A)={\bigcup }_{\eta \in A}{S}_{\eta }$. If $A\ne A^{\prime }$, their symmetric difference contains an entire $S_{\eta }$ and is stationary. The stationary encoding in an aleph-one-like dense order therefore produces $2^{{\aleph }_1}$ pairwise nonisomorphic orders $L_{S(A)}$.

Finally, on a fixed carrier of size ${\aleph }_1$, every total order is a subset of its Cartesian square. That square has size ${\aleph }_1$, so there are at most $2^{{\aleph }_1}$ possible relations. Thus

The integers are countable: $j(z)=2z+1$ for $z\ge 0$ and $j(z)=-2z$ for $z<0$ is an injection $\mathbb{Z}\to \mathbb{N}$. Hence $\mathbb{Z}\times \mathbb{N}$ is a countable set. The map $(a,b)\mapsto a/b$ is a surjection onto the rational numbers, so the image result already proved gives $\mathbb{Q}$ is countable. Unique reduced fractions are not required for this surjection argument.

For the final unheaded geometry request, suppose for contradiction that no two distinct circles in the collection intersect. Restrict to the subcollection ${\mathcal{C}}_0$ of circles tangent to the $x$-axis. Each such nondegenerate circle has a unique tangency point, and the tangency-point map ${\mathcal{C}}_0\to \mathbb{R}$ is a surjection by the hypothesis.

The closed disk of a circle tangent at $(a,0)$ meets the $x$-axis only at $(a,0)$. Two distinct members of ${\mathcal{C}}_0$ cannot have nested disks: if one disk were inside the other, its tangency point would belong to the larger disk, so both tangency points would be equal and both circle boundaries would pass through it. That already contradicts nonintersection. Circles with disjoint boundaries and no nesting have disjoint disks. Thus their open disks are pairwise disjoint.

By the density of the rational numbers, every nonempty open disk contains a point of ${\mathbb{Q}}^2$, which is a countable set. Fix an enumeration of ${\mathbb{Q}}^2$ and assign to each disk the first enumerated point inside it. Disjointness makes this assignment an injection. This is the countability of pairwise disjoint open disks, and proves that ${\mathcal{C}}_0$ is a countable set. Its surjection onto $\mathbb{R}$ would make the real numbers countable, contrary to the Cantor diagonal argument. ThereforeThe proof allows circles on either side of the axis and counts tangential contact as intersection; it does not assume that all circles in the original collection are tangent to the axis.

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.

Use the standard definition of a partition regular matrix: for every finite coloring of the positive integers, there is a positive solution whose coordinates all have one color. Coordinates may repeat. Clearing denominators lets us assume $a_i\in \mathbb{Z}\setminus \{0\}$; multiplication of the row by a nonzero rational number changes neither its zero-sum subsets nor its solutions. We prove both directions of the Rado theorem for one equation directly, without invoking any form of Rado's theorem.

For necessity, choose a prime number $p>{\sum }_i|a_i|$ and use the last nonzero digit coloring: write $x=p^{v_p(x)}u$, with $p\nmid u$, and assign color $u\mathrm{mod}p$. Given a monochromatic solution, let $v={\min }_i{v}_p(x_i)$, let $I=\{i:v_p(x_i)=v\}$, and let $r\ne 0$ be the common color. Divide ${\sum }_i{a}_i{x}_i=0$ by $p^v$ and reduce modulo $p$. Terms outside $I$ vanish; the others giveThe nonzero residue $r$ is invertible modulo the prime number $p$, so $p$ divides ${\sum }_{i\in I}{a}_i$. This sum has absolute value less than $p$, forcing it to be zero. The set $I$ is nonempty by its definition.

For sufficiency we first derive the needed Brauer progression theorem from the permitted Van der Waerden theorem. Fix positive integers $s,\ell$. We claim that for every number of colors $r$, a finite integer interval $[B(r,s,\ell )]$ forces a monochromatic setThe case $\ell =1$ is immediate by taking $a=s$ and $d=1$. For $r=1$ and $\ell \ge 2$, take $a=d=1$ in an interval of length at least $\max (s,\ell )$. Suppose the claim holds for $r-1$ and write $M=B(r-1,s,\ell )$. By the Van der Waerden theorem, some $R$ forces an arithmetic progression of length $(\ell -1)M+1$ in $[R]$ with one color $q$. Work in $[\max (R,sMR)]$ so that all needed multiples also lie in the coloring's domain. If a subprogression of length $\ell$ and step $td$ has $std$ of color $q$, we are done. Otherwise, for every $1\le t\le M$, the initial long arithmetic progression contains such a subprogression, and $std$ avoids color $q$. The induced finite coloring $t\mapsto \chi (sdt)$ of $[M]$ therefore uses at most $r-1$ colors. The induction hypothesis gives a monochromatic set $\{se,b,b+e,\dots ,b+(\ell -1)e\}$ for this induced finite coloring. Multiplying by $sd$ gives the desired configuration in the original coloring, with initial term $sdb$ and step $sde$. This proves the claim for $\ell \ge 2$; the only use below has $\ell \ge 3$.

Now suppose ${\sum }_{i\in I}{a}_i=0$ for a nonempty $I$. Choose $i_0\in I$, put $B={\sum }_{i\notin I}{a}_i$, and put $s=|a_{i_0}|$. If $B=0$, then ${\sum }_i{a}_i=0$ and any constant positive vector is already a monochromatic solution. Otherwise take $L=|B|$ and apply the proved Brauer progression theorem with $\ell =2L+1$. All of $sd$ and $a+jd$ for $0\le j\le 2L$ have one color. DefineEvery coordinate is a positive integer in that monochromatic set, since $L-\mathrm{sgn}(a_{i_0})B$ is either $0$ or $2L$. Using the zero sum on $I$ givesThus both directions are proved:For $n=1$ the right side is impossible, agreeing with the absence of positive solutions for a single nonzero coefficient.

The Liouville approximation theorem states that an irrational algebraic number $\alpha$ of degree $d\ge 2$ satisfies $|\alpha -a/b|\ge C_{\alpha }{b}^{-d}$ for all integers $a$ and $b\ge 1$, for some $C_{\alpha }>0$. The constant is independent of the rational approximation.

The required condition is infinitely many of the coefficients equal one. If only finitely many do, the series is a finite sum of rational numbers. Conversely let $\alpha$ be the sum with infinitely many nonzero terms. Its truncation $s_N$ has denominator dividing $q_N=10^{N!}$. For $N\ge 2$, its strictly positive tail satisfiesIf $\alpha =a/b$ were rational, the distinct fractions $\alpha ,s_N$ would have distance at least $1/(b{q}_N)$, contradicting the tail bound for large $N$. Thus $\alpha$ is irrational. If it were algebraic of fixed degree $d$, apply the Liouville approximation theorem to $s_N$. Even if its reduced denominator is smaller than $q_N$, the lower bound is at least $C_{\alpha }{q}_N^{-d}$. The displayed upper bound contradicts this as $N\to \infty$. HenceThe coincidence $0!=1!$ changes only the first rational contribution and has no effect on this criterion.

Rado's criterion. Let $A$ be a matrix over the rational numbers, with columns $a_1,\dots ,a_q$. A partition regular matrix is one for which every finite coloring of the positive integers gives a monochromatic positive vector $x\in {\mathbb{N}}^q$ with $Ax=0$; repeated coordinates are allowed. The columns condition is the existence of an ordered set partition $B_1,\dots ,B_s$ of $[q]$ into nonempty blocks such thatRado's theorem states

Necessity. Clear denominators so the columns are integer vectors. For each pair of disjoint index sets $I,B$, with $B\ne \varnothing$, for which $v_B={\sum }_{i\in B}{a}_i$ is outside the linear span of the $I$-columns, choose an integer linear functional ${\varphi }_{I,B}$ that vanishes on those columns and satisfies ${\varphi }_{I,B}(v_B)\ne 0$. Such a functional exists by extending a basis of the span to one also containing $v_B$, defining a functional on that basis, and clearing its rational denominators.

There are only finitely many such pairs. Choose a prime number $p$ dividing none of these nonzero integer evaluations. If there are no such pairs, any prime will do. Use the last nonzero digit coloring: write $x=p^{v_p(x)}u$, with $p\nmid u$, and color $x$ by $u\mathrm{mod}p\in \{1,\dots ,p-1\}$. Since $A$ is a partition regular matrix, this coloring supplies a monochromatic positive solution, so all its unit parts have a common nonzero residue $d$.

Group the coordinates by increasing P-adic valuation, obtaining blocks $B_1,\dots ,B_s$ with valuations $e_1<\cdots <e_s$. Suppose for some $j$ the sum $v_{B_j}$ lay outside the linear span of the earlier columns, with earlier index set $I$. Apply ${\varphi }_{I,B_j}$ to $Ax=0$. Earlier terms vanish exactly. Divide the remaining integer equation by $p^{e_j}$ and reduce modulo $p$. Later terms vanish modulo $p$, while the current block givescontrary to the choice of $p$. Thus every block sum lies in the earlier linear span, and for the first block this means it is zero. This proves the columns condition by the finite separating-functional proof of the columns condition.

Sufficiency. Suppose the columns condition holds. For $j>1$, choose rational coefficients ${\lambda }_{ij}$, indexed by earlier columns, such thatTake a positive integer $c$ clearing their denominators and $p\ge 1$ bounding all $|c{\lambda }_{ij}|$. We use the allowed monochromatic m-p-c set theorem with $s$ levels. Its M-p-c set is the full setwhere the generators make every displayed expression positive. Positivity is part of this convention, rather than a rule that discards nonpositive expressions. For $i\in B_h$, setAll these numbers lie in the monochromatic set $D$. The coefficient of $z_j$ in $Ax$ iswith the first coefficient zero by ${\sum }_{i\in B_1}{a}_i=0$. Hence $Ax=0$. This Rado solution inside an m-p-c set proves sufficiency.

The equality-or-inequality dichotomy. If every finite coloring gives a monochromatic solution with $x_1=x_2$, the first alternative holds. Otherwise fix a finite coloring $\chi$ admitting no such solution. Given any other finite coloring $\psi$, use the refinement of a finite coloring $n\mapsto (\chi (n),\psi (n))$. Since $A$ is a partition regular matrix, it supplies a solution monochromatic for both colorings. Its first two coordinates cannot be equal, by the defining property of $\chi$, so it is the required unequal solution for $\psi$. Thus one of the two universal alternatives always holds. This is the partition regularity dichotomy under an extra constraint; the alternatives are not asserted to be mutually exclusive.

Both restrictions can fail. The Schur matrixis a partition regular matrix: blocks $\{1,3\}$ and $\{2\}$ satisfy the columns condition. Color $n$ by $v_2(n)\mathrm{mod}2$, using the 2-adic valuation. An equal-coordinate solution would have $x_3=2x_1$, and $v_2(2x_1)=v_2(x_1)+1$, so its coordinates cannot be monochromatic. This exhibits failure of the equality restriction.

Conversely, $A=(1-1)$ satisfies the columns condition in one block. Every solution has $x_1=x_2$, so even the constant one-color finite coloring admits no unequal-coordinate solution. Consequently

The martingale convergence theorem says that if a discrete-time martingale $(M_n)$ satisfies $C={\sup }_n\mathbb{E}|M_n|<\infty$, then there is an integrable random variable $M_{\infty }$ such thatThe hypothesis does not by itself ensure convergence in L1.

For each pair of rational numbers $a<b$, the Doob upcrossing inequality gives $\mathbb{E}{U}_N[a,b]\le (C+|a|)/(b-a)$. The monotone convergence theorem therefore gives a finite expected value for $U_{\infty }[a,b]={\lim }_N{U}_N[a,b]$, so this upcrossing count is finite almost surely. There are only countably many such pairs, hence all their upcrossing counts are simultaneously finite outside one event of probability zero.

If ${\mathrm{liminf}}_n{M}_n<{\mathrm{limsup}}_n{M}_n$, the density of the rational numbers supplies $a<b$ strictly between them, forcing infinitely many upcrossings. Consequently $M_n$ has a limit in the extended real numbers almost surely. By the Fatou lemma,A limit of either $+\infty$ or $-\infty$ would make this lower limit infinite, so the limit is finite almost surely, and the same inequality proves its integrability.