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?
abstract-algebra elementary-number-theory prime-numbers alternative-proof semigroups
|
show 5 more comments
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?
abstract-algebra elementary-number-theory prime-numbers alternative-proof semigroups
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
|
show 5 more comments
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?
abstract-algebra elementary-number-theory prime-numbers alternative-proof semigroups
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
abstract-algebra elementary-number-theory prime-numbers alternative-proof semigroups
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
|
show 5 more comments
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
|
show 5 more comments
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}$.
@Copy It is poor form to change the question in a way that invalidates existing answers.
– Tobias Kildetoft
Nov 23 at 17:08
add a comment |
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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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}$.
@Copy It is poor form to change the question in a way that invalidates existing answers.
– Tobias Kildetoft
Nov 23 at 17:08
add a comment |
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}$.
@Copy It is poor form to change the question in a way that invalidates existing answers.
– Tobias Kildetoft
Nov 23 at 17:08
add a comment |
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}$.
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}$.
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
add a comment |
@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
add a comment |
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
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