Can we expand “induction principle” to a partial order $(X, leq)$?Induction on Real NumbersExistence of a well-ordered set with a special elementExamples of proofs by induction with respect to relations that are not strict total orders.Common Binary Relation that is not a partial orderMathematical structures with a canonical partial orderCan a partially ordered set always be partitioned by its chains?Are these partial order or total orders?Given a partial order $R$ on the set $A$, prove that there exists a total order $leq$ on $A$ such that $R subseteq le$Higher order partial orderPartially Ordered Set and Equivalence RelationshipCan mathematical induction be applied on any total order set?

The Staircase of Paint

Why did the HMS Bounty go back to a time when whales are already rare?

How can Trident be so inexpensive? Will it orbit Triton or just do a (slow) flyby?

Calculating Wattage for Resistor in High Frequency Application?

When were female captains banned from Starfleet?

How do you respond to a colleague from another team when they're wrongly expecting that you'll help them?

What is this called? Old film camera viewer?

Does a 'pending' US visa application constitute a denial?

Why is so much work done on numerical verification of the Riemann Hypothesis?

Why do we read the Megillah by night and by day?

Drawing ramified coverings with tikz

MTG Artifact and Enchantment Rulings

Has any country ever had 2 former presidents in jail simultaneously?

Can not upgrade Kali,not enough space in /var/cache/apt/archives

Are the IPv6 address space and IPv4 address space completely disjoint?

How is flyblackbird.com operating under Part 91K?

Footnote and citation at the end of a sentence

Should I outline or discovery write my stories?

Varistor? Purpose and principle

What should you do when eye contact makes your subordinate uncomfortable?

Offered money to buy a house, seller is asking for more to cover gap between their listing and mortgage owed

Non-trope happy ending?

How to explain what's wrong with this application of the chain rule?

A social experiment. What is the worst that can happen?



Can we expand “induction principle” to a partial order $(X, leq)$?


Induction on Real NumbersExistence of a well-ordered set with a special elementExamples of proofs by induction with respect to relations that are not strict total orders.Common Binary Relation that is not a partial orderMathematical structures with a canonical partial orderCan a partially ordered set always be partitioned by its chains?Are these partial order or total orders?Given a partial order $R$ on the set $A$, prove that there exists a total order $leq$ on $A$ such that $R subseteq le$Higher order partial orderPartially Ordered Set and Equivalence RelationshipCan mathematical induction be applied on any total order set?













4












$begingroup$


We know that every infinite can be made well-ordered with an unknown order.
Also we can expand the induction principle on any infinite set in
the sense that
it can made well ordered.
Now partially ordered set may not be a well ordered set with respect
to the partial order.
Let a partially ordered set $(X, leq)$ with respect to this particular
order $'leq'$ and suppose that this partial order $'leq '$ does not make the
set $X$ well-ordered.



My question is-



Can we expand "induction principle" to the partially order set $(X,leq)$ keeping
in mind that $(X,leq)$ is not well ordered?



I have great confusion here.










share|cite|improve this question











$endgroup$











  • $begingroup$
    Supposing the answer were "yes", why do you think one would have stated the principle for well-orders in the first place? Definitions and hypotheses usually have a reason.
    $endgroup$
    – Marc van Leeuwen
    Mar 20 at 12:56











  • $begingroup$
    @MarcvanLeeuwen, I did not get you. Can you elaborate it?
    $endgroup$
    – M. A. SARKAR
    Mar 21 at 4:26










  • $begingroup$
    For comparison, if the law says that you may drive car provided you have a valid driver's licence, and you ask whether more generally people can legally drive when they have no driver's licence, then you can expect a negative answer. If the answer were "yes", what would be the point of a driver's licence in the first place ?
    $endgroup$
    – Marc van Leeuwen
    Mar 21 at 4:57










  • $begingroup$
    @MarcvanLeeuwen, Can you elaborate it mathematically just like other users rather than your philosophically view?
    $endgroup$
    – M. A. SARKAR
    Mar 21 at 6:44










  • $begingroup$
    Mine was not a technical mathematical comment, so no I cannot elaborate on it mathematically. If you don't like my comments, feel free to ignore them.
    $endgroup$
    – Marc van Leeuwen
    Mar 21 at 7:41















4












$begingroup$


We know that every infinite can be made well-ordered with an unknown order.
Also we can expand the induction principle on any infinite set in
the sense that
it can made well ordered.
Now partially ordered set may not be a well ordered set with respect
to the partial order.
Let a partially ordered set $(X, leq)$ with respect to this particular
order $'leq'$ and suppose that this partial order $'leq '$ does not make the
set $X$ well-ordered.



My question is-



Can we expand "induction principle" to the partially order set $(X,leq)$ keeping
in mind that $(X,leq)$ is not well ordered?



I have great confusion here.










share|cite|improve this question











