17
$\begingroup$

Question. Is there a direct construction of the integers which does not involve taking any quotients?

I am of course aware of the usual construction. I am also aware of the nice axiomatic characterization of the integers.

I am most interested in a direct construction. I am sure that one could probably use a disjoint union of $\mathbb{N}$ and $\mathbb{N}^{+}$ to construct $\mathbb{Z}$. But this involves 2 intermediate constructions (as well as dealing with cases).

Edit. By "direct construction", I mean something like the Peano construction for $\mathbb{N}$, seen as the inductive type built from $0$ and $\mathit{succ}$. Then one also constructs the operations of addition, multiplication, etc. Another way to think of it: suppose you wanted to have a datatype of "integers" in a lambda calculus which only allows inductive constructions and no quotients, how would you do it?

$\endgroup$
22
  • 2
    $\begingroup$ The free group on one generator? Or do you want to define multiplication, as well? Maybe you should provide an example of a "direct" construction of something else to show what you have in mind. $\endgroup$ Jun 22, 2010 at 14:13
  • 8
    $\begingroup$ Strings of symbols, from a three-letter alphabet (representing digits 0, 1, -1; thought of as base 3 expansions). All but finitely many digits must be zero. Define operations essentially as in grade-school. Is that what you want for "direct"? I took balanced ternary, since you don't want to start with positive integers... $\endgroup$ Jun 22, 2010 at 14:18
  • 7
    $\begingroup$ 0 (zero), S (successor) , P (predecessor) Add the axioms PS(x)=SP(x)=x. $\endgroup$
    – Kaveh
    Aug 1, 2010 at 7:33
  • 7
    $\begingroup$ Could you explain your motivation? Are you trying to get an efficient implementation of the integers, or something that works well in a proof assistant, or something that is mathematically elegant, or what? $\endgroup$ Nov 7, 2011 at 14:17
  • 2
    $\begingroup$ Maybe god gave us the natural numbers and forced us to do some work to get the integers? $\endgroup$ Aug 18, 2013 at 1:14

9 Answers 9

15
$\begingroup$

Informally speaking, taking the limit of two's complement as the number of bits goes to $\infty$, the integers are just the eventually constant binary sequences (which are naturally represented by finite binary sequences). For this to work, said sequences must start with the least significant bit, i.e., $1001011\overline{0}$ is interpreted as $2^0+2^3+2^5+2^6$ and $1001010\overline{1}$ is interpreted as $2^0+2^3+2^5-2^7$. The arithmetic and ordering of these strings is natural (and efficient for microprocessors when we restrict from $\mathbb{Z}$ to, say, $\{-2^{63},\ldots,2^{63}-1\}$).

The above can be reinterpreted as the following less direct construction. If $R$ is the inverse limit of rings $\lim_{\infty\leftarrow n}\mathbb{Z}/2^n\mathbb{Z}$, then the diagonal map $\Delta\colon\mathbb{Z}\rightarrow R$ given by $m\mapsto \lim_{\infty\leftarrow n}(m\mod 2^n)$ is an injective ring homomorphism. [Edit: The image is characterized as the set of $\vec x\in R$ for which the truth value of $x(n+1)=x(n)$ is eventually constant.] Moreover, the ordering of $\mathbb{Z}$ is coded via $m\geq 0\Leftrightarrow(m\mod 2^n: n\in\mathbb{N})$ is eventually constant.

Update: I couldn't resist the temptation to write a functional programming implementation.

$\endgroup$
13
$\begingroup$

You could try base -2 representations, also called negabinary strings. These are finite strings drawn from the alphabet $\{ 0, 1\}$, starting with 1 (except when zero or empty, depending on your choice of convention), where we weight places by powers of $-2$. You have unique representations, and reasonably straightforward arithmetic operations.

$\endgroup$
3
$\begingroup$

The group $\mathbf{Z}$ is the group of differences of the monoid $\mathbf{N}$, and the ring $\mathbf{Z}$ is the ring of endomorphisms of the (commutative) group $\mathbf{Z}$.

$\endgroup$
3
  • $\begingroup$ This is the usual construction, right? $\endgroup$ Aug 16, 2013 at 14:49
  • 3
    $\begingroup$ What's a "group of differences"? The obvious constructions require a quotient. $\endgroup$ Aug 16, 2013 at 15:29
  • 1
    $\begingroup$ Where "quotient" involves "equivalence" rather than a "division" :-) $\endgroup$ Aug 18, 2013 at 4:21
3
$\begingroup$

(was a comment, now an answer)...

Strings of symbols, from a three-letter alphabet (representing digits 0, 1, -1; thought of as base 3 expansions). All but finitely many digits must be zero. Define operations essentially as in grade-school. Is that what you want for "direct"? I took balanced ternary, since you don't want to start with positive integers...

$\endgroup$
3
$\begingroup$

There is a paper by Fressola and Krone here Integer Construction by Induction that seems to do what you want to achieve.

$\endgroup$
1
  • $\begingroup$ It definitely answers the question that I asked. I guess I really wanted to ask for the result to have a more natural ordering. More like balanced ternary. $\endgroup$ Nov 6, 2011 at 13:43
2
$\begingroup$

Is it not enough to modify Peano's construction? An idea (which is different from the onw linked by Iii) might be the following: Peano's construction makes use a function $succ(n)$ which verify the classical properties:

  1. There is no $n$ such that $0=succ(n)$
  2. $succ(n)=succ(m)$ implies $n=m$
  3. If $0\in A$ and $succ(n)\in A$ for all $n\in A$, then $A=\mathbb N$

Maybe it is possible characterize $\mathbb Z$ making use of two (different) functions, $prec(\cdot)$ and $succ(\cdot)$, related by $prec(succ(n))=succ(prec(n))=n$. Of course, now the first property cannot be true, the second property above has to be required for both $prec$ and $succ$ and, finally, the third property has to be replaced with the following

Induction on $\mathbb Z$: If $A\subseteq Z$ contains at least one element and, moreover, for any $a\in A$ one has $prec(a),succ(a)\in A$, then $A=\mathbb Z$.

Should work.

$\endgroup$
3
  • 7
    $\begingroup$ This seems to be the same as what Kaveh suggested in a comment on the question. The OP objected there that the axiom prec(succ(n)) = succ(prec(n)) = n induces a quotient. That is, the integers will not be simply the terms built from succ, pred, and 0 but rather equivalence classes of such terms. $\endgroup$ Nov 6, 2011 at 23:38
  • 1
    $\begingroup$ Andreas is correct: I was looking for a quotient-free construction. And axioms 1-3 above are really another way of stating Goguen's "no junk, no confusion" axioms. $\endgroup$ Nov 7, 2011 at 0:40
  • $\begingroup$ OK, sorry, I missed that comment. $\endgroup$ Nov 7, 2011 at 7:08
2
$\begingroup$

I would say: the free group on one element. I guess you can translate this into a series of first-order axioms. Notice that multiplication comes for free as composition between automorphisms of the group with itself.

Addendum: Prompted by the comment below, I am not thinking about the usual description of the free group through a chain of $1$'s and $-1$'s but on the universal property.

Let me give some specifics. A group is a tuple $(G,m,e,i)$ with $G$ a set, $m \colon G \times G \to G$ a map $e \in G$ and $i \colon G \to G$ satisfying certain commutativities that amount to the defining properties of group (associativity, $e$ is the neutral element and $i(g)$ is the inverse of the element $g \in G$). A free group in one element is such a tuple $(F, \dot , 1, op)$ satisfying that for any choice of a $g \in G$ from a group $(G,m,e,i)$ there is one and only one homomorphism $(F, \dot , 1, op) \to (G,m,e,i)$ taking $1$ to $g$. I propose to translate this description into a series of first order formulas, that was my suggestion.

