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