What is an example of a proof by minimal counterexample?











up vote
7
down vote

favorite
1












I was reading about proof by infinite descent, and proof by minimal counterexample. My understanding of it is that we assume the existance of some smallest counterexample $A$ that disproves some proposition $P$, then go onto show that there is some smaller counterexample to this which to me seems like a mix of infinite descent and 'reverse proof by contradiction'.



My question is, how do we know that there might be some counterexample? Furthermore, are there any examples of this?










share|cite|improve this question




















  • 3




    If there aren't any counterexamples, the theorem is true, and we're done, so it's only the case where there is a counterexample that we have to deal with. This method of proof goes back (at least) to Fermat, who called it "proof by infinite descent." Google that, and you'll find lots of examples.
    – saulspatz
    Nov 17 at 19:14










  • Related: matheducators.stackexchange.com/questions/10021/…
    – Ethan Bolker
    Nov 17 at 19:25






  • 1




    Any uneven natural number is prime. Counterexample 9 = 3*3.
    – Uwe
    Nov 17 at 21:52










  • Are you referring to things like i.stack.imgur.com/RxeiH.png?
    – forest
    Nov 18 at 9:12






  • 2




    (If I understand correctly) "proof by minimal counterexample" proves that a minimal counterexample does not exist (wikipedia), and the 2 comments above are not correct.
    – user202729
    Nov 18 at 16:23















up vote
7
down vote

favorite
1












I was reading about proof by infinite descent, and proof by minimal counterexample. My understanding of it is that we assume the existance of some smallest counterexample $A$ that disproves some proposition $P$, then go onto show that there is some smaller counterexample to this which to me seems like a mix of infinite descent and 'reverse proof by contradiction'.



My question is, how do we know that there might be some counterexample? Furthermore, are there any examples of this?










share|cite|improve this question




















  • 3




    If there aren't any counterexamples, the theorem is true, and we're done, so it's only the case where there is a counterexample that we have to deal with. This method of proof goes back (at least) to Fermat, who called it "proof by infinite descent." Google that, and you'll find lots of examples.
    – saulspatz
    Nov 17 at 19:14










  • Related: matheducators.stackexchange.com/questions/10021/…
    – Ethan Bolker
    Nov 17 at 19:25






  • 1




    Any uneven natural number is prime. Counterexample 9 = 3*3.
    – Uwe
    Nov 17 at 21:52










  • Are you referring to things like i.stack.imgur.com/RxeiH.png?
    – forest
    Nov 18 at 9:12






  • 2




    (If I understand correctly) "proof by minimal counterexample" proves that a minimal counterexample does not exist (wikipedia), and the 2 comments above are not correct.
    – user202729
    Nov 18 at 16:23













up vote
7
down vote

favorite
1









up vote
7
down vote

favorite
1






1





I was reading about proof by infinite descent, and proof by minimal counterexample. My understanding of it is that we assume the existance of some smallest counterexample $A$ that disproves some proposition $P$, then go onto show that there is some smaller counterexample to this which to me seems like a mix of infinite descent and 'reverse proof by contradiction'.



My question is, how do we know that there might be some counterexample? Furthermore, are there any examples of this?










share|cite|improve this question















I was reading about proof by infinite descent, and proof by minimal counterexample. My understanding of it is that we assume the existance of some smallest counterexample $A$ that disproves some proposition $P$, then go onto show that there is some smaller counterexample to this which to me seems like a mix of infinite descent and 'reverse proof by contradiction'.



My question is, how do we know that there might be some counterexample? Furthermore, are there any examples of this?







proof-writing examples-counterexamples infinite-descent






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Nov 17 at 22:00









José Carlos Santos

143k20112209




143k20112209










asked Nov 17 at 19:09









Jonathan Low

415




415








  • 3




    If there aren't any counterexamples, the theorem is true, and we're done, so it's only the case where there is a counterexample that we have to deal with. This method of proof goes back (at least) to Fermat, who called it "proof by infinite descent." Google that, and you'll find lots of examples.
    – saulspatz
    Nov 17 at 19:14










  • Related: matheducators.stackexchange.com/questions/10021/…
    – Ethan Bolker
    Nov 17 at 19:25






  • 1




    Any uneven natural number is prime. Counterexample 9 = 3*3.
    – Uwe
    Nov 17 at 21:52










  • Are you referring to things like i.stack.imgur.com/RxeiH.png?
    – forest
    Nov 18 at 9:12






  • 2




    (If I understand correctly) "proof by minimal counterexample" proves that a minimal counterexample does not exist (wikipedia), and the 2 comments above are not correct.
    – user202729
    Nov 18 at 16:23














  • 3




    If there aren't any counterexamples, the theorem is true, and we're done, so it's only the case where there is a counterexample that we have to deal with. This method of proof goes back (at least) to Fermat, who called it "proof by infinite descent." Google that, and you'll find lots of examples.
    – saulspatz
    Nov 17 at 19:14










  • Related: matheducators.stackexchange.com/questions/10021/…
    – Ethan Bolker
    Nov 17 at 19:25






  • 1




    Any uneven natural number is prime. Counterexample 9 = 3*3.
    – Uwe
    Nov 17 at 21:52










  • Are you referring to things like i.stack.imgur.com/RxeiH.png?
    – forest
    Nov 18 at 9:12






  • 2




    (If I understand correctly) "proof by minimal counterexample" proves that a minimal counterexample does not exist (wikipedia), and the 2 comments above are not correct.
    – user202729
    Nov 18 at 16:23








