Another Proof of Euclid's Theorem (infinite number of primes)?











up vote
0
down vote

favorite












Here $mathbb N = {2,3,4,dots}$ with the binary operation of addition.



If $m in mathbb N$ we denote by $G_{mathbb N} (m)$ the semigroup generated by $m$.



Definition: A number $p$ is said to be prime if for all $m lt p$, $;p notin G_{mathbb N} (m) $.



We denote the set of non-empty finite subsets of $mathbb N$ by $mathcal F (mathbb N)$.



Let $mathtt E$ be a function



$quad mathtt E: mathbb N to mathcal F (mathbb N)$



satisfying the following:



$quad quadquadforall n in mathbb N$



$tag 0 mathtt E (2) = {2}$



$tag 1 text{ If } (forall text{ prime } p lt n) ; n notin G_{mathbb N} (p) text{ then } mathtt E (n) = {n}$



$tag 2 text{ If } , (exists text{ prime } p lt n) ; n in G_{mathbb N} (p) text{ then } mathtt E (n) text{ is the union of all such primes}$



$tag 3 mathtt E (n+1) cap mathtt E (n) = emptyset$



We have the following result:



Theorem 1: There exist one and only one function $mathtt E$ satisfying $text{(0)}$ thru $text{(2)}$; it will also satisfy $text{(3)}$. Moreover, for every $n$, all the numbers in the set $mathtt E (n)$ are prime (the prime 'factors').




Question: Can the theorem be proved in this $(mathbb N,+)$ setting?




If yes, we can continue.



Theorem 2: The set of all prime numbers is an infinite set.

Proof

If $a_1$ is any number, consider the 'next further out' number



$tag 4 a_2 = sum_{i=1}^{a_1+1}, a_1 = sum_{i=1}^{a_1},( a_1 + 1)$.



