1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I Proving a proposition directly

  1. Sep 13, 2016 #1
    Say we have a proposition like "##\sqrt{2}## is an irrational number." So I know that this statement in particular cannot really be proved directly; you must use contradiction. However, I am not concerned with exactly with what the statement says, but rather its structure. Evidently, it is not in the if-then form. Or in other words, the proposition is not phrased as an implication. We know that to prove implications directly, we show that q being true results from p being true. However, for the proposition like "##\sqrt{2}## is an irrational number," it seems that there is only a conclusion q, and thus there is no implication. Thus, what would be the logical form of proving this directly, if there is no implication? Can you only prove statements of this syntactic form it indirectly?
     
  2. jcsd
  3. Sep 13, 2016 #2

    jbriggs444

    User Avatar
    Science Advisor

    The predicate "is irrational" is defined as "is not the ratio of two integers". That makes the distinction between a direct proof and an indirect proof somewhat vague.
     
  4. Sep 13, 2016 #3

    fresh_42

    Staff: Mentor

    Of course it is a conclusion: You have to define, what numbers are, say ##R##, what rational numbers are, say ##Q##, or what irrational numbers are, say ##J##.
    Then the statement reads ##(\; \sqrt{2} \in \{x \in R \, | \, x^2=2 \in R \} \; \wedge R = Q \cup J \; \Rightarrow \; \sqrt{2} \notin Q\;)## or ##(\; \sqrt{2} \in \{x \in R \, | \, x^2=2 \in R \} \; \wedge R = Q \cup J \; \Rightarrow \; \sqrt{2} \in J\;)##. If ##R=\mathbb{Z}## then ##\sqrt{2}## isn't even a number.

    (edited)
     
  5. Sep 13, 2016 #4

    fresh_42

    Staff: Mentor

    In addition I do not believe that it cannot be proven directly. E.g. rational numbers can be expressed as a terminating output of a TM as a pair ##(1+\dots +1 \; , \;1+\dots +1)## after finitely many steps. I assume (although I don't know a source), that it's possible to show that such an algorithm cannot halt on ##\sqrt{2}## not by contradiction but by proving that there is always another step needed.
     
  6. Sep 13, 2016 #5
    But where in the statement "##sqrt{2}## is an even number" is there a hypothesis? If there is no hypothesis, how could be prove it directly? In general, if a proposition we are trying to prove only has a conclusion and not a hypothesis, how do we prove it directly?
     
  7. Sep 13, 2016 #6

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    You can convert every proof by contradiction to a direct proof by negating every step and inverting the logical order, as ##\bar A \Rightarrow B## (with B false for a contradiction)is equivalent to ##A \Leftarrow \bar B##.

    "sqrt(2) is irrational" IS a hypothesis. A direct proof works along the line of 1=1 => ... => .... => sqrt(2) is irrational
     
  8. Sep 13, 2016 #7
    It's just that in a direct proof, for an implication ##P \implies Q##, we assume that P is true and derive Q. It seems that ##\sqrt{2}## is irrational is not phrased as an implication, meaning that there is no P to assume in order to derive Q.
     
  9. Sep 13, 2016 #8

    fresh_42

    Staff: Mentor

    Again. There is! The definition of ##\sqrt{2}## and the definition of the various number sets are your ##P##.
     
  10. Sep 13, 2016 #9
    So is the point that since this definition information is not terribly useful, we revert to using a proof by contradiction?
     
  11. Sep 13, 2016 #10

    fresh_42

    Staff: Mentor

    I already gave you an example on how a positive proof could look like. And of course are the definitions useful. It is the only way to describe what we are talking about. Without them how could we know what irrational means? Or what a number is? E.g. ##\sqrt{2}## doesn't even exist if we only would have the integers, the rationals or several other rings or fields.
    The proof by contradiction we all have in mind is just an especially simple one. However, there is an entire logic department in mathematics that only allows constructive methods, see https://en.wikipedia.org/wiki/Constructivism_(mathematics). It complicates things a lot and it is by far not trivial to decide what "can only be proven by contradiction". I don't think our example here belongs to this class.

    Maybe you're also interested in here: https://en.wikipedia.org/wiki/Reductio_ad_absurdum
     
    Last edited: Sep 13, 2016
  12. Sep 13, 2016 #11
    What about in the statement such as ##\sqrt{xy} \geqslant \frac{2xy}{x + y}## for all positive x,y that are real numbers? What is the hypothesis and the conclusion in this proposition?
     
  13. Sep 13, 2016 #12

    fresh_42

    Staff: Mentor

    If ##\mathbb{F}## is an Archimedean ordered field, then ##\sqrt{xy} \geqslant \frac{2xy}{x + y}## for all ##x,y \in \mathbb{F}## with ##xy > 0##.
     
  14. Sep 13, 2016 #13
    So the proof would consist of manipulating the conclusion ##\sqrt{xy} \geqslant \frac{2xy}{x + y}## until we arrive at a statement such as ##(x - y)^2 \geqslant 0##, which is always true. Would this be considered a direct proof? How are we using ##P## in the implication ##P \implies Q## to derive ##Q## in this particular example?
     
  15. Sep 13, 2016 #14

    fresh_42

    Staff: Mentor

    It is a direct proof, because the proof will be:
    ##\mathbb{F}## an Archimedean ordered field ##\Longrightarrow \; x^2>0## for all ##x \in \mathbb{F}-\{0\} \; \Longrightarrow \sqrt{xy} \geqslant \frac{2xy}{x + y}## for all ##xy>0##.
    No contradiction and nothing indirect. Only the fact that squares are positive in these number fields. However, I'm not 100% sure whether the Archimedean ordering is necessary or just a preordered field. In any case we need the property that ##-1## is no square.
     
  16. Sep 13, 2016 #15
    Ah, I see. So we are using backward reasoning on the conclusion to find a condition that is a natural consequence of the hypothesis, namely that ##(x - y)^2 \geqslant 0##.

    So, in general, can all provable theorems be proven either directly, by contraposition,or by contradiction? Are these the fundamental ways to show that ##P \implies Q## is true?
     
  17. Sep 13, 2016 #16

    fresh_42

    Staff: Mentor

    I don't know. I'm no logician. In principle we have a set of assumptions which we take for granted: the axioms of a system. Then there are rules, which define how to conclude one statement from another. These systems (axioms and rules of deviations) may differ among different logic systems. The mostly used system is probably Zermelo-Fraenkel plus the continuum hypothesis of set theory and intuitive logic. But the debates on the axiom of choice alone fills libraries. And I've met logicians who restricted themselves to only positive deviations without the possibility of proofs by contradiction.

    See e.g. https://en.wikipedia.org/wiki/Proposition or google for systems of logic. It's basically a science on its own.
     
  18. Sep 14, 2016 #17
    I think there should be a fairly simple alternative method. As an example we have:
    49/44=1.11363636.....

    We have three important components here so to speak:
    a) The number "1" that occurs before the decimal
    b) The part "11" that occurs just after the decimal
    c) The part "36" that repeats itself forever

    Now every real number has some decimal representation (which uniquely identifies the real number). The decimal representation can be associated with a function f:N→N (so that there is 1-1 correspondence between decimal representations and the associated functions) where:
    f(0) is some value belonging to N
    for all a>0 f(a) belongs to {0,1,2,3,4,5,6,7,8,9}

    We have already seen that the function f for a rational number is of a very specific form. I think one subtle point here might be that no matter which function f we use for a specific rational number, it would always be periodic. Another subtle and important point is that the function f can be periodic only for rational numbers. Not quite sure, but I think one could show it by explicitly describing m/n (with m,n natural numbers) for for any decimal representation that is periodic.

    Now we have an algorithm for determining square root of any arbitrary number in terms of decimal representation. More specifically (for our purpose) given any number x∈N we can write a program** say Px for the function f above that uniquely identifies the square-root of x.

    Basically we would want to analyze the program for x=2, the program P2 that is. Specifically we would want to show that the outputs of the program P2 never periodically repeat themselves (in the sense discussed above).

    It seems the main underlying assumptions here would be the justification for the algorithms (on the very least when the arguments are natural numbers) giving decimal representation for division (of fractions) and square-root.


    **Essentially we could write a recursive function g:N→N such that:
    g(x)=index of the program Px
    But that is not required here I think
     
    Last edited: Sep 14, 2016
  19. Sep 14, 2016 #18
    In more simple terms, what I meant was something along these lines:
    Suppose the answer to square-root of 2 is of the form:
    1.abcdabcdabcd...
    where a,b,c,d are from 0 to 9. Here the length of tail is 0 (suppose we start counting right after the decimal point) and length of period is 4. We want to show that this can't possibly be the correct result. Once we generalise this for a period of arbitrary length, we are half-way there.

    We would now want to show that no matter what the length of tail is, and no matter what length of period we choose, the resulting number can't be square-root of 2.
     
  20. Jan 24, 2017 #19

    Mark44

    Staff: Mentor

    This is not true, in general. For example, 1, which is a real number, can be represented as 1.000... as well as 0.999... In the first representation, the 0's repeat endlessly. In the second case, the 9's repeat endlessly.

    1/2 can be represented as .500... or as .4999..., 1/4 can be written as .25000... or as .24999...
     
  21. Jan 24, 2017 #20

    jbriggs444

    User Avatar
    Science Advisor

    A decimal representation identifies a real number uniquely in the sense that exactly one real number is identified by a given sequence. It does not represent a real number uniquely in the sense that more than one decimal can [in some cases] represent a given real number.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Proving a proposition directly
Loading...