Natural numbers are defined inductively https://softwarefoundations.cis.upenn.edu/lf-current/Basics.html#lab30 as s(s(...s(0)...)).

Such definition is nothing special, especially when one can observe how rich and useful and widely used theory (arithmetics) emerge from such simple notion. But are there more general natural numbers, e.g. defined by some kind of additional functions (e.g. s(t(s(t(s(0)))))) or a(a(0, 0))...)?

Maybe such generalized numbers can be used for the enumeration of the lambda terms (or software programs in some kind of formal language). And such enumeration can help for program synthesis, e.g. article https://arxiv.org/pdf/1804.02477.pdf considers the program synthesis (finding one program, optimal in some kind of sense) as the non-smooth optimization/search problem over the space of all syntactically correct terms (programs) into some language.

Maybe generalized numberings (of combinatorial structures) can help in such tasks and enable the construction of optimization theory for such kind of problems. See https://en.wikipedia.org/wiki/Structured_prediction with some other approach of finding the symbolic/combinatorial element that is optimal in some kind.

I have found article https://arxiv.org/abs/1910.07750 which has the notion of numbering, but I am not sure whether it is the thing I am speaking in my question. Or maybe notions of lattice (partially ordered sets) is the one I am seeking?

  • 1
    $\begingroup$ There are other concepts defined inductively, yes. One common example would be regular expressions, you can actually apply induction for proofs on them. If there are similar sets that are also treated as numbers I don't know though; except of course integers, but I'm sure you already considered these. $\endgroup$ – Dirk Jan 27 at 10:14
  • $\begingroup$ I guess - there is no such notions as "arithmethic" or "analysis" for such more complex inductive structures (like strings generated from some grammar, etc.) or maybe - there is? $\endgroup$ – TomR Jan 27 at 10:22
  • 1
    $\begingroup$ The Peano axioms can be stated succinctly as thus: the non-negative integers comprise (i) a discretely ordered semiring (ii) subject to the axiom schema of induction (see e.g. here). This can be a springboard to generalizations, e.g. you might consider anything satisfying (i) to generalize the non-negative integers. $\endgroup$ – J.G. Jan 27 at 10:34
  • $\begingroup$ I am not an expert in this field, but you could read about ordinal numbers and cardinal numbers. Ordinal numbers are a generalisation of the natural numbers. $\endgroup$ – 3nondatur Jan 28 at 10:32
  • 1
    $\begingroup$ You might want to look at An extended arithmetic by Garrett Birkhoff [Duke Mathematical Journal 3 #2 (June 1937), pp. 311-316]. I don't think there is a freely available digital copy on the internet (my copy is actually a photocopy from a library bound volume), so if you don't have access to a copy of the paper, maybe these google references to the paper could be of use to you. $\endgroup$ – Dave L. Renfro Jan 28 at 11:57

A possible generalization of the natural numbers is the free monoid $A^*$ on an alphabet $A$ (if $A$ is a one-letter alphabet, you recover the natural numbers). You can generate the elements of $A^*$ starting from the empty word $1$ by using $|A|$ successor functions. For instance, if $A = \{a,b\}$, use $S_a$ and $S_b$,the functions defined by $S_a(u) = ua$ and $S_b(u) = ub$.

To answer your remark, there is still some specific analysis in the free monoid (see this paper for a nontrivial example), but nothing comparable to the natural numbers.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.