Addendum 2: I have just realized that this way the description is second-order.

$\endgroup$
2
  • 1
    $\begingroup$ But this still has quotients (eg $xy^{-1}y=x$) which is what the OP was trying to avoid. $\endgroup$ Nov 7, 2011 at 13:45
  • $\begingroup$ @Richard Rast. Thanks for your comment. I didn't notice the first comment in the question either. However I wonder if there is a description of the free group that does not go through a quotient, something using the universal property. $\endgroup$
    – Leo Alonso
    Nov 7, 2011 at 15:57
1
$\begingroup$

I provided a direct axiomatization of integers for instance under the MO question Axiomatic definition... by @Victor Makarov, in the post Part 2: Cyclands and integers. This axiomatization makes no direct reference to the natural numbers, or to any linear order.

$\endgroup$
3
  • 2
    $\begingroup$ Gerald Edgar already mentioned balanced ternary in a comment attached to the question. $\endgroup$
    – S. Carnahan
    Aug 18, 2013 at 1:40
  • $\begingroup$ @S.Carnahan, thank you for pointing to Gerald Edgar and his $(-1\ 0\ 1)$ construction. Sorry for overlooking it at the time. $\endgroup$ Aug 18, 2013 at 4:04
  • $\begingroup$ The $(-1\ 0\ 1)$ portion of my question got removed by me, it got replaced by the original answer by Gerald Edgar (got copied by him from his own earlier comment). $\endgroup$ Aug 19, 2013 at 2:03
0
$\begingroup$

We define a [formal language][1] as follows:

The free language $\mathcal J$ of all strings $J$ (words) in

alphabet : $R, L$

including the empty string, [].

This language comes naturally equipped with the concatenation operation,

$\tag 1 +: (J,J^{'}) \mapsto JJ^{'}$.

A string $M \text{ in } \mathcal J$ is said to be direct (or pure) if it does not contain both of the letters $R$ and $L$.

The strings $RL$ and $LR$ in $\mathcal J$ are called vis-à-vis steps.

If a vis-à-vis step is inserted anywhere into a string $J$, then the new output string is said to be an expansion of $J$.

If a vis-à-vis step can be removed from a string $J$, then the new output string is said to be a contraction of $J$.

Any string can be contracted to a direct string and can itself be obtained by expanding that same direct string. Two strings $J$ and $J^{'}$ are said to be homoJnic if $J$ can be be transformed into $J^{'}$ using expansions and contractions. When this is the case we can write $J == J^{'}$.

If $J_\alpha == J_\beta$ and ${J_\alpha}^{'} == {J_\beta}^{'}$ then $J_\alpha {J_\alpha}^{'} == J_\beta {J_\beta}^{'}$.

The addition of integers $\mathbb Z$ can therefore be defined as concatenation that is invariant under homoJnic transformations, each class being represented by a direct strings in $\mathcal J$.

Example: Adding two direct $RRRRR + LL = RRRRRLL == RRRRL == RRR$

Example: Since $RRRRR == RRLRRRR$ and $LL == RLLL$, we have
$\qquad RRLRRRR + RLLL = RRLRRRRRLLL == RRR$

$\endgroup$
3
  • $\begingroup$ It seems to me that the need constantly to perform contraction steps in order to do anything with these integers suggests that we are dealing with a quotient (of strings by the "homoJnicity" relation) in all but name. $\endgroup$
    – LSpice
    Nov 28, 2017 at 17:57
  • $\begingroup$ (Specifically, see also mathoverflow.net/questions/29090/… and mathoverflow.net/a/80221/2383.) $\endgroup$
    – LSpice
    Nov 28, 2017 at 17:59
  • $\begingroup$ @LSpice I wrote this up with the idea that a computer might understand it as constructive 'homotopy' math, and wouldn't have to understand set theory and partitions. I'm not a computer scientist - just taking a shot at it! $\endgroup$ Nov 28, 2017 at 18:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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