Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I've got to prove (or disprove) the following statement:

$\exists x \in \mathbb{N} \; \forall y \in \mathbb{N}: y \mid x$,

which translates into "It exists such $x$ from the set of natural numbers, that it is divisible by every other natural number."

What puzzles me is that (at the first sight) theoretically we can always build such $x$ by simple multiplication with $y$, but at the same time I am not really sure if we can do this in general. Let for example $y$ be bigger than $x$ (which it can be since this should work for every natural $y$); this clearly does not divide into $y$ anymore. Again by multiplication, I could find a new $x$ that would statisfy the condition... but so can I find $y$ bigger than this new $x$...

So in fact, this statement would only be true when there exists the biggest natual number that is at the same time a multiple of all the previous natural numbers. This clearly cannot be satisfied.

Could this already do as a proof that such $x$ does not exist or do I have to prove the negation of the original statement $\lnot (\exists x \in \mathbb{N} \; \forall y \in \mathbb{N}: y \mid x)$?

EDIT: Note that we distinguish between $\mathbb{N}$ and $\mathbb{N}_0$ ($0 \not\in \mathbb{N}$, but $0 \in \mathbb{N}_0$).

share|improve this question
add comment

4 Answers 4

up vote 3 down vote accepted

If you include $0$ in the natural numbers then note that $0$ is divided by any other number, except for itself. It is often the custom to say that $0$ does divides itself, to allow the relation to be reflexive.

In this case indeed $0$ is such number.

However if $0$ is not included in your definition of the natural numbers then the answer is no. Such number would be divisible by all the prime numbers, and therefore will be at least as large as any of them. Since the prime numbers are unbounded it means that such number will be at least as large as any other number, and therefore it would be larger than all of them. There is no number which is larger than all the natural numbers, and so the answer is negative.

share|improve this answer
add comment

If you consider zero as a natural number then $\,x=0\,$ solves your problem as

$$\forall\,\,y\in\Bbb N\;\;,\;\;y\,\mid 0\Longleftrightarrow\,\,\exists\,n\in\Bbb N\,\,s.t.\,\,0=ny$$

and choosing $\,n=0\,$ does the job.

If you mean non-zero $\,x\,$ then the answer is no as it wouldcontradict hte Fundamental Theorem of Arithmetic

share|improve this answer
add comment

In one sense, the answer is yes: $0$ is divisible by any positive integer, and depending on how you define divisibility, $0$ may be divisible by $0$ as well.

However, in another sense, the answer is no: if $n$ is a positive integer and $m$ divides $n$, then $n \ge m$, so a positive integer can never be divisible by all positive integers.

Finally, perhaps it's worth mentioning that one can construct a non-standard model of Peano arithmetic in which there exists a non-zero number divisible by every standard natural number. Indeed, you have already made the key observation needed: for any finite set $D$ of standard natural numbers, I can construct a standard natural number that is divisible by everything in $D$. Thus, by the compactness theorem, there is a non-standard model with a non-standard number that is divisible by all standard natural numbers. (Alternatively, take an ultrapower of the standard model and consider the class of $(1, 2, 3!, 4!, 5!, 6!, \ldots)$.)

share|improve this answer
1  
As for the last paragraph, I think it should be mentioned that while it will be divisible by any standard number it will not be divisible by all the numbers (internally). This can be confusing to someone unfamiliar with internal and external definability issues. –  Asaf Karagila Dec 16 '12 at 12:20
add comment

In case you define $N$ such that $0\in N$:

Note that $x|y$ does not imply that $x\leq y$

In fact $\forall y\in N [y|0]$ and $0\in N$. This is because $\forall y\in N[(y)(0)=0]$

share|improve this answer
    
Does $0|0$? I thought that no number can be divided by zero. :-) –  Asaf Karagila Dec 16 '12 at 11:48
    
Depends on your definition. I say $x \mid y$ if and only if $\exists z . y = x z$, in which case $x \mid x$ always. –  Zhen Lin Dec 16 '12 at 11:50
    
So did I, yet extending (or contracting...?) the definition of "divide" from ring theory to the naturals makes the cut...I think. –  DonAntonio Dec 16 '12 at 11:50
    
I was going to say what Zhen lin said. $0=0$x$0$. –  Amr Dec 16 '12 at 11:51
    
Sorry, we distinguish between $\mathbb{N}$ and $\mathbb{N}_0$ ($0 \not\in \mathbb{N}$, but $0 \in \mathbb{N}_0$) –  smihael Dec 16 '12 at 11:51
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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