A concrete model of the two-generated free Abelian lattice-ordered group is the lattice subgroup of real-valued functions on ${\mathbb{R}}^2$ generated by the coordinate projections $X(x,y)=x$, $Y(x,y)=y$. Its elements are finite joins of finite meets of integer linear forms $ax+by$. Thus they are continuous positively homogeneous piecewise linear functions, with pointwise addition and lattice operations. This is the piecewise integer-linear representation of a free Abelian lattice-ordered group.

For the construction, first form the term algebra on two symbols using addition, negation, zero, join and meet, then identify terms that agree in every Abelian lattice-ordered group. Evaluation under any assignment of the two generators factors through this quotient, proving its universal property. To obtain the concrete function model, use the identity-detection theorem that the real line generates the variety of Abelian lattice-ordered groups. Its proof passes a failed identity to a prime ordered quotient, chooses its finitely many active linear pieces, and uses the rational-inequality alternative underlying Farkas' lemma to find a real witness. This makes evaluation on ${\mathbb{R}}^2$ injective as well as surjective onto the generated function group.

Its underlying group is not ${\mathbb{Z}}^n$ for any finite $n$. The integer-linear hinge functions have infinite independent rank: $h_k(x,y)=(x-ky)\vee 0$ are integer-linearly independent for distinct integers $k$. On $y=1$, only $h_k$ has a slope jump at $x=k$, so each coefficient in a finite relation must vanish. The underlying group therefore has infinite rank of an abelian group despite having two lattice generators.

No: there are at most three, including zero and the whole group. A two-generator ordered Abelian group is torsion-free and has rank of an abelian group at most two. A convex subgroup of an ordered group is pure: if $ng\in C$ with $n>0$, then $g$ lies between zero and $ng$ or their negatives, so $g\in C$. Therefore a proper inclusion $C<D$ of convex subgroups increases rational rank: an element of $D\setminus C$ cannot have a nonzero integer multiple in $C$. Convex subgroups form a chain, so a rank-two group permits at most two strict inclusions. This is the bound for convex subgroups of a finite-rank ordered Abelian group. It is sharp: lexicographically ordered group ${\mathbb{Z}}^2$ has exactly $0$, $\{0\}\times \mathbb{Z}$, and ${\mathbb{Z}}^2$.

Construct the conjugacy of positive real-line bumps using $u=v=\alpha$. Since both $\alpha f$ and $\alpha g$ are greater than $\beta$, choose the fundamental-interval map to be identity on $[\alpha ,\beta ]$ and then increase from $\beta$ to the respective right endpoints. Equivariant extension along $f$ and $g$ gives a conjugator on their supports fixing $[\alpha ,\beta ]$. Extend it over the remaining portions of $J=[\gamma ,\gamma h]$, fixing the endpoints of $J$; both support intervals lie strictly inside $J$. Call the resulting interval bijection $b_0$. It satisfies $f{b}_0=b_{0}g$ on $J$.

The point $\gamma$ lies in a positive orbital of $h$, because $\gamma h>\gamma$. Its half-open cells $J{h}^n$, $n\in \mathbb{Z}$, partition that orbital. Extend byand set $b$ to identity outside the orbital. Since $b_0$ fixes the cell endpoints, this is an order automorphism and satisfies $bh=hb$. Each cell is preserved; $f$ and $g$ are identity on all cells other than the original one, so $fb=bg$ holds everywhere. Finally $b$ fixes $[\alpha ,\beta ]$ pointwise, and $a$ is supported inside that interval. Hence $ba=ab$. ThusThis is conjugating positive bumps while preserving a fundamental interval; merely choosing an arbitrary conjugator would not ensure either commutation relation.

