# I Proving a proposition directly

1. Sep 13, 2016

### Mr Davis 97

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. Sep 13, 2016

### jbriggs444

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.

3. Sep 13, 2016

### 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)

4. Sep 13, 2016

### 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.

5. Sep 13, 2016

### Mr Davis 97

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?

6. Sep 13, 2016

### 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

7. Sep 13, 2016

### Mr Davis 97

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.

8. Sep 13, 2016

### Staff: Mentor

Again. There is! The definition of $\sqrt{2}$ and the definition of the various number sets are your $P$.

9. Sep 13, 2016

### Mr Davis 97

So is the point that since this definition information is not terribly useful, we revert to using a proof by contradiction?

10. Sep 13, 2016

### 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
11. Sep 13, 2016

### Mr Davis 97

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?

12. Sep 13, 2016

### 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$.

13. Sep 13, 2016

### Mr Davis 97

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?

14. Sep 13, 2016

### 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.

15. Sep 13, 2016

### Mr Davis 97

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?

16. Sep 13, 2016

### 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.

17. Sep 14, 2016

### SSequence

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
18. Sep 14, 2016

### SSequence

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.

19. Jan 24, 2017

### 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...

20. Jan 24, 2017

### jbriggs444

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.

21. Jan 24, 2017

### Staff: Mentor

This last part is the most important.
1.11363636... can be represented as
$1 + \frac{11}{100} + \frac{36}{10^4} + \frac{36}{10^6} + \dots + \frac{36}{10^{2n}} + \dots$
The part starting with the first fraction with numerator 36 is a convergent geometric series, and there is a formula for its sum.
Yes, every rational number has a decimal representation with a repeating part.
Irrational numbers do not have a repeating pattern in their decimal representations. That is well known.
There is an algorithm for hand-calculating the square root of any nonnegative number. See https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Digit-by-digit_calculation, especially the two examples, one of which shows a few steps in calculating $\sqrt 2$. This technique used to be taught in grade school -- I learned it and can still do it, although with calculators and computers, there's not much need for me to do so. This method relies on Newton's Method to do the calculation.
This is more abstract that it needs to be. We don't need to "write a program." There is already an algorithm that has been around for a few hundred years.

22. Jan 25, 2017

### SSequence

The whole post was perhaps a bit more abstract than it needed to be. What I just meant was that if we place enough 0's along with 2 (call the result a) and see what is the largest value whose square is less than a, we can get square-root of 2 to enough decimal places (not difficult to make it precise). By itself it is probably the most obvious method to calculate it.

I was just thinking that if we analyze this process (the multiplication process involved that is) we should able to get the insight that why there can't be an infinite repetition of digits after any given point (except that of 9 or 0 forever in case of exact square-root). Obviously I didn't do it myself, otherwise I would have written it in a clearer fashion.

Last edited: Jan 25, 2017
23. Jan 25, 2017

### jbriggs444

For instance, you envision an algorithm like "binary search" that starts with the knowledge that ${1.0}^2$ is less than 2.00 and ${1.5}^2$ is greater. It splits the difference, computes ${1.25}^2$ and notes that it is has four decimal places and is less than 2.0000. So the algorithm recurses, attempting to find $\sqrt{2.0000}$ in the range between 1.25 and 1.50.

In my opinion, the extra decimal places in the 2.0000 are annoying and add little to the description of the algorithm. But I think I understand why you are using them.
One might be able to proceed in such a fashion. Most mathematicians would find it easier to build on a structure of well-known and easier to prove facts. It is already known that the no rational number can be the square root of two, it is already known that all rational numbers have repeating decimal expansions and that all repeating decimal expansions correspond to rational numbers. One easily concludes that the square root of two, if it exists, can not have a repeating decimal expansion.

The existence of a decimal expansion for the square root of two can also be proven. The algorithm above is an attractive way to do that for those of us who are programmers at heart. [Even more attractive if one works in binary]

24. Jan 25, 2017

### SSequence

Something much simpler really. Since we are just talking about square-root of 2, we have:
12=1 < 2 (1 is largest number whose square is less than 2)
142=196 < 200 (14 is largest number whose square is less than 200)
1412=19981 < 20000 (141 is largest number whose square is less than 20000)
14142=1999396 < 2000000 (1414 is largest number whose square is less than 2000000)
141422=199996164 < 200000000 (14142 is largest number whose sqr is less than 200000000)
........

25. Jan 25, 2017

### jbriggs444

It's actually the same algorithm. Call it "decimal search". You start with the knowledge that $1^2 < 2 < 2^2$ and proceed to evaluate 1.12 through 1.92. You find that 1.42 is the highest next-digit that yields a square that is still less than 2 and recurse looking for $\sqrt{2}$ between 1.4 and 1.5.