3




3




If there aren't any counterexamples, the theorem is true, and we're done, so it's only the case where there is a counterexample that we have to deal with. This method of proof goes back (at least) to Fermat, who called it "proof by infinite descent." Google that, and you'll find lots of examples.
– saulspatz
Nov 17 at 19:14




If there aren't any counterexamples, the theorem is true, and we're done, so it's only the case where there is a counterexample that we have to deal with. This method of proof goes back (at least) to Fermat, who called it "proof by infinite descent." Google that, and you'll find lots of examples.
– saulspatz
Nov 17 at 19:14












Related: matheducators.stackexchange.com/questions/10021/…
– Ethan Bolker
Nov 17 at 19:25




Related: matheducators.stackexchange.com/questions/10021/…
– Ethan Bolker
Nov 17 at 19:25




1




1




Any uneven natural number is prime. Counterexample 9 = 3*3.
– Uwe
Nov 17 at 21:52




Any uneven natural number is prime. Counterexample 9 = 3*3.
– Uwe
Nov 17 at 21:52












Are you referring to things like i.stack.imgur.com/RxeiH.png?
– forest
Nov 18 at 9:12




Are you referring to things like i.stack.imgur.com/RxeiH.png?
– forest
Nov 18 at 9:12




2




2




(If I understand correctly) "proof by minimal counterexample" proves that a minimal counterexample does not exist (wikipedia), and the 2 comments above are not correct.
– user202729
Nov 18 at 16:23




(If I understand correctly) "proof by minimal counterexample" proves that a minimal counterexample does not exist (wikipedia), and the 2 comments above are not correct.
– user202729
Nov 18 at 16:23










4 Answers
4






active

oldest

votes

















up vote
23
down vote



accepted










Consider, for instance, the statment