Write the two supports as $I_f=(l_f,r_f)$ and $I_g=(l_g,r_g)$. Every point in a support moves strictly right: a positive nonidentity order automorphism has no fixed point inside its one support interval. Choose $u\in I_f$, $v\in I_g$ and an increasing bijection $\theta :[u,uf]\to [v,vg]$ matching endpoints. The half-open intervals $[u{f}^n,u{f}^{n+1})$, for $n\in \mathbb{Z}$, partition $I_f$, because the iterates tend to its endpoints. DefineThe endpoint choices make adjacent pieces fit, giving an increasing bijection $b:I_f\to I_g$ with $fb=bg$. Extend over the two complementary closed rays by increasing maps taking $l_f,r_f$ to $l_g,r_g$. Outside the supports both automorphisms are identity, so $fb=bg$ still holds. Therefore $\boxed{b^{-1}fb=g}$. This gives the conjugacy of positive real-line bumps.

For a faithful transitive ordered action, primitivity here means that the only invariant equivalence relations with convex classes are equality and the universal relation. The trichotomy is: a regular Archimedean action, an order two-transitive action, or a periodic action. In the regular case the chain is an ordered additive subgroup of $\mathbb{R}$, acting by translations. In the periodic case there is a fixed-point-free period $z$ on the Dedekind completion, commuting with the action and having cofinal and coinitial integer iterates; inside a period interval the relevant stabilizer acts order two-transitively. These are the cases of the McCleary trichotomy theorem.

Only the regular Archimedean case satisfies the inequality. It is a linearly ordered group. For positive $a,b$, if $a\le b$, then $ab\le b^2\le b^2{a}^2$; if $b\le a$, then $ab\le a^2\le b^2{a}^2$. Taking $a=|f|$, $b=|g|$ proves the displayed inequality.

To exclude an order two-transitive action, choose $x<y<z<t$. Choose an automorphism taking $(x,y)$ to $(y,z)$ and replace it by its pointwise join with the identity, giving positive $a$ with $xa=y$, $ya=z$. Similarly obtain positive $b$ with $xb=x$, $yb=t$. ThenThus $ab\nleqq b^2{a}^2$, while $|a|=a$ and $|b|=b$. The same construction inside a period interval excludes the periodic case, using the order two-transitive stabilizer supplied by the classification.

Here transitivity is order n-transitivity: increasing tuples are compared, rather than arbitrary reorderings. For increasing tuples ${\alpha }_1<\cdots <{\alpha }_n$ and ${\beta }_1<\cdots <{\beta }_n$, choose $h_{ij}$ sending both ${\alpha }_i$ to ${\beta }_i$ and ${\alpha }_j$ to ${\beta }_j$ when $i\ne j$, using order two-transitivity. For $i=j$, choose an element sending the single point to its target, using transitivity. Define

This belongs to the lattice-ordered permutation group. At ${\alpha }_i$, all terms in its $i$th inner meet equal ${\beta }_i$. At ${\alpha }_k$, every inner meet is at most ${\beta }_k$, because its $j=k$ term takes that value. The outer join is consequently exactly ${\beta }_k$ there. Thus $h$ maps the whole tuple to its target. This finite interpolation by lattice operations proves every finite order-transitivity without assuming the group permits arbitrary cut-and-paste restrictions of its elements.

For each $g\ne 1$, choose a value in a lattice-ordered group $P_g$, using Zorn's lemma. Such a value is a prime convex lattice subgroup. Otherwise the last construction in Question 1(i) would give two larger convex lattice subgroups whose intersection is $P_g$; maximality among subgroups omitting $g$ would put $g$ in both, hence in their intersection. Thus the right coset set ${\Omega }_g=P_g\backslash G$ is a totally ordered set.

Right multiplication defines an action ${\rho }_g(a):P_{g}h\mapsto P_{g}ha$. It is well-defined, preserves the total order, and has inverse ${\rho }_g(a^{-1})$. The coset formulas from Question 1(i) show pointwise preservation of both join and meet, becauseand likewise for the meet.

Take the disjoint union of these chains, arranged in any fixed order sum of the indices $g\ne 1$. Let every $a\in G$ act on each component by ${\rho }_g(a)$. This gives a lattice-ordered group homomorphism into the order automorphisms of one chain. It is injective: a nonidentity $a$ moves the identity coset in ${\Omega }_a$, since $P_{a}a\ne P_a$. Its image is closed under pointwise join and meet, giving exactly the required lattice-ordered permutation group. This is the Holland representation theorem.

