Direct construction of the integers

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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}$.

Answer 4

(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...

Answer 5

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

Answer 6

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.

Answer 7

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.

Answer 8

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.

Answer 9

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$