How do we know if Euclid's theorem is the same for every instance? (euclid's theorem is a proof that there are infinite prime numbers by contradiction, stating that for every finite series of prime numbers there can always be a new prime number generated from that list) but how do we know that this applies every time?
because euclid proved it
>>7753981
If you are asking this, you don't understand the proof.
>>7753981
>how do we know that this applies every time
Because it doesn't matter how long your list of primes is, by constructing a new number in the way he specified you show that the list is incomplete.
If you are this thickheaded then I recommend making a finite list of primes, using his instructions to construct the new number and then try to factorize that new number with only the primes in your list.
It is false, since one can not construct infinitely many primes.
>>7754017
You don't understand my question, I'm asking if there can ever be a finite list of primes that is eventually complete, because this theorem has only been applied a few times considering the infinite number of numbers
>>7754896
No.
You have literally no understanding of the proof. Even further, you appear to have no understanding of proofs in general.
>>7754896
It applies simultaneously to every possible finite list of primes.
May Christ deliver your soul when you get asked to do an epsilon-delta argument.
>>7754896
Ok so I'm just going to walk you through the proof.
Assume for contradiction that there is not an infinite number of primes. Then there is a finite number of primes. Then I can list all the primes, so I will represent the list as follows:
[math]a_1, a_2, \dotsc, a_n[/math]
So then any prime number is on the above list. Now we consider the following number:
[math]p = a_1 \cdot a_2 \cdot \dotsc \cdot a_n + 1[/math]
Now by the fundamental theorem of arithmetic (https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic), we know that either [math]p[/math] is prime, or the product of prime numbers. Clearly, [math]p[/math] is not divisible by any prime number based on how [math]p[/math] was constructed. Thus, [math]p[/math] must be prime. But [math]p[/math] is clearly not on the list as well (it is not equal to any member of the list). Thus, there is a prime number which is not on the list, a contradiction.
Thus, if you have ANY finite list of prime numbers, you can construct a number which is relatively prime to that list. Thus, there cannot be a finite number of prime numbers.
>>7754177
you wot m8?
Euclid's theorem IS a construction for infinitely many primes. Given a list of primes it is possible to generate another prime that isn't on that list.
>>7755355
So this is technically wrong. The proof gives you a way to construct a number relatively prime to the list. For example, consider the list {3, 5}. The proof really can only work to contradict the assumption of a finite number of primes, not to actually construct prime numbers.
>>7753981
What if infinity is prime man!!! fucking mind blown!
It doesn't. It proves that there are infinitely many primes, not an infinite number of primes. Euclid proves that for every n, there exist P primes. A lot of people misinterpret this as for every P there exist n.
OP, what you have just discovered is the quantifier shift fallacy. Euclid proves that any list of primes is incomplete (in that there will always be more primes) , but you cannot logically conclude that there are an actual infinite number of primes.
You dont need to be skeptical because the function is recursive.
>>7755532
I'd just like to add as well, I didn't actually explain what the quantifier shift fallacy was. The quantifier shift fallacy says, loosely, you cannot shift for all there exist to there exist for all. If this is not clear, consider this example:
For every person x, there exists a person y such that y is the mother of x.
Therefore, there exists a person y for such that y is the mother of x for all x.
In plain English: Just because everyone has a mother does not mean that there is one person who is everyone's mother.
>>7755532
> but you cannot logically conclude that there are an actual infinite number of primes.
>The set of all prime numbers cannot be finite because being finite causes it to be incomplete
>Sets can either be finite or infinite
>So the set of all prime numbers is infinite.
Theorem: There are infinitely many natural numbers
Proof:
Assume there is a list that contains all natural numbers that goes
1, 2, ..., n
n being the last member of the list.
However, we can construct a number n + 1 which is not on the list because for any x in the list that is not n
n > x and n + 1 > n so n + 1 > n > x
so the list is incomplete.
QED.
But this anon would say:
>HURR DUURRR YOU CNUUT NO NUFFIN SO U KUNT CONCLUD THREER RRR UNFUNYTE NUMBERS DUUHHHRRRR
>IF IIH WERR 2 CAUNT FOR A WHYLE THIN I WULT HIT TEH LST NAMBER DURRRRR
>>7755536
I'm not surprised that a poster on /sci/ disputes this, but this is not only an exercise in basic logic, but also well known and well documented.
https://www.google.com/url?sa=t&source=web&rct=j&url=http://empslocal.ex.ac.uk/people/staff/apgalton/Slides/CTT-slides.ppt&ved=0ahUKEwj3g_u0iojKAhVMHD4KHfrfAJgQFggwMAg&usg=AFQjCNE9m1u4kFxplKLpXe7PVe9azuo_bQ&sig2=o4iucq2k8CnIQ2P9VRbdAA
https://www.google.com/url?sa=t&source=web&rct=j&url=http://www.humanities.mcmaster.ca/~rarthur/papers/x%2Bdx%3Dx.pdf&ved=0ahUKEwj91r_FiojKAhWBcD4KHWfABpYQFggxMAg&usg=AFQjCNHSG9TKbD9L26WWXp85VUR0-76Icg&sig2=aoJhg3DNYByhiefDhvLR9Q
Let me just reiterate.
Euclid proves:
For all natural numbers n, there exists a set of primes P such that |P| > n.
This is not logically the same as saying there exists a P for all natural numbers n such that |P| > n.
>>7754896
no, but there is probably a prime number so large that it's the largest prime number you'll ever need, sort of how you only need a small number of pi's digits to accurately calculate the size of the universe.
So basically, what is the largest number that we'll ever need to use, and what is the first prime number smaller than that? Once we know, we can just generate all the prime numbers up to that one, and we'll have a practically complete list of prime numbers
>>7755536
Also, I'd like to point out:
The natural numbers being infinite is postulated.
The fact that infinite sets exist at all is postulated (its an axiom we assume).
>>7755542
>Euclid proves:
For all natural numbers n
And the natural numbers are also infinite. So for the infinity of natural numbers there
>exists a set of primes P such that |P| > n.
That is just rewording 'there are infinite prime numbers'. Nothing amazing here.
Also, your links go to a download. Not doing that, thank you. Either you copy paste the important bits or I will just google search an answer for you.
There you go:
https://www.google.com/#q=Prime+numbers+are+infinite
I really love argumenting! For my undergraduate thesis I also gave the professor a google search. Got an A+ on that one.
Anyways...
>>7755545
>The natural numbers being infinite is postulated.
But you can logically prove it as I stated.
>The fact that infinite sets exist at all is postulated (its an axiom we assume).
So what? It being an axiom doesn't make it wrong. It makes it even more right than if it were a provable statement because it is inherently true.
>any quantity is equal to itself
Well that is just an axiom! Clearly you can't prove that a=a therefore I am right and 1 does not equal 1. That is just an axiom!
>>7755552
Read a book on logic. I'm not going to argue with freshmen about mathematics they don't understand. Ask your professor about the quantifier shift fallacy and how it relates to Euclid's theorem on primes.
>>7755555
> I'm not going to argue with freshmen about mathematics they don't understand
Well, I understand that there are infinitely many prime numbers. If your little mind can't grasp that then that is just a waste of quints.
>>7755560
That's right. There are infinitely many primes. But there are not an infinite number of primes! Now you get it. Ok I am leaving this thread now. Yiu might still want to read up on some basic logic. I figured that they taught it in most schools but apparently not yours. If your prof doesn't get it after you bring it up, I'd strongly suggest getting your money back. If, afterward, you ever switch to MIT, let me know and I'll show you around.
>>7755562
If you are actually being raised by some radical, new-age logician then I feel deeply sorry for you. Not only are you applying you fallacy inappropriately to this situation, but the actual philosophical issue at hand is of absolutely no interest to working mathematicians.