Let $T_e$ be the theory of the extension axioms for an unrestricted binary relation. It has quantifier elimination. To prove this, consider a conjunction of literals $\theta (y,\mathbf{x})$. A witness $y$ equal to one of the parameters is handled by substitution. A witness distinct from them is governed entirely by a finite pattern of incoming edges, outgoing edges and its loop. For each equality pattern of the parameter tuple, incompatible literals make the pattern impossible, and every compatible pattern is supplied by the appropriate extension axiom. Thus existence of a witness is a finite disjunction of quantifier-free conditions on the parameters. Disjunctive normal form and induction on formulas eliminate all remaining quantifiers.

Given any formula $\varphi (\mathbf{x})$, choose a quantifier-free $\psi (\mathbf{x})$ withBy compactness theorem, finitely many extension axioms ${\sigma }_1,\dots ,{\sigma }_s$ already entail this particular universally quantified equivalence. Each has asymptotic probability one by the assumption. The union bound givesTherefore the universal equivalence also has asymptotic probability one. We obtain asymptotic equivalence to a quantifier-free formula, uniformly over every tuple in each structure satisfying those finitely many axioms. An infinite conjunction of probability-one events is not used; the finite consequence supplied by compactness is essential.

For an unrestricted binary relation $R$, the extension axioms permit arbitrary directed edges and loops. For each $m\ge 0$ and each choice of bits ${ϵ}_i,{\delta }_i,\eta \in \{0,1\}$, require that every tuple of distinct $x_1,\dots ,x_m$ has a fresh element $y$ withHere $P^1$ denotes $P$ and $P^0$ denotes $\neg P$; the notation is a literal abbreviation, not exponentiation of a relation. Incoming and outgoing choices are independent, and the loop bit is also specified. These are the extension axioms for an unrestricted binary relation. If one instead restricts to undirected loop-free graphs, the allowable patterns reduce to the random-graph extension axioms of Question 2; no such restriction is imposed here.

As usual, a class of structures here is closed under isomorphism and uses standard finite-structure encodings. First suppose $K$ is defined by $\exists R\varphi$, with $\varphi$ in partial fixed-point logic. Deterministically enumerate the polynomial-length encodings of $R$ and evaluate $\varphi$ on each expansion. PFP evaluation is in PSPACE even without a supplied order: a relation of fixed arity requires polynomially many bits, iteration has at most exponentially many states, and a polynomial-length counter suffices to stop after that many stages. If no consecutive stages agree before a repeat must have occurred, the partial fixed point is empty. Nested fixed points have fixed syntactic depth and can be evaluated with reused polynomial storage. Thus the encoding language of $K$ is in PSPACE.

Conversely, suppose that encoding language is decidable in PSPACE. Expand each structure by a freely chosen linear order $R$. On such ordered expansions, the assumed characterization gives a PFP sentence $\psi (R)$ deciding whether the reduct belongs to $K$. Since $K$ is isomorphism-invariant, the answer is independent of the particular chosen order. HenceThe expression inside the second-order quantifier is PFP, since the assertion that $R$ is a linear order is first-order. Every finite universe has a linear order. This proves both directions, using an existentially supplied order when the original signature has none. The construction is also the order-independent consequence of part (a), which shows that existential relation quantification does not increase PFP's power on an already ordered structure.

Fix a partial fixed-point logic formula $\varphi (R,\mathbf{x})$, with $R$ of arity $k$. On a finite ordered structure, an interpretation of $R$ is a bit string of length $n^k$. To decide whether some interpretation makes $\varphi$ true at a given tuple, enumerate all these strings and evaluate $\varphi$ for each. Evaluation uses polynomial space by the permitted characterization of PFP, and the enumerating counter also has polynomial length. Storage is reused between interpretations. Thus the resulting pointed-structure property is decidable in PSPACE.