$endgroup$











  • $begingroup$
    Supposing the answer were "yes", why do you think one would have stated the principle for well-orders in the first place? Definitions and hypotheses usually have a reason.
    $endgroup$
    – Marc van Leeuwen
    Mar 20 at 12:56











  • $begingroup$
    @MarcvanLeeuwen, I did not get you. Can you elaborate it?
    $endgroup$
    – M. A. SARKAR
    Mar 21 at 4:26










  • $begingroup$
    For comparison, if the law says that you may drive car provided you have a valid driver's licence, and you ask whether more generally people can legally drive when they have no driver's licence, then you can expect a negative answer. If the answer were "yes", what would be the point of a driver's licence in the first place ?
    $endgroup$
    – Marc van Leeuwen
    Mar 21 at 4:57










  • $begingroup$
    @MarcvanLeeuwen, Can you elaborate it mathematically just like other users rather than your philosophically view?
    $endgroup$
    – M. A. SARKAR
    Mar 21 at 6:44










  • $begingroup$
    Mine was not a technical mathematical comment, so no I cannot elaborate on it mathematically. If you don't like my comments, feel free to ignore them.
    $endgroup$
    – Marc van Leeuwen
    Mar 21 at 7:41













4












4








4


1



$begingroup$


We know that every infinite can be made well-ordered with an unknown order.
Also we can expand the induction principle on any infinite set in
the sense that
it can made well ordered.
Now partially ordered set may not be a well ordered set with respect
to the partial order.
Let a partially ordered set $(X, leq)$ with respect to this particular
order $'leq'$ and suppose that this partial order $'leq '$ does not make the
set $X$ well-ordered.



My question is-



Can we expand "induction principle" to the partially order set $(X,leq)$ keeping
in mind that $(X,leq)$ is not well ordered?



I have great confusion here.










share|cite|improve this question











$endgroup$




We know that every infinite can be made well-ordered with an unknown order.
Also we can expand the induction principle on any infinite set in
the sense that
it can made well ordered.
Now partially ordered set may not be a well ordered set with respect
to the partial order.
Let a partially ordered set $(X, leq)$ with respect to this particular
order $'leq'$ and suppose that this partial order $'leq '$ does not make the
set $X$ well-ordered.



My question is-



Can we expand "induction principle" to the partially order set $(X,leq)$ keeping
in mind that $(X,leq)$ is not well ordered?



I have great confusion here.







elementary-set-theory order-theory






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Mar 20 at 13:44









user21820

39.7k543157




39.7k543157










asked Mar 20 at 8:36









M. A. SARKARM. A. SARKAR

2,4341819




2,4341819











  • $begingroup$
    Supposing the answer were "yes", why do you think one would have stated the principle for well-orders in the first place? Definitions and hypotheses usually have a reason.
    $endgroup$
    – Marc van Leeuwen
    Mar 20 at 12:56











  • $begingroup$
    @MarcvanLeeuwen, I did not get you. Can you elaborate it?
    $endgroup$
    – M. A. SARKAR
    Mar 21 at 4:26










  • $begingroup$
    For comparison, if the law says that you may drive car provided you have a valid driver's licence, and you ask whether more generally people can legally drive when they have no driver's licence, then you can expect a negative answer. If the answer were "yes", what would be the point of a driver's licence in the first place ?
    $endgroup$
    – Marc van Leeuwen
    Mar 21 at 4:57










  • $begingroup$
    @MarcvanLeeuwen, Can you elaborate it mathematically just like other users rather than your philosophically view?
    $endgroup$
    – M. A. SARKAR
    Mar 21 at 6:44










  • $begingroup$
    Mine was not a technical mathematical comment, so no I cannot elaborate on it mathematically. If you don't like my comments, feel free to ignore them.
    $endgroup$
    – Marc van Leeuwen
    Mar 21 at 7:41
















  • $begingroup$
    Supposing the answer were "yes", why do you think one would have stated the principle for well-orders in the first place? Definitions and hypotheses usually have a reason.
    $endgroup$
    – Marc van Leeuwen
    Mar 20 at 12:56











  • $begingroup$
    @MarcvanLeeuwen, I did not get you. Can you elaborate it?
    $endgroup$
    – M. A. SARKAR
    Mar 21 at 4:26










  • $begingroup$
    For comparison, if the law says that you may drive car provided you have a valid driver's licence, and you ask whether more generally people can legally drive when they have no driver's licence, then you can expect a negative answer. If the answer were "yes", what would be the point of a driver's licence in the first place ?
    $endgroup$
    – Marc van Leeuwen
    Mar 21 at 4:57










  • $begingroup$
    @MarcvanLeeuwen, Can you elaborate it mathematically just like other users rather than your philosophically view?
    $endgroup$
    – M. A. SARKAR
    Mar 21 at 6:44










  • $begingroup$
    Mine was not a technical mathematical comment, so no I cannot elaborate on it mathematically. If you don't like my comments, feel free to ignore them.
    $endgroup$
    – Marc van Leeuwen
    Mar 21 at 7:41















$begingroup$
Supposing the answer were "yes", why do you think one would have stated the principle for well-orders in the first place? Definitions and hypotheses usually have a reason.
$endgroup$
– Marc van Leeuwen
Mar 20 at 12:56





$begingroup$
Supposing the answer were "yes", why do you think one would have stated the principle for well-orders in the first place? Definitions and hypotheses usually have a reason.
$endgroup$
– Marc van Leeuwen
Mar 20 at 12:56













$begingroup$
@MarcvanLeeuwen, I did not get you. Can you elaborate it?
$endgroup$
– M. A. SARKAR
Mar 21 at 4:26




$begingroup$
@MarcvanLeeuwen, I did not get you. Can you elaborate it?
$endgroup$
– M. A. SARKAR
Mar 21 at 4:26












$begingroup$
For comparison, if the law says that you may drive car provided you have a valid driver's licence, and you ask whether more generally people can legally drive when they have no driver's licence, then you can expect a negative answer. If the answer were "yes", what would be the point of a driver's licence in the first place ?
$endgroup$
– Marc van Leeuwen
Mar 21 at 4:57




$begingroup$
For comparison, if the law says that you may drive car provided you have a valid driver's licence, and you ask whether more generally people can legally drive when they have no driver's licence, then you can expect a negative answer. If the answer were "yes", what would be the point of a driver's licence in the first place ?
$endgroup$
– Marc van Leeuwen
Mar 21 at 4:57












$begingroup$
@MarcvanLeeuwen, Can you elaborate it mathematically just like other users rather than your philosophically view?
$endgroup$
– M. A. SARKAR
Mar 21 at 6:44




$begingroup$
@MarcvanLeeuwen, Can you elaborate it mathematically just like other users rather than your philosophically view?
$endgroup$
– M. A. SARKAR
Mar 21 at 6:44












$begingroup$
Mine was not a technical mathematical comment, so no I cannot elaborate on it mathematically. If you don't like my comments, feel free to ignore them.
$endgroup$
– Marc van Leeuwen
Mar 21 at 7:41




$begingroup$
Mine was not a technical mathematical comment, so no I cannot elaborate on it mathematically. If you don't like my comments, feel free to ignore them.
$endgroup$
– Marc van Leeuwen
Mar 21 at 7:41










3 Answers
3






active

oldest

votes


















4












$begingroup$

We can't even do induction on a total order if it's not well-ordered. Like on $Bbb Q$ or $Bbb R$ with the standard order. So in general a partial order is out of the question.



One could impose a well-ordering-like requirement on the partial order (every non-empty subset of $X$ has a minimal element), and then it is called a well-founded partial order. In that case one can indeed induct on a partial order.






share|cite|improve this answer











$endgroup$












  • $begingroup$
    It is nice. I am talking that relation $rho$ which makes $X$ poset but well-ordered. Can we have induction on $X$ with respect to $rho$ ?
    $endgroup$
    – M. A. SARKAR
    Mar 20 at 9:08







  • 1




    $begingroup$
    @Arthur You can do some inductions in some totally ordered sets that are not well-ordered. For example, on the reals. Therefore, your first and second sentences are false. The third sentence is also false, since you can also do induction in well-founded sets, which might not be totaly ordered.
    $endgroup$
    – user647486
    Mar 20 at 9:15











  • $begingroup$
    @user, my question is for arbitrary poset
    $endgroup$
    – M. A. SARKAR
    Mar 20 at 9:15







  • 1




    $begingroup$
    @user647486: you can do induction on any set, if you are allowed to choose your own definition of “doing induction”. The “induction on real numbers” you link is a very nice principle, but it isn’t the most standard sense of “doing induction”, which (as this answer correctly says) fails over the reals and other non-well-founded orderings. The only shortcoming in this answer is its suggestion that well-foundedness and induction for partial orders are something novel or speculative — in fact they’re long-established and well-studied.
    $endgroup$
    – Peter LeFanu Lumsdaine
    Mar 20 at 13:28







  • 1




    $begingroup$
    @user647486 "no difference between the statement of induction on the reals and strong induction" seems a bit much. I agree that one can do induction-like arguments on the reals under certain conditions, but I think it's a bit of a stretch to say it's the same as conventional induction.
    $endgroup$
    – Arthur
    Mar 20 at 13:54



















11












$begingroup$

Induction can be performed over any relation $R$ over a set $X$, provided the relation is well-founded: any subset $S subseteq X$ must have a minimal element with respect to $R$. A minimal element of $S$ is an element $m in S$ such that there is no $x in S$ with $x R m$.



For total orders, being well-founded is equivalent to being well-ordered.



Note: Assuming the axiom of dependent choice (a weaker form of the axiom of choice), one can show that a relation is well-founded if and only if there is no infinite descending chain of elements in $X$ (with respect to the relation $R$).



Note 2: The Axiom of Choice is equivalent to stating that any set can be well-ordered. Thus, one could in principle do (transfinite) induction over any set.



The problem is that the Axiom of Choice is not constructive, which means that no one knows anything about what the well-ordering given by the axiom looks like. Therefore, it is in practice impossible to use that well-ordering.






share|cite|improve this answer










New contributor




Daniel Ahlsén is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






$endgroup$












  • $begingroup$
    So on totally ordered set , we can do induction
    $endgroup$
    – M. A. SARKAR
    Mar 20 at 9:17






  • 3




    $begingroup$
    No, not in general, since not all total orders are well-founded. The standard order on the integers is one example. Well-foundedness is equivalent to well-orderedness for total orders.
    $endgroup$
    – Daniel Ahlsén
    Mar 20 at 10:22


















0












$begingroup$

One way to view the principle of induction is a manner to show there can be no counterexamples to the proposition being proved. In general the set of values for which a proposition fails can be any subset. So if you want to be able to show a proposition is valid by establishing that there are no minimal counterexamples, which is what the principle of strong induction does, then one needs an ordering with the property that every non-empty set has a minimal element. For total orderings, that is the property of being a well ordering. For partial orderings, it is the property of being well-founded. So if you want to employ an inductive argument of strong induction type (showing that validity of a proposition for all $y<x$ implies validity for $x$), then nothing weaker than having a well founded partial ordering will allow for such an induction principle to be valid.



To see why, take a partial ordering for which some non-empty set $S$ has no minimal element. Then for the proposition $P$ for which $P(x)$ says $xnotin S$ it is true that $forall x: (forall y: (y<xto P(y))to P(x)$ (because it is equivalent to the negation of "$S$ has a minimal element"), but the conclusion of the induction principle, namely $forall x:P(x)$, is false. Therefore the strong induction principle is not valid in such a situation.






share|cite|improve this answer









$endgroup$












    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%2f3155166%2fcan-we-expand-induction-principle-to-a-partial-order-x-leq%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









    4












    $begingroup$

    We can't even do induction on a total order if it's not well-ordered. Like on $Bbb Q$ or $Bbb R$ with the standard order. So in general a partial order is out of the question.



    One could impose a well-ordering-like requirement on the partial order (every non-empty subset of $X$ has a minimal element), and then it is called a well-founded partial order. In that case one can indeed induct on a partial order.






    share|cite|improve this answer











    $endgroup$












    • $begingroup$
      It is nice. I am talking that relation $rho$ which makes $X$ poset but well-ordered. Can we have induction on $X$ with respect to $rho$ ?
      $endgroup$
      – M. A. SARKAR
      Mar 20 at 9:08







    • 1




      $begingroup$
      @Arthur You can do some inductions in some totally ordered sets that are not well-ordered. For example, on the reals. Therefore, your first and second sentences are false. The third sentence is also false, since you can also do induction in well-founded sets, which might not be totaly ordered.
      $endgroup$
      – user647486
      Mar 20 at 9:15











    • $begingroup$
      @user, my question is for arbitrary poset
      $endgroup$
      – M. A. SARKAR
      Mar 20 at 9:15







    • 1




      $begingroup$
      @user647486: you can do induction on any set, if you are allowed to choose your own definition of “doing induction”. The “induction on real numbers” you link is a very nice principle, but it isn’t the most standard sense of “doing induction”, which (as this answer correctly says) fails over the reals and other non-well-founded orderings. The only shortcoming in this answer is its suggestion that well-foundedness and induction for partial orders are something novel or speculative — in fact they’re long-established and well-studied.
      $endgroup$
      – Peter LeFanu Lumsdaine
      Mar 20 at 13:28







    • 1




      $begingroup$
      @user647486 "no difference between the statement of induction on the reals and strong induction" seems a bit much. I agree that one can do induction-like arguments on the reals under certain conditions, but I think it's a bit of a stretch to say it's the same as conventional induction.
      $endgroup$
      – Arthur
      Mar 20 at 13:54
















    4












    $begingroup$

    We can't even do induction on a total order if it's not well-ordered. Like on $Bbb Q$ or $Bbb R$ with the standard order. So in general a partial order is out of the question.



    One could impose a well-ordering-like requirement on the partial order (every non-empty subset of $X$ has a minimal element), and then it is called a well-founded partial order. In that case one can indeed induct on a partial order.






    share|cite|improve this answer











    $endgroup$












    • $begingroup$
      It is nice. I am talking that relation $rho$ which makes $X$ poset but well-ordered. Can we have induction on $X$ with respect to $rho$ ?
      $endgroup$
      – M. A. SARKAR
      Mar 20 at 9:08







    • 1




      $begingroup$
      @Arthur You can do some inductions in some totally ordered sets that are not well-ordered. For example, on the reals. Therefore, your first and second sentences are false. The third sentence is also false, since you can also do induction in well-founded sets, which might not be totaly ordered.
      $endgroup$
      – user647486
      Mar 20 at 9:15











    • $begingroup$
      @user, my question is for arbitrary poset
      $endgroup$
      – M. A. SARKAR
      Mar 20 at 9:15







    • 1




      $begingroup$
      @user647486: you can do induction on any set, if you are allowed to choose your own definition of “doing induction”. The “induction on real numbers” you link is a very nice principle, but it isn’t the most standard sense of “doing induction”, which (as this answer correctly says) fails over the reals and other non-well-founded orderings. The only shortcoming in this answer is its suggestion that well-foundedness and induction for partial orders are something novel or speculative — in fact they’re long-established and well-studied.
      $endgroup$
      – Peter LeFanu Lumsdaine
      Mar 20 at 13:28







    • 1




      $begingroup$
      @user647486 "no difference between the statement of induction on the reals and strong induction" seems a bit much. I agree that one can do induction-like arguments on the reals under certain conditions, but I think it's a bit of a stretch to say it's the same as conventional induction.
      $endgroup$
      – Arthur
      Mar 20 at 13:54














    4












    4








    4





    $begingroup$

    We can't even do induction on a total order if it's not well-ordered. Like on $Bbb Q$ or $Bbb R$ with the standard order. So in general a partial order is out of the question.



    One could impose a well-ordering-like requirement on the partial order (every non-empty subset of $X$ has a minimal element), and then it is called a well-founded partial order. In that case one can indeed induct on a partial order.






    share|cite|improve this answer











    $endgroup$



    We can't even do induction on a total order if it's not well-ordered. Like on $Bbb Q$ or $Bbb R$ with the standard order. So in general a partial order is out of the question.



    One could impose a well-ordering-like requirement on the partial order (every non-empty subset of $X$ has a minimal element), and then it is called a well-founded partial order. In that case one can indeed induct on a partial order.







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    edited Mar 20 at 13:52

























    answered Mar 20 at 8:56









    ArthurArthur

    119k7119202




    119k7119202











    • $begingroup$
      It is nice. I am talking that relation $rho$ which makes $X$ poset but well-ordered. Can we have induction on $X$ with respect to $rho$ ?
      $endgroup$
      – M. A. SARKAR
      Mar 20 at 9:08







    • 1




      $begingroup$
      @Arthur You can do some inductions in some totally ordered sets that are not well-ordered. For example, on the reals. Therefore, your first and second sentences are false. The third sentence is also false, since you can also do induction in well-founded sets, which might not be totaly ordered.
      $endgroup$
      – user647486
      Mar 20 at 9:15











    • $begingroup$
      @user, my question is for arbitrary poset
      $endgroup$
      – M. A. SARKAR
      Mar 20 at 9:15







    • 1




      $begingroup$
      @user647486: you can do induction on any set, if you are allowed to choose your own definition of “doing induction”. The “induction on real numbers” you link is a very nice principle, but it isn’t the most standard sense of “doing induction”, which (as this answer correctly says) fails over the reals and other non-well-founded orderings. The only shortcoming in this answer is its suggestion that well-foundedness and induction for partial orders are something novel or speculative — in fact they’re long-established and well-studied.
      $endgroup$
      – Peter LeFanu Lumsdaine
      Mar 20 at 13:28







    • 1




      $begingroup$
      @user647486 "no difference between the statement of induction on the reals and strong induction" seems a bit much. I agree that one can do induction-like arguments on the reals under certain conditions, but I think it's a bit of a stretch to say it's the same as conventional induction.
      $endgroup$
      – Arthur
      Mar 20 at 13:54

















    • $begingroup$
      It is nice. I am talking that relation $rho$ which makes $X$ poset but well-ordered. Can we have induction on $X$ with respect to $rho$ ?
      $endgroup$
      – M. A. SARKAR
      Mar 20 at 9:08







    • 1




      $begingroup$
      @Arthur You can do some inductions in some totally ordered sets that are not well-ordered. For example, on the reals. Therefore, your first and second sentences are false. The third sentence is also false, since you can also do induction in well-founded sets, which might not be totaly ordered.
      $endgroup$
      – user647486
      Mar 20 at 9:15











    • $begingroup$
      @user, my question is for arbitrary poset
      $endgroup$
      – M. A. SARKAR
      Mar 20 at 9:15







    • 1




      $begingroup$
      @user647486: you can do induction on any set, if you are allowed to choose your own definition of “doing induction”. The “induction on real numbers” you link is a very nice principle, but it isn’t the most standard sense of “doing induction”, which (as this answer correctly says) fails over the reals and other non-well-founded orderings. The only shortcoming in this answer is its suggestion that well-foundedness and induction for partial orders are something novel or speculative — in fact they’re long-established and well-studied.
      $endgroup$
      – Peter LeFanu Lumsdaine
      Mar 20 at 13:28







    • 1




      $begingroup$
      @user647486 "no difference between the statement of induction on the reals and strong induction" seems a bit much. I agree that one can do induction-like arguments on the reals under certain conditions, but I think it's a bit of a stretch to say it's the same as conventional induction.
      $endgroup$
      – Arthur
      Mar 20 at 13:54
















    $begingroup$
    It is nice. I am talking that relation $rho$ which makes $X$ poset but well-ordered. Can we have induction on $X$ with respect to $rho$ ?
    $endgroup$
    – M. A. SARKAR
    Mar 20 at 9:08





    $begingroup$
    It is nice. I am talking that relation $rho$ which makes $X$ poset but well-ordered. Can we have induction on $X$ with respect to $rho$ ?
    $endgroup$
    – M. A. SARKAR
    Mar 20 at 9:08





    1




    1




    $begingroup$
    @Arthur You can do some inductions in some totally ordered sets that are not well-ordered. For example, on the reals. Therefore, your first and second sentences are false. The third sentence is also false, since you can also do induction in well-founded sets, which might not be totaly ordered.
    $endgroup$
    – user647486
    Mar 20 at 9:15





    $begingroup$
    @Arthur You can do some inductions in some totally ordered sets that are not well-ordered. For example, on the reals. Therefore, your first and second sentences are false. The third sentence is also false, since you can also do induction in well-founded sets, which might not be totaly ordered.
    $endgroup$
    – user647486
    Mar 20 at 9:15













    $begingroup$
    @user, my question is for arbitrary poset
    $endgroup$
    – M. A. SARKAR
    Mar 20 at 9:15





    $begingroup$
    @user, my question is for arbitrary poset
    $endgroup$
    – M. A. SARKAR
    Mar 20 at 9:15





    1




    1




    $begingroup$
    @user647486: you can do induction on any set, if you are allowed to choose your own definition of “doing induction”. The “induction on real numbers” you link is a very nice principle, but it isn’t the most standard sense of “doing induction”, which (as this answer correctly says) fails over the reals and other non-well-founded orderings. The only shortcoming in this answer is its suggestion that well-foundedness and induction for partial orders are something novel or speculative — in fact they’re long-established and well-studied.
    $endgroup$
    – Peter LeFanu Lumsdaine
    Mar 20 at 13:28





    $begingroup$
    @user647486: you can do induction on any set, if you are allowed to choose your own definition of “doing induction”. The “induction on real numbers” you link is a very nice principle, but it isn’t the most standard sense of “doing induction”, which (as this answer correctly says) fails over the reals and other non-well-founded orderings. The only shortcoming in this answer is its suggestion that well-foundedness and induction for partial orders are something novel or speculative — in fact they’re long-established and well-studied.
    $endgroup$
    – Peter LeFanu Lumsdaine
    Mar 20 at 13:28





    1




    1




    $begingroup$
    @user647486 "no difference between the statement of induction on the reals and strong induction" seems a bit much. I agree that one can do induction-like arguments on the reals under certain conditions, but I think it's a bit of a stretch to say it's the same as conventional induction.
    $endgroup$
    – Arthur
    Mar 20 at 13:54





    $begingroup$
    @user647486 "no difference between the statement of induction on the reals and strong induction" seems a bit much. I agree that one can do induction-like arguments on the reals under certain conditions, but I think it's a bit of a stretch to say it's the same as conventional induction.
    $endgroup$
    – Arthur
    Mar 20 at 13:54












    11












    $begingroup$

    Induction can be performed over any relation $R$ over a set $X$, provided the relation is well-founded: any subset $S subseteq X$ must have a minimal element with respect to $R$. A minimal element of $S$ is an element $m in S$ such that there is no $x in S$ with $x R m$.



    For total orders, being well-founded is equivalent to being well-ordered.



    Note: Assuming the axiom of dependent choice (a weaker form of the axiom of choice), one can show that a relation is well-founded if and only if there is no infinite descending chain of elements in $X$ (with respect to the relation $R$).



    Note 2: The Axiom of Choice is equivalent to stating that any set can be well-ordered. Thus, one could in principle do (transfinite) induction over any set.



    The problem is that the Axiom of Choice is not constructive, which means that no one knows anything about what the well-ordering given by the axiom looks like. Therefore, it is in practice impossible to use that well-ordering.






    share|cite|improve this answer










    New contributor




    Daniel Ahlsén is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.






    $endgroup$












    • $begingroup$
      So on totally ordered set , we can do induction
      $endgroup$
      – M. A. SARKAR
      Mar 20 at 9:17






    • 3




      $begingroup$
      No, not in general, since not all total orders are well-founded. The standard order on the integers is one example. Well-foundedness is equivalent to well-orderedness for total orders.
      $endgroup$
      – Daniel Ahlsén
      Mar 20 at 10:22















    11












    $begingroup$

    Induction can be performed over any relation $R$ over a set $X$, provided the relation is well-founded: any subset $S subseteq X$ must have a minimal element with respect to $R$. A minimal element of $S$ is an element $m in S$ such that there is no $x in S$ with $x R m$.



    For total orders, being well-founded is equivalent to being well-ordered.



    Note: Assuming the axiom of dependent choice (a weaker form of the axiom of choice), one can show that a relation is well-founded if and only if there is no infinite descending chain of elements in $X$ (with respect to the relation $R$).



    Note 2: The Axiom of Choice is equivalent to stating that any set can be well-ordered. Thus, one could in principle do (transfinite) induction over any set.



    The problem is that the Axiom of Choice is not constructive, which means that no one knows anything about what the well-ordering given by the axiom looks like. Therefore, it is in practice impossible to use that well-ordering.






    share|cite|improve this answer










    New contributor




    Daniel Ahlsén is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.






    $endgroup$












    • $begingroup$
      So on totally ordered set , we can do induction
      $endgroup$
      – M. A. SARKAR
      Mar 20 at 9:17






    • 3




      $begingroup$
      No, not in general, since not all total orders are well-founded. The standard order on the integers is one example. Well-foundedness is equivalent to well-orderedness for total orders.
      $endgroup$
      – Daniel Ahlsén
      Mar 20 at 10:22













    11












    11








    11





    $begingroup$

    Induction can be performed over any relation $R$ over a set $X$, provided the relation is well-founded: any subset $S subseteq X$ must have a minimal element with respect to $R$. A minimal element of $S$ is an element $m in S$ such that there is no $x in S$ with $x R m$.



    For total orders, being well-founded is equivalent to being well-ordered.



    Note: Assuming the axiom of dependent choice (a weaker form of the axiom of choice), one can show that a relation is well-founded if and only if there is no infinite descending chain of elements in $X$ (with respect to the relation $R$).



    Note 2: The Axiom of Choice is equivalent to stating that any set can be well-ordered. Thus, one could in principle do (transfinite) induction over any set.



    The problem is that the Axiom of Choice is not constructive, which means that no one knows anything about what the well-ordering given by the axiom looks like. Therefore, it is in practice impossible to use that well-ordering.






    share|cite|improve this answer










    New contributor




    Daniel Ahlsén is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.






    $endgroup$



    Induction can be performed over any relation $R$ over a set $X$, provided the relation is well-founded: any subset $S subseteq X$ must have a minimal element with respect to $R$. A minimal element of $S$ is an element $m in S$ such that there is no $x in S$ with $x R m$.



    For total orders, being well-founded is equivalent to being well-ordered.



    Note: Assuming the axiom of dependent choice (a weaker form of the axiom of choice), one can show that a relation is well-founded if and only if there is no infinite descending chain of elements in $X$ (with respect to the relation $R$).



    Note 2: The Axiom of Choice is equivalent to stating that any set can be well-ordered. Thus, one could in principle do (transfinite) induction over any set.



    The problem is that the Axiom of Choice is not constructive, which means that no one knows anything about what the well-ordering given by the axiom looks like. Therefore, it is in practice impossible to use that well-ordering.







    share|cite|improve this answer










    New contributor




    Daniel Ahlsén is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.









    share|cite|improve this answer



    share|cite|improve this answer








    edited Mar 21 at 8:45





















    New contributor




    Daniel Ahlsén is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.









    answered Mar 20 at 9:04









    Daniel AhlsénDaniel Ahlsén

    3265




    3265




    New contributor




    Daniel Ahlsén is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.





    New contributor





    Daniel Ahlsén is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.






    Daniel Ahlsén is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.











    • $begingroup$
      So on totally ordered set , we can do induction
      $endgroup$
      – M. A. SARKAR
      Mar 20 at 9:17






    • 3




      $begingroup$
      No, not in general, since not all total orders are well-founded. The standard order on the integers is one example. Well-foundedness is equivalent to well-orderedness for total orders.
      $endgroup$
      – Daniel Ahlsén
      Mar 20 at 10:22
















    • $begingroup$
      So on totally ordered set , we can do induction
      $endgroup$
      – M. A. SARKAR
      Mar 20 at 9:17






    • 3




      $begingroup$
      No, not in general, since not all total orders are well-founded. The standard order on the integers is one example. Well-foundedness is equivalent to well-orderedness for total orders.
      $endgroup$
      – Daniel Ahlsén
      Mar 20 at 10:22















    $begingroup$
    So on totally ordered set , we can do induction
    $endgroup$
    – M. A. SARKAR
    Mar 20 at 9:17




    $begingroup$
    So on totally ordered set , we can do induction
    $endgroup$
    – M. A. SARKAR
    Mar 20 at 9:17




    3




    3




    $begingroup$
    No, not in general, since not all total orders are well-founded. The standard order on the integers is one example. Well-foundedness is equivalent to well-orderedness for total orders.
    $endgroup$
    – Daniel Ahlsén
    Mar 20 at 10:22




    $begingroup$
    No, not in general, since not all total orders are well-founded. The standard order on the integers is one example. Well-foundedness is equivalent to well-orderedness for total orders.
    $endgroup$
    – Daniel Ahlsén
    Mar 20 at 10:22











    0












    $begingroup$

    One way to view the principle of induction is a manner to show there can be no counterexamples to the proposition being proved. In general the set of values for which a proposition fails can be any subset. So if you want to be able to show a proposition is valid by establishing that there are no minimal counterexamples, which is what the principle of strong induction does, then one needs an ordering with the property that every non-empty set has a minimal element. For total orderings, that is the property of being a well ordering. For partial orderings, it is the property of being well-founded. So if you want to employ an inductive argument of strong induction type (showing that validity of a proposition for all $y<x$ implies validity for $x$), then nothing weaker than having a well founded partial ordering will allow for such an induction principle to be valid.



    To see why, take a partial ordering for which some non-empty set $S$ has no minimal element. Then for the proposition $P$ for which $P(x)$ says $xnotin S$ it is true that $forall x: (forall y: (y<xto P(y))to P(x)$ (because it is equivalent to the negation of "$S$ has a minimal element"), but the conclusion of the induction principle, namely $forall x:P(x)$, is false. Therefore the strong induction principle is not valid in such a situation.






    share|cite|improve this answer









    $endgroup$

















      0












      $begingroup$

      One way to view the principle of induction is a manner to show there can be no counterexamples to the proposition being proved. In general the set of values for which a proposition fails can be any subset. So if you want to be able to show a proposition is valid by establishing that there are no minimal counterexamples, which is what the principle of strong induction does, then one needs an ordering with the property that every non-empty set has a minimal element. For total orderings, that is the property of being a well ordering. For partial orderings, it is the property of being well-founded. So if you want to employ an inductive argument of strong induction type (showing that validity of a proposition for all $y<x$ implies validity for $x$), then nothing weaker than having a well founded partial ordering will allow for such an induction principle to be valid.



      To see why, take a partial ordering for which some non-empty set $S$ has no minimal element. Then for the proposition $P$ for which $P(x)$ says $xnotin S$ it is true that $forall x: (forall y: (y<xto P(y))to P(x)$ (because it is equivalent to the negation of "$S$ has a minimal element"), but the conclusion of the induction principle, namely $forall x:P(x)$, is false. Therefore the strong induction principle is not valid in such a situation.






      share|cite|improve this answer









      $endgroup$















        0












        0








        0





        $begingroup$

        One way to view the principle of induction is a manner to show there can be no counterexamples to the proposition being proved. In general the set of values for which a proposition fails can be any subset. So if you want to be able to show a proposition is valid by establishing that there are no minimal counterexamples, which is what the principle of strong induction does, then one needs an ordering with the property that every non-empty set has a minimal element. For total orderings, that is the property of being a well ordering. For partial orderings, it is the property of being well-founded. So if you want to employ an inductive argument of strong induction type (showing that validity of a proposition for all $y<x$ implies validity for $x$), then nothing weaker than having a well founded partial ordering will allow for such an induction principle to be valid.



        To see why, take a partial ordering for which some non-empty set $S$ has no minimal element. Then for the proposition $P$ for which $P(x)$ says $xnotin S$ it is true that $forall x: (forall y: (y<xto P(y))to P(x)$ (because it is equivalent to the negation of "$S$ has a minimal element"), but the conclusion of the induction principle, namely $forall x:P(x)$, is false. Therefore the strong induction principle is not valid in such a situation.






        share|cite|improve this answer









        $endgroup$



        One way to view the principle of induction is a manner to show there can be no counterexamples to the proposition being proved. In general the set of values for which a proposition fails can be any subset. So if you want to be able to show a proposition is valid by establishing that there are no minimal counterexamples, which is what the principle of strong induction does, then one needs an ordering with the property that every non-empty set has a minimal element. For total orderings, that is the property of being a well ordering. For partial orderings, it is the property of being well-founded. So if you want to employ an inductive argument of strong induction type (showing that validity of a proposition for all $y<x$ implies validity for $x$), then nothing weaker than having a well founded partial ordering will allow for such an induction principle to be valid.



        To see why, take a partial ordering for which some non-empty set $S$ has no minimal element. Then for the proposition $P$ for which $P(x)$ says $xnotin S$ it is true that $forall x: (forall y: (y<xto P(y))to P(x)$ (because it is equivalent to the negation of "$S$ has a minimal element"), but the conclusion of the induction principle, namely $forall x:P(x)$, is false. Therefore the strong induction principle is not valid in such a situation.







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered Mar 21 at 7:58









        Marc van LeeuwenMarc van Leeuwen

        88.5k5111229




        88.5k5111229



























            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.




            draft saved


            draft discarded














            StackExchange.ready(
            function ()
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3155166%2fcan-we-expand-induction-principle-to-a-partial-order-x-leq%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

            Adding axes to figuresAdding axes labels to LaTeX figuresLaTeX equivalent of ConTeXt buffersRotate a node but not its content: the case of the ellipse decorationHow to define the default vertical distance between nodes?TikZ scaling graphic and adjust node position and keep font sizeNumerical conditional within tikz keys?adding axes to shapesAlign axes across subfiguresAdding figures with a certain orderLine up nested tikz enviroments or how to get rid of themAdding axes labels to LaTeX figures

            Tähtien Talli Jäsenet | Lähteet | NavigointivalikkoSuomen Hippos – Tähtien Talli

            Do these cracks on my tires look bad? The Next CEO of Stack OverflowDry rot tire should I replace?Having to replace tiresFishtailed so easily? Bad tires? ABS?Filling the tires with something other than air, to avoid puncture hassles?Used Michelin tires safe to install?Do these tyre cracks necessitate replacement?Rumbling noise: tires or mechanicalIs it possible to fix noisy feathered tires?Are bad winter tires still better than summer tires in winter?Torque converter failure - Related to replacing only 2 tires?Why use snow tires on all 4 wheels on 2-wheel-drive cars?