Rieg theory

Question

What is the subrieg of $[0,\infty)$ generated by $\mathbb Q_{\geq0}$, with ordinary exponentiation and $0^0=1$? Which equations hold between its expressions? Is the canonical map from the rieg freely generated by the rig $\mathbb Q_{\geq0}$ injective?

First distinction

The nonnegative rationals themselves are not closed under exponentiation: $2^{1/2}$ is already irrational. The question concerns the closure under all rieg operations and the relations in that closure.

Next step

State the universal property of the rieg generated by the rig $\mathbb Q_{\geq0}$, then write its canonical evaluation map into $[0,\infty)$. To prove a relation is additional, exhibit two terms with the same real value and prove that their equality does not follow from the rieg axioms and the specified rational rig relations. Merely finding two equal real expressions does not establish this.

Original problem 7.0.3.

Yes. Every De Morgan algebra $(A,\vee,\wedge,0,1,\neg)$ is a rieg with $x+y=x\vee y$, $xy=x\wedge y$ and $x^y=x\vee\neg y$: the laws $x^0=1$, $x^1=x$, $1^x=1$, $x^{y+z}=x^yx^z$, $(xy)^z=x^zy^z$ and $(x^y)^z=x^{yz}$ follow from distributivity and $\neg0=1$, $\neg1=0$, $\neg(y\vee z)=\neg y\wedge\neg z$, $\neg(y\wedge z)=\neg y\vee\neg z$. For a Boolean algebra this is the rieg $x^y=(y\Rightarrow x)$ of Notes on Rieg Theory, Example 5.0.2 and Proposition 5.3.1. In particular $[0,1]$ with $\max$, $\min$ and $x^y=\max(x,1-y)$ is a nontrivial connected compact Hausdorff topological rieg; all three operations are continuous. Its addition is idempotent, hence not cancellative, as Compact riegs with cancellative addition are trivial requires of every example. Not yet verified by a human.

Question

Does a nontrivial connected compact Hausdorff topological rieg exist? All three binary operations—addition, multiplication, and exponentiation—are required to be continuous.

Current result

Compact rieg no-go proves that every compact Hausdorff topological rieg with cancellative addition is trivial. Connectedness is not needed for that result. Thus a positive answer must have noncancellative addition; the general existence question remains open here.

The original motivation compares connected topological algebra with profinite algebra. A path-connected topological rig is contractible: a path $p$ from $0$ to $1$ gives $H(t,x)=p(t)x$. This observation concerns path-connectedness and does not by itself settle the connected compact case.

Next step

Choose a compact connected noncancellative topological semiring and test whether it admits a jointly continuous exponentiation satisfying all the rieg equations, especially $x^0=1$, $x^1=x$, and $x^{y+z}=x^yx^z$. Failure of a particular candidate is not a general nonexistence theorem.

Source

Original problem 7.0.5.

Question

Let $F_1$ be the free rieg on one generator $x$. Can its elements be interpreted as combinatorial games? Can the unique rieg homomorphism

be interpreted in terms of those games?

What an answer must provide

Specify the games and their equality, interpret $0,1,+,\times$, and exponentiation, and show that the rieg equations hold. A full model of $F_1$ must also identify when two game expressions represent the same element; a map out of $F_1$ alone need not be injective.

Next step

Give a concrete candidate for exponentiation of games, then test the exponent laws and the evaluation $x\mapsto0$. The existing recursive-coalgebra model of impartial games does not by itself supply these rieg operations.

Sources: original problem 7.0.1; Classical vs quantum computation.

Partial answer to the second task. (a) Equality of the functions on $\mathbb N$ is decidable. For $x\geq1$ every subterm is either identically $0$ or $\geq1$, and which case occurs is read off from the term; rewriting from the inside out by $u+0\mapsto u$, $u\cdot0\mapsto0$, $u^0\mapsto1$ and $0^v\mapsto0$ for $v\neq0$ turns a term, without changing its values at $x\geq1$, into $0$ or into a term without $0$. Two $0$-free terms agree on $\mathbb N_{>0}$ exactly when the one-variable identity holds in $(\mathbb N_{>0},+,\cdot,\uparrow,1)$, which is decidable (Richardson, Z. Math. Logik Grundlagen Math. 15 (1969); see Burris–Yeats, The saga of the high school identities, Algebra Universalis 52, §3), and the values at $x=0$ are computed directly. (b) The evaluation $F_1\to\mathbb N^{\mathbb N}$ is not injective: $x\cdot0^x$ and $0$ define the same function, but in the three-element rieg $\{0,\tfrac12,1\}$ with $\max$, $\min$ and $y^z=\max(y,1-z)$ (one of the four exponentiations on the three-element chain in Notes on Rieg Theory, Appendix B.2, Figure 8; see also Connected compact Hausdorff riegs) the term $x\cdot0^x$ takes the value $\tfrac12$ at $x=\tfrac12$. Without $0$ the analogous question is Tarski's high school algebra problem (Wilkie; Gurevič). The first task, a characterization of the functions, remains open; on $\mathbb N_{>0}$ the one-variable term functions without $0$ form Skolem's class, which is well ordered by eventual domination (Ehrenfeucht, Algebra Universalis 3 (1973)). Not yet verified by a human.

