+ Reply to thread
Results 1 to 12 of 12

Thread: First non-constructive proof

  1. #1
    Elephant CRSP's avatar
    Registered
    Feb 2009
    Location
    Perfidious Albion
    Posts
    936

    Default First non-constructive proof

    What was the first non-constructive proof in mathematics that was widely believed? I did a course as an undergraduate where the course notes stated that Hilbert's original proof of the Nullstellensatz was the first, and at the time caused a revolution (e.g. Gordan's famous quote "das ist nicht Mathematik, das ist Theologie".) However, some other reading suggestes that some non-constructive proofs have been around for a long time, and the move away from constructive mathematics began at the start of the nineteenth century, and was a long time coming.

    So, which was it? Was there a revolution, started by Hilbert or somebody else, or a gradual movement away from constructivism?
    Les sanglots longs des violons de l'automne blessent mon coeur
    D'une langueur Monotone

  2. #2
    Stegodon kk fusion's avatar
    Registered
    Feb 2009
    Location
    France/Germany
    Posts
    298

    Default Re: First non-constructive proof

    Convergence tests often prove that a series converges without giving an actual boundary value.

    Is that what you're looking for?

  3. #3
    Member
    Registered
    Mar 2009
    Posts
    55

    Default Re: First non-constructive proof

    Euclid's proof of the infinitude of primes isn't exactly a non-constructive proof, but modern statements of it often involve showing that something (a prime not on the "list") must exist, without explicitly generating it. Apparently Euclid's original formulation was more in the form of an algorithm for generating a "new" prime.

  4. #4
    Banned
    Registered
    Mar 2009
    Location
    Michigan
    Posts
    3,590

    Default Re: First non-constructive proof

    So for the math-impaired, what exactly is a non-constructive proof?

  5. #5
    Elephant
    Registered
    Mar 2009
    Location
    Tokyo, Japan
    Posts
    960

    Default Re: First non-constructive proof

    Quote Originally posted by Excalibre
    So for the math-impaired, what exactly is a non-constructive proof?
    A constructive proof says "X exists, and this is how you find or create it."
    A non-constructive proof only says that X exists. How you find it is your problem.

    For example, if you prove that a list of objects can not be complete, then you have proved that an object exists that is not on the list. What that object is, and where to find it, is not mentioned in your proof.
    No cage, thank you. I'm a human being.

  6. #6
    aka ivan the not-quite-as-terrible ivan astikov's avatar
    Registered
    Feb 2009
    Location
    moston, UK.
    Posts
    4,779

    Default Re: First non-constructive proof

    Does. not. compute. Need. more. input.
    To sleep, perchance to experience amygdalocortical activation and prefrontal deactivation.

  7. #7
    Member
    Registered
    Feb 2009
    Posts
    44

    Default Re: First non-constructive proof

    I would think they'd date back to antiquity, and that paying effort towards distinguishing the constructive and non-constructive aspects of proof is, like so many other metamathematical concerns and investigations, more modern. But I suppose it depends on exactly what one chooses to consider constructive.

    E.g., I assert that there is an unbeatable strategy for one of the players in chess. Proof: either white has an unbeatable strategy, or every sequence of moves white makes leaves open the possibility for black to win, in which case black can fashion a strategy which keeps taking such moves and thus guarantee a win for themself. Is this to count as constructive? I still have no idea whether its white or black or both who have the unbeatable strategy, much less what the moves of that strategy are. But, I could write a brute-force program to figure it out. Although, it'd take far, far too long to get anywhere, and so why pretend this provides constructive support, when clearly I haven't actually carried out any such computation? Yet...

    Should I instead conflate constructive proof with intuitionistic logic? Probably not, since in this case, non-constructivity is certainly the historically ubiquitous norm. Still, the idea does bring up some interesting examples, along the lines of little things taken for granted without a moment's hesitation all over the place in everyday mathematics; e.g., the assumption that every inhabited set of natural numbers has a least element. Indeed, in a sense, any invocation of the excluded middle without further justification is use of a pure existence proof: I know that A and ~A cannot both be false, so there exists at least one of them which is true. But I haven't determined which...

  8. #8
    Banned
    Registered
    Mar 2009
    Location
    Michigan
    Posts
    3,590

    Default Re: First non-constructive proof

    Quote Originally posted by Indistinguishable
    I would think they'd date back to antiquity, and that paying effort towards distinguishing the constructive and non-constructive aspects of proof is, like so many other metamathematical concerns and investigations, more modern. But I suppose it depends on exactly what one chooses to consider constructive.

    E.g., I assert that there is an unbeatable strategy for one of the players in chess. Proof: either white has an unbeatable strategy, or every sequence of moves white makes leaves open the possibility for black to win, in which case black can fashion a strategy which keeps taking such moves and thus guarantee a win for themself. Is this to count as constructive? I still have no idea whether its white or black or both who have the unbeatable strategy, much less what the moves of that strategy are. But, I could write a brute-force program to figure it out. Although, it'd take far, far too long to get anywhere, and so why pretend this provides constructive support, when clearly I haven't actually carried out any such computation? Yet...

    Should I instead conflate constructive proof with intuitionistic logic? Probably not, since in this case, non-constructivity is certainly the historically ubiquitous norm. Still, the idea does bring up some interesting examples, along the lines of little things taken for granted without a moment's hesitation all over the place in everyday mathematics; e.g., the assumption that every inhabited set of natural numbers has a least element. Indeed, in a sense, any invocation of the excluded middle without further justification is use of a pure existence proof: I know that A and ~A cannot both be false, so there exists at least one of them which is true. But I haven't determined which...
    what

  9. #9
    Member
    Registered
    Feb 2009
    Posts
    44

    Default Re: First non-constructive proof

    chicken butt

  10. #10
    Stegodon
    Registered
    Mar 2009
    Location
    Los Angeles
    Posts
    155

    Default Re: First non-constructive proof

    Quote Originally posted by sublight
    Quote Originally posted by Excalibre
    So for the math-impaired, what exactly is a non-constructive proof?
    A constructive proof says "X exists, and this is how you find or create it."
    A non-constructive proof only says that X exists. How you find it is your problem.

    For example, if you prove that a list of objects can not be complete, then you have proved that an object exists that is not on the list. What that object is, and where to find it, is not mentioned in your proof.
    How is that even a "proof" and not just unsubstantiated hogwash?

  11. #11
    Elephant CRSP's avatar
    Registered
    Feb 2009
    Location
    Perfidious Albion
    Posts
    936

    Default Re: First non-constructive proof

    You prove that it's impossible for something not to be the case, therefore it must be the case. Objection to that tactic is at the heart of constructivism.

    Quote Originally posted by Indistinguishable
    I would think they'd date back to antiquity, and that paying effort towards distinguishing the constructive and non-constructive aspects of proof is, like so many other metamathematical concerns and investigations, more modern. But I suppose it depends on exactly what one chooses to consider constructive.
    Hmm. Weren't most ancient mathematicians finitists (either strict, or maintained Aristotle's distinction between potential and actual infinities)? In that case, wouldn't maintaining the metamathematical distinction be quite old?

    In fact, when did finitism finally die out? Was Kronecker's strict finitism an idiosyncrasy, or representative of a more widespread school of thought, still popular at the time?
    Les sanglots longs des violons de l'automne blessent mon coeur
    D'une langueur Monotone

  12. #12
    Member
    Registered
    Feb 2009
    Posts
    44

    Default Re: First non-constructive proof

    I imagine his strict finitism was a bit of an anomaly, hence the reason we remember Kronecker for it and not everyone else from the time. Which isn't to say that everyone else was hunky dory with arbitrary manipulations of reified infinities, but they mostly (I imagine, I don't know for sure; but consider contemporaries like Cauchy, Riemann, Weierstrass, etc.) would have no problem with discussion of limiting values of processes. And while perhaps the ancients would be a bit bothered by some of this, they certainly would have no problem with double negation elimination and so forth; I think right up until around the 20th century, almost everyone was content to follow in the lines of Aristotle, who had stated that, for example, if "No S is P" is false, then "Some S is P" is true.

    Let me put it this way: consider Brouwer's proof that every continuous function from a closed disc to itself has a fixed point, via establishing the impossibility of it moving every point. Archetypally non-constructive, but I can't imagine most mathematicians of Kronecker's day having any problem with it, whatever their views on the infinite; even Aristotle would accept the final leap (from the established falsity of "No point is fixed" to the truth of "Some point is fixed").

+ Reply to thread

Posting rules

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts