Proving a proposition directly

[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?

 

[jbriggs444]

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.

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.

 

[fresh_42]

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?

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)

 

[fresh_42]

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.

 

[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?

 

[mfb]

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

 

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

 

[fresh_42]

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.

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

 

[Mr Davis 97]

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

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

 

[fresh_42]

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

 

[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?

 

[fresh_42]

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?

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

 

[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?

 

[fresh_42]

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?

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.

 

[Mr Davis 97]

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.

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?

 

[fresh_42]

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.

 

[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 P_x 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 P₂ that is. Specifically we would want to show that the outputs of the program P₂ 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 P_x
But that is not required here I think

 

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

 

[Mark44]

Now every real number has some decimal representation (which uniquely identifies the real number).

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

 

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

 

[Mark44]

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

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.

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.

Yes, every rational number has a decimal representation with a repeating part.

Another subtle and important point is that the function f can be periodic only for rational numbers.

Irrational numbers do not have a repeating pattern in their decimal representations. That is well known.

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.

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.

More specifically (for our purpose) given any number x∈N we can write a program** say P_x for the function f above that uniquely identifies the square-root of x.

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.

Basically we would want to analyze the program for x=2, the program P₂ that is. Specifically we would want to show that the outputs of the program P₂ 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 P_x
But that is not required here I think

 

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

 

[jbriggs444]

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.

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.

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 forever).

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]

 

[SSequence]

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.0 and 1.25.

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

 

[jbriggs444]

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

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.1² through 1.9². You find that 1.4² 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.

 

[mfb]

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

That way you have to do up to 10 calculations per digit (if you have to test 1 to 9). Possible, but extremely inefficient. There are algorithms that double the number of correct digits in every step.

 

[FactChecker]

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.

You can always convert it to a format of an "if .. then" statement. If n=√2, then n is irrational.