Question

Which functions $\mathbb N\to\mathbb N$ can be represented by a term in the free rieg $F_1$ on one generator?

Here a term is built from $0,1,x$ using addition, multiplication, and binary exponentiation. Evaluating $x=n$ in the natural-number rieg gives its function, with $0^0=1$.

Two distinct tasks

1. Characterize the functions obtained by this evaluation.
2. Determine when two terms give the same function on $\mathbb N$.

The second question must distinguish equality of functions on this particular rieg from equality forced by the axioms in the free rieg.

Next step

Identify a property shared by all representable functions and prove it by induction on terms, or exhibit a function together with a rigorous nonrepresentability argument. A table of small inputs alone cannot establish representability or equality for all natural numbers.

Original problem 7.0.2.

Partial answer. For a presheaf $X$ let $X_{\mathrm{fin}}\subseteq X$ consist of the elements that generate a finite-valued subpresheaf; $X\mapsto X_{\mathrm{fin}}$ is the left exact coreflection onto locally finite presheaves (for a free monoid it is $h_*$ of Hora, Topoi of automata I, arXiv:2411.06358, Lemma 2.20). Every map from a finite presheaf into $X$ lands in $X_{\mathrm{fin}}$, and a finite presheaf representing $\operatorname{Hom}(-,X)$ on $\mathbf{fPSh}(\mathcal C)$ is necessarily $X_{\mathrm{fin}}$. Hence: (1) With $\Omega$ and $G^F$ computed in all presheaves, $\mathbf{fPSh}(\mathcal C)$ has a subobject classifier iff $\Omega_{\mathrm{fin}}$ is finite-valued, and has an exponential of $G$ by $F$ iff $(G^F)_{\mathrm{fin}}$ is finite-valued; these are then the universal objects. (2) It is a topos iff for every object $c$ and finite $X$ only finitely many $R\subseteq y(c)\times X$ have, for every $d$, finitely many pullbacks $(f\times X)^*R$ along $f:d\to c$. (3) If all hom-sets are finite, it is a topos iff every finite presheaf on each slice $\mathcal C/c$ has finitely many subpresheaves. Essentially finite slices are not necessary: for an infinite group $G$ and $M=G\sqcup\{0\}$, $\mathbf{fPSh}(M)$ is a topos ($M$ has three right ideals and $\operatorname{Sub}(M\times X)$ has at most $4^{|X|}$ elements), although $\operatorname{End}(0)=M$ in $M/{\ast}$. A subobject classifier is not enough: on nonempty finite sets $\Omega$ is finite-valued, but the presheaf of equivalence relations has the subpresheaves “at most $k$ classes” for all $k$, so it has no power object. For the monoid $(\mathbb N,+)$ there is no subobject classifier, since every ideal $n+\mathbb N$ lies in $\Omega_{\mathrm{fin}}$ (nor is it cartesian closed: Notes on Rieg Theory, Example 4.1.8). Open: a criterion in terms of $\mathcal C$ alone, local cartesian closedness, and whether for finite hom-sets the condition in (3) forces essentially finite slices. Not yet verified by a human.

Question

For a small category $\mathcal C$, when is the category

of pointwise finite-valued presheaves an elementary topos, or locally cartesian closed?

The motivation is enumerative combinatorics and Burnside riegs. This question was discussed with Jérémie Marquès.

Known sufficient condition

Finite limits are computed pointwise. If every slice $\mathcal C/c$ is essentially finite, then the usual presheaf subobject classifier and exponentials are finite-valued, so $\mathbf{fPSh}(\mathcal C)$ is an elementary topos. This includes finite categories and groups regarded as one-object categories.

Here are the two relevant ambient formulas. The value $\Omega(c)$ is the set of sieves on $c$, so the ambient classifier is finite-valued exactly when there are finitely many sieves on each object. For finite-valued $F,G$,

so the ambient exponential is finite-valued exactly when these sets are finite for every $c$.

These criteria describe when the ambient constructions stay in the finite-valued subcategory. They are not, without an additional argument, a necessary-and-sufficient classification of when that subcategory has its own classifier and exponentials.

Remaining question and next step

