Finite Sets Induction
$begingroup$
Every finite set of natural numbers has a maximum.
Hint: Induct on the number of elements. A set with n + 1 elements is a set of n elements union a set of 1 element.
What is the P(n) statement and how does the induction step work?
proof-verification proof-writing
edited Dec 3 '18 at 2:09
Ethan Bolker
42.2k548111
asked Dec 3 '18 at 2:08
Robert KleinRobert Klein
65
$endgroup$
add a comment |
$begingroup$
Every finite set of natural numbers has a maximum.
Hint: Induct on the number of elements. A set with n + 1 elements is a set of n elements union a set of 1 element.
What is the P(n) statement and how does the induction step work?
proof-verification proof-writing
edited Dec 3 '18 at 2:09
Ethan Bolker
42.2k548111
asked Dec 3 '18 at 2:08
Robert KleinRobert Klein
65
$endgroup$
$begingroup$
P(n) = every set of $n$ elements has a maximum element. And if $P(k)$ is true. And $M$ be a set of $k+1$ elements and $x in M$ then $M -{x}$ is a set of $k$ elements so it has a max. Can you figure out how to prove $M = (M - {x}) cup {x}$ has a max?
$endgroup$
– fleablood
Dec 3 '18 at 2:25
add a comment |
$begingroup$
Every finite set of natural numbers has a maximum.
Hint: Induct on the number of elements. A set with n + 1 elements is a set of n elements union a set of 1 element.
What is the P(n) statement and how does the induction step work?
proof-verification proof-writing
edited Dec 3 '18 at 2:09
Ethan Bolker
42.2k548111
asked Dec 3 '18 at 2:08
Robert KleinRobert Klein
65
$endgroup$
Every finite set of natural numbers has a maximum.
Hint: Induct on the number of elements. A set with n + 1 elements is a set of n elements union a set of 1 element.
What is the P(n) statement and how does the induction step work?
proof-verification proof-writing
proof-verification proof-writing
edited Dec 3 '18 at 2:09
Ethan Bolker
42.2k548111
asked Dec 3 '18 at 2:08
Robert KleinRobert Klein
65
edited Dec 3 '18 at 2:09
Ethan Bolker
42.2k548111
asked Dec 3 '18 at 2:08
Robert KleinRobert Klein
65
edited Dec 3 '18 at 2:09
Ethan Bolker
42.2k548111
edited Dec 3 '18 at 2:09
Ethan Bolker
42.2k548111
edited Dec 3 '18 at 2:09
Ethan Bolker
42.2k548111
42.2k548111
asked Dec 3 '18 at 2:08
Robert KleinRobert Klein
65
asked Dec 3 '18 at 2:08
Robert KleinRobert Klein
65
asked Dec 3 '18 at 2:08
Robert KleinRobert Klein
65
65
$begingroup$
P(n) = every set of $n$ elements has a maximum element. And if $P(k)$ is true. And $M$ be a set of $k+1$ elements and $x in M$ then $M -{x}$ is a set of $k$ elements so it has a max. Can you figure out how to prove $M = (M - {x}) cup {x}$ has a max?
$endgroup$
– fleablood
Dec 3 '18 at 2:25
add a comment |
$begingroup$
P(n) = every set of $n$ elements has a maximum element. And if $P(k)$ is true. And $M$ be a set of $k+1$ elements and $x in M$ then $M -{x}$ is a set of $k$ elements so it has a max. Can you figure out how to prove $M = (M - {x}) cup {x}$ has a max?
$endgroup$
– fleablood
Dec 3 '18 at 2:25
$begingroup$
P(n) = every set of $n$ elements has a maximum element. And if $P(k)$ is true. And $M$ be a set of $k+1$ elements and $x in M$ then $M -{x}$ is a set of $k$ elements so it has a max. Can you figure out how to prove $M = (M - {x}) cup {x}$ has a max?
$endgroup$
– fleablood
Dec 3 '18 at 2:25
$begingroup$
P(n) = every set of $n$ elements has a maximum element. And if $P(k)$ is true. And $M$ be a set of $k+1$ elements and $x in M$ then $M -{x}$ is a set of $k$ elements so it has a max. Can you figure out how to prove $M = (M - {x}) cup {x}$ has a max?
$endgroup$
– fleablood
Dec 3 '18 at 2:25
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
P(n) = every set of $n$ elements has a maximum element. And if $P(k)$ is true. And $M$ be a set of $k+1$ elements and $x in M$ then $M -{x}$ is a set of $k$ elements so it has a max. Can you figure out how to prove $M = (M - {x}) cup {x}$ has a max?
Hint: What is $max(max (M-{x}), x)$? What happens if $x le max (M-{x})$? Can you show that $M$ has a max? If so what is it? What happens if $x > max (M-{x})$? Can you show that $M$ has a max? Is so what is it?
Are there any other possibilities?
Base Step:
$P(1)$ if $M$ is a set with one element it has a maximum.
Proof: If $M = {n}$ has one element than $n$ is maximal. ($n ge x$ for all $x in M$ as $n$ is the only $x in M$ and $n ge n$.)
Hypothese for $n = k$ an immediate consecuences:
Assume $P(k)$. Assume $M$ has $k + 1$ elements. Let $x in M$. Then $M - {x}$ has $k$ elements. So a $M - {x}$ has a maximal element. Call it $m$.
Induction step:
$x ne m$ as $m in M - {x}$ and $xnot in M - {x}$. So either $x < m$ which would mean $m ge x$ and $m ge y$ for all $y in M - {x}$ so $m ge y$ for all $y in( M - {x}) cup {x} = M$. So $M$ has a maximal element.
.
But if $x > m$ then $xge y$ for all $y in M - {x}$ and $x ge x$ so $x ge y$ for all $y in( M - {x}) cup {x} = M$. So $M$ has a maximal element.
answered Dec 3 '18 at 2:29
fleabloodfleablood
69.2k22685
$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%2f3023507%2ffinite-sets-induction%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
$begingroup$
P(n) = every set of $n$ elements has a maximum element. And if $P(k)$ is true. And $M$ be a set of $k+1$ elements and $x in M$ then $M -{x}$ is a set of $k$ elements so it has a max. Can you figure out how to prove $M = (M - {x}) cup {x}$ has a max?
Hint: What is $max(max (M-{x}), x)$? What happens if $x le max (M-{x})$? Can you show that $M$ has a max? If so what is it? What happens if $x > max (M-{x})$? Can you show that $M$ has a max? Is so what is it?
Are there any other possibilities?
Base Step:
$P(1)$ if $M$ is a set with one element it has a maximum.
Proof: If $M = {n}$ has one element than $n$ is maximal. ($n ge x$ for all $x in M$ as $n$ is the only $x in M$ and $n ge n$.)
Hypothese for $n = k$ an immediate consecuences:
Assume $P(k)$. Assume $M$ has $k + 1$ elements. Let $x in M$. Then $M - {x}$ has $k$ elements. So a $M - {x}$ has a maximal element. Call it $m$.
Induction step:
$x ne m$ as $m in M - {x}$ and $xnot in M - {x}$. So either $x < m$ which would mean $m ge x$ and $m ge y$ for all $y in M - {x}$ so $m ge y$ for all $y in( M - {x}) cup {x} = M$. So $M$ has a maximal element.
.
But if $x > m$ then $xge y$ for all $y in M - {x}$ and $x ge x$ so $x ge y$ for all $y in( M - {x}) cup {x} = M$. So $M$ has a maximal element.
answered Dec 3 '18 at 2:29
fleabloodfleablood
69.2k22685
$endgroup$
add a comment |
$begingroup$
P(n) = every set of $n$ elements has a maximum element. And if $P(k)$ is true. And $M$ be a set of $k+1$ elements and $x in M$ then $M -{x}$ is a set of $k$ elements so it has a max. Can you figure out how to prove $M = (M - {x}) cup {x}$ has a max?
Hint: What is $max(max (M-{x}), x)$? What happens if $x le max (M-{x})$? Can you show that $M$ has a max? If so what is it? What happens if $x > max (M-{x})$? Can you show that $M$ has a max? Is so what is it?
Are there any other possibilities?
Base Step:
$P(1)$ if $M$ is a set with one element it has a maximum.
Proof: If $M = {n}$ has one element than $n$ is maximal. ($n ge x$ for all $x in M$ as $n$ is the only $x in M$ and $n ge n$.)
Hypothese for $n = k$ an immediate consecuences:
Assume $P(k)$. Assume $M$ has $k + 1$ elements. Let $x in M$. Then $M - {x}$ has $k$ elements. So a $M - {x}$ has a maximal element. Call it $m$.
Induction step:
$x ne m$ as $m in M - {x}$ and $xnot in M - {x}$. So either $x < m$ which would mean $m ge x$ and $m ge y$ for all $y in M - {x}$ so $m ge y$ for all $y in( M - {x}) cup {x} = M$. So $M$ has a maximal element.
.
But if $x > m$ then $xge y$ for all $y in M - {x}$ and $x ge x$ so $x ge y$ for all $y in( M - {x}) cup {x} = M$. So $M$ has a maximal element.
answered Dec 3 '18 at 2:29
fleabloodfleablood
69.2k22685
$endgroup$
add a comment |
$begingroup$
P(n) = every set of $n$ elements has a maximum element. And if $P(k)$ is true. And $M$ be a set of $k+1$ elements and $x in M$ then $M -{x}$ is a set of $k$ elements so it has a max. Can you figure out how to prove $M = (M - {x}) cup {x}$ has a max?
Hint: What is $max(max (M-{x}), x)$? What happens if $x le max (M-{x})$? Can you show that $M$ has a max? If so what is it? What happens if $x > max (M-{x})$? Can you show that $M$ has a max? Is so what is it?
Are there any other possibilities?
Base Step:
$P(1)$ if $M$ is a set with one element it has a maximum.
Proof: If $M = {n}$ has one element than $n$ is maximal. ($n ge x$ for all $x in M$ as $n$ is the only $x in M$ and $n ge n$.)
Hypothese for $n = k$ an immediate consecuences:
Assume $P(k)$. Assume $M$ has $k + 1$ elements. Let $x in M$. Then $M - {x}$ has $k$ elements. So a $M - {x}$ has a maximal element. Call it $m$.
Induction step:
$x ne m$ as $m in M - {x}$ and $xnot in M - {x}$. So either $x < m$ which would mean $m ge x$ and $m ge y$ for all $y in M - {x}$ so $m ge y$ for all $y in( M - {x}) cup {x} = M$. So $M$ has a maximal element.
.
But if $x > m$ then $xge y$ for all $y in M - {x}$ and $x ge x$ so $x ge y$ for all $y in( M - {x}) cup {x} = M$. So $M$ has a maximal element.
answered Dec 3 '18 at 2:29
fleabloodfleablood
69.2k22685
$endgroup$
P(n) = every set of $n$ elements has a maximum element. And if $P(k)$ is true. And $M$ be a set of $k+1$ elements and $x in M$ then $M -{x}$ is a set of $k$ elements so it has a max. Can you figure out how to prove $M = (M - {x}) cup {x}$ has a max?
Hint: What is $max(max (M-{x}), x)$? What happens if $x le max (M-{x})$? Can you show that $M$ has a max? If so what is it? What happens if $x > max (M-{x})$? Can you show that $M$ has a max? Is so what is it?
Are there any other possibilities?
Base Step:
$P(1)$ if $M$ is a set with one element it has a maximum.
Proof: If $M = {n}$ has one element than $n$ is maximal. ($n ge x$ for all $x in M$ as $n$ is the only $x in M$ and $n ge n$.)
Hypothese for $n = k$ an immediate consecuences:
Assume $P(k)$. Assume $M$ has $k + 1$ elements. Let $x in M$. Then $M - {x}$ has $k$ elements. So a $M - {x}$ has a maximal element. Call it $m$.
Induction step:
$x ne m$ as $m in M - {x}$ and $xnot in M - {x}$. So either $x < m$ which would mean $m ge x$ and $m ge y$ for all $y in M - {x}$ so $m ge y$ for all $y in( M - {x}) cup {x} = M$. So $M$ has a maximal element.
.
But if $x > m$ then $xge y$ for all $y in M - {x}$ and $x ge x$ so $x ge y$ for all $y in( M - {x}) cup {x} = M$. So $M$ has a maximal element.
answered Dec 3 '18 at 2:29
fleabloodfleablood
69.2k22685
edited Dec 3 '18 at 2:41
answered Dec 3 '18 at 2:29
fleabloodfleablood
69.2k22685
answered Dec 3 '18 at 2:29
fleabloodfleablood
69.2k22685
answered Dec 3 '18 at 2:29
fleabloodfleablood
69.2k22685
69.2k22685
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%2f3023507%2ffinite-sets-induction%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$
P(n) = every set of $n$ elements has a maximum element. And if $P(k)$ is true. And $M$ be a set of $k+1$ elements and $x in M$ then $M -{x}$ is a set of $k$ elements so it has a max. Can you figure out how to prove $M = (M - {x}) cup {x}$ has a max?
$endgroup$
– fleablood
Dec 3 '18 at 2:25