A simple argument using $text{(3)}$ shows that $mathtt E (a_1) subsetneq mathtt E (a_2);$ (c.f. Bill Dubuque's remark).



Employing recursion we get a sequence $a_1, a_2, a_3,dots$ with a corresponding chain of strictly increasing sets



$quad mathtt E (a_1) subsetneq mathtt E (a_2) subsetneq E (a_3) dots$



So there are sets of prime numbers with more elements than any finite set. $blacksquare$



My Work



Please see



Using the recursion theorem to implement the Sieve of Eratosthenes.



The proof of theorem 2 is along the lines found in the proof given by Filip Saidak. Also, if we set $a_1$ to $1$ in theorem 2 we get the researched OEIS sequence A007018.



Note that the proof supplied by Filip Saidak has most likely been known for many years; see Bill Dubuque's answer to the math.stackexchange.com question



Is there an intuitionist (i.e., constructive) proof of the infinitude of primes?










share|cite|improve this question
























  • Note, multiplication (of positive integers) is recursive addition. That is, we define $acdot1$ to be $a$ and $acdot(n+1)$ to be $acdot n+a$.
    – Barry Cipra
    Nov 22 at 17:39












  • @BarryCipra Yes I know. But I get excited when something that appears 'bound to multiplication' - the prime numbers - can get released into a more elementary framework.
    – CopyPasteIt
    Nov 22 at 17:44










  • Agreed. It's like discovering that gold isn't just valuable stuff that giltters, but can be dealt with profitably as heavy stuff that settles to the bottom.
    – Barry Cipra
    Nov 22 at 17:48












  • @BarryCipra Yes, sieving for gold seems like fun!
    – CopyPasteIt
    Nov 22 at 17:50






  • 1




    The proof via $,n(n!+!1),$ has more prime factors than $n$ for $,nge 1$ is surely much older than Saidak's 2005 paper. The generated sequence is OEIS A007018. Note: adding $1$ yields Sylvestoer sequence $a_{n+1} = a_n^2 - a_n + 1 = $ OEIS A000058. See the OEIS notes for other connections.
    – Bill Dubuque
    Nov 22 at 18:05

















up vote
0
down vote

favorite












Here $mathbb N = {2,3,4,dots}$ with the binary operation of addition.



If $m in mathbb N$ we denote by $G_{mathbb N} (m)$ the semigroup generated by $m$.



Definition: A number $p$ is said to be prime if for all $m lt p$, $;p notin G_{mathbb N} (m) $.



We denote the set of non-empty finite subsets of $mathbb N$ by $mathcal F (mathbb N)$.



Let $mathtt E$ be a function



$quad mathtt E: mathbb N to mathcal F (mathbb N)$



satisfying the following:



$quad quadquadforall n in mathbb N$



$tag 0 mathtt E (2) = {2}$



$tag 1 text{ If } (forall text{ prime } p lt n) ; n notin G_{mathbb N} (p) text{ then } mathtt E (n) = {n}$



$tag 2 text{ If } , (exists text{ prime } p lt n) ; n in G_{mathbb N} (p) text{ then } mathtt E (n) text{ is the union of all such primes}$



$tag 3 mathtt E (n+1) cap mathtt E (n) = emptyset$



We have the following result:



Theorem 1: There exist one and only one function $mathtt E$ satisfying $text{(0)}$ thru $text{(2)}$; it will also satisfy $text{(3)}$. Moreover, for every $n$, all the numbers in the set $mathtt E (n)$ are prime (the prime 'factors').




Question: Can the theorem be proved in this $(mathbb N,+)$ setting?




If yes, we can continue.



Theorem 2: The set of all prime numbers is an infinite set.

Proof

If $a_1$ is any number, consider the 'next further out' number



$tag 4 a_2 = sum_{i=1}^{a_1+1}, a_1 = sum_{i=1}^{a_1},( a_1 + 1)$.



A simple argument using $text{(3)}$ shows that $mathtt E (a_1) subsetneq mathtt E (a_2);$ (c.f. Bill Dubuque's remark).



Employing recursion we get a sequence $a_1, a_2, a_3,dots$ with a corresponding chain of strictly increasing sets



$quad mathtt E (a_1) subsetneq mathtt E (a_2) subsetneq E (a_3) dots$



So there are sets of prime numbers with more elements than any finite set. $blacksquare$



My Work



Please see



Using the recursion theorem to implement the Sieve of Eratosthenes.



The proof of theorem 2 is along the lines found in the proof given by Filip Saidak. Also, if we set $a_1$ to $1$ in theorem 2 we get the researched OEIS sequence A007018.



Note that the proof supplied by Filip Saidak has most likely been known for many years; see Bill Dubuque's answer to the math.stackexchange.com question



Is there an intuitionist (i.e., constructive) proof of the infinitude of primes?










share|cite|improve this question
























  • Note, multiplication (of positive integers) is recursive addition. That is, we define $acdot1$ to be $a$ and $acdot(n+1)$ to be $acdot n+a$.
    – Barry Cipra
    Nov 22 at 17:39












  • @BarryCipra Yes I know. But I get excited when something that appears 'bound to multiplication' - the prime numbers - can get released into a more elementary framework.
    – CopyPasteIt
    Nov 22 at 17:44










  • Agreed. It's like discovering that gold isn't just valuable stuff that giltters, but can be dealt with profitably as heavy stuff that settles to the bottom.
    – Barry Cipra
    Nov 22 at 17:48












  • @BarryCipra Yes, sieving for gold seems like fun!
    – CopyPasteIt
    Nov 22 at 17:50






  • 1




    The proof via $,n(n!+!1),$ has more prime factors than $n$ for $,nge 1$ is surely much older than Saidak's 2005 paper. The generated sequence is OEIS A007018. Note: adding $1$ yields Sylvestoer sequence $a_{n+1} = a_n^2 - a_n + 1 = $ OEIS A000058. See the OEIS notes for other connections.
    – Bill Dubuque
    Nov 22 at 18:05















up vote
0
down vote

favorite









up vote
0
down vote

favorite











Here $mathbb N = {2,3,4,dots}$ with the binary operation of addition.



If $m in mathbb N$ we denote by $G_{mathbb N} (m)$ the semigroup generated by $m$.



Definition: A number $p$ is said to be prime if for all $m lt p$, $;p notin G_{mathbb N} (m) $.



We denote the set of non-empty finite subsets of $mathbb N$ by $mathcal F (mathbb N)$.



Let $mathtt E$ be a function



$quad mathtt E: mathbb N to mathcal F (mathbb N)$



satisfying the following:



$quad quadquadforall n in mathbb N$



$tag 0 mathtt E (2) = {2}$



$tag 1 text{ If } (forall text{ prime } p lt n) ; n notin G_{mathbb N} (p) text{ then } mathtt E (n) = {n}$



$tag 2 text{ If } , (exists text{ prime } p lt n) ; n in G_{mathbb N} (p) text{ then } mathtt E (n) text{ is the union of all such primes}$



$tag 3 mathtt E (n+1) cap mathtt E (n) = emptyset$



We have the following result:



Theorem 1: There exist one and only one function $mathtt E$ satisfying $text{(0)}$ thru $text{(2)}$; it will also satisfy $text{(3)}$. Moreover, for every $n$, all the numbers in the set $mathtt E (n)$ are prime (the prime 'factors').




Question: Can the theorem be proved in this $(mathbb N,+)$ setting?




If yes, we can continue.



Theorem 2: The set of all prime numbers is an infinite set.

Proof

If $a_1$ is any number, consider the 'next further out' number



$tag 4 a_2 = sum_{i=1}^{a_1+1}, a_1 = sum_{i=1}^{a_1},( a_1 + 1)$.



A simple argument using $text{(3)}$ shows that $mathtt E (a_1) subsetneq mathtt E (a_2);$ (c.f. Bill Dubuque's remark).



Employing recursion we get a sequence $a_1, a_2, a_3,dots$ with a corresponding chain of strictly increasing sets



$quad mathtt E (a_1) subsetneq mathtt E (a_2) subsetneq E (a_3) dots$



So there are sets of prime numbers with more elements than any finite set. $blacksquare$



My Work



Please see



Using the recursion theorem to implement the Sieve of Eratosthenes.



The proof of theorem 2 is along the lines found in the proof given by Filip Saidak. Also, if we set $a_1$ to $1$ in theorem 2 we get the researched OEIS sequence A007018.



Note that the proof supplied by Filip Saidak has most likely been known for many years; see Bill Dubuque's answer to the math.stackexchange.com question



Is there an intuitionist (i.e., constructive) proof of the infinitude of primes?










share|cite|improve this question















Here $mathbb N = {2,3,4,dots}$ with the binary operation of addition.



If $m in mathbb N$ we denote by $G_{mathbb N} (m)$ the semigroup generated by $m$.



Definition: A number $p$ is said to be prime if for all $m lt p$, $;p notin G_{mathbb N} (m) $.



We denote the set of non-empty finite subsets of $mathbb N$ by $mathcal F (mathbb N)$.



Let $mathtt E$ be a function



$quad mathtt E: mathbb N to mathcal F (mathbb N)$



satisfying the following:



$quad quadquadforall n in mathbb N$



$tag 0 mathtt E (2) = {2}$



$tag 1 text{ If } (forall text{ prime } p lt n) ; n notin G_{mathbb N} (p) text{ then } mathtt E (n) = {n}$



$tag 2 text{ If } , (exists text{ prime } p lt n) ; n in G_{mathbb N} (p) text{ then } mathtt E (n) text{ is the union of all such primes}$



$tag 3 mathtt E (n+1) cap mathtt E (n) = emptyset$



We have the following result:



Theorem 1: There exist one and only one function $mathtt E$ satisfying $text{(0)}$ thru $text{(2)}$; it will also satisfy $text{(3)}$. Moreover, for every $n$, all the numbers in the set $mathtt E (n)$ are prime (the prime 'factors').




Question: Can the theorem be proved in this $(mathbb N,+)$ setting?




If yes, we can continue.



Theorem 2: The set of all prime numbers is an infinite set.

Proof

If $a_1$ is any number, consider the 'next further out' number



$tag 4 a_2 = sum_{i=1}^{a_1+1}, a_1 = sum_{i=1}^{a_1},( a_1 + 1)$.



A simple argument using $text{(3)}$ shows that $mathtt E (a_1) subsetneq mathtt E (a_2);$ (c.f. Bill Dubuque's remark).



Employing recursion we get a sequence $a_1, a_2, a_3,dots$ with a corresponding chain of strictly increasing sets



$quad mathtt E (a_1) subsetneq mathtt E (a_2) subsetneq E (a_3) dots$



So there are sets of prime numbers with more elements than any finite set. $blacksquare$



My Work



Please see



Using the recursion theorem to implement the Sieve of Eratosthenes.



The proof of theorem 2 is along the lines found in the proof given by Filip Saidak. Also, if we set $a_1$ to $1$ in theorem 2 we get the researched OEIS sequence A007018.



Note that the proof supplied by Filip Saidak has most likely been known for many years; see Bill Dubuque's answer to the math.stackexchange.com question



Is there an intuitionist (i.e., constructive) proof of the infinitude of primes?







abstract-algebra elementary-number-theory prime-numbers alternative-proof semigroups






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Nov 24 at 12:11

























asked Nov 22 at 17:10









CopyPasteIt

3,9541627




3,9541627












  • Note, multiplication (of positive integers) is recursive addition. That is, we define $acdot1$ to be $a$ and $acdot(n+1)$ to be $acdot n+a$.
    – Barry Cipra
    Nov 22 at 17:39












  • @BarryCipra Yes I know. But I get excited when something that appears 'bound to multiplication' - the prime numbers - can get released into a more elementary framework.
    – CopyPasteIt
    Nov 22 at 17:44










  • Agreed. It's like discovering that gold isn't just valuable stuff that giltters, but can be dealt with profitably as heavy stuff that settles to the bottom.
    – Barry Cipra
    Nov 22 at 17:48












  • @BarryCipra Yes, sieving for gold seems like fun!
    – CopyPasteIt
    Nov 22 at 17:50






  • 1




    The proof via $,n(n!+!1),$ has more prime factors than $n$ for $,nge 1$ is surely much older than Saidak's 2005 paper. The generated sequence is OEIS A007018. Note: adding $1$ yields Sylvestoer sequence $a_{n+1} = a_n^2 - a_n + 1 = $ OEIS A000058. See the OEIS notes for other connections.
    – Bill Dubuque
    Nov 22 at 18:05




















  • Note, multiplication (of positive integers) is recursive addition. That is, we define $acdot1$ to be $a$ and $acdot(n+1)$ to be $acdot n+a$.
    – Barry Cipra
    Nov 22 at 17:39












  • @BarryCipra Yes I know. But I get excited when something that appears 'bound to multiplication' - the prime numbers - can get released into a more elementary framework.
    – CopyPasteIt
    Nov 22 at 17:44










  • Agreed. It's like discovering that gold isn't just valuable stuff that giltters, but can be dealt with profitably as heavy stuff that settles to the bottom.
    – Barry Cipra
    Nov 22 at 17:48












  • @BarryCipra Yes, sieving for gold seems like fun!
    – CopyPasteIt
    Nov 22 at 17:50






  • 1




    The proof via $,n(n!+!1),$ has more prime factors than $n$ for $,nge 1$ is surely much older than Saidak's 2005 paper. The generated sequence is OEIS A007018. Note: adding $1$ yields Sylvestoer sequence $a_{n+1} = a_n^2 - a_n + 1 = $ OEIS A000058. See the OEIS notes for other connections.
    – Bill Dubuque
    Nov 22 at 18:05


















Note, multiplication (of positive integers) is recursive addition. That is, we define $acdot1$ to be $a$ and $acdot(n+1)$ to be $acdot n+a$.
– Barry Cipra
Nov 22 at 17:39






Note, multiplication (of positive integers) is recursive addition. That is, we define $acdot1$ to be $a$ and $acdot(n+1)$ to be $acdot n+a$.
– Barry Cipra
Nov 22 at 17:39














@BarryCipra Yes I know. But I get excited when something that appears 'bound to multiplication' - the prime numbers - can get released into a more elementary framework.
– CopyPasteIt
Nov 22 at 17:44




@BarryCipra Yes I know. But I get excited when something that appears 'bound to multiplication' - the prime numbers - can get released into a more elementary framework.
– CopyPasteIt
Nov 22 at 17:44












Agreed. It's like discovering that gold isn't just valuable stuff that giltters, but can be dealt with profitably as heavy stuff that settles to the bottom.
– Barry Cipra
Nov 22 at 17:48






Agreed. It's like discovering that gold isn't just valuable stuff that giltters, but can be dealt with profitably as heavy stuff that settles to the bottom.
– Barry Cipra
Nov 22 at 17:48














@BarryCipra Yes, sieving for gold seems like fun!
– CopyPasteIt
Nov 22 at 17:50




@BarryCipra Yes, sieving for gold seems like fun!
– CopyPasteIt
Nov 22 at 17:50




1




1




The proof via $,n(n!+!1),$ has more prime factors than $n$ for $,nge 1$ is surely much older than Saidak's 2005 paper. The generated sequence is OEIS A007018. Note: adding $1$ yields Sylvestoer sequence $a_{n+1} = a_n^2 - a_n + 1 = $ OEIS A000058. See the OEIS notes for other connections.
– Bill Dubuque
Nov 22 at 18:05






The proof via $,n(n!+!1),$ has more prime factors than $n$ for $,nge 1$ is surely much older than Saidak's 2005 paper. The generated sequence is OEIS A007018. Note: adding $1$ yields Sylvestoer sequence $a_{n+1} = a_n^2 - a_n + 1 = $ OEIS A000058. See the OEIS notes for other connections.
– Bill Dubuque
Nov 22 at 18:05












1 Answer
1






active

oldest

votes

















up vote
1
down vote













It is valid, but seems to be fundamentally the same as the classical proof; both hinge upon the fact that $p_1times p_2times cdotstimes p_n+1$ is divisible by some prime not in ${p_1,p_2,dots,p_n}$.






share|cite|improve this answer





















  • @Copy It is poor form to change the question in a way that invalidates existing answers.
    – Tobias Kildetoft
    Nov 23 at 17:08











Your Answer





StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3009367%2fanother-proof-of-euclids-theorem-infinite-number-of-primes%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























1 Answer
1






active

oldest

votes








1 Answer
1






active

oldest

votes









active

oldest

votes






active

oldest

votes








up vote
1
down vote













It is valid, but seems to be fundamentally the same as the classical proof; both hinge upon the fact that $p_1times p_2times cdotstimes p_n+1$ is divisible by some prime not in ${p_1,p_2,dots,p_n}$.






share|cite|improve this answer





















  • @Copy It is poor form to change the question in a way that invalidates existing answers.
    – Tobias Kildetoft
    Nov 23 at 17:08















up vote
1
down vote













It is valid, but seems to be fundamentally the same as the classical proof; both hinge upon the fact that $p_1times p_2times cdotstimes p_n+1$ is divisible by some prime not in ${p_1,p_2,dots,p_n}$.






share|cite|improve this answer





















  • @Copy It is poor form to change the question in a way that invalidates existing answers.
    – Tobias Kildetoft
    Nov 23 at 17:08













up vote
1
down vote










up vote
1
down vote









It is valid, but seems to be fundamentally the same as the classical proof; both hinge upon the fact that $p_1times p_2times cdotstimes p_n+1$ is divisible by some prime not in ${p_1,p_2,dots,p_n}$.






share|cite|improve this answer












It is valid, but seems to be fundamentally the same as the classical proof; both hinge upon the fact that $p_1times p_2times cdotstimes p_n+1$ is divisible by some prime not in ${p_1,p_2,dots,p_n}$.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered Nov 22 at 17:22









Rafay Ashary

80118




80118












  • @Copy It is poor form to change the question in a way that invalidates existing answers.
    – Tobias Kildetoft
    Nov 23 at 17:08


















  • @Copy It is poor form to change the question in a way that invalidates existing answers.
    – Tobias Kildetoft
    Nov 23 at 17:08
















@Copy It is poor form to change the question in a way that invalidates existing answers.
– Tobias Kildetoft
Nov 23 at 17:08




@Copy It is poor form to change the question in a way that invalidates existing answers.
– Tobias Kildetoft
Nov 23 at 17:08


















draft saved

draft discarded




















































Thanks for contributing an answer to Mathematics Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.





Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


Please pay close attention to the following guidance:


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3009367%2fanother-proof-of-euclids-theorem-infinite-number-of-primes%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







Popular posts from this blog

Ellipse (mathématiques)

Quarter-circle Tiles

Mont Emei