Find a general criterion beyond essentially finite slices. For a proposed criterion, distinguish closure under the ambient presheaf constructions from existence of the required universal objects inside the finite-valued category.

Note 8 records the right Kan extension approach. Its first missing ingredient is the precise adjunction or comonad that would implement the reduction.

Source

Original problem 6.0.1.

The earlier problem list records the name “Higgs Prime conjecture” but does not state the conjecture. No precise claim or proof is specified here.

The next step is to recover the intended statement and its connection to riegs from the original source before using this item as a research problem or a result.

Sources: original problem 7.0.4; Higgs prime. The latter identifies the terminology, not the missing conjecture.

The aim is to develop the theory of semirings with exponentiation across four subjects: logic, finite and profinite arithmetic, enumerative combinatorics, and category theory.

The central object is a rieg: a commutative semiring with an exponentiation operation satisfying the exponent laws, with the convention $0^0=1$.

The concrete questions in this project are:

• Rational subrieg of the nonnegative reals: determine the relations introduced by exponentiation.
• Free rieg elements as games: find a game interpretation compatible with the rieg operations and evaluation at zero.
• Unary functions represented by terms: characterize the functions on natural numbers obtained from a free rieg.
• Connected compact Hausdorff riegs: answered positively by the unit interval with $\max$, $\min$ and $x^y=\max(x,1-y)$; by the compact no-go theorem every example has noncancellative addition.
• Finite-valued presheaf categories: identify when categorical counting has the topos structure motivating Burnside riegs.

The target is a single mathematical account that states the definitions and examples precisely and separates established results from these remaining questions. The proposed title is Notes on Rieg theory: semiring with exponentials in logic, profinite arithmetic, enumerative combinatorics, and category theory.

Absorbed into Finite presheaf topoi. The left exact comonad can be taken to be $X\mapsto X_{\mathrm{fin}}$, the coreflection onto locally finite presheaves (elements generating finite-valued subpresheaves). Every map from a finite presheaf factors through it, so the subobject classifier and the exponentials of $\mathbf{fPSh}(\mathcal C)$, when they exist, are $\Omega_{\mathrm{fin}}$ and $(G^F)_{\mathrm{fin}}$; the resulting criterion is in the resolution of that note. Not yet verified by a human.

Aim

Find a criterion for $[\mathcal C^{\mathrm{op}},\mathbf{FinSet}]$ to be an elementary topos or locally cartesian closed, as asked in Finite presheaf topoi.

Proposed approach

Use a left-exact comonad to reduce the question to existence of suitable right Kan extensions. The motivating idea is to understand which indexing categories have limits for every finite-set-valued diagram, then impose corresponding conditions on comma categories.

This is an approach to formulate, not an established reduction. A particular comonad and adjunction have not yet been specified. In particular, no right adjoint to the inclusion of finite-valued presheaves into all presheaves is assumed here.

Next step

Specify the categories, functors, and adjunction involved. Write the proposed right Kan extension pointwise as a limit, then prove both its finiteness and the implication for exponentials or the subobject classifier. Compare the resulting condition with the existing sufficient condition that every slice $\mathcal C/c$ is essentially finite.

The underlying finite-presheaf question was discussed with Jérémie Marquès.

Theorem

Let $R$ be a compact Hausdorff topological rieg. If its additive commutative monoid is cancellative, then $R$ has one element. Connectedness is not required.

Lemma

Every compact Hausdorff commutative cancellative topological monoid $(S,+,0)$ is a group.

Proof. First, every nonempty compact Hausdorff commutative topological semigroup has an idempotent. By compactness and Zorn's lemma, choose a minimal nonempty closed subsemigroup $K$. For $a\in K$, the set $a+K$ is a nonempty closed subsemigroup (using commutativity), hence equals $K$. Thus

is a nonempty closed subsemigroup and equals $K$. In particular, $a+a=a$.

For $s\in S$, the closure of $\{ns:n\geq1\}$ is a compact commutative subsemigroup and contains an idempotent $e$. Cancellativity applied to $e+e=e+0$ gives $e=0$. Choose a net $n_i s\to0$. A subnet of $(n_i-1)s$ converges to some $t$, and continuity gives $s+t=0$. Every element therefore has an additive inverse. $\square$

Proof of the theorem

The lemma gives an additive inverse $-1$ of $1$, and a rieg containing an additive inverse of $1$ is degenerate (Notes on Rieg Theory, Claim 2.3.1: $1=0^0=0^{1+(-1)}=0^1\,0^{-1}=0$). $\square$

What remains

This settles the cancellative case of the connected compact Hausdorff problem. The noncancellative case has a positive answer: the unit interval with $\max$, $\min$ and $x^y=\max(x,1-y)$ is a nontrivial connected compact Hausdorff rieg (Connected compact Hausdorff riegs).