2
$\begingroup$

Peano Arithmetic (PA) models have a prime number structure and commutativity of addition and multiplication. Presburger arithmetic (PrA) models of arithmetic have addition without multiplication and without a prime number structure. However, as I understand it, when we add the axiom of induction and the multiplication relation to PrA, we get a model of the multiplicative natural numbers from which commutativity follows, as in PA.

My question is whether induction plus multiplication implies a prime structure with commutativity, or if there is a model of arithmetic which has a prime number structure and is not commutative? Does the definition of "prime" rely on the commutativity of multiplication of natural numbers?

Improve this question
$\endgroup$
4
  • 7
    $\begingroup$ I don’t understand the question. You wrote yourself that arithmetic with multiplication and induction implies commutativity, hence it has no non-commutative model. And what is “prime number structure” supposed to mean? $\endgroup$
    – Emil Jeřábek
    Commented Mar 27, 2013 at 12:05
  • 4
    $\begingroup$ I realized you might mean an arithmetic with only multiplication, but no addition. But then the question is as unclear as before: (1) How do you formulate induction using multiplication? The usual statement requires successor. (2) What are other axioms of the theory besides induction? The usual axioms of Robinson’s arithmetic are not applicable, as they explain multiplication in terms of addition. (3) If successor is included in the language: in standard natural numbers, $+$ is definable in terms of $\cdot$ and successor (if $c\ne0$, then $a+b=c$ if and only if $S(ac)S(bc)=S(S(ab)c^2)$). ... $\endgroup$
    – Emil Jeřábek
    Commented Mar 27, 2013 at 13:08
  • 3
    $\begingroup$ ... I would expect any reasonable axiomatization of arithmetic with successor, multiplication, and induction to prove the basic properties of addition defined using this formula, in which case it becomes a notational variant of Peano arithmetic. In any case, you need to reformulate the question in a clear, coherent, and unambiguous way. $\endgroup$
    – Emil Jeřábek
    Commented Mar 27, 2013 at 13:11
  • 1
    $\begingroup$ I was thinking there might be a system where every number has a unique prime decomposition, but is nevertheless non-commutative in general. Maybe I'd have to give up full induction. Sorry for the fuzzy question, it is a fuzzy idea. The question came up because I was thinking about building the numbers with blocks by stacking using multiplication and 3*1 looks so different from 1*3. $\endgroup$
    – user10290
    Commented Mar 28, 2013 at 12:20

2 Answers 2

Reset to default
2
$\begingroup$

Commutativity is not necessary for the notion of primes. For instance, consider the Hurwitz integers, namely quaternions whose components are either all integers or all half-integers:

$$ H = \{ a + bi + cj + dk : (a, b, c, d) \in \mathbb{Z}^4 \cup (\mathbb{Z} + \frac{1}{2})^4 \} $$

These form a non-commutative ring. Moreover, there is a version of unique factorisation discussed here:

http://www.m-hikari.com/imf/imf-2012/41-44-2012/perngIMF41-44-2012.pdf

A factorisation of a non-zero Hurwitz integer into irreducibles is unique up to applying operations known as unit-migration, recombination, and meta-commutation.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ This is an excellent example. Worth noting, perhaps: John Conway and Derek Smith also talk about factorizations in the quaternions (and the octonions) in On Quaternions and Octonions : amazon.com/dp/1568811349 $\endgroup$
    – Steven Stadnicki
    Commented Dec 2, 2016 at 18:58
1
$\begingroup$

Yes, I believe there are.

I believe I came across such system in my research.

First you take the zero out of natural numbers and try to work with the remaining numbers in a system where no number is left unrepresented. To do so you do a displacement: 1 represents 0, 2 represents 1 and so on.

You can check the introduction of the idea here (it is just the introduction): " https://repositorioaberto.uab.pt/bitstream/10400.2/1292/1/p_50_58.%20pdf.pdf "

In such system, addition is different because 1 is the neutral element of addition:

2++1=2

a++1=a

And generally

a++b=a+b-1

Multiplication is therefore not commutative, because for example

2**3=3++3=5

3**2=2++2++2=(2++2)++2=3++2=4

And generally

a**b=a*b-(a-1)

But prime numbers remain the structure of this system

The new primes are simply

new prime=old prime+1

Since there is a correspondence between normal arithmetics and this system (which I have checked), the prime structure holds

There is no way to decompose a new prime other than right multiplication by two of its natural antecessor:

For example the new prime 8 can be obtained by

7**2=8 But multiplication by two on the right is just a sort of application of the neutral element of mutiplication displaced for the new system, the equivalent of adding one unit: 7++2=8

This should not therefore be considered a "legal" multiplication for the purpose of prime identification.

Therefore primes remain primes in this non-commutative arithmetic.

I am sorry if this does not sound very rigorous. Later I can eventually provide more details and proofs. Now I am finishing a project on my daytime job.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Thanks Fernando, in your system does each number have a unique prime decomposition? I see 5 = 2**3, and is this the only way to decompose 5? $\endgroup$
    – user10290
    Commented Mar 28, 2013 at 12:02
  • $\begingroup$ Interesting question. No, it does not. Factorize for example 6=2*3=3*2 (in our system). In the new system the factorizations are: 2*3 transforms into 24=7 3*2 transforms into 33=7 These are two prime factorizations for the same number. However, for practical purposes, it is always possible to choose as "unique" the factorization that orders primes in descendent order (this is what I do to uniquely represent numbers from their factors in another number system that I build upon this one) Therefore we would have 6=3*2 leading to 7=3**3. $\endgroup$
    – Fernando Pimentel
    Commented Mar 28, 2013 at 16:23

You must log in to answer this question.