Every $ninmathbb{N}setminus{1}$ can be written as a product of prime numbers (including the case in which there's a single prime number appearing only once).




Suppose otherwise. Then there would be a smallest $ninmathbb{N}setminus{1}$ that would not be possible the express as a product of prime numbers. In particular, this implies that $n$ cannot be a prime number. Since $n$ is also not $1$, it can be written as $atimes b$, where $a,bin{2,3,ldots,n-1}$. But, since $n$ is the smallest counterexample, neither $a$ nor $b$ are counterexamples and therefore both of them can be written as a product of prime numbers. But then $n(=atimes b)$ can be written in such a way too.






share|cite|improve this answer






























    up vote
    13
    down vote













    Such a proof will often go as follows.




    • Assume for contradiction that there is a counterexample to $P$ within some well-ordered set $X$.

    • Consider the (certainly non-empty) set of all $X$ which are counterexamples to $P$. This set has a least element (that's what it means to be a well-order), so…

    • Consider the smallest counterexample.

    • Show that you can find a smaller counterexample.

    • Contradiction, so there can't have been any counterexamples to $P$ after all.

    • Therefore $P$ is true.






    share|cite|improve this answer




























      up vote
      10
      down vote













      Assume the $sqrt{2}$ is rational then there are whole numbers $(a,b)$ such that $sqrt{2}=a/b$ and $a$ is the smallest number with this property but then we find that $a/2, b/2$ are also whole numbers with this property. So there is a smaller example.



      I think this must be the example people are the most familiar with and it's a kind of infinite descent even though we often don't refer to it as such.






      share|cite|improve this answer

















      • 1




        In this proof how do we know that $a/2$, $b/2$ are also whole numbers? (I'm probably missing something obvious.)
        – LarsH
        Nov 18 at 0:50








      • 1




        It isn't obvious but it is infamous. I can't find it for you now because I am out to dinner. But you can find by looking up the classic proof regarding the irrationality of square root of 2. Its in Bertrand Russell's history of western philosophy...
        – Mason
        Nov 18 at 0:57






      • 3




        @LarsH ny squaring the equation and wiggling it a bit you can prove that a is even, and then that b is also even.
        – Dan M.
        Nov 18 at 2:29










      • Here are the details
        – Mason
        Nov 18 at 2:38






      • 1




        @LarsH We have $2 = a^2/b^2$ hence $2b^2 = a^2$ from which: $a^2$ is even, hence $a$ is even, hence $a^2$ is a multiple of 4, hence $b^2=a^2/2$ is even, hence $b$ is even. So, both $a,b$ are even.
        – chi
        Nov 18 at 11:11




















      up vote
      1
      down vote













      A fundamental example in number theory is descent by (Euclidean) division with remainder (or, equivalently, by repeated subtraction), as in the following basic result.



      Lemma $ $ Let $,S,$ be a nonempty set of positive integers that is closed under subtraction $> 0,,$ i.e. for all $ ,n,min S, ,$ $ n > m Rightarrow n-m, in, S.,$ Then the least $ :ellin S,$ divides every element of $, S.$



      Proof ${bf 1}, $ If not there is a least nonmultiple $ ,nin S,,$ contra $ ,n-ell in S,$ is a nonmultiple of $ ,ell.$



      Proof ${bf 2}, , S,$ closed under subtraction $ ,Rightarrow,S,$ closed under remainder (mod), when it is $ne 0,$ since mod is simply repeated subtraction, i.e. $ abmod b, =, a - k b, =, a!-!b!-!b!-cdots! -!b.,$ Therefore $ ,nin S,$ $Rightarrow$ $ , (nbmod ell) = 0,,$ else it is in $, S,$ and smaller than $ ,ell,,$ contra minimality of $ ,ell.$



      Remark $ $ In a nutshell, two applications of induction yield the following inferences



      $begin{eqnarray}rm S closed under {bf subtraction} &:Rightarrow:&rm S closed under {bf mod} = remainder = repeated subtraction \
      &:Rightarrow:&rm S closed under {bf gcd} = repeated mod (Euclid's algorithm) end{eqnarray}$



      This yields Bezout's GCD identity: the set $ ,S,$ of integers of form $ ,a_1,x_1 + cdots + a_n x_n, x_iin mathbb Z,,$ is closed under subtraction so Lemma $Rightarrow$ every positive $ ,kin S,$ is divisible by $ ,d = $ least positive $ in S.,$ Therefore $ ,a_iin S$ $,Rightarrow,$ $ dmid a_i,,$ i.e. $ ,d,$ is a common divisor of all $ ,a_i,,$ necessarily the greatest such because $ cmid a_i$ $Rightarrow$ $ ,cmid d = a_!,x_1!+!cdots!+!a_nx_n$ $Rightarrow$ $ ,cle d.,$ When interpreted constructively, this yields the extended Euclidean algorithm for the gcd.






      share|cite|improve this answer





















        Your Answer





        StackExchange.ifUsing("editor", function () {
        return StackExchange.using("mathjaxEditing", function () {
        StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
        StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
        });
        });
        }, "mathjax-editing");

        StackExchange.ready(function() {
        var channelOptions = {
        tags: "".split(" "),
        id: "69"
        };
        initTagRenderer("".split(" "), "".split(" "), channelOptions);

        StackExchange.using("externalEditor", function() {
        // Have to fire editor after snippets, if snippets enabled
        if (StackExchange.settings.snippets.snippetsEnabled) {
        StackExchange.using("snippets", function() {
        createEditor();
        });
        }
        else {
        createEditor();
        }
        });

        function createEditor() {
        StackExchange.prepareEditor({
        heartbeatType: 'answer',
        convertImagesToLinks: true,
        noModals: true,
        showLowRepImageUploadWarning: true,
        reputationToPostImages: 10,
        bindNavPrevention: true,
        postfix: "",
        imageUploader: {
        brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
        contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
        allowUrls: true
        },
        noCode: true, onDemand: true,
        discardSelector: ".discard-answer"
        ,immediatelyShowMarkdownHelp:true
        });


        }
        });














        draft saved

        draft discarded


















        StackExchange.ready(
        function () {
        StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3002706%2fwhat-is-an-example-of-a-proof-by-minimal-counterexample%23new-answer', 'question_page');
        }
        );

        Post as a guest















        Required, but never shown

























        4 Answers
        4






        active

        oldest

        votes








        4 Answers
        4






        active

        oldest

        votes









        active

        oldest

        votes






        active

        oldest

        votes








        up vote
        23
        down vote



        accepted










        Consider, for instance, the statment




        Every $ninmathbb{N}setminus{1}$ can be written as a product of prime numbers (including the case in which there's a single prime number appearing only once).




        Suppose otherwise. Then there would be a smallest $ninmathbb{N}setminus{1}$ that would not be possible the express as a product of prime numbers. In particular, this implies that $n$ cannot be a prime number. Since $n$ is also not $1$, it can be written as $atimes b$, where $a,bin{2,3,ldots,n-1}$. But, since $n$ is the smallest counterexample, neither $a$ nor $b$ are counterexamples and therefore both of them can be written as a product of prime numbers. But then $n(=atimes b)$ can be written in such a way too.






        share|cite|improve this answer



























          up vote
          23
          down vote



          accepted










          Consider, for instance, the statment




          Every $ninmathbb{N}setminus{1}$ can be written as a product of prime numbers (including the case in which there's a single prime number appearing only once).




          Suppose otherwise. Then there would be a smallest $ninmathbb{N}setminus{1}$ that would not be possible the express as a product of prime numbers. In particular, this implies that $n$ cannot be a prime number. Since $n$ is also not $1$, it can be written as $atimes b$, where $a,bin{2,3,ldots,n-1}$. But, since $n$ is the smallest counterexample, neither $a$ nor $b$ are counterexamples and therefore both of them can be written as a product of prime numbers. But then $n(=atimes b)$ can be written in such a way too.






          share|cite|improve this answer

























            up vote
            23
            down vote



            accepted







            up vote
            23
            down vote



            accepted






            Consider, for instance, the statment




            Every $ninmathbb{N}setminus{1}$ can be written as a product of prime numbers (including the case in which there's a single prime number appearing only once).




            Suppose otherwise. Then there would be a smallest $ninmathbb{N}setminus{1}$ that would not be possible the express as a product of prime numbers. In particular, this implies that $n$ cannot be a prime number. Since $n$ is also not $1$, it can be written as $atimes b$, where $a,bin{2,3,ldots,n-1}$. But, since $n$ is the smallest counterexample, neither $a$ nor $b$ are counterexamples and therefore both of them can be written as a product of prime numbers. But then $n(=atimes b)$ can be written in such a way too.






            share|cite|improve this answer














            Consider, for instance, the statment




            Every $ninmathbb{N}setminus{1}$ can be written as a product of prime numbers (including the case in which there's a single prime number appearing only once).




            Suppose otherwise. Then there would be a smallest $ninmathbb{N}setminus{1}$ that would not be possible the express as a product of prime numbers. In particular, this implies that $n$ cannot be a prime number. Since $n$ is also not $1$, it can be written as $atimes b$, where $a,bin{2,3,ldots,n-1}$. But, since $n$ is the smallest counterexample, neither $a$ nor $b$ are counterexamples and therefore both of them can be written as a product of prime numbers. But then $n(=atimes b)$ can be written in such a way too.







            share|cite|improve this answer














            share|cite|improve this answer



            share|cite|improve this answer








            edited yesterday

























            answered Nov 17 at 19:16









            José Carlos Santos

            143k20112209




            143k20112209






















                up vote
                13
                down vote













                Such a proof will often go as follows.




                • Assume for contradiction that there is a counterexample to $P$ within some well-ordered set $X$.

                • Consider the (certainly non-empty) set of all $X$ which are counterexamples to $P$. This set has a least element (that's what it means to be a well-order), so…

                • Consider the smallest counterexample.

                • Show that you can find a smaller counterexample.

                • Contradiction, so there can't have been any counterexamples to $P$ after all.

                • Therefore $P$ is true.






                share|cite|improve this answer

























                  up vote
                  13
                  down vote













                  Such a proof will often go as follows.




                  • Assume for contradiction that there is a counterexample to $P$ within some well-ordered set $X$.

                  • Consider the (certainly non-empty) set of all $X$ which are counterexamples to $P$. This set has a least element (that's what it means to be a well-order), so…

                  • Consider the smallest counterexample.

                  • Show that you can find a smaller counterexample.

                  • Contradiction, so there can't have been any counterexamples to $P$ after all.

                  • Therefore $P$ is true.






                  share|cite|improve this answer























                    up vote
                    13
                    down vote










                    up vote
                    13
                    down vote









                    Such a proof will often go as follows.




                    • Assume for contradiction that there is a counterexample to $P$ within some well-ordered set $X$.

                    • Consider the (certainly non-empty) set of all $X$ which are counterexamples to $P$. This set has a least element (that's what it means to be a well-order), so…

                    • Consider the smallest counterexample.

                    • Show that you can find a smaller counterexample.

                    • Contradiction, so there can't have been any counterexamples to $P$ after all.

                    • Therefore $P$ is true.






                    share|cite|improve this answer












                    Such a proof will often go as follows.




                    • Assume for contradiction that there is a counterexample to $P$ within some well-ordered set $X$.

                    • Consider the (certainly non-empty) set of all $X$ which are counterexamples to $P$. This set has a least element (that's what it means to be a well-order), so…

                    • Consider the smallest counterexample.

                    • Show that you can find a smaller counterexample.

                    • Contradiction, so there can't have been any counterexamples to $P$ after all.

                    • Therefore $P$ is true.







                    share|cite|improve this answer












                    share|cite|improve this answer



                    share|cite|improve this answer










                    answered Nov 17 at 19:16









                    Patrick Stevens

                    28.1k52874




                    28.1k52874






















                        up vote
                        10
                        down vote













                        Assume the $sqrt{2}$ is rational then there are whole numbers $(a,b)$ such that $sqrt{2}=a/b$ and $a$ is the smallest number with this property but then we find that $a/2, b/2$ are also whole numbers with this property. So there is a smaller example.



                        I think this must be the example people are the most familiar with and it's a kind of infinite descent even though we often don't refer to it as such.






                        share|cite|improve this answer

















                        • 1




                          In this proof how do we know that $a/2$, $b/2$ are also whole numbers? (I'm probably missing something obvious.)
                          – LarsH
                          Nov 18 at 0:50








                        • 1




                          It isn't obvious but it is infamous. I can't find it for you now because I am out to dinner. But you can find by looking up the classic proof regarding the irrationality of square root of 2. Its in Bertrand Russell's history of western philosophy...
                          – Mason
                          Nov 18 at 0:57






                        • 3




                          @LarsH ny squaring the equation and wiggling it a bit you can prove that a is even, and then that b is also even.
                          – Dan M.
                          Nov 18 at 2:29










                        • Here are the details
                          – Mason
                          Nov 18 at 2:38






                        • 1




                          @LarsH We have $2 = a^2/b^2$ hence $2b^2 = a^2$ from which: $a^2$ is even, hence $a$ is even, hence $a^2$ is a multiple of 4, hence $b^2=a^2/2$ is even, hence $b$ is even. So, both $a,b$ are even.
                          – chi
                          Nov 18 at 11:11

















                        up vote
                        10
                        down vote













                        Assume the $sqrt{2}$ is rational then there are whole numbers $(a,b)$ such that $sqrt{2}=a/b$ and $a$ is the smallest number with this property but then we find that $a/2, b/2$ are also whole numbers with this property. So there is a smaller example.



                        I think this must be the example people are the most familiar with and it's a kind of infinite descent even though we often don't refer to it as such.






                        share|cite|improve this answer

















                        • 1




                          In this proof how do we know that $a/2$, $b/2$ are also whole numbers? (I'm probably missing something obvious.)
                          – LarsH
                          Nov 18 at 0:50








                        • 1




                          It isn't obvious but it is infamous. I can't find it for you now because I am out to dinner. But you can find by looking up the classic proof regarding the irrationality of square root of 2. Its in Bertrand Russell's history of western philosophy...
                          – Mason
                          Nov 18 at 0:57






                        • 3




                          @LarsH ny squaring the equation and wiggling it a bit you can prove that a is even, and then that b is also even.
                          – Dan M.
                          Nov 18 at 2:29










                        • Here are the details
                          – Mason
                          Nov 18 at 2:38






                        • 1




                          @LarsH We have $2 = a^2/b^2$ hence $2b^2 = a^2$ from which: $a^2$ is even, hence $a$ is even, hence $a^2$ is a multiple of 4, hence $b^2=a^2/2$ is even, hence $b$ is even. So, both $a,b$ are even.
                          – chi
                          Nov 18 at 11:11















                        up vote
                        10
                        down vote










                        up vote
                        10
                        down vote









                        Assume the $sqrt{2}$ is rational then there are whole numbers $(a,b)$ such that $sqrt{2}=a/b$ and $a$ is the smallest number with this property but then we find that $a/2, b/2$ are also whole numbers with this property. So there is a smaller example.



                        I think this must be the example people are the most familiar with and it's a kind of infinite descent even though we often don't refer to it as such.






                        share|cite|improve this answer












                        Assume the $sqrt{2}$ is rational then there are whole numbers $(a,b)$ such that $sqrt{2}=a/b$ and $a$ is the smallest number with this property but then we find that $a/2, b/2$ are also whole numbers with this property. So there is a smaller example.



                        I think this must be the example people are the most familiar with and it's a kind of infinite descent even though we often don't refer to it as such.







                        share|cite|improve this answer












                        share|cite|improve this answer



                        share|cite|improve this answer










                        answered Nov 17 at 19:20









                        Mason

                        1,7991426




                        1,7991426








                        • 1




                          In this proof how do we know that $a/2$, $b/2$ are also whole numbers? (I'm probably missing something obvious.)
                          – LarsH
                          Nov 18 at 0:50








                        • 1




                          It isn't obvious but it is infamous. I can't find it for you now because I am out to dinner. But you can find by looking up the classic proof regarding the irrationality of square root of 2. Its in Bertrand Russell's history of western philosophy...
                          – Mason
                          Nov 18 at 0:57






                        • 3




                          @LarsH ny squaring the equation and wiggling it a bit you can prove that a is even, and then that b is also even.
                          – Dan M.
                          Nov 18 at 2:29










                        • Here are the details
                          – Mason
                          Nov 18 at 2:38






                        • 1




                          @LarsH We have $2 = a^2/b^2$ hence $2b^2 = a^2$ from which: $a^2$ is even, hence $a$ is even, hence $a^2$ is a multiple of 4, hence $b^2=a^2/2$ is even, hence $b$ is even. So, both $a,b$ are even.
                          – chi
                          Nov 18 at 11:11
















                        • 1




                          In this proof how do we know that $a/2$, $b/2$ are also whole numbers? (I'm probably missing something obvious.)
                          – LarsH
                          Nov 18 at 0:50








                        • 1




                          It isn't obvious but it is infamous. I can't find it for you now because I am out to dinner. But you can find by looking up the classic proof regarding the irrationality of square root of 2. Its in Bertrand Russell's history of western philosophy...
                          – Mason
                          Nov 18 at 0:57






                        • 3




                          @LarsH ny squaring the equation and wiggling it a bit you can prove that a is even, and then that b is also even.
                          – Dan M.
                          Nov 18 at 2:29










                        • Here are the details
                          – Mason
                          Nov 18 at 2:38






                        • 1




                          @LarsH We have $2 = a^2/b^2$ hence $2b^2 = a^2$ from which: $a^2$ is even, hence $a$ is even, hence $a^2$ is a multiple of 4, hence $b^2=a^2/2$ is even, hence $b$ is even. So, both $a,b$ are even.
                          – chi
                          Nov 18 at 11:11










                        1




                        1




                        In this proof how do we know that $a/2$, $b/2$ are also whole numbers? (I'm probably missing something obvious.)
                        – LarsH
                        Nov 18 at 0:50






                        In this proof how do we know that $a/2$, $b/2$ are also whole numbers? (I'm probably missing something obvious.)
                        – LarsH
                        Nov 18 at 0:50






                        1




                        1




                        It isn't obvious but it is infamous. I can't find it for you now because I am out to dinner. But you can find by looking up the classic proof regarding the irrationality of square root of 2. Its in Bertrand Russell's history of western philosophy...
                        – Mason
                        Nov 18 at 0:57




                        It isn't obvious but it is infamous. I can't find it for you now because I am out to dinner. But you can find by looking up the classic proof regarding the irrationality of square root of 2. Its in Bertrand Russell's history of western philosophy...
                        – Mason
                        Nov 18 at 0:57




                        3




                        3




                        @LarsH ny squaring the equation and wiggling it a bit you can prove that a is even, and then that b is also even.
                        – Dan M.
                        Nov 18 at 2:29




                        @LarsH ny squaring the equation and wiggling it a bit you can prove that a is even, and then that b is also even.
                        – Dan M.
                        Nov 18 at 2:29












                        Here are the details
                        – Mason
                        Nov 18 at 2:38




                        Here are the details
                        – Mason
                        Nov 18 at 2:38




                        1




                        1




                        @LarsH We have $2 = a^2/b^2$ hence $2b^2 = a^2$ from which: $a^2$ is even, hence $a$ is even, hence $a^2$ is a multiple of 4, hence $b^2=a^2/2$ is even, hence $b$ is even. So, both $a,b$ are even.
                        – chi
                        Nov 18 at 11:11






                        @LarsH We have $2 = a^2/b^2$ hence $2b^2 = a^2$ from which: $a^2$ is even, hence $a$ is even, hence $a^2$ is a multiple of 4, hence $b^2=a^2/2$ is even, hence $b$ is even. So, both $a,b$ are even.
                        – chi
                        Nov 18 at 11:11












                        up vote
                        1
                        down vote













                        A fundamental example in number theory is descent by (Euclidean) division with remainder (or, equivalently, by repeated subtraction), as in the following basic result.



                        Lemma $ $ Let $,S,$ be a nonempty set of positive integers that is closed under subtraction $> 0,,$ i.e. for all $ ,n,min S, ,$ $ n > m Rightarrow n-m, in, S.,$ Then the least $ :ellin S,$ divides every element of $, S.$



                        Proof ${bf 1}, $ If not there is a least nonmultiple $ ,nin S,,$ contra $ ,n-ell in S,$ is a nonmultiple of $ ,ell.$



                        Proof ${bf 2}, , S,$ closed under subtraction $ ,Rightarrow,S,$ closed under remainder (mod), when it is $ne 0,$ since mod is simply repeated subtraction, i.e. $ abmod b, =, a - k b, =, a!-!b!-!b!-cdots! -!b.,$ Therefore $ ,nin S,$ $Rightarrow$ $ , (nbmod ell) = 0,,$ else it is in $, S,$ and smaller than $ ,ell,,$ contra minimality of $ ,ell.$



                        Remark $ $ In a nutshell, two applications of induction yield the following inferences



                        $begin{eqnarray}rm S closed under {bf subtraction} &:Rightarrow:&rm S closed under {bf mod} = remainder = repeated subtraction \
                        &:Rightarrow:&rm S closed under {bf gcd} = repeated mod (Euclid's algorithm) end{eqnarray}$



                        This yields Bezout's GCD identity: the set $ ,S,$ of integers of form $ ,a_1,x_1 + cdots + a_n x_n, x_iin mathbb Z,,$ is closed under subtraction so Lemma $Rightarrow$ every positive $ ,kin S,$ is divisible by $ ,d = $ least positive $ in S.,$ Therefore $ ,a_iin S$ $,Rightarrow,$ $ dmid a_i,,$ i.e. $ ,d,$ is a common divisor of all $ ,a_i,,$ necessarily the greatest such because $ cmid a_i$ $Rightarrow$ $ ,cmid d = a_!,x_1!+!cdots!+!a_nx_n$ $Rightarrow$ $ ,cle d.,$ When interpreted constructively, this yields the extended Euclidean algorithm for the gcd.






                        share|cite|improve this answer

























                          up vote
                          1
                          down vote













                          A fundamental example in number theory is descent by (Euclidean) division with remainder (or, equivalently, by repeated subtraction), as in the following basic result.



                          Lemma $ $ Let $,S,$ be a nonempty set of positive integers that is closed under subtraction $> 0,,$ i.e. for all $ ,n,min S, ,$ $ n > m Rightarrow n-m, in, S.,$ Then the least $ :ellin S,$ divides every element of $, S.$



                          Proof ${bf 1}, $ If not there is a least nonmultiple $ ,nin S,,$ contra $ ,n-ell in S,$ is a nonmultiple of $ ,ell.$



                          Proof ${bf 2}, , S,$ closed under subtraction $ ,Rightarrow,S,$ closed under remainder (mod), when it is $ne 0,$ since mod is simply repeated subtraction, i.e. $ abmod b, =, a - k b, =, a!-!b!-!b!-cdots! -!b.,$ Therefore $ ,nin S,$ $Rightarrow$ $ , (nbmod ell) = 0,,$ else it is in $, S,$ and smaller than $ ,ell,,$ contra minimality of $ ,ell.$



                          Remark $ $ In a nutshell, two applications of induction yield the following inferences



                          $begin{eqnarray}rm S closed under {bf subtraction} &:Rightarrow:&rm S closed under {bf mod} = remainder = repeated subtraction \
                          &:Rightarrow:&rm S closed under {bf gcd} = repeated mod (Euclid's algorithm) end{eqnarray}$



                          This yields Bezout's GCD identity: the set $ ,S,$ of integers of form $ ,a_1,x_1 + cdots + a_n x_n, x_iin mathbb Z,,$ is closed under subtraction so Lemma $Rightarrow$ every positive $ ,kin S,$ is divisible by $ ,d = $ least positive $ in S.,$ Therefore $ ,a_iin S$ $,Rightarrow,$ $ dmid a_i,,$ i.e. $ ,d,$ is a common divisor of all $ ,a_i,,$ necessarily the greatest such because $ cmid a_i$ $Rightarrow$ $ ,cmid d = a_!,x_1!+!cdots!+!a_nx_n$ $Rightarrow$ $ ,cle d.,$ When interpreted constructively, this yields the extended Euclidean algorithm for the gcd.






                          share|cite|improve this answer























                            up vote
                            1
                            down vote










                            up vote
                            1
                            down vote









                            A fundamental example in number theory is descent by (Euclidean) division with remainder (or, equivalently, by repeated subtraction), as in the following basic result.



                            Lemma $ $ Let $,S,$ be a nonempty set of positive integers that is closed under subtraction $> 0,,$ i.e. for all $ ,n,min S, ,$ $ n > m Rightarrow n-m, in, S.,$ Then the least $ :ellin S,$ divides every element of $, S.$



                            Proof ${bf 1}, $ If not there is a least nonmultiple $ ,nin S,,$ contra $ ,n-ell in S,$ is a nonmultiple of $ ,ell.$



                            Proof ${bf 2}, , S,$ closed under subtraction $ ,Rightarrow,S,$ closed under remainder (mod), when it is $ne 0,$ since mod is simply repeated subtraction, i.e. $ abmod b, =, a - k b, =, a!-!b!-!b!-cdots! -!b.,$ Therefore $ ,nin S,$ $Rightarrow$ $ , (nbmod ell) = 0,,$ else it is in $, S,$ and smaller than $ ,ell,,$ contra minimality of $ ,ell.$



                            Remark $ $ In a nutshell, two applications of induction yield the following inferences



                            $begin{eqnarray}rm S closed under {bf subtraction} &:Rightarrow:&rm S closed under {bf mod} = remainder = repeated subtraction \
                            &:Rightarrow:&rm S closed under {bf gcd} = repeated mod (Euclid's algorithm) end{eqnarray}$



                            This yields Bezout's GCD identity: the set $ ,S,$ of integers of form $ ,a_1,x_1 + cdots + a_n x_n, x_iin mathbb Z,,$ is closed under subtraction so Lemma $Rightarrow$ every positive $ ,kin S,$ is divisible by $ ,d = $ least positive $ in S.,$ Therefore $ ,a_iin S$ $,Rightarrow,$ $ dmid a_i,,$ i.e. $ ,d,$ is a common divisor of all $ ,a_i,,$ necessarily the greatest such because $ cmid a_i$ $Rightarrow$ $ ,cmid d = a_!,x_1!+!cdots!+!a_nx_n$ $Rightarrow$ $ ,cle d.,$ When interpreted constructively, this yields the extended Euclidean algorithm for the gcd.






                            share|cite|improve this answer












                            A fundamental example in number theory is descent by (Euclidean) division with remainder (or, equivalently, by repeated subtraction), as in the following basic result.



                            Lemma $ $ Let $,S,$ be a nonempty set of positive integers that is closed under subtraction $> 0,,$ i.e. for all $ ,n,min S, ,$ $ n > m Rightarrow n-m, in, S.,$ Then the least $ :ellin S,$ divides every element of $, S.$



                            Proof ${bf 1}, $ If not there is a least nonmultiple $ ,nin S,,$ contra $ ,n-ell in S,$ is a nonmultiple of $ ,ell.$



                            Proof ${bf 2}, , S,$ closed under subtraction $ ,Rightarrow,S,$ closed under remainder (mod), when it is $ne 0,$ since mod is simply repeated subtraction, i.e. $ abmod b, =, a - k b, =, a!-!b!-!b!-cdots! -!b.,$ Therefore $ ,nin S,$ $Rightarrow$ $ , (nbmod ell) = 0,,$ else it is in $, S,$ and smaller than $ ,ell,,$ contra minimality of $ ,ell.$



                            Remark $ $ In a nutshell, two applications of induction yield the following inferences



                            $begin{eqnarray}rm S closed under {bf subtraction} &:Rightarrow:&rm S closed under {bf mod} = remainder = repeated subtraction \
                            &:Rightarrow:&rm S closed under {bf gcd} = repeated mod (Euclid's algorithm) end{eqnarray}$



                            This yields Bezout's GCD identity: the set $ ,S,$ of integers of form $ ,a_1,x_1 + cdots + a_n x_n, x_iin mathbb Z,,$ is closed under subtraction so Lemma $Rightarrow$ every positive $ ,kin S,$ is divisible by $ ,d = $ least positive $ in S.,$ Therefore $ ,a_iin S$ $,Rightarrow,$ $ dmid a_i,,$ i.e. $ ,d,$ is a common divisor of all $ ,a_i,,$ necessarily the greatest such because $ cmid a_i$ $Rightarrow$ $ ,cmid d = a_!,x_1!+!cdots!+!a_nx_n$ $Rightarrow$ $ ,cle d.,$ When interpreted constructively, this yields the extended Euclidean algorithm for the gcd.







                            share|cite|improve this answer












                            share|cite|improve this answer



                            share|cite|improve this answer










                            answered Nov 17 at 22:37









                            Bill Dubuque

                            207k29189624




                            207k29189624






























                                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.





                                Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


                                Please pay close attention to the following guidance:


                                • Please be sure to answer the question. Provide details and share your research!

                                But avoid



                                • Asking for help, clarification, or responding to other answers.

                                • Making statements based on opinion; back them up with references or personal experience.


                                To learn more, see our tips on writing great answers.




                                draft saved


                                draft discarded














                                StackExchange.ready(
                                function () {
                                StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3002706%2fwhat-is-an-example-of-a-proof-by-minimal-counterexample%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

                                AnyDesk - Fatal Program Failure

                                How to calibrate 16:9 built-in touch-screen to a 4:3 resolution?

                                QoS: MAC-Priority for clients behind a repeater