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












-1














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 '18 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 '18 at 17:44






  • 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 '18 at 18:05








  • 1




    @CopyPasteIt The least factor $> 1$ of $n$ is prime (i.e. irreducible) is already quite minimal.
    – Bill Dubuque
    Nov 22 '18 at 19:08








  • 1




    @CopyPasteIt Well one can unwind everything down to Peano arithmetic, but that won't be very arithmetically enlightening. Why prefer assembly language over the beautiful higher-level language carefully crafted by number theorists over many centuries?
    – Bill Dubuque
    Nov 22 '18 at 19:37


















-1














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 '18 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 '18 at 17:44






  • 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 '18 at 18:05








  • 1




    @CopyPasteIt The least factor $> 1$ of $n$ is prime (i.e. irreducible) is already quite minimal.
    – Bill Dubuque
    Nov 22 '18 at 19:08








  • 1




    @CopyPasteIt Well one can unwind everything down to Peano arithmetic, but that won't be very arithmetically enlightening. Why prefer assembly language over the beautiful higher-level language carefully crafted by number theorists over many centuries?
    – Bill Dubuque
    Nov 22 '18 at 19:37
















-1












-1








-1







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 '18 at 12:11







CopyPasteIt

















asked Nov 22 '18 at 17:10









CopyPasteItCopyPasteIt

4,0651627




4,0651627












  • 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 '18 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 '18 at 17:44






  • 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 '18 at 18:05








  • 1




    @CopyPasteIt The least factor $> 1$ of $n$ is prime (i.e. irreducible) is already quite minimal.
    – Bill Dubuque
    Nov 22 '18 at 19:08








  • 1




    @CopyPasteIt Well one can unwind everything down to Peano arithmetic, but that won't be very arithmetically enlightening. Why prefer assembly language over the beautiful higher-level language carefully crafted by number theorists over many centuries?
    – Bill Dubuque
    Nov 22 '18 at 19:37




















  • 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 '18 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 '18 at 17:44






  • 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 '18 at 18:05








  • 1




    @CopyPasteIt The least factor $> 1$ of $n$ is prime (i.e. irreducible) is already quite minimal.
    – Bill Dubuque
    Nov 22 '18 at 19:08








  • 1




    @CopyPasteIt Well one can unwind everything down to Peano arithmetic, but that won't be very arithmetically enlightening. Why prefer assembly language over the beautiful higher-level language carefully crafted by number theorists over many centuries?
    – Bill Dubuque
    Nov 22 '18 at 19:37


















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 '18 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 '18 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 '18 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 '18 at 17:44




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 '18 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 '18 at 18:05






1




1




@CopyPasteIt The least factor $> 1$ of $n$ is prime (i.e. irreducible) is already quite minimal.
– Bill Dubuque
Nov 22 '18 at 19:08






@CopyPasteIt The least factor $> 1$ of $n$ is prime (i.e. irreducible) is already quite minimal.
– Bill Dubuque
Nov 22 '18 at 19:08






1




1




@CopyPasteIt Well one can unwind everything down to Peano arithmetic, but that won't be very arithmetically enlightening. Why prefer assembly language over the beautiful higher-level language carefully crafted by number theorists over many centuries?
– Bill Dubuque
Nov 22 '18 at 19:37






@CopyPasteIt Well one can unwind everything down to Peano arithmetic, but that won't be very arithmetically enlightening. Why prefer assembly language over the beautiful higher-level language carefully crafted by number theorists over many centuries?
– Bill Dubuque
Nov 22 '18 at 19:37












1 Answer
1






active

oldest

votes


















1














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

















  • 1




    @Copy It is poor form to change the question in a way that invalidates existing answers.
    – Tobias Kildetoft
    Nov 23 '18 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',
autoActivateHeartbeat: false,
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









1














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

















  • 1




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
















1














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

















  • 1




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














1












1








1






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 '18 at 17:22









Rafay AsharyRafay Ashary

83618




83618








  • 1




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














  • 1




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








1




1




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




@Copy It is poor form to change the question in a way that invalidates existing answers.
– Tobias Kildetoft
Nov 23 '18 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

How to change which sound is reproduced for terminal bell?

Title Spacing in Bjornstrup Chapter, Removing Chapter Number From Contents

Can I use Tabulator js library in my java Spring + Thymeleaf project?