Apply the assumed PFP characterization of PSPACE on ordered structures to this property. It gives a PFP formula $\psi (\mathbf{x})$ such thatTo justify the formula version from a sentence characterization, temporarily name the tuple by finitely many new constants, apply the characterization in that expanded finite signature, and replace those constants by the free variables, renaming bound variables to avoid capture. This does not introduce a new order assumption: the input already interprets $<$ as a linear order. Multiple quantified relations are handled by repeated application.

Every fixed second-order logic sentence is evaluable in PSPACE. On a universe of size $n$, a relation of arity $k$ is stored using $n^k$ bits. Enumerate its possible interpretations with a counter of the same polynomial length, recursively evaluate the inner formula and reuse the storage. Universal quantifiers require checking all interpretations; existential ones stop at the first success. The fixed quantifier depth and fixed arities bound total space by a polynomial, even though time can be exponential. First-order quantifiers and Boolean operations require no larger bound.

If $NP=PSPACE$, this places the class defined by the assumed second-order sentence in NP. Fagin's theorem would give an equivalent existential second-order sentence, again contradicting the hypothesis. HenceFor completeness, $NP\subseteq PSPACE$: a polynomial-time nondeterministic computation can be searched deterministically depth first, retaining a polynomial-length computation branch and reusing space. Thus the inequality is a strict containment under the stated hypothesis.

Here equivalence means equivalence on all finite structures of the chosen signature, and an existential sentence means an existential second-order sentence. Suppose, towards a contradiction, that P equals NP. We use that P is closed under complementation, that fixed first-order model checking is polynomial-time, and that guessing a polynomial-length string followed by a polynomial-time test is in NP.

Under this equality, evaluating any fixed second-order logic sentence is in P. Prove this by induction through its quantifiers and Boolean operations. The first-order part is already polynomial-time. If an inner formula can be evaluated in P, existentially quantifying a relation of fixed arity guesses at most $n^k$ bits and then performs the inner polynomial-time test. This gives an NP procedure and hence, under the assumption, a P procedure. A universal relation quantifier is handled by complementing the corresponding existential test. Boolean combinations remain polynomial-time as well. A fixed formula has only finitely many such steps and fixed arities, so the resulting time bound is polynomial.

Consequently every second-order definable class lies in P, hence in NP. By Fagin's theorem it has an equivalent existential second-order sentence. This contradicts the posited second-order sentence with no such equivalent. ThereforeThe proof uses the equality assumption to collapse quantifier alternation; it does not assume an unproved strictness statement about the polynomial hierarchy.

Fagin's theorem states that, for a finite relational signature, an isomorphism-invariant class of finite structures has its standard encoding language in NP if and only if it is definable by an existential second-order logic sentencewhere $\psi$ is first-order and the relation variables have fixed finite arities. The forward implication includes the substantive encoding of a polynomially bounded accepting computation by relations. In the reverse implication the relations are polynomial-length certificates and the fixed first-order sentence can be checked in polynomial time. This is a finite-structure characterization; no order need be named in the input signature.

Suppose a first-order sentence $\theta$ defined the bipartite graphs, equivalently the 2-colourable graphs. Let $q$ be its quantifier rank and $r=3^q$. Choose an odd integer $N>2r+1$, and compareBoth have $2N$ vertices. Every marked radius-$r$ neighbourhood in either graph is a path with $2r+1$ vertices and its middle vertex marked: the choice of $N$ prevents the ball from wrapping around a cycle. Thus every vertex has exactly the same neighbourhood type in both graphs, and that type occurs $2N$ times in each. Any bijection of their universes meets the Hanf locality lemma hypothesis.

Therefore $A$ and $B$ agree on $\theta$. But $A$ is an even cycle and is bipartite, whereas $B$ contains odd cycles and is not bipartite. This contradiction provesThe equal total size is useful here: no large-count threshold or comparison of unequal multiplicities is needed.

An exact-count form of the Hanf locality lemma is as follows. For every quantifier rank $q$, put $r=3^q$. If finite relational structures $A,B$ admit a bijection $f:A\to B$ such thatthen $A$ and $B$ agree on every first-order sentence of quantifier rank at most $q$. Equivalently, they have the same number of occurrences of every marked radius-$r$ one-point neighbourhood type. The individual local isomorphisms need not be restrictions of $f$.

