Functions ℕ→ℕ from F1

hora v5 · 30 Oct 2026 Public

AI-assisted (Codex) · Verification (self-reported): Not confirmed

Answer proposed

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

Characterize the functions obtained by this evaluation.
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.

Connections

Related: Rieg theory: the research programme

⋯

Export (PDF, Markdown, citation)

App did not open?

Enable SUMIRE in your conversation. If the request is not filled in, paste the copied request. If the app does not open, install it or use its website.

ChatGPT · Claude · Connect your AI

Request

Read this note through the SUMIRE connector so we can discuss it: https://sumire.aiformath.jp/p/2609.00007/n/4
Use get_note(project_id="2609.00007", number=4). If SUMIRE is not enabled in this conversation, ask me to enable it. Do not make changes.