I am studying proofs and logic in mathematics. One problem that I would like to complete is to prove that $1/2$ is not an integer. The problem is a bit open ended, so I need to wrap my head around this.
From this it would seem that one would need a definition of an integer and then show that $1/2$ doesn't meet this definition. So I need a definition of integer and my questions is:
What is a common definition of the integers?
According to Wikipedia, and integer is "a number that can be written without a fractional component." but I am guessing that there is a more precise definition. I would guess that the definition of the rational numbers comes after the integers. Is that right? So I would also need a definition of rational number.
$\endgroup$ 66 Answers
$\begingroup$As many have pointed out, much depends on how you define things, but using the well known Peano Axioms as a basis, here is a formal proof that $\frac{1}{2}$ is not a natural number (I know, that's not quite the same as it not being an integer, but I just wanted to give you some idea as to how to do this formally ... besides, if it is not a natural number, then the only way it could still be an integer is for it to be negative, which you can probably easily rule out when actually formalizing all integers). I defined $\frac{1}{2}$ as that object that, when added to itself, results in $1$ (which is $s(0)$ (the successor of $0$) in Peano Arithmetic):
$\def\fitch#1#2{\begin{array}{|l}#1 \\ \hline #2\end{array}}$
$\fitch{ 1. \forall x \ \neg s(x) = 0 \quad PA1\\ 2. \forall x \forall y (s(x) = s(y) \rightarrow x = y) \quad PA2\\ 3. \forall x \ x + 0 = x \quad PA3\\ 4. \forall x \forall y \ x + s(y) = s(x + y) \quad PA4\\ 5. \forall x (\neg x = 0 \rightarrow \exists y \ x = s(y)) \quad Predecessor \ Lemma\\ 6. \forall x \forall y \ s(x) + y = s(x + y) \quad Lemma \ Addition \ Left \ Recursion }{ \fitch{ 7. \exists x \ x + x = s(0) \quad Assumption }{ \fitch{ 8. a + a = s(0) \quad Assumption}{ \fitch{ 9. a = 0 \quad Assumption}{ 10. 0 + 0 = s(0) \quad = \ Elim \ 6,7\\ 11. 0 + 0 = 0 \quad \forall \ Elim \ 3\\ 12. s(0) = 0 \quad = \ Elim \ 10,11\\ 13. \neg s(0) = 0 \quad \forall \ Elim \ 1\\ 14. \bot \quad \bot \ Intro \ 12,13 }\\ 15. \neg a = 0 \quad \neg \ Intro \ 9-14\\ 16. \neg a = 0 \rightarrow \exists y \ a = s(y)\quad \forall \ Elim \ 5\\ 17. \exists y \ a = s(y)\quad \rightarrow \ Elim \ 15,16\\ \fitch{ 18. a = s(b) \quad Assumption}{ 19. s(b) + s(b) = s(0) \quad = \ Elim \ 8,18\\ 20. s(b) + s(b) = s(s(b) + b) \quad \forall \ Elim \ 4\\ 21. s(s(b) + b) = s(0) \quad = \ Elim \ 19,20\\ 22. s(s(b) + b) = s(0) \rightarrow s(b) + b = 0 \quad \forall \ Elim \ 2\\ 23. s(b) + b = 0 \quad \rightarrow \ Elim \ 21,22\\ 24. s(b) + b = s(b + b) \quad \forall \ Elim \ 6\\ 25. s(b + b) = 0 \quad = \ Elim \ 23,24\\ 26. \neg s(b + b) = 0 \quad = \ Elim \ 1\\ 27. \bot \quad \bot \ Intro \ 25,26\\ }\\ 28. \bot \quad \exists \ Elim \ 17, 18-27 }\\ 29. \bot \quad \exists \ Elim \ 7, 8-28 }\\ 30. \neg \exists x \ x + x = s(0) \quad \neg \ Intro \ 7-29}$
$\endgroup$ 4 $\begingroup$Here is an outline of how one might try to attack the problem:
- Start with some basic set theory. At the very least, you will want to understand what an equivalence relation is.
- Next, define the natural numbers $\mathbb{N}$ axiomatically. You can build the naturals in a rather abstract way, but that probably isn't really necessary. We can define the naturals by the Peano Axioms, then deduce many of their important properties. Going through the details of the axioms, and actually proving the properties, would be a good exercise (which you could easily spend several weeks or months on, depending on how deeply you get into it, and how rigorous you want to be). As pbierre noted in another answer, the natural numbers encapsulate our intuitions about discreteness and counting. The Peano Axioms make this formal.
- Next, build the integers $\mathbb{Z}$. One way to get the integers from the naturals is to define an equivalence relation on $\mathbb{N}\times\mathbb{N}$ by saying that $(a,b) \sim (x,y)$ if $a+y = b+x$ (the idea is that the pair $(a,b)$ is equivalent to the integer $a-b$). In this setting, an integer is an equivalence class of ordered pairs of natural numbers, with respect to the above equivalence relation. One would then want to show that this collection of equivalence classes behaves like we would expect the integers to behave (i.e. do we have addition and multiplication that work correctly? do the natural numbers appear as a "subset" of the integers in some meaningful way? etc.). As an undergraduate, I learned this in a Moore-method style class, so I don't really have a good reference---you'll want to find something on "axiomatic set theory," maybe?
- With the integers in hand, it is now possible to build the rationals $\mathbb{Q}$. The construction is similar: a rational number is an equivalence class of ordered pairs of integers, where the equivalence relation is $(a,b) = (x,y)$ if $ay = bx$ (this should look reminiscent of the "cross-multiplication." Again, we want to first show that addition and multiplication work, then show that the integers embed into the rationals. (Again, I don't have any good references---huzzah for the Moore method. :\ )
- Finally, once you have all of these wonderful sets of numbers, it is relatively straight-forward to show that $\frac{1}{2}$ is not an integer (since we finally have definitions both of "integers" and "$\frac{1}{2}$".
The outline above is, actually, quite a lot of work, and it took modern mathematicians a hell of a long time to figure it out and justify each step. This constituted the better part of two semesters of study as an undergraduate, so don't expect to get there overnight.
$\endgroup$ 1 $\begingroup$One nice definition that distinguishes the integers from the rationals or the reals (with their usual axioms, minus those of multiplicative inverses) is that every set of integers that is bounded from below has a least element. This is usually referred to as the well-ordering principle.
You can use this property to show that 1/2 is therefore not an integer (in fact, you can use this to show immediately that there is no integer $n\in \mathbb{Z}$ such that $0<z<1$ by essentially the same argument!)
Of course, as was mentioned in some comments, you need definitions all the way down to really speak of complete rigour.
The rabbit-hole went straight on like a tunnel for some way, and then dipped suddenly down, so suddenly that Alice had not a moment to think about stopping herself before she found herself falling down a very deep well.
Alice in Wonderland
$\endgroup$ 5 $\begingroup$The "definition" of integer builds off the common-sense experience of counting numbers, which is learned by toddlers in counting small numbers of discrete phenomena (e.g., fingers, cookies, people in family, claps of hands). Discrete objects are perceived by infants thanks to the segmentation process of their perceptual brain processes, which decide what parts of the world are connected, and which are unconnected. These processes are only partially understood.
Integers evolved from counting numbers over history, with the addition of zero and negative counting numbers coming from an increasingly formal, abstract treatment.
When you ask for a definition of integer, you are are asking for a definition of counting. Everybody knows how to count objects, and computer vision systems can be programmed to count objects, but there is a commonsense aspect to the notion of discrete, atomic (indivisible) phenomenon that defies straightforward definition, and you can't define counting (or integers) without defining what constitutes perception of discrete phenomena.
$\endgroup$ $\begingroup$The "reason" (but not the proof) that $\frac 12 $ is not an integer is that:
$0 < 1 < 2$.
If $\frac 12 > 0$ then $\frac 12 *0 < \frac 12 *1 < \frac 12 *2$ and $0 < \frac 12 < 1$ and no integer can be between $0$ and $1$.. If $\frac 12 < 0$ we will get the contradiction: $0 > \frac 12 > 1$ but $1> 0$. And if $\frac 12 = 0$ then $0 = \frac 12 = 1$ which is contradictory.
But clearly there are a lot of unstated assumptions being made.
A lot can be covered by the definitions, axioms, and fundamental propositions of fields. $0$ is such that $a+0 = a$, $1$ is such that $1*a = a$ and $\frac 1a$ is such that $\frac 1a*a = 1$. Those are field definitions. We can prove $0 \ne 1$ and that $0*a = 0$. If $m < b$ then $a + m < b+m$ and if $m > 0$ then $am < ab$ is an ordered field axiom and from that we can prove that $0 < 1$. $2 = 1+1$ can be a definition and it would follow that $2 > 1 > 0$.
So from that the proof that $0 < \frac 12 < 1$ is valid. (But read up on Ordered Fields to understand exactly how that would all work).
To define the integers and to claim that $1$ is the least positive integer might require brushing up on the Peano postulates.
Roughly by definition. $0$ is a natural number. $S(n)$ is defined to be "the successor of $n$". This is equivalent to $n + 1$ except we define this before we define $1$ and before we define $+$. As definition the natural numbers are are $0$ and $S(n)$ for natural numbers. By definition $1 = S(0)$ and by axiom there is not natural $n$ so that $S(n) = 0$ and by axiom $n = m \iff S(n) = S(m)$.
From that we can define addition and we can define $n \le m$ as there exists a natural $b$ so that $n + b = m$ (and if $b \ne 0$ then $n < m$). So that will allow as to claim that there are no natural numbers, $a$ so that $0 < a < 1$.
BUT the field definitions and the Peano postulates were two very different approaches and to unite them and make them compatible will take a lot of work.
So that's your homework. Read up on the Ordered Field definitions, and the Peano postulates.
Meanwhile... "a number that can be written without a fractional component" is clearly for too circular and informal to be of use to anyone.
$\endgroup$ $\begingroup$Other answers nicely put forth what a definition of integer might be, so here is how you could prove that $\frac{1}{2}$ is not a integer by using the following two properties of integers.
There are finitely many integers between two numbers.
Integers are a closed set under multiplication.
Proof
Assume that $\frac{1}{2}$ is a integer.
Then $\frac{1}{2}*\frac{1}{2} = \frac{1}{4}$ should also necessarily be a integer by the second property.
We could similarly show that $\frac{1}{16}$ is a integer and so forth............
Eventually we get a infinitude of integers between $0$ and $1$ which contradicts the first property.
Hence by contradiction the proof is complete.
$\endgroup$
