Mixing
Every nonempty subset of the natural numbers has a least number
$begingroup$
Proposition: Every nonempty subset $A$ of $mathbb{N}$ has a least element.
We assume the opposite: $$exists left( A subseteq mathbb{N} wedge A neq varnothing right): forall s in A: exists a in A: s > a$$
Be $A subseteq mathbb{N}$ and $A neq varnothing$.
Be $s in A$ and $a_n in A$ for every $n in mathbb{N}_{ge 1}$ and be $s > a_1$ and $a_n > a_{n+1}$.
Proposition: $$s - a_n ge n$$
Proof with mathematical induction:
The base case holds since $s > a_1 implies s-a_1 ge 1$.
Also: $a_n > a_{n+1} implies a_n - a_{n+1} ge 1$ and with this $s - a_n ge n$ implies $s - a_{n+1} ge n+1 quad square$
Since $s - a_n ge n$ and $a_n ge 0$ holds we get: $$s ge n quad forall n in mathbb{N}_{ge 1}$$
But it is $s < s+1 in mathbb{N}_{ge 1} text{ Contradiction!} quad square$
First question: Is this proof valid?
Second question: Do you know different proofs for this proposition?
Cheers
elementary-number-theory elementary-set-theory induction
asked Nov 13 '15 at 0:34
Harald MeisnerHarald Meisner
8918
$endgroup$
add a comment |
$begingroup$
Proposition: Every nonempty subset $A$ of $mathbb{N}$ has a least element.
We assume the opposite: $$exists left( A subseteq mathbb{N} wedge A neq varnothing right): forall s in A: exists a in A: s > a$$
Be $A subseteq mathbb{N}$ and $A neq varnothing$.
Be $s in A$ and $a_n in A$ for every $n in mathbb{N}_{ge 1}$ and be $s > a_1$ and $a_n > a_{n+1}$.
Proposition: $$s - a_n ge n$$
Proof with mathematical induction:
The base case holds since $s > a_1 implies s-a_1 ge 1$.
Also: $a_n > a_{n+1} implies a_n - a_{n+1} ge 1$ and with this $s - a_n ge n$ implies $s - a_{n+1} ge n+1 quad square$
Since $s - a_n ge n$ and $a_n ge 0$ holds we get: $$s ge n quad forall n in mathbb{N}_{ge 1}$$
But it is $s < s+1 in mathbb{N}_{ge 1} text{ Contradiction!} quad square$
First question: Is this proof valid?
Second question: Do you know different proofs for this proposition?
Cheers
elementary-number-theory elementary-set-theory induction
asked Nov 13 '15 at 0:34
Harald MeisnerHarald Meisner
8918
$endgroup$
$begingroup$
The denial of "Each nonempty subsets of N has a least element" is not what you have, it is instead "There is a specific nonempty subset B of N which does not have a least element. Go for the contradiction from there...
$endgroup$
– coffeemath
Nov 13 '15 at 0:39
$begingroup$
Hello coffemath, how would this change the proof itself?
$endgroup$
– Harald Meisner
Nov 13 '15 at 0:44
add a comment |
$begingroup$
Proposition: Every nonempty subset $A$ of $mathbb{N}$ has a least element.
We assume the opposite: $$exists left( A subseteq mathbb{N} wedge A neq varnothing right): forall s in A: exists a in A: s > a$$
Be $A subseteq mathbb{N}$ and $A neq varnothing$.
Be $s in A$ and $a_n in A$ for every $n in mathbb{N}_{ge 1}$ and be $s > a_1$ and $a_n > a_{n+1}$.
Proposition: $$s - a_n ge n$$
Proof with mathematical induction:
The base case holds since $s > a_1 implies s-a_1 ge 1$.
Also: $a_n > a_{n+1} implies a_n - a_{n+1} ge 1$ and with this $s - a_n ge n$ implies $s - a_{n+1} ge n+1 quad square$
Since $s - a_n ge n$ and $a_n ge 0$ holds we get: $$s ge n quad forall n in mathbb{N}_{ge 1}$$
But it is $s < s+1 in mathbb{N}_{ge 1} text{ Contradiction!} quad square$
First question: Is this proof valid?
Second question: Do you know different proofs for this proposition?
Cheers
elementary-number-theory elementary-set-theory induction
asked Nov 13 '15 at 0:34
Harald MeisnerHarald Meisner
8918
$endgroup$
Proposition: Every nonempty subset $A$ of $mathbb{N}$ has a least element.
We assume the opposite: $$exists left( A subseteq mathbb{N} wedge A neq varnothing right): forall s in A: exists a in A: s > a$$
Be $A subseteq mathbb{N}$ and $A neq varnothing$.
Be $s in A$ and $a_n in A$ for every $n in mathbb{N}_{ge 1}$ and be $s > a_1$ and $a_n > a_{n+1}$.
Proposition: $$s - a_n ge n$$
Proof with mathematical induction:
The base case holds since $s > a_1 implies s-a_1 ge 1$.
Also: $a_n > a_{n+1} implies a_n - a_{n+1} ge 1$ and with this $s - a_n ge n$ implies $s - a_{n+1} ge n+1 quad square$
Since $s - a_n ge n$ and $a_n ge 0$ holds we get: $$s ge n quad forall n in mathbb{N}_{ge 1}$$
But it is $s < s+1 in mathbb{N}_{ge 1} text{ Contradiction!} quad square$
First question: Is this proof valid?
Second question: Do you know different proofs for this proposition?
Cheers
elementary-number-theory elementary-set-theory induction
elementary-number-theory elementary-set-theory induction
asked Nov 13 '15 at 0:34
Harald MeisnerHarald Meisner
8918
asked Nov 13 '15 at 0:34
Harald MeisnerHarald Meisner
8918
edited Nov 13 '15 at 1:01
Harald Meisner
asked Nov 13 '15 at 0:34
Harald MeisnerHarald Meisner
8918
asked Nov 13 '15 at 0:34
Harald MeisnerHarald Meisner
8918
asked Nov 13 '15 at 0:34
Harald MeisnerHarald Meisner
8918
8918
$begingroup$
The denial of "Each nonempty subsets of N has a least element" is not what you have, it is instead "There is a specific nonempty subset B of N which does not have a least element. Go for the contradiction from there...
$endgroup$
– coffeemath
Nov 13 '15 at 0:39
$begingroup$
Hello coffemath, how would this change the proof itself?
$endgroup$
– Harald Meisner
Nov 13 '15 at 0:44
add a comment |
$begingroup$
The denial of "Each nonempty subsets of N has a least element" is not what you have, it is instead "There is a specific nonempty subset B of N which does not have a least element. Go for the contradiction from there...
$endgroup$
– coffeemath
Nov 13 '15 at 0:39
$begingroup$
Hello coffemath, how would this change the proof itself?
$endgroup$
– Harald Meisner
Nov 13 '15 at 0:44
$begingroup$
The denial of "Each nonempty subsets of N has a least element" is not what you have, it is instead "There is a specific nonempty subset B of N which does not have a least element. Go for the contradiction from there...
$endgroup$
– coffeemath
Nov 13 '15 at 0:39
$begingroup$
The denial of "Each nonempty subsets of N has a least element" is not what you have, it is instead "There is a specific nonempty subset B of N which does not have a least element. Go for the contradiction from there...
$endgroup$
– coffeemath
Nov 13 '15 at 0:39
$begingroup$
Hello coffemath, how would this change the proof itself?
$endgroup$
– Harald Meisner
Nov 13 '15 at 0:44
$begingroup$
Hello coffemath, how would this change the proof itself?
$endgroup$
– Harald Meisner
Nov 13 '15 at 0:44
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
One standard argument is as follows:
Suppose $AsubseteqBbb N$ has no least element. If $0in A$ then $A$ would have a least element. So $0notin A$. Now suppose $0notin A,1notin A,ldots, n-1notin A$. If $nin A$ under these assumptions, then $A$ would have a least element. So, by induction, $nnotin A$ for every $ninBbb N$. Therefore $A=emptyset$.
answered Nov 13 '15 at 0:45
Tim RaczkowskiTim Raczkowski
17.3k21243
$endgroup$
add a comment |
$begingroup$
The sequence you introduce is not necessary and, moreover, building it requires recursion.
Suppose $A$ has no least element. Consider the set
$$
A^*={ninmathbb{N}:n<a,text{for all $ain A$}}
$$
Note that $Acap A^*=emptyset$, because if $ain Acap A^*$ we would have $a<a$, a contradiction.
We prove by induction that $nin A^*$, for all $ninmathbb{N}$.
$0in A^*$; indeed, if $0notin A^*$, there exists $ain A$ with $ale0$; thus $0in A$ and $A$ has a least element.
Suppose $nin A^*$. If $n+1notin A^*$, there exists $ain A$ with $ale n+1$. Since $nin A^*$ we have $n<a$ and therefore $a=n+1$. Then $a=n+1$ is the least element of $A$.
Therefore $A^*=mathbb{N}$ and so $A$ is empty.
If your natural numbers start at $1$, the proof is exactly the same.
The proof relies on the fact that “$n<ale n+1$ implies $a=n+1$”, that in turn is the same as “$0<ale 1$ implies $a=1$. Indeed, since $ane0$, we have $a=b+1$, for some $b$; thus $b+1le 1$ and therefore $ble0$, which implies $b=0$ and so $a=1$.
answered Nov 13 '15 at 1:08
egregegreg
181k1485203
$endgroup$
$begingroup$
Hello egreg, what's the problem with recursion in my proof?
$endgroup$
– Harald Meisner
Nov 13 '15 at 12:26
$begingroup$
@HaraldMeisner That you first have to prove the recursion theorem. Did you?
$endgroup$
– egreg
Nov 13 '15 at 12:50
$begingroup$
Yes, we are allowed to use recursion
$endgroup$
– Harald Meisner
Nov 13 '15 at 13:00
$begingroup$
@HaraldMeisner Good for you, but why doing a complicated proof when a simpler one is available?
$endgroup$
– egreg
Nov 13 '15 at 13:25
add a comment |
$begingroup$
Well, it might not be kosher to bring a baseball bat to a cricket game but:
$mathbb N subset mathbb R$ and the reals have the least upper bound property. A is bounded below by 0. so $x =inf A$ exists.
It's easy to show x is an integer. (Else there exists a $y$ such that $x < y < lceil xrceil$ so y is also a lower bound so $x$ is not inf.) And it's easy to show $x in A$. (Else $x + 1/10$ is also a lower bound and x is not inf.)
So $x = inf A$ and $x in A$ imply $x$ is the least element in A.
====
A bit more cricket:
Assume non-empty A has no minimum element.
We can do a downward induction to prove the following statement: For any integer m, there is an element of A that is less than m.
Sub-base case: Let a be in A. then for all m > a the statement is true because a < m.
Base case: as A does not have a minimum element, a is not the minimum element. So there is an element of A that is less than a.
Induction step: Assume the statement is true for m. The element of A less than m must be less than or equal to m - 1. If it isn't equal to m, than the there is an element of A less than m -1. If it is equal to m, then m is an element of A but it isn't the minimum element as there is no minimum element. So there is an element of A less than m - 1.
Hence this statement is true for all integers.
But it's not true for 0 or any negative integer.
So our assumption was wrong, and non-empty A has a minimum element.
answered Nov 13 '15 at 1:21
fleabloodfleablood
69.8k22685
$endgroup$
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',
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
});
}
});
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%2f1526610%2fevery-nonempty-subset-of-the-natural-numbers-has-a-least-number%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
One standard argument is as follows:
Suppose $AsubseteqBbb N$ has no least element. If $0in A$ then $A$ would have a least element. So $0notin A$. Now suppose $0notin A,1notin A,ldots, n-1notin A$. If $nin A$ under these assumptions, then $A$ would have a least element. So, by induction, $nnotin A$ for every $ninBbb N$. Therefore $A=emptyset$.
answered Nov 13 '15 at 0:45
Tim RaczkowskiTim Raczkowski
17.3k21243
$endgroup$
add a comment |
$begingroup$
One standard argument is as follows:
Suppose $AsubseteqBbb N$ has no least element. If $0in A$ then $A$ would have a least element. So $0notin A$. Now suppose $0notin A,1notin A,ldots, n-1notin A$. If $nin A$ under these assumptions, then $A$ would have a least element. So, by induction, $nnotin A$ for every $ninBbb N$. Therefore $A=emptyset$.
answered Nov 13 '15 at 0:45
Tim RaczkowskiTim Raczkowski
17.3k21243
$endgroup$
add a comment |
$begingroup$
One standard argument is as follows:
Suppose $AsubseteqBbb N$ has no least element. If $0in A$ then $A$ would have a least element. So $0notin A$. Now suppose $0notin A,1notin A,ldots, n-1notin A$. If $nin A$ under these assumptions, then $A$ would have a least element. So, by induction, $nnotin A$ for every $ninBbb N$. Therefore $A=emptyset$.
answered Nov 13 '15 at 0:45
Tim RaczkowskiTim Raczkowski
17.3k21243
$endgroup$
One standard argument is as follows:
Suppose $AsubseteqBbb N$ has no least element. If $0in A$ then $A$ would have a least element. So $0notin A$. Now suppose $0notin A,1notin A,ldots, n-1notin A$. If $nin A$ under these assumptions, then $A$ would have a least element. So, by induction, $nnotin A$ for every $ninBbb N$. Therefore $A=emptyset$.
answered Nov 13 '15 at 0:45
Tim RaczkowskiTim Raczkowski
17.3k21243
answered Nov 13 '15 at 0:45
Tim RaczkowskiTim Raczkowski
17.3k21243
answered Nov 13 '15 at 0:45
Tim RaczkowskiTim Raczkowski
17.3k21243
answered Nov 13 '15 at 0:45
Tim RaczkowskiTim Raczkowski
17.3k21243
17.3k21243
add a comment |
add a comment |
$begingroup$
The sequence you introduce is not necessary and, moreover, building it requires recursion.
Suppose $A$ has no least element. Consider the set
$$
A^*={ninmathbb{N}:n<a,text{for all $ain A$}}
$$
Note that $Acap A^*=emptyset$, because if $ain Acap A^*$ we would have $a<a$, a contradiction.
We prove by induction that $nin A^*$, for all $ninmathbb{N}$.
$0in A^*$; indeed, if $0notin A^*$, there exists $ain A$ with $ale0$; thus $0in A$ and $A$ has a least element.
Suppose $nin A^*$. If $n+1notin A^*$, there exists $ain A$ with $ale n+1$. Since $nin A^*$ we have $n<a$ and therefore $a=n+1$. Then $a=n+1$ is the least element of $A$.
Therefore $A^*=mathbb{N}$ and so $A$ is empty.
If your natural numbers start at $1$, the proof is exactly the same.
The proof relies on the fact that “$n<ale n+1$ implies $a=n+1$”, that in turn is the same as “$0<ale 1$ implies $a=1$. Indeed, since $ane0$, we have $a=b+1$, for some $b$; thus $b+1le 1$ and therefore $ble0$, which implies $b=0$ and so $a=1$.
answered Nov 13 '15 at 1:08
egregegreg
181k1485203
$endgroup$
$begingroup$
Hello egreg, what's the problem with recursion in my proof?
$endgroup$
– Harald Meisner
Nov 13 '15 at 12:26
$begingroup$
@HaraldMeisner That you first have to prove the recursion theorem. Did you?
$endgroup$
– egreg
Nov 13 '15 at 12:50
$begingroup$
Yes, we are allowed to use recursion
$endgroup$
– Harald Meisner
Nov 13 '15 at 13:00
$begingroup$
@HaraldMeisner Good for you, but why doing a complicated proof when a simpler one is available?
$endgroup$
– egreg
Nov 13 '15 at 13:25
add a comment |
$begingroup$
The sequence you introduce is not necessary and, moreover, building it requires recursion.
Suppose $A$ has no least element. Consider the set
$$
A^*={ninmathbb{N}:n<a,text{for all $ain A$}}
$$
Note that $Acap A^*=emptyset$, because if $ain Acap A^*$ we would have $a<a$, a contradiction.
We prove by induction that $nin A^*$, for all $ninmathbb{N}$.
$0in A^*$; indeed, if $0notin A^*$, there exists $ain A$ with $ale0$; thus $0in A$ and $A$ has a least element.
Suppose $nin A^*$. If $n+1notin A^*$, there exists $ain A$ with $ale n+1$. Since $nin A^*$ we have $n<a$ and therefore $a=n+1$. Then $a=n+1$ is the least element of $A$.
Therefore $A^*=mathbb{N}$ and so $A$ is empty.
If your natural numbers start at $1$, the proof is exactly the same.
The proof relies on the fact that “$n<ale n+1$ implies $a=n+1$”, that in turn is the same as “$0<ale 1$ implies $a=1$. Indeed, since $ane0$, we have $a=b+1$, for some $b$; thus $b+1le 1$ and therefore $ble0$, which implies $b=0$ and so $a=1$.
answered Nov 13 '15 at 1:08
egregegreg
181k1485203
$endgroup$
$begingroup$
Hello egreg, what's the problem with recursion in my proof?
$endgroup$
– Harald Meisner
Nov 13 '15 at 12:26
$begingroup$
@HaraldMeisner That you first have to prove the recursion theorem. Did you?
$endgroup$
– egreg
Nov 13 '15 at 12:50
$begingroup$
Yes, we are allowed to use recursion
$endgroup$
– Harald Meisner
Nov 13 '15 at 13:00
$begingroup$
@HaraldMeisner Good for you, but why doing a complicated proof when a simpler one is available?
$endgroup$
– egreg
Nov 13 '15 at 13:25
add a comment |
$begingroup$
The sequence you introduce is not necessary and, moreover, building it requires recursion.
Suppose $A$ has no least element. Consider the set
$$
A^*={ninmathbb{N}:n<a,text{for all $ain A$}}
$$
Note that $Acap A^*=emptyset$, because if $ain Acap A^*$ we would have $a<a$, a contradiction.
We prove by induction that $nin A^*$, for all $ninmathbb{N}$.
$0in A^*$; indeed, if $0notin A^*$, there exists $ain A$ with $ale0$; thus $0in A$ and $A$ has a least element.
Suppose $nin A^*$. If $n+1notin A^*$, there exists $ain A$ with $ale n+1$. Since $nin A^*$ we have $n<a$ and therefore $a=n+1$. Then $a=n+1$ is the least element of $A$.
Therefore $A^*=mathbb{N}$ and so $A$ is empty.
If your natural numbers start at $1$, the proof is exactly the same.
The proof relies on the fact that “$n<ale n+1$ implies $a=n+1$”, that in turn is the same as “$0<ale 1$ implies $a=1$. Indeed, since $ane0$, we have $a=b+1$, for some $b$; thus $b+1le 1$ and therefore $ble0$, which implies $b=0$ and so $a=1$.
answered Nov 13 '15 at 1:08
egregegreg
181k1485203
$endgroup$
The sequence you introduce is not necessary and, moreover, building it requires recursion.
Suppose $A$ has no least element. Consider the set
$$
A^*={ninmathbb{N}:n<a,text{for all $ain A$}}
$$
Note that $Acap A^*=emptyset$, because if $ain Acap A^*$ we would have $a<a$, a contradiction.
We prove by induction that $nin A^*$, for all $ninmathbb{N}$.
$0in A^*$; indeed, if $0notin A^*$, there exists $ain A$ with $ale0$; thus $0in A$ and $A$ has a least element.
Suppose $nin A^*$. If $n+1notin A^*$, there exists $ain A$ with $ale n+1$. Since $nin A^*$ we have $n<a$ and therefore $a=n+1$. Then $a=n+1$ is the least element of $A$.
Therefore $A^*=mathbb{N}$ and so $A$ is empty.
If your natural numbers start at $1$, the proof is exactly the same.
The proof relies on the fact that “$n<ale n+1$ implies $a=n+1$”, that in turn is the same as “$0<ale 1$ implies $a=1$. Indeed, since $ane0$, we have $a=b+1$, for some $b$; thus $b+1le 1$ and therefore $ble0$, which implies $b=0$ and so $a=1$.
answered Nov 13 '15 at 1:08
egregegreg
181k1485203
answered Nov 13 '15 at 1:08
egregegreg
181k1485203
answered Nov 13 '15 at 1:08
egregegreg
181k1485203
answered Nov 13 '15 at 1:08
egregegreg
181k1485203
181k1485203
$begingroup$
Hello egreg, what's the problem with recursion in my proof?
$endgroup$
– Harald Meisner
Nov 13 '15 at 12:26
$begingroup$
@HaraldMeisner That you first have to prove the recursion theorem. Did you?
$endgroup$
– egreg
Nov 13 '15 at 12:50
$begingroup$
Yes, we are allowed to use recursion
$endgroup$
– Harald Meisner
Nov 13 '15 at 13:00
$begingroup$
@HaraldMeisner Good for you, but why doing a complicated proof when a simpler one is available?
$endgroup$
– egreg
Nov 13 '15 at 13:25
add a comment |
$begingroup$
Hello egreg, what's the problem with recursion in my proof?
$endgroup$
– Harald Meisner
Nov 13 '15 at 12:26
$begingroup$
@HaraldMeisner That you first have to prove the recursion theorem. Did you?
$endgroup$
– egreg
Nov 13 '15 at 12:50
$begingroup$
Yes, we are allowed to use recursion
$endgroup$
– Harald Meisner
Nov 13 '15 at 13:00
$begingroup$
@HaraldMeisner Good for you, but why doing a complicated proof when a simpler one is available?
$endgroup$
– egreg
Nov 13 '15 at 13:25
$begingroup$
Hello egreg, what's the problem with recursion in my proof?
$endgroup$
– Harald Meisner
Nov 13 '15 at 12:26
$begingroup$
Hello egreg, what's the problem with recursion in my proof?
$endgroup$
– Harald Meisner
Nov 13 '15 at 12:26
$begingroup$
@HaraldMeisner That you first have to prove the recursion theorem. Did you?
$endgroup$
– egreg
Nov 13 '15 at 12:50
$begingroup$
@HaraldMeisner That you first have to prove the recursion theorem. Did you?
$endgroup$
– egreg
Nov 13 '15 at 12:50
$begingroup$
Yes, we are allowed to use recursion
$endgroup$
– Harald Meisner
Nov 13 '15 at 13:00
$begingroup$
Yes, we are allowed to use recursion
$endgroup$
– Harald Meisner
Nov 13 '15 at 13:00
$begingroup$
@HaraldMeisner Good for you, but why doing a complicated proof when a simpler one is available?
$endgroup$
– egreg
Nov 13 '15 at 13:25
$begingroup$
@HaraldMeisner Good for you, but why doing a complicated proof when a simpler one is available?
$endgroup$
– egreg
Nov 13 '15 at 13:25
add a comment |
$begingroup$
Well, it might not be kosher to bring a baseball bat to a cricket game but:
$mathbb N subset mathbb R$ and the reals have the least upper bound property. A is bounded below by 0. so $x =inf A$ exists.
It's easy to show x is an integer. (Else there exists a $y$ such that $x < y < lceil xrceil$ so y is also a lower bound so $x$ is not inf.) And it's easy to show $x in A$. (Else $x + 1/10$ is also a lower bound and x is not inf.)
So $x = inf A$ and $x in A$ imply $x$ is the least element in A.
====
A bit more cricket:
Assume non-empty A has no minimum element.
We can do a downward induction to prove the following statement: For any integer m, there is an element of A that is less than m.
Sub-base case: Let a be in A. then for all m > a the statement is true because a < m.
Base case: as A does not have a minimum element, a is not the minimum element. So there is an element of A that is less than a.
Induction step: Assume the statement is true for m. The element of A less than m must be less than or equal to m - 1. If it isn't equal to m, than the there is an element of A less than m -1. If it is equal to m, then m is an element of A but it isn't the minimum element as there is no minimum element. So there is an element of A less than m - 1.
Hence this statement is true for all integers.
But it's not true for 0 or any negative integer.
So our assumption was wrong, and non-empty A has a minimum element.
answered Nov 13 '15 at 1:21
fleabloodfleablood
69.8k22685
$endgroup$
add a comment |
$begingroup$
Well, it might not be kosher to bring a baseball bat to a cricket game but:
$mathbb N subset mathbb R$ and the reals have the least upper bound property. A is bounded below by 0. so $x =inf A$ exists.
It's easy to show x is an integer. (Else there exists a $y$ such that $x < y < lceil xrceil$ so y is also a lower bound so $x$ is not inf.) And it's easy to show $x in A$. (Else $x + 1/10$ is also a lower bound and x is not inf.)
So $x = inf A$ and $x in A$ imply $x$ is the least element in A.
====
A bit more cricket:
Assume non-empty A has no minimum element.
We can do a downward induction to prove the following statement: For any integer m, there is an element of A that is less than m.
Sub-base case: Let a be in A. then for all m > a the statement is true because a < m.
Base case: as A does not have a minimum element, a is not the minimum element. So there is an element of A that is less than a.
Induction step: Assume the statement is true for m. The element of A less than m must be less than or equal to m - 1. If it isn't equal to m, than the there is an element of A less than m -1. If it is equal to m, then m is an element of A but it isn't the minimum element as there is no minimum element. So there is an element of A less than m - 1.
Hence this statement is true for all integers.
But it's not true for 0 or any negative integer.
So our assumption was wrong, and non-empty A has a minimum element.
answered Nov 13 '15 at 1:21
fleabloodfleablood
69.8k22685
$endgroup$
add a comment |
$begingroup$
Well, it might not be kosher to bring a baseball bat to a cricket game but:
$mathbb N subset mathbb R$ and the reals have the least upper bound property. A is bounded below by 0. so $x =inf A$ exists.
It's easy to show x is an integer. (Else there exists a $y$ such that $x < y < lceil xrceil$ so y is also a lower bound so $x$ is not inf.) And it's easy to show $x in A$. (Else $x + 1/10$ is also a lower bound and x is not inf.)
So $x = inf A$ and $x in A$ imply $x$ is the least element in A.
====
A bit more cricket:
Assume non-empty A has no minimum element.
We can do a downward induction to prove the following statement: For any integer m, there is an element of A that is less than m.
Sub-base case: Let a be in A. then for all m > a the statement is true because a < m.
Base case: as A does not have a minimum element, a is not the minimum element. So there is an element of A that is less than a.
Induction step: Assume the statement is true for m. The element of A less than m must be less than or equal to m - 1. If it isn't equal to m, than the there is an element of A less than m -1. If it is equal to m, then m is an element of A but it isn't the minimum element as there is no minimum element. So there is an element of A less than m - 1.
Hence this statement is true for all integers.
But it's not true for 0 or any negative integer.
So our assumption was wrong, and non-empty A has a minimum element.
answered Nov 13 '15 at 1:21
fleabloodfleablood
69.8k22685
$endgroup$
Well, it might not be kosher to bring a baseball bat to a cricket game but:
$mathbb N subset mathbb R$ and the reals have the least upper bound property. A is bounded below by 0. so $x =inf A$ exists.
It's easy to show x is an integer. (Else there exists a $y$ such that $x < y < lceil xrceil$ so y is also a lower bound so $x$ is not inf.) And it's easy to show $x in A$. (Else $x + 1/10$ is also a lower bound and x is not inf.)
So $x = inf A$ and $x in A$ imply $x$ is the least element in A.
====
A bit more cricket:
Assume non-empty A has no minimum element.
We can do a downward induction to prove the following statement: For any integer m, there is an element of A that is less than m.
Sub-base case: Let a be in A. then for all m > a the statement is true because a < m.
Base case: as A does not have a minimum element, a is not the minimum element. So there is an element of A that is less than a.
Induction step: Assume the statement is true for m. The element of A less than m must be less than or equal to m - 1. If it isn't equal to m, than the there is an element of A less than m -1. If it is equal to m, then m is an element of A but it isn't the minimum element as there is no minimum element. So there is an element of A less than m - 1.
Hence this statement is true for all integers.
But it's not true for 0 or any negative integer.
So our assumption was wrong, and non-empty A has a minimum element.
answered Nov 13 '15 at 1:21
fleabloodfleablood
69.8k22685
edited Nov 13 '15 at 2:21
answered Nov 13 '15 at 1:21
fleabloodfleablood
69.8k22685
answered Nov 13 '15 at 1:21
fleabloodfleablood
69.8k22685
answered Nov 13 '15 at 1:21
fleabloodfleablood
69.8k22685
69.8k22685
add a comment |
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.
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%2f1526610%2fevery-nonempty-subset-of-the-natural-numbers-has-a-least-number%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
$begingroup$
The denial of "Each nonempty subsets of N has a least element" is not what you have, it is instead "There is a specific nonempty subset B of N which does not have a least element. Go for the contradiction from there...
$endgroup$
– coffeemath
Nov 13 '15 at 0:39
$begingroup$
Hello coffemath, how would this change the proof itself?
$endgroup$
– Harald Meisner
Nov 13 '15 at 0:44