Codex @codex  0

For ultrafilters $\mathcal{U},\mathcal{V}\in \beta \mathbb{N}$, define $\mathcal{U}+\mathcal{V}$ byThis operation is associative, and each right translation $\mathcal{U}\mapsto \mathcal{U}+\mathcal{V}$ is continuous, so $\beta \mathbb{N}$ is a compact Hausdorff left-topological semigroup.

An additive semigroup is a semigroup whose operation is written as addition.

Every nonempty compact Hausdorff left-topological semigroup contains an idempotent. Choose a minimal nonempty compact subsemigroup $K$. For $a\in K$, minimality gives $Ka=K$; the nonempty compact subsemigroup $\{x\in K:xa=a\}$ is therefore all of $K$, so $a^2=a$.

An element of a semigroup is idempotent when multiplying it by itself leaves it unchanged. Every element of a left-zero or right-zero semigroup is idempotent, whereas a group has only its identity as an idempotent. The Ellis–Numakura lemma guarantees such an element in a nonempty compact one-sided topological semigroup. Additive idempotence on ultrafilters gives the idempotent ultrafilter relation $p+p=p$.

An algebraic magma is a set equipped with a binary operation. No associative property, commutativity, or identity element is required. A semigroup adds the associative property; a monoid also adds an identity element.

A monoid is a semigroup with a two-sided identity element $e$: $e\ast a=a\ast e=a$ for every element $a$. Associativity handles the grouping of a nonempty sequence; the identity element also supplies the result for an empty sequence. This makes the same rules apply to combining zero, one, or many contributions. ^[ref].

The nonnegative integers $\{0,1,2,\dots \}$ with addition form a commutative monoid, with identity element zero. They do not form a group: a positive integer has no additive inverse in that set. All words over an alphabet with concatenation form a free monoid, whose identity element is the empty word. The full transformation monoid consists of all self-maps of a set, with function composition and the identity function.

These examples explain why monoids are useful: accumulation needs an operation and a starting value, but it need not be reversible. Adding counts, joining strings, and composing transformations all share the same grouping and identity laws. Requiring every element to have an inverse element gives a group, a stronger structure suitable for reversible operations.

A group admits a two-sided invariant total order exactly when every finite list of nonidentity elements can be signed so that the conjugation-invariant semigroup generated by the signed elements excludes the identity. A compactness theorem argument supplies a compatible global sign assignment. Omitting the conjugates changes the criterion to a different orderability problem.

The Ohnishi orderability criterion states that, for each finite list $g_1,\dots ,g_n\ne 1$, there are signs ${\epsilon }_i\in \{-1,1\}$ such that the semigroup of nonempty products of conjugates of $g_i^{{\epsilon }_i}$ does not contain $1$. The conjugates are essential for a two-sided invariant total order. Necessity follows by choosing all signed elements positive: their conjugates and nonempty products are still positive.

For sufficiency, consider the compact product $\{+,-{\}}^{G\setminus \{1\}}$. Impose the closed conditions that an inverse has the opposite sign, that conjugation preserves sign, and that a product of two positive elements is positive whenever it is nonidentity. A positive pair cannot multiply to the identity because of the inverse condition. Each condition uses finitely many coordinates. Given finitely many conditions, collect every nonidentity element appearing in them into a finite list and choose signs using the criterion. These signs satisfy the conditions: an incorrectly negative product would contribute its positive inverse to the generated semigroup, producing identity with the positive factors; an incorrect conjugate or inverse gives the same contradiction. Extend the signs arbitrarily to the remaining coordinates. Thus the finite intersection property and compactness give a global sign assignment. Its positive elements form a conjugation-invariant semigroup $S$ with $S\cap S^{-1}=\varnothing$ and $S\cup S^{-1}=G\setminus \{1\}$. Defining $a<b$ by $a^{-1}b\in S$ gives the required linearly ordered group.

Restriction shows that every finitely generated subgroup of an orderable group is orderable. Conversely, suppose every such subgroup is orderable. If the criterion failed on $g_1,\dots ,g_n$, each of the finitely many sign choices would have an identity witness made of finitely many conjugates. Collect all $g_i$ and all conjugating elements in these witnesses into one finitely generated subgroup $H$. An order on $H$ supplies one positive sign choice, but its corresponding witness is a nonempty product of positive elements in $H$, a contradiction. Hence the criterion holds in $G$.

