Mixing
Can mathematical induction be applied on any total order set?
$begingroup$
I found a statement said that the proposition "Mathematical induction can be applied on any total order set" is False.
(The place I found the statement might not be believable.)
This means that there is a counterexample where cannot the math induction be applied.
I didn't find out much information about the relation of Mathematical induction and total-ordered set. So I guess somewhere I thought wrong.
I have no robust concept about them though, however I thought that any total-ordered set can be applied math induction, stated with my naive intuition below:
Because Mathematical induction is based on well-ordering principle, which is applied on $mathbb{Z^+}$, I'd consider that any total-ordered set is isomorphic to $mathbb{Z^+}$. By applying a topological sort on the total-ordered set, we can get a chain. The chain is actually the longest path of the total ordered set, so it preserves the order property. The isomorphism $f$ can be defined by: For all elements $x$ in the total-ordered set, $f(x)=$ " $x$'s order number in the chain".
Hence, I "guess" that math induction can be applied on the total-ordered set,
based on the assumption that "If any set is isomorphic to $mathbb{Z^+}$, and that isomorphism preserves the order information, then math induction can be applied on it", which I cannot tell is correct or not.
Thanks for any hint and correction!
induction order-theory
asked Jan 31 at 9:08
OOD WaterballOOD Waterball
1325
$endgroup$
|
show 2 more comments
$begingroup$
I found a statement said that the proposition "Mathematical induction can be applied on any total order set" is False.
(The place I found the statement might not be believable.)
This means that there is a counterexample where cannot the math induction be applied.
I didn't find out much information about the relation of Mathematical induction and total-ordered set. So I guess somewhere I thought wrong.
I have no robust concept about them though, however I thought that any total-ordered set can be applied math induction, stated with my naive intuition below:
Because Mathematical induction is based on well-ordering principle, which is applied on $mathbb{Z^+}$, I'd consider that any total-ordered set is isomorphic to $mathbb{Z^+}$. By applying a topological sort on the total-ordered set, we can get a chain. The chain is actually the longest path of the total ordered set, so it preserves the order property. The isomorphism $f$ can be defined by: For all elements $x$ in the total-ordered set, $f(x)=$ " $x$'s order number in the chain".
Hence, I "guess" that math induction can be applied on the total-ordered set,
based on the assumption that "If any set is isomorphic to $mathbb{Z^+}$, and that isomorphism preserves the order information, then math induction can be applied on it", which I cannot tell is correct or not.
Thanks for any hint and correction!
induction order-theory
asked Jan 31 at 9:08
OOD WaterballOOD Waterball
1325
$endgroup$
5
$begingroup$
"total ordering" and "well-ordering" are not at all the same.
$endgroup$
– Tobias Kildetoft
Jan 31 at 9:11
5
$begingroup$
Try the real numbers. They are totally ordered. What is the "next real number" after $1$?
$endgroup$
– Arthur
Jan 31 at 9:11
$begingroup$
This will work only with ordered group that is countable
$endgroup$
– Shaq
Jan 31 at 9:22
1
$begingroup$
@Shaq Yeah, the rational numbers would like to have a word with you. (Technically it's possible, but it's rare to see it in action. Most often it's something like induction on the denominator instead of on the actual rational number.)
$endgroup$
– Arthur
Jan 31 at 9:30
1
$begingroup$
@Shaq "To put them ( the rationals) in chain" still is not well-ordering them. We "can put them" in chain (i.e., in a sequence) because we know they're countable, but we've no idea what a well order of them is and that's what we need to apply induction in a reasonable way.
$endgroup$
– DonAntonio
Jan 31 at 10:18
|
show 2 more comments
$begingroup$
I found a statement said that the proposition "Mathematical induction can be applied on any total order set" is False.
(The place I found the statement might not be believable.)
This means that there is a counterexample where cannot the math induction be applied.
I didn't find out much information about the relation of Mathematical induction and total-ordered set. So I guess somewhere I thought wrong.
I have no robust concept about them though, however I thought that any total-ordered set can be applied math induction, stated with my naive intuition below:
Because Mathematical induction is based on well-ordering principle, which is applied on $mathbb{Z^+}$, I'd consider that any total-ordered set is isomorphic to $mathbb{Z^+}$. By applying a topological sort on the total-ordered set, we can get a chain. The chain is actually the longest path of the total ordered set, so it preserves the order property. The isomorphism $f$ can be defined by: For all elements $x$ in the total-ordered set, $f(x)=$ " $x$'s order number in the chain".
Hence, I "guess" that math induction can be applied on the total-ordered set,
based on the assumption that "If any set is isomorphic to $mathbb{Z^+}$, and that isomorphism preserves the order information, then math induction can be applied on it", which I cannot tell is correct or not.
Thanks for any hint and correction!
induction order-theory
asked Jan 31 at 9:08
OOD WaterballOOD Waterball
1325
$endgroup$
I found a statement said that the proposition "Mathematical induction can be applied on any total order set" is False.
(The place I found the statement might not be believable.)
This means that there is a counterexample where cannot the math induction be applied.
I didn't find out much information about the relation of Mathematical induction and total-ordered set. So I guess somewhere I thought wrong.
I have no robust concept about them though, however I thought that any total-ordered set can be applied math induction, stated with my naive intuition below:
Because Mathematical induction is based on well-ordering principle, which is applied on $mathbb{Z^+}$, I'd consider that any total-ordered set is isomorphic to $mathbb{Z^+}$. By applying a topological sort on the total-ordered set, we can get a chain. The chain is actually the longest path of the total ordered set, so it preserves the order property. The isomorphism $f$ can be defined by: For all elements $x$ in the total-ordered set, $f(x)=$ " $x$'s order number in the chain".
Hence, I "guess" that math induction can be applied on the total-ordered set,
based on the assumption that "If any set is isomorphic to $mathbb{Z^+}$, and that isomorphism preserves the order information, then math induction can be applied on it", which I cannot tell is correct or not.
Thanks for any hint and correction!
induction order-theory
induction order-theory
asked Jan 31 at 9:08
OOD WaterballOOD Waterball
1325
asked Jan 31 at 9:08
OOD WaterballOOD Waterball
1325
edited Jan 31 at 9:12
OOD Waterball
asked Jan 31 at 9:08
OOD WaterballOOD Waterball
1325
asked Jan 31 at 9:08
OOD WaterballOOD Waterball
1325
asked Jan 31 at 9:08
OOD WaterballOOD Waterball
1325
1325
5
$begingroup$
"total ordering" and "well-ordering" are not at all the same.
$endgroup$
– Tobias Kildetoft
Jan 31 at 9:11
5
$begingroup$
Try the real numbers. They are totally ordered. What is the "next real number" after $1$?
$endgroup$
– Arthur
Jan 31 at 9:11
$begingroup$
This will work only with ordered group that is countable
$endgroup$
– Shaq
Jan 31 at 9:22
1
$begingroup$
@Shaq Yeah, the rational numbers would like to have a word with you. (Technically it's possible, but it's rare to see it in action. Most often it's something like induction on the denominator instead of on the actual rational number.)
$endgroup$
– Arthur
Jan 31 at 9:30
1
$begingroup$
@Shaq "To put them ( the rationals) in chain" still is not well-ordering them. We "can put them" in chain (i.e., in a sequence) because we know they're countable, but we've no idea what a well order of them is and that's what we need to apply induction in a reasonable way.
$endgroup$
– DonAntonio
Jan 31 at 10:18
|
show 2 more comments
5
$begingroup$
"total ordering" and "well-ordering" are not at all the same.
$endgroup$
– Tobias Kildetoft
Jan 31 at 9:11
5
$begingroup$
Try the real numbers. They are totally ordered. What is the "next real number" after $1$?
$endgroup$
– Arthur
Jan 31 at 9:11
$begingroup$
This will work only with ordered group that is countable
$endgroup$
– Shaq
Jan 31 at 9:22
1
$begingroup$
@Shaq Yeah, the rational numbers would like to have a word with you. (Technically it's possible, but it's rare to see it in action. Most often it's something like induction on the denominator instead of on the actual rational number.)
$endgroup$
– Arthur
Jan 31 at 9:30
1
$begingroup$
@Shaq "To put them ( the rationals) in chain" still is not well-ordering them. We "can put them" in chain (i.e., in a sequence) because we know they're countable, but we've no idea what a well order of them is and that's what we need to apply induction in a reasonable way.
$endgroup$
– DonAntonio
Jan 31 at 10:18
5
5
$begingroup$
"total ordering" and "well-ordering" are not at all the same.
$endgroup$
– Tobias Kildetoft
Jan 31 at 9:11
$begingroup$
"total ordering" and "well-ordering" are not at all the same.
$endgroup$
– Tobias Kildetoft
Jan 31 at 9:11
5
5
$begingroup$
Try the real numbers. They are totally ordered. What is the "next real number" after $1$?
$endgroup$
– Arthur
Jan 31 at 9:11
$begingroup$
Try the real numbers. They are totally ordered. What is the "next real number" after $1$?
$endgroup$
– Arthur
Jan 31 at 9:11
$begingroup$
This will work only with ordered group that is countable
$endgroup$
– Shaq
Jan 31 at 9:22
$begingroup$
This will work only with ordered group that is countable
$endgroup$
– Shaq
Jan 31 at 9:22
1
1
$begingroup$
@Shaq Yeah, the rational numbers would like to have a word with you. (Technically it's possible, but it's rare to see it in action. Most often it's something like induction on the denominator instead of on the actual rational number.)
$endgroup$
– Arthur
Jan 31 at 9:30
$begingroup$
@Shaq Yeah, the rational numbers would like to have a word with you. (Technically it's possible, but it's rare to see it in action. Most often it's something like induction on the denominator instead of on the actual rational number.)
$endgroup$
– Arthur
Jan 31 at 9:30
1
1
$begingroup$
@Shaq "To put them ( the rationals) in chain" still is not well-ordering them. We "can put them" in chain (i.e., in a sequence) because we know they're countable, but we've no idea what a well order of them is and that's what we need to apply induction in a reasonable way.
$endgroup$
– DonAntonio
Jan 31 at 10:18
$begingroup$
@Shaq "To put them ( the rationals) in chain" still is not well-ordering them. We "can put them" in chain (i.e., in a sequence) because we know they're countable, but we've no idea what a well order of them is and that's what we need to apply induction in a reasonable way.
$endgroup$
– DonAntonio
Jan 31 at 10:18
|
show 2 more comments
1 Answer
1
active
oldest
votes
$begingroup$
One very general form of induction is well-founded induction. Suppose $le$ well-founds $S$. Since any non-empty subset of $S$ has a $lt$-minimal element, contrapositively $$(forall xin S(xlt ytophi(x))tophi(y))toforall yin S(phi(y)).$$
One can't generalise this to total ordering, which doesn't guarantee an analogous property of $S$'s non-empty subsets.
However, one can sometimes induct without knowing how to well-found a set. For example, real induction relies on the fact that subsets of $Bbb R$ have infima and suprema.
answered Jan 31 at 9:27
J.G.J.G.
32.8k23250
$endgroup$
$begingroup$
"Real induction" is essentially just that a real interval is a connected space in the order topology ( because $Bbb R$ is order-dense in itself and any bounded non-empty subset has a $sup$ and $inf.$ E.g. if $C$ is an open cover of $[0,1]$ let $xin A$ iff $xin [0,1]$ and $[0,x]$ can be covered by a finite subset of $C.$ We show that $A$ is open-and-closed in the connected space $[0,1],$ and since $A$ is not empty (because $0in A$), therefore $A=[0,1].$...............+1
$endgroup$
– DanielWainfleet
Jan 31 at 11:21
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%2f3094670%2fcan-mathematical-induction-be-applied-on-any-total-order-set%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$
One very general form of induction is well-founded induction. Suppose $le$ well-founds $S$. Since any non-empty subset of $S$ has a $lt$-minimal element, contrapositively $$(forall xin S(xlt ytophi(x))tophi(y))toforall yin S(phi(y)).$$
One can't generalise this to total ordering, which doesn't guarantee an analogous property of $S$'s non-empty subsets.
However, one can sometimes induct without knowing how to well-found a set. For example, real induction relies on the fact that subsets of $Bbb R$ have infima and suprema.
answered Jan 31 at 9:27
J.G.J.G.
32.8k23250
$endgroup$
$begingroup$
"Real induction" is essentially just that a real interval is a connected space in the order topology ( because $Bbb R$ is order-dense in itself and any bounded non-empty subset has a $sup$ and $inf.$ E.g. if $C$ is an open cover of $[0,1]$ let $xin A$ iff $xin [0,1]$ and $[0,x]$ can be covered by a finite subset of $C.$ We show that $A$ is open-and-closed in the connected space $[0,1],$ and since $A$ is not empty (because $0in A$), therefore $A=[0,1].$...............+1
$endgroup$
– DanielWainfleet
Jan 31 at 11:21
add a comment |
$begingroup$
One very general form of induction is well-founded induction. Suppose $le$ well-founds $S$. Since any non-empty subset of $S$ has a $lt$-minimal element, contrapositively $$(forall xin S(xlt ytophi(x))tophi(y))toforall yin S(phi(y)).$$
One can't generalise this to total ordering, which doesn't guarantee an analogous property of $S$'s non-empty subsets.
However, one can sometimes induct without knowing how to well-found a set. For example, real induction relies on the fact that subsets of $Bbb R$ have infima and suprema.
answered Jan 31 at 9:27
J.G.J.G.
32.8k23250
$endgroup$
$begingroup$
"Real induction" is essentially just that a real interval is a connected space in the order topology ( because $Bbb R$ is order-dense in itself and any bounded non-empty subset has a $sup$ and $inf.$ E.g. if $C$ is an open cover of $[0,1]$ let $xin A$ iff $xin [0,1]$ and $[0,x]$ can be covered by a finite subset of $C.$ We show that $A$ is open-and-closed in the connected space $[0,1],$ and since $A$ is not empty (because $0in A$), therefore $A=[0,1].$...............+1
$endgroup$
– DanielWainfleet
Jan 31 at 11:21
add a comment |
$begingroup$
One very general form of induction is well-founded induction. Suppose $le$ well-founds $S$. Since any non-empty subset of $S$ has a $lt$-minimal element, contrapositively $$(forall xin S(xlt ytophi(x))tophi(y))toforall yin S(phi(y)).$$
One can't generalise this to total ordering, which doesn't guarantee an analogous property of $S$'s non-empty subsets.
However, one can sometimes induct without knowing how to well-found a set. For example, real induction relies on the fact that subsets of $Bbb R$ have infima and suprema.
answered Jan 31 at 9:27
J.G.J.G.
32.8k23250
$endgroup$
One very general form of induction is well-founded induction. Suppose $le$ well-founds $S$. Since any non-empty subset of $S$ has a $lt$-minimal element, contrapositively $$(forall xin S(xlt ytophi(x))tophi(y))toforall yin S(phi(y)).$$
One can't generalise this to total ordering, which doesn't guarantee an analogous property of $S$'s non-empty subsets.
However, one can sometimes induct without knowing how to well-found a set. For example, real induction relies on the fact that subsets of $Bbb R$ have infima and suprema.
answered Jan 31 at 9:27
J.G.J.G.
32.8k23250
edited Jan 31 at 12:32
answered Jan 31 at 9:27
J.G.J.G.
32.8k23250
answered Jan 31 at 9:27
J.G.J.G.
32.8k23250
answered Jan 31 at 9:27
J.G.J.G.
32.8k23250
32.8k23250
$begingroup$
"Real induction" is essentially just that a real interval is a connected space in the order topology ( because $Bbb R$ is order-dense in itself and any bounded non-empty subset has a $sup$ and $inf.$ E.g. if $C$ is an open cover of $[0,1]$ let $xin A$ iff $xin [0,1]$ and $[0,x]$ can be covered by a finite subset of $C.$ We show that $A$ is open-and-closed in the connected space $[0,1],$ and since $A$ is not empty (because $0in A$), therefore $A=[0,1].$...............+1
$endgroup$
– DanielWainfleet
Jan 31 at 11:21
add a comment |
$begingroup$
"Real induction" is essentially just that a real interval is a connected space in the order topology ( because $Bbb R$ is order-dense in itself and any bounded non-empty subset has a $sup$ and $inf.$ E.g. if $C$ is an open cover of $[0,1]$ let $xin A$ iff $xin [0,1]$ and $[0,x]$ can be covered by a finite subset of $C.$ We show that $A$ is open-and-closed in the connected space $[0,1],$ and since $A$ is not empty (because $0in A$), therefore $A=[0,1].$...............+1
$endgroup$
– DanielWainfleet
Jan 31 at 11:21
$begingroup$
"Real induction" is essentially just that a real interval is a connected space in the order topology ( because $Bbb R$ is order-dense in itself and any bounded non-empty subset has a $sup$ and $inf.$ E.g. if $C$ is an open cover of $[0,1]$ let $xin A$ iff $xin [0,1]$ and $[0,x]$ can be covered by a finite subset of $C.$ We show that $A$ is open-and-closed in the connected space $[0,1],$ and since $A$ is not empty (because $0in A$), therefore $A=[0,1].$...............+1
$endgroup$
– DanielWainfleet
Jan 31 at 11:21
$begingroup$
"Real induction" is essentially just that a real interval is a connected space in the order topology ( because $Bbb R$ is order-dense in itself and any bounded non-empty subset has a $sup$ and $inf.$ E.g. if $C$ is an open cover of $[0,1]$ let $xin A$ iff $xin [0,1]$ and $[0,x]$ can be covered by a finite subset of $C.$ We show that $A$ is open-and-closed in the connected space $[0,1],$ and since $A$ is not empty (because $0in A$), therefore $A=[0,1].$...............+1
$endgroup$
– DanielWainfleet
Jan 31 at 11:21
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%2f3094670%2fcan-mathematical-induction-be-applied-on-any-total-order-set%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
5
$begingroup$
"total ordering" and "well-ordering" are not at all the same.
$endgroup$
– Tobias Kildetoft
Jan 31 at 9:11
5
$begingroup$
Try the real numbers. They are totally ordered. What is the "next real number" after $1$?
$endgroup$
– Arthur
Jan 31 at 9:11
$begingroup$
This will work only with ordered group that is countable
$endgroup$
– Shaq
Jan 31 at 9:22
1
$begingroup$
@Shaq Yeah, the rational numbers would like to have a word with you. (Technically it's possible, but it's rare to see it in action. Most often it's something like induction on the denominator instead of on the actual rational number.)
$endgroup$
– Arthur
Jan 31 at 9:30
1
$begingroup$
@Shaq "To put them ( the rationals) in chain" still is not well-ordering them. We "can put them" in chain (i.e., in a sequence) because we know they're countable, but we've no idea what a well order of them is and that's what we need to apply induction in a reasonable way.
$endgroup$
– DonAntonio
Jan 31 at 10:18