In mathematical logic, a Gödel numbering is a function that assigns to each symbol and well-formed formula of some formal language a unique natural number, called its Gödel number. The concept was used by Kurt Gödel for the proof of his incompleteness theorems. (Gödel 1931)

The natural numbers, N, form a commutative monoid under addition (identity element zero), or multiplication (identity element one). A submonoid of N under addition is called a numerical monoid. The positive integers, N ∖ {0}, form a commutative monoid under multiplication (identity element one).

The set of integers Z forms a commutative ring under addition and multiplication

What happens if I replace a unique natural number that form a commutative Monoid with the set of integers Z that form a commutative Ring ?

The more specific question should be: What happens if I use (not if I replace) a unique natural number that form a commutative Monoid as (not with) the set of integers Z that form a commutative Ring ?

Monoid $\Rightarrow$ Ring

P.S: I don't want replace formally but I do not want to really change, but to make it believe that it is as if I had replaced.


closed as unclear what you're asking by Andreas Blass, Neil Strickland, Andrés E. Caicedo, Eric Wofsey, Noah Schweber Jan 2 at 18:01

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ All uses of Gödel numbering that I'm aware of (in particular its use in the incompleteness theorems) use far more than the commutative monoid structure of $\mathbb N$. Usually, one begins with the commutative semiring structure (i.e., one begins with addition and multiplication) and defines more complicated operations and predicates in terms of these. $\endgroup$ – Andreas Blass Jan 2 at 15:33
  • $\begingroup$ Sorry, begins with the commutative semiring structure and go to Monoidal structure only or also you can begins from monoidal structure and go to commutative ring structure ? Why you should start from a higher structure only and go down to the lower one then ? Can you start from lower and go to higher ? $\endgroup$ – Peter Long Jan 2 at 15:40
  • 2
    $\begingroup$ Who (other than you) goes to the lower, monoidal structure on $\mathbb N$, in the context of Gödel numbering? $\endgroup$ – Andreas Blass Jan 2 at 15:42
  • $\begingroup$ But can we do it ? Is possible to go in the context of Gödel numbering, go down towards to the monoidal structure and then go up again? Because my goal is to get down to the monoidal structure in order "to go back" from there to up the commutative semiring structure again $\endgroup$ – Peter Long Jan 2 at 16:23
  • 3
    $\begingroup$ @PeterLong I can't tell what you're getting at at all here, and to be honest I don't think you can either. My comments re: several of your math.stackexchange questions apply here as well: can you clearly and precisely state the issues you see, rather than just throwing out complicated phrases? There may be a good question here (although, more appropriate for MSE) but as currently phrased it is too unclear to admit an answer (given that you don't find Joel's answer satisfactory for some reason). $\endgroup$ – Noah Schweber Jan 2 at 18:07

The purpose of Gödel coding is the process of arithmetization, by which syntactic or other combinatorial ideas that are not directly expressible in arithmetic can be simulated by a process of faithful representation. The point is that in our arithmetic theories, we are entitled to refer to concepts such as formulas and proofs and so on, by means of the Gödel codes.

Meanwhile, the structure of the natural numbers $\langle\mathbb{N},+,\cdot,0,1\rangle$ is bi-interpretable with the structure of the integers $\langle\mathbb{Z},+,\cdot,0,1\rangle$, in the sense that each of these structures can define a copy of the other, in such a way that it can also definably see how it is translated into the others. Namely, the natural numbers $\mathbb{N}$ are the sums-of-four-squares in $\mathbb{Z}$, and there are diverse ways to define a copy of $\mathbb{Z}$ inside $\mathbb{N}$.

So although it is traditional to take the Peano axioms PA as an axiomatization of the natural numbers $\mathbb{N}$, one can translate the axioms to make a equivalent corresponding axiomatization of $\mathbb{Z}$.