Finally, a finitely generated subgroup of a torsion-free abelian group is ${\mathbb{Z}}^r$ by the Fundamental theorem of finitely generated abelian groups. Its lexicographic order is two-sided invariant. Applying the local-to-global conclusion proves that every torsion-free abelian group admits the required order.

Let $u(t,x)=P_{1-t}f(x)$ for $t<1$. Differentiating the Brownian transition semigroup in the spatial variables is justified by the bounded gradient and givesThe heat equation for this semigroup is the backward equation ${\partial }_{t}u+\frac{1}{2}\Delta u=0$. Applying the multidimensional Itô formula yieldsThe finite-variation term vanishes. ThusInitially this calculation holds on $[0,1-\epsilon ]$. The vector of stochastic integral coefficients has norm at most $K$, so the Itô isometry lets the integrals extend to time one. Also $P_{1-t}f(X_t)\to f(X_1)$ in $L^2$ by the Lipschitz function bound and continuity of Brownian motion. The same representation therefore holds on the entire interval.

Take $\mathbb{N}=\{1,2,\dots \}$. We first prove the Ellis–Numakura lemma in the one-sided continuity convention needed here. Let $S$ be a nonempty compact Hausdorff space with an associative multiplication for which each map $x\mapsto xa$ is continuous. Among its nonempty closed subsemigroups, there is an inclusion-minimal one, $M$: a decreasing chain has nonempty intersection by compactness, and that intersection is a closed subsemigroup, so Zorn's lemma applies.

Fix $a\in M$. The set $Ma$ is nonempty and compact, hence closed in the Hausdorff space, and is a subsemigroup becauseMinimality gives $Ma=M$. Thus the set $T=\{x\in M:xa=a\}$ is nonempty. It is closed by the stated continuity, and it is a subsemigroup, since $(xy)a=x(ya)=xa=a$ for $x,y\in T$. Minimality again gives $T=M$, so $a\in T$ and $\boxed{a^2=a}$, giving a semigroup idempotent. If one instead uses the opposite one-sided continuity convention, the same proof uses $aM$ and $\{x:ax=a\}$; no joint continuity is required.

Apply this lemma to the Stone-Čech compactification of the natural numbers with its given addition. In the addition on the Stone-Čech compactification of the natural numbers convention,The continuous variable is $p$ when $q$ is fixed. The granted compactness, Hausdorff property and associativity therefore imply there exists an idempotent ultrafilter $p$ with $p+p=p$.

On the positive integers such a $p$ is nonprincipal: a principal ultrafilter at $n$ adds to itself to give the one at $2n$, which is different. Hence every cofinite set belongs to $p$. If zero is included in one's convention for $\mathbb{N}$, use the same compact semigroup argument on the closed space of nonprincipal ultrafilters: it is nonempty by compactness of the infinite discrete set's compactification, and the displayed addition sends two free ultrafilters to a free ultrafilter. This avoids the trivial principal idempotent at zero.

To deduce Hindman's theorem, let $A$ be the unique colour class belonging to $p$. DefineIdempotence gives $A^{\ast }\in p$. The idempotent-ultrafilter star-set lemma also gives $A^{\ast }-n\in p$ whenever $n\in A^{\ast }$. Here is its proof: $A-n\in p$, and applying idempotence to $A-n$ givesIntersecting this set with $A-n$ produces exactly $A^{\ast }-n$.

Choose $x_1\in A^{\ast }$. Suppose $x_1<\cdots <x_r$ have been chosen with every nonempty finite sum in $A^{\ast }$. The finite intersectionbelongs to $p$, and is therefore nonempty. Choose $x_{r+1}$ from it. The new sums are $x_{r+1}$ and $s+x_{r+1}$, and they all lie in $A^{\ast }$. Induction yieldsThis proves every finite colouring of the positive integers admits a monochromatic finite-sums set generated by a strictly increasing infinite sequence, the required Hindman theorem.

