Direct construction of the integers - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T15:29:43Z http://mathoverflow.net/feeds/question/29090 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/29090/direct-construction-of-the-integers Direct construction of the integers Jacques Carette 2010-06-22T14:01:59Z 2011-11-09T22:33:15Z <p>Is there a direct construction of the integers which does not involve taking any quotients? I am of course aware of the <a href="http://en.wikipedia.org/wiki/Integer#Construction" rel="nofollow">usual construction</a>. I am also aware of the nice <a href="http://mathoverflow.net/questions/23193/axiomatic-definition-of-integers" rel="nofollow">axiomatic characterization</a> of the integers.</p> <p>I am most interested in a <strong>direct</strong> 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).</p> <p>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?</p> http://mathoverflow.net/questions/29090/direct-construction-of-the-integers/80212#80212 Answer by lii for Direct construction of the integers lii 2011-11-06T13:28:28Z 2011-11-06T13:28:28Z <p>There is a paper here <a href="http://www.denison.edu/academics/departments/mathcs/fressola_paper.pdf" rel="nofollow">http://www.denison.edu/academics/departments/mathcs/fressola_paper.pdf</a> that seems to do what you want to achieve.</p> http://mathoverflow.net/questions/29090/direct-construction-of-the-integers/80221#80221 Answer by Valerio Capraro for Direct construction of the integers Valerio Capraro 2011-11-06T16:18:05Z 2011-11-06T16:26:18Z <p>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:</p> <ol> <li>There is no $n$ such that $0=succ(n)$</li> <li>$succ(n)=succ(m)$ implies $n=m$</li> <li>If $0\in A$ and $succ(n)\in A$ for all $n\in A$, then $A=\mathbb N$</li> </ol> <p>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</p> <p><strong>Induction on $\mathbb Z$:</strong> 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$.</p> <p>Should work.</p> http://mathoverflow.net/questions/29090/direct-construction-of-the-integers/80292#80292 Answer by S. Carnahan for Direct construction of the integers S. Carnahan 2011-11-07T11:27:21Z 2011-11-07T11:27:21Z <p>You could try <a href="http://en.wikipedia.org/wiki/Negative_base" rel="nofollow">base -2 representations</a>, also called negabinary strings. These are finite strings drawn from the alphabet <code>$\{ 0, 1\}$</code>, 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.</p> http://mathoverflow.net/questions/29090/direct-construction-of-the-integers/80296#80296 Answer by Leo Alonso for Direct construction of the integers Leo Alonso 2011-11-07T11:38:10Z 2011-11-08T10:45:17Z <p>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.</p> <p><strong>Addendum</strong>: Prompted by the comment below, I am not thinking about the usual <em>description</em> of the free group through a chain of $1$'s and $-1$'s but on the <em>universal property</em>.</p> <p>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.</p> <p><strong>Addendum 2</strong>: I have just realized that this way the description is second-order.</p> http://mathoverflow.net/questions/29090/direct-construction-of-the-integers/80315#80315 Answer by David Milovich for Direct construction of the integers David Milovich 2011-11-07T17:16:19Z 2011-11-09T22:33:15Z <p>Informally speaking, taking the limit of <a href="http://en.wikipedia.org/wiki/Two%27s_complement" rel="nofollow">two's complement</a> 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, <em>i.e.,</em> $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\}$).</p> <p>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.</p> <p><strong>Update:</strong> I couldn't resist the temptation to write a <a href="http://codepad.org/BfuzCK5B" rel="nofollow">functional programming implementation</a>.</p>