In this sense, it doesn't matter whether you use natural numbers or integers in the Gödel coding; doing so will achiever the same ends in the end. There is essentially no fundamental difference in the ideas and methods.

  • $\begingroup$ mm.. but this not depend by how you can use this informations for moving through this context ? For example: the set of integers with respect to subtraction is not a group but a quasi-group, $+$ is associative and $−$ is not. With $+$ we even have a group. There is essentially no fundamental difference , yes, because informations are always the same but not the purpose for which you can use that information. $\endgroup$ – Peter Long Jan 2 at 15:35
  • $\begingroup$ it doesn't matter whether you use natural numbers or integers in the Gödel coding There is something that I do not understand yet, but it is not tied to what you wrote, but for how, what you wrote could be used. $\endgroup$ – Peter Long Jan 2 at 15:35
  • 3
    $\begingroup$ The point of my answer is not that the structures are the same, but rather that they have the same capacity to be used for arithmetization, which is all the matters for Gödelization (as mentioned also by Andreas Blass in his comment), because they can be interpreted in each other. $\endgroup$ – Joel David Hamkins Jan 2 at 15:42
  • $\begingroup$ that they have the same capacity to be used for arithmetization But I know that for example, godelization can be used to 'convert' vectors into scalars like here For example, what happens if you can convert velocity (vector quantity) into speed (scalar quantity) ? Something does not come back because it seems that a concrete physical limit can be overcome if you use 'godelization', for example $\endgroup$ – Peter Long Jan 2 at 16:35
  • $\begingroup$ and then you do not overcome anything that is 'physically' because the physical problem seems only a mathematical coding problem, not only a real "physical" problem but just an apparent physical query. To represent a vector quantity in a scalar quantity does not involve reaching the limit that was previously said to be 'physical'? $\endgroup$ – Peter Long Jan 2 at 16:36

Suppose you were trying a similar attempt of arithmetization, but you decided to do so for Presburger arithmetic. Well, there would be a couple of problems. The first is that you have only addition, so that your possibilities for encoding are limited, and it would be challenging to find a unique code for every statement, AND be able to refer to this code inside the theory. The second is that Presburger arithmetic is decidable, so you cannot get an incompleteness result like that of Goedel: you can tell which statements are true of the (additive) monoid of the natural numbers.

The reason Goedel chose (the semiring of) natural numbers is because the theory he was working with had as a model the natural numbers with multiplication and addition. If you chose to axiomatize properties of another structure such as a commutative ring, you could try to use the language to code statements by members of the structure, but you could not necessarily get the results Goedel did; it depends on whether the theory of the structure is (inherently? I forget the technical adjective) undecidable.

Gerhard "The Other Hand Has Fingers" Paseman, 2019.01.02.

  • $\begingroup$ To answer the question in the title, it is not clear to me how to use an element as a structure. Since you are talking of codes as in Goedel arithmetization, it sounds like you want to represent (statements about members of a structure) by (entities which are placeholders for such members) in order to talk about proving such statements inside the theory. I do not see how you would do the replacement or what you could do after that. Gerhard "Give Me A Reason Why" Paseman, 2019.01.02. $\endgroup$ – Gerhard Paseman Jan 2 at 17:54
  • $\begingroup$ You say had as a model the natural numbers with multiplication and addition, but what happens if I choose as model if I use $-$ and $+$ operations (a quasi-group structure), I want to choose integers numbers not natural numbers $\endgroup$ – Peter Long Jan 2 at 19:36
  • $\begingroup$ You can, but now the axioms are different. You do not have 0 as least element any more. Gerhard "Other Things May Change Too" Paseman, 2019.01.02. $\endgroup$ – Gerhard Paseman Jan 2 at 20:01
  • 3
    $\begingroup$ Your goal is unclear, as is your question. If you said that you wanted to expand arithmetization by looking at other structures, and that you wanted to get an incompleteness result, you might look at structures whose elementary theories are undecidable. You do not say that though, so we the answerers are left to guess. Gerhard "MathOverflow Doesn't Like Arbitrary Guessing" Paseman, 2019.01.02. $\endgroup$ – Gerhard Paseman Jan 2 at 22:11
  • 2
    $\begingroup$ Goedels result makes sense because it talks about theories. It helps to have the elementary theory of the natural numbers, because that is an undecidable set, but there are other routes to it, developed after the 1931 result. If your goal is to do away with the natural numbers, starting with a theory that talks about the natural numbers seems a poor choice to me. Gerhard "Still Not Sure Of Goal" Paseman, 2019.01.02. $\endgroup$ – Gerhard Paseman Jan 2 at 22:45

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