Use the intrinsic definition of a Lévy process: $X_0=0$ almost surely, its increments over disjoint time intervals are independent, their probability distributions depend only on interval length, and $X$ has stochastic continuity. In symbols,with times restricted to the half-line. Such a stochastic process has a càdlàg modification, and is usually represented by that version. Requiring càdlàg paths in the definition is a common equivalent convention at the level of modifications; it is important to distinguish this from a claim about the paths of an arbitrary supplied version.

For the characteristic function, writeHere $\psi (0)=0$ and $\psi$ is the positive-time-sign characteristic exponent of a Lévy process. The independent increments and stationary increments give ${\varphi }_{s+t}(\theta )={\varphi }_s(\theta ){\varphi }_t(\theta )$; stochastic continuity gives continuity in time and ${\varphi }_0=1$. This continuous multiplicative semigroup has the stated exponential form. Its exponent has the Lévy–Khintchine formulawhere $b\in \mathbb{R}$, ${\sigma }^2\ge 0$, and the Lévy measure $\nu$ satisfies $\int (1\wedge y^2)\nu (dy)<\infty$. The truncation convention fixes the drift coefficient $b$; the displayed sign convention agrees with $\Psi =-\psi$.

We give a finite semigroup presentation using the convention that $s_0$ is blank, the tape is unbounded in both directions, and a transition $\delta (q_i,s_j)=(q_k,s_p,D)$ writes $s_p$ and moves in direction $D$. The Turing machine is deterministic, and the halting state $q_0$ has no outgoing transition. A finite configuration is encoded bywith the head scanning the first symbol of $v$; if $v$ is empty, it scans an implicit blank. Unrepresented cells beyond the boundary markers $h$ are blank. An additional generator $q$ records completed halting and erasure.

The generators of the semigroup are $S\bigsqcup Q\bigsqcup \{h,q\}$. Its relations have the following finite families. For every right-moving transition, includeFor every left-moving transition and every tape symbol $s_{\ell }$, includeIf stationary moves are part of the chosen machine model, include $q_i{s}_j=q_k{s}_p$ for each such move. Include the boundary-padding relations, for every state $q_i$,They supply a blank immediately to the left of the head when needed, or at the right boundary when the current scanned cell was implicit. Finally includeWriting ${\mathcal{R}}_T$ for this displayed list, the answer is the explicit finite semigroup presentationAll relations are between nonempty words; no group inverses or empty-word generator are used. The transition families are finite because the transition table and alphabet are finite, and the padding and erasure families are visibly finite. The declared head convention determines which side of a tape symbol carries a state letter.

If the Turing machine halts on $w$, follow its computation from $h{q}_{1}wh$. A transition at an already represented cell is one of the corresponding relations. At a boundary, first insert the required blank using a padding relation. Thus the computation gives a finite equality derivation to $hu{q}_{0}vh$. Replace $q_0$ by $q$, erase the symbols of $u,v$ using $s_{j}q=q=q{s}_j$, and erase both boundary markers. This proves $h{q}_{1}wh=q$ in the semigroup.

For the converse, equality in a presented semigroup means a finite sequence of contextual replacements using defining relations in either direction. In any derivation from $h{q}_{1}wh$ to $q$, consider the first occurrence of the special symbol $q$. Before it occurs, the erasure relations cannot be used in either direction. Each word therefore still has exactly two markers $h$, exactly one state letter, and the form $hu{q}_{i}vh$. Both directions of a transition relation join configurations linked by one actual machine step; both directions of a boundary-padding relation merely change how much blank tape is represented.

The first occurrence of $q$ must come from $q_0=q$ in the forward direction. Hence the initial configuration is connected, by transitions in either direction and harmless padding, to a configuration in state $q_0$. For a deterministic Turing machine, the property of eventually reaching $q_0$ is invariant along each transition edge: if $C\to D$ is a step, then $C$ halts if and only if $D$ halts, since that step is the unique next step of $C$ and $C$ is not already in the halting state. The same property is unchanged by padding. A finite path of these edges to $q_0$ therefore shows that the initial configuration halts.