A bounded-degree threshold version permits the type counts to be different when both exceed a sufficiently large bound depending on the degree bound and $q$. We need only the exact-count form. Its locality content is that sufficiently large matching neighbourhoods and their multiplicities determine all sentences up to the prescribed quantifier rank.

For a relational first-order structure $A$, form its Gaifman graph: distinct elements are adjacent when they occur together in a tuple of some interpreted relation. Let $d_A$ be graph distance, with distance infinite between different components. For a tuple $\mathbf{a}=(a_1,\dots ,a_m)$, its radius-$r$ neighbourhood has universeThe neighbourhood structure is the induced relational structure on this set, expanded by constants marking the entries of $\mathbf{a}$ in their original order. Its isomorphism type thus records the centres, not just the unmarked ball. For one binary graph relation, this is the usual union of the radius-$r$ graph balls. This formulation assumes the finite relational signatures used in the finite-model setting.

Assume $A$ is a countable model of $T$ and its automorphism group is an oligomorphic permutation group. Complete types are constant on automorphism orbits, so only finitely many complete $n$-types are realized in $A$, for each $n$.

These realized types are dense in the Stone topology on a type space $S_n(T)$. Indeed, any nonempty basic clopen set $[\theta ]$ is given by a formula consistent with $T$. Completeness implies $T\models \exists \mathbf{x}\theta$, and thus some tuple in $A$ realizes a type in $[\theta ]$. A finite set of points is closed in a Hausdorff space; if it is also dense, it is the whole space. Therefore $S_n(T)$ equals the finite set of types realized in $A$. This proves (iii) implies (ii), and the previous part then yields (i). We have establishedIn particular, the argument does not assume that an arbitrary countable model is saturated or that its type-orbits coincide before that coincidence has been proved.

We use the finite-structure convention of Section B. Express that $<$ is a strict linear order by irreflexivity, transitivity and comparability of distinct points. Express that $E$ is an equivalence relation by reflexivity, symmetry and transitivity. All these assertions use at most the three variable names $x,y,z$.

In a finite linearly ordered structure, every equivalence class has a unique least element. The two-variable formulaselects exactly those least elements. Apply part (b) to this formula, using $k=3$, to obtain ${\mathrm{Rep}}_n\in L^3$ saying that at least $n$ representatives exist. The required sentence isThis gives the least representatives of finite equivalence classes construction. Under the two structural axioms, counting representatives is exactly counting equivalence classes.

Finiteness is essential to the assertion as written in this section. If it were interpreted as applying to all infinite structures, the general claim would fail, not merely this choice of representatives. Partition the rational order into three dense classes, or into four dense classes, and let $E$ mean belonging to the same class. In the three-pebble version of the Ehrenfeucht-Fraïssé game, the duplicator can play indefinitely between these structures: after one pebble is moved, at most two old classes remain represented; a new point can be placed in the required interval in its corresponding old class, or in a class different from both. Density makes every required placement possible in either structure. Thus the structures agree on all $L^3$ sentences although one has three classes and the other four. The finite reading of the printed request is therefore necessary for $n=4$.

Choose a variable name $y\ne x$ among the $k$ available names and defineThe formula $C_m^y$ is obtained by interchanging the names $x,y$ throughout $C_m^x$, including bound occurrences. Its only free variable is $y$. A permutation of variable names preserves membership in $L^k$, so every formula in this recursion still uses at most the original $k$ names. In particular, bound variables inside a copy of $\varphi$ do not accidentally capture the previous comparison: their scope stays inside that copy.

Induction proves that $C_m^x(a)$ holds exactly when there is an increasing $m$-tuple of satisfying elements whose first entry is $a$. Any set of $m$ distinct points in a linear order can be put in increasing order. Therefore the variable-recycling count on a linear orderis the required sentence. This does not use counting quantifiers or additional variable names, and it applies equally to infinite linear orders.