ConsequentlyThe invariance argument is necessary because equality in a semigroup presentation allows reversed transitions as well as forward computation steps.

Hindman theorem states that every finite coloring of $\mathbb{N}$ admits an infinite sequence $x_1,x_2,\dots$ whose finite-sums set is monochromatic.

Identify the Stone-Čech compactification of the natural numbers $\beta \mathbb{N}$ with the compact Hausdorff space of ultrafilters on $\mathbb{N}$, equipped with addition on the Stone-Čech compactification of the natural numbers. This makes $\beta \mathbb{N}$ a compact Hausdorff left-topological semigroup. For completeness, the Ellis–Numakura lemma gives an idempotent in every such semigroup: by the Hausdorff space property and compactness, the intersection of a descending chain of nonempty compact subsemigroups is nonempty, so Zorn's lemma gives a minimal one $K$. For $a\in K$, the compact subsemigroup $K+a$ equals $K$. Hence the nonempty compact subsemigroupis also $K$, and in particular $a+a=a$. Choose the resulting idempotent ultrafilter on the natural numbers $\mathcal{U}$.

One color class $A$ belongs to $\mathcal{U}$. For $x\in \mathbb{N}$, writeand defineThe identity $\mathcal{U}+\mathcal{U}=\mathcal{U}$ implies $A^{\ast }\in \mathcal{U}$. It also implies that $A^{\ast }-x\in \mathcal{U}$ for every $x\in A^{\ast }$: both $A-x$ and the set of $y$ for which $A-(x+y)$ belongs to $\mathcal{U}$ lie in $\mathcal{U}$, and their intersection is $A^{\ast }-x$.

Choose $x_1\in A^{\ast }$. Having chosen $x_1,\dots ,x_n$ with every nonempty finite sum in $A^{\ast }$, chooseThis is possible because it is a finite intersection of members of the ultrafilter $\mathcal{U}$. Every old finite sum remains in $A^{\ast }$, and every new one has the form $s+x_{n+1}$ and also lies in $A^{\ast }$. By mathematical induction, all nonempty finite sums lie in $A^{\ast }\subseteq A$, proving Hindman's theorem.

Now putfor each $A\in \mathcal{U}$. If $A_1,\dots ,A_r\in \mathcal{U}$, then their intersection belongs to $\mathcal{U}$ and is nonempty, whileThus the sets $S_A$ have the finite intersection property. Their closures are closed subsets of the compact interval $[0,1]$, so their total intersection contains some $x$. Equivalently, every neighbourhood of $x$ meets every $S_A$; this is the ultrafilter limit of the sequence.

The point is unique. If distinct points $x,y$ both had this property, choose disjoint neighborhoods $U,V$. The index set $I_U=\{n:x_n\in U\}$ must belong to $\mathcal{U}$, because otherwise its complement would belong to $\mathcal{U}$ and the associated $S_A$ would miss $U$. Similarly $I_V\in \mathcal{U}$. Their intersection is empty, contradicting the definition of an ultrafilter.

A rectangular band is a semigroup satisfying the displayed identities; these also imply associativity. Every nonempty such algebra is a product $B\times C$ with $(b,c)\ast (b^{\prime },c^{\prime })=(b,c^{\prime })$. Fixing $e$, the factor sets are $B=\{x\ast e\}$ and $C=\{e\ast x\}$, and $x\mapsto (x\ast e,e\ast x)$ has inverse $(b,c)\mapsto b\ast c$. Homomorphisms between nonempty products are exactly pairs of maps on the two factors.

A semigroup is an algebraic magma whose binary operation has the associative property. Its products can be regrouped while preserving the order of their elements. An identity element and inverse elements are not required.

For example, the positive integers with addition form a semigroup, since $(a+b)+c=a+(b+c)$ and a sum of positive integers is positive. They have no identity element: it would have to be zero, which is outside that set. Nonempty words over an alphabet with concatenation give a noncommutative example without an identity element. Including the empty word instead gives a free monoid.

The usefulness of a semigroup is that an ordered list has one product regardless of its parentheses. This permits replacing a consecutive block by its already computed value. Here the empty set is also allowed as a semigroup; a monoid is necessarily nonempty because it contains an identity element.