If you can understand why this proof technique breaks down for some humans at certain conditions, then you will understand why proofs by contradiction can sometimes break down for valid reasons (hint: they require the Law of Excluded Middle to be true, which is not always so certain, e.g. in intuitionistic logic) ;> I can prove to you by contradiction that `1` is the largest natural number. Here it goes: Assume that `1` is _not_ the largest natural number. Then let `n > 1` be the largest natural number. But wait! Then `n² > n` is even larger a natural number, which is a contradiction :q Therefore the _original_ statement that `1` is the largest natural number must have been true ;> Can you tell what's wrong with this proof? :> Don't get me wrong: I liked your analogy, it actually demonstrates this proof technique very well. I like it! :) It's just that it also demonstrates very well why this proof technique can break down sometimes :J
I think Proof by Contradiction is only used when the given statement says something is *not* true, so you can show the contradictions when that something *is* true to prove that it has to be not true
Sci Twi I can tell you much which is wrong with your proof. You cannot assume that the inference of n^2 > n from n > 1 is valid if n is assumed by hypothesis to be the largest number. Also, the law of the excluded middle is not what is strictly required for proof by contradiction to work. What you need is the law of non-contradiction instead, because this law allows P and not P to be a default falsum. Then I can state the first premise as “Q implies P and not P”, and since P and not P is a falsum, then it must be the case that the negation of it is true. This demonstrates not Q by the inference of modus tollens. I other words, this is a consequence of the inference rule “A implies B”, “not B” to conclude “not A”, Also known as the law of contrapositives.
Hmm, it doesn't seem like a good answer, because there wasn't any contradiction there (IMHO this statement cannot be proven unless you give a very specific definition of "human" that makes the proof trivial). In fact it seems like a good example for illustrating why something that looks like a proof actually isn't rigorous. A better advice would be: use proof by contradiction if you can find a contradiction. It doesn't have to be limited to when the statement has a "not"
To be fair there are probably better ways to demonstrate the idea (ways which don't involve problems with the actual proof) An example would be "Prove 3 is not even". Prove it by assuming that 3 is even, which means that dividing it by 2 would produce an integer.. Show that 3 / 2 is NOT an integer, and that proves it. No nitpicking necessary as (I think) there aren't any inherent flaws that aren't just pushing it (I doubt anyone would argue that dividing 2n by 2 would not produce an integer if n is an integer) I will agree however that the comments are unnecessary
We have been trying to talk sense to sqrt(2), but it just keeps being stubborn and so utterly irrational. It's impossible to talk to it. It won't change its mind no matter what, and no matter how clearly it's shown how wrong it is. A lost case.
The story is told that this proof was originally discovered by one of the students in Pythagoras's school. But one of the most strongly held Pythagorean beliefs -- a religious belief, not a rational* one, obviously! -- was that all numbers were rational, that the whole universe consisted of "harmonious ratios". The story continues that they had the student killed, in order to suppress his proof that this wasn't the case. (But I think they had him drowned at sea, rather than throwing him off a building.) * So, an irrational belief in the rationality of the universe? ;-)
I think the best way to really understand this is to also prove that sqrt(3) is irrational and that sqrt(4) is irrational, and notice where that last proof doesn't work. For 3 and 5, there are several cases in the lemma, but they still prove that the only way a^2 can be a multiple is if a is a multiple. With 4, another case works when it wasn't supposed to, which is how we can have perfect squares.
That would be a long video, because he would have to start with a discussion of the extension of the factorial function to non-integers (e.g. the gamma function).
Suppose root 2 has rationality To find a contradiction we must try to write our root as fraction a on b but show we can't, for something goes awry By squaring our equation on both sides then multiply; a squared is 2b squared That 2 divides a squared is thus implied and therefore 4 (squared factors come in pairs) But be a squared a multiple of 4 Then half that (b squared) must divide by 2 By using the same logic as before Then 4 divides b squared, it must be true To share no factors, a and b are bound But 2 they share, a contradiction found
Very important the explanation of why gcd(a,b)=1. And a lots of teachers skip that part. Practically the contradiction is that, if sqrt(2) is rational than his fraction can be simplified infinitely by 2.
Год назад
An easy (although less formally strict) way to prove that if a² is even, then a is even: The prime factor of 2 has to come from somewhere, it cannot be a product of multiple prime factors in a×a (because then it would not be prime), so each a must have at least one prime factor 2. And an alternative second blackboard: √2×b=2k b=√2×k b=a/b×k 1=a×k 1=2k² 0.5=k² 0.25=k
woow, nice proof! I think the proof of humans can't fly just the "add-on" , the main thing in this video is showing how to use the contradiction-based proof can you make a video/videos about combinatorics? It will be nice and great if you explain it!
01:15 The fact that it has the "not" in its definition doesn't necessarily mean that one has to prove it by contradiction. One can also prove it by contrapositive. It also doesn't mean that one _cannot_ use direct proof ;) And your other proof (for the lemma) shows exactly that: it also had the word "not" in it ("not odd", a.k.a. even), but you didn't have to prove it by contradiction - you could prove it by contrapositive, and it worked just fine. 01:40 But they _can_ ! I can fly in my dreams :D There's even a song by Astral Projection about that ;) 02:47 Fun fact: that symbol on the end of the proof is called a *tombstone* :D So in case of this particular proof (that people cannot fly), it is _literally_ a tombstone :D 03:07 And what if I want to prove something that has a nut making the statement? :D 04:03 This assumption seems to be superfluous, and it is rarely explained why do we make it at all. And this is bad, because the contradiction in the proof actually only contradicts this assumption and nothing else. Which means that if we relaxed this assumption, then we have no contradiction and the proof breaks down :P But this is a good thing! Because it shows how the proof depends on it, and how this might be a mistake. Because we actually _can_ express `√2` as a fraction! Here it is: 1414213562… √2 = ------------------------ 1000000000… It's just that fraction has infinitely many digits in the numerator and the denominator, and they both contain infinitely many factors of `2`, so we can reduce them infinitely many times (I can even demonstrate it geometrically). But we don't want to deal with such fractions, so we don't include them amongst rational numbers and that's why the `GCD(a,b) = 1` assumption is needed. It says that we're not interested in such solutions, and the proof by contradiction tells us (by contradicting this particular assumption): "Well, too bad, because if you want it to be a fraction, it would have to be an infinite one. If you can't allow for that, then no can do." :J 04:39 Since you already assumed that `GCD(a,b) = 1`, you didn't have to go that far ;> You could just square both sides: √2 = a/b (√2)² = (a/b)² 2 = a² / b² and notice that since `GCD(a,b) = 1`, we already know that `a` and `b` don't have any common factors other than `1`, so they cannot be divided to get an integer. But on the left hand side, we have `2`, which is an integer! This requires the right hand side to be an integer as well, but we cannot fulfil this requirement, because `b²` does not divide `a²`! This is a contradiction we're looking for, so we're done. And it shows even better that the entire proof really depends on the `GCD(a,b) = 1` assumption. You don't even need the lemma for that. Speaking of the lemma, though, it can be proved in much easier and direct way, from the Fundamental Theorem of Arithmetics: In order to extract a square root of an integer, it has to have each prime factor appearing an even number of times, because raising something to the second power just doubles each prime factor. If `x` is not even, then it cannot have any factor of `2` in it, and taking the square root (if possible at all) won't produce that factor out of thin air. So the resulting number cannot be even either. 10:31 It's interesting to check that proof technique for `√4`, because then we have that `a = 4` and `b = 1`, and they satisfy the condition that `GCD(a,b) = 1`: after all, `GCD(4,1) = 1` :) So we can't get the contradiction. And thanks to the Gods of Mathematics for that! Because `√4` is clearly rational (even better: an integer!), so we would be in deep trouble if our proof said otherwise :q
You don’t need to make the gcd(a, b) assumption explicitly, it’s trivially derived: Let √2 = a / b and b ≠ 0. Let a′ = a / gcd(a, b) and b′ = b / gcd(a, b). Notice that gcd(a′, b′) = 1. Now perform the rest of the proof as before but with a′ and b′. In your representation of √2 as a fraction, neither nominator nor denominator is a number. > and they both contain infinitely many factors of `2` You don’t know that. Nominator could be odd. You would have to prove what it’s last digit is but of course you cannot since it’s not a number anyway. > since `GCD(a,b) = 1`, we already know that `a` and `b` don't have any common factors other than `1`, so they cannot be divided to get an integer. […] If b = 1 then b² divides a² so to go on this path you also have to separately prove that √2 is not an integer.
_"In your representation of √2 as a fraction, neither nominator nor denominator is a number."_ If they are not numbers, then pretty much every number that is defined as a limit of an infinite power series is not a number as well :q But mathematicians seem to treat them as numbers just fine. When I wrote this infinite fraction, what I really meant is something based on what +blackpenredpen did in the video, but continued indefinitely instead of finishing after just two steps. First he obtained `a²/b²` and observed that they're both even, which gives us the first pair of factors of 2. But then the numerator and the denominator could be rewritten in terms of two other numbers and the process can be continued, which will produce another pair of factors of 2, etc. And if you add up those partial sums, and keep track of the resulting fraction, you will get bigger and bigger numbers in the numerator and the denominator, while their ratio will start approaching `√2`. "In the limit" you should end up with the infinite fraction I wrote. _"You don’t know that. Nominator could be odd. You would have to prove (...)"_ The proof is in the pudding ;) that is, in the proof for the irrationality of `√2` itself in the video above: when you follow the proof, you get those factors of 2 over and over again, infinitely many times. So they _are_ there indeed. _"If b = 1 then b² divides a²"_ True, I forgot to mention about this loophole for perfect squares. I do that under another video by +Sen Zen, though. Go figure. Also, for future discussions, keep in mind that Google doesn't like my comments from some reasons, and 90% of them don't show up to anyone else except myself :( I might have explained this loophole in one of them which you don't see. The one under +Sen Zen's videos seems to be visible. _"so to go on this path you also have to separately prove that √2 is not an integer."_ Sure, here it goes: `√2` is definitely more than `1`, because: 1² = 1·1 = 1. And we know that: (√2)² = (√2)·(√2) = 2. But it's also definitely less than 2, because: 2² = 2·2 = 4. So `√2` must have been a number between 1 and 2. But there is no integer between 1 and 2, so `√2` cannot be an integer. It could still be a fraction, though, and here comes the classic proof. But this consideration is usually done _before_ one starts the classic proof, so we can safely assume that it has been done indeed before we start proving it in the way described in the video.
> If they are not numbers, then pretty much every number that is defined as a limit of an infinite power series is not a number as well What power series does 1000000000… represent? > And if you add up those partial sums, and keep track of the resulting fraction, you will get bigger and bigger numbers in the numerator and the denominator, while their ratio will start approaching `√2`. "In the limit" you should end up with the infinite fraction I wrote. The ratio will approach √2, that’s true, but nominator and denominator approach infinity which is not a number. > But this consideration is usually done before one starts the classic proof Proof in the video does not require that step.
Sure, 1414213562.../1000000000... is not a valid rational number. But in order to know why (or even whether or not it matters), we need to go in a bit of more detail. Let's express the statement "square root of 2 is not a rational number" in the language of natural numbers (Peano arithmetic); we get: "There don't exist such non-zero numbers a, b, so that a*a=2*b*b". (It's nice that even though Peano arithmentic knows nothing about roots and fractions, we can in fact make this statement in this language). Now the proof starts with an assumption that a and b are coprime (i.e. they aren't both even), and results in a contradiction (that they are in fact both even). But do we know that they are coprime? Not necessarily, but we can take them to be coprime. This depends on the statement I have made in another comment: "Every non-empty set of natural numbers has a minimum", or, equivalently, "If a set of natural numbers doesn't have a minimum, then it is empty". Of course, first-order Peano arithmetic knows nothing about sets, either, so let's rephrase it: "Given formula F(x), if F(n) for some n, then there exists such m that F(x) holds for m, but not for any number smaller than m". (I.e. m is the minimum number for which F(x) holds.) This can be proven from the axiom of induction; again, I'll leave the proof as an exercise for the reader. (In the first-order language, this is an axiom schema: "Given formula F(x), if F(0) and F(n)->F(n+1), then F(x) holds for every x.") Now we can continue the proof: Let A be a minimum number for which there exists the corresponding number B. A and B can't be both divisible by 2. (Otherwise, we could divide them both by 2 and get another pair for which the equation holds. This also depends on the fact that if the number B exists, it is unique.) Then we make the rest of the steps and reach the contradiction that A and B are in fact both even. Therefore, the minimum A and B don't exist. Therefore, neither does any pair of non-zero a and b such that a*a=2*b*b. So does the claim depend on a and b being finite? Well, not necessarily. It only depends on the axiom of induction. (The first-order Peano arithmetic has many non-standard models with infinite numbers, but that "square root of 2 is not a rational number" holds in all of them.)
> So does the claim depend on a and b being finite? Yes, it does: > Let A be a minimum number for which there exists the corresponding number B. Since infinity is not a number, you assume A and B are finite.
6:22 I don’t see how they’re the same. Assuming we prove that if a^2 is odd then so is a, if a^2 is even that could still mean that a is odd, and vice versa. Neither statement proves the other.
"Assuming we prove that if a^2 is odd then so is a, if a^2 is even that could still mean that a is odd, and vice versa." Be careful about the order in which things are said. He proves that if a is odd, then a^2 is odd. This is, indeed, equivalent to "if a^2 is even, then a is even."
Great video! However, I don’t quite understand the contrapositive part of the lemma. How does proving that b is odd when b squared is odd prove the case with even numbers. Wouldn’t that still leave the possibility for b to be odd if b squared is even?
This proof implicitly depends on the following statement: "Every non-empty set of natural numbers has a minimum". This statement happens to be true, but it's not obvious. (It can be proven using the axiom of induction; I'll leave this as an exercise for the reader. Hint: Try to prove an equivalent statement: if the set has no minimum, then it is empty.)
Can someone explain me why we needed a proof by contrapositive? Would it be wrong to say a=2n => a^2=4n^2=2(2n^2) or a^2=4n^2 => (4n^2-a^2)=0 => (2n-a)(2n+a)=0 => a=2n ? I am a first year physics student, sorry in advance if the reason is simple or my mistake is blatant. Besides this uncertainty thank you very much for the video, it was crystal clear and made me understand the proof immediately!
Oh wait i think i understood, is what I said useless because of the direction of my implication? Because I am proving that if a is even then a^2 is even as well, but not the opposite (if a^2 is even then so is a). I think that this is my mistake right?
You're the best proof that there is still reason and rationality at Berkeley. Good job mate! I wish that only SQRT(2) was irrational over there, but on the scale of irrational behavior the SJW's are better at math. Somehow.
Wait, how exactly does a and b being equal prove that sqrt(2) is irrational? Since a/b can still be displayed as a fraction(albeit not in lowest terms), wouldn't that automatically mean that sqrt(2) is rational according to this proof since lowering it to its simplified form would still yield a "a/b" style fraction? Or am I missing something here?
3 года назад
We only suppose we can write square root of two as a fraction. If we could, then it would be rational and it would have the property of being writable as a/b, where b cannot divide a. This proof shows that it cannot have this property, otherwise there would be a contradiction, therefore it is irrational. This is how proof how contradiction works - you assume something is true, make conclusion out of it and if the conclusion is wrong, the hypothesis also must be wrong.
I was just wondering what "shading the box" at thee end of a proof means. He seems to do it in a lot of his videos and he always has a cheeky smile on his face. Is it some inside joke or actual mathematical notation?
It's similar to writing "QED". It's just a symbol to denote the end of a proof. It's useful if you're reading a math text, since you will know where the proofs end.
Let x= sqrt(2) or, x^2 = 2 or {(x^2) - 2} = 0 By using rational root theorem, there is no rational root to this equation. So root to this equation is irrational. Therefore, x = sqrt(2) is IRRATIONAL
I never took algebra in school (way back in the 80's) but I saw this same proof in a big blue book by Websters dictionary. It is Euclid's proof. I believe that when you get to the step where you square both sides, you are done, because that fraction must equal 2/1. What am I missing here? That a square can never be twice another square? I can understand that easily. All even squares are 4x another square.
And this means all even squares are divisible by 4. So if there was a square that was twice another square, that would cause an infinite decent down to 2. So: Even/even - no Even/odd - no Odd? noooo... If root 2 = a/b. Then 2 = a^2/b^2. See what I'm saying?
At the last step sir gcd is 1 you said that contradicts but when we have even divided by even then we would get the simpler fraction with gcd 1 anyone please clarify😢
We started off assuming GCD(1,1). However, we later showed that a/b is divisible (since and a and b are both even). This is impossible by what we first started with, meaning sqrt(2) is not rational. What you are confused by is the rub we found, that despite GCD(a,b) = 1, a/b is divisible.
@@tomasbeltran04050 If you cancel, then you can do the same argument again, and find out that the fractions have common factors again. But they shouldn't because you already cancelled out all of the common factors.
It's like when they tried to prove people were witches. They'd drown them and if they survived then they were a witch. It's a proof by contradiction by assuming they were a witch before drowning them.
Shay It is true that you can't conclude from if a² is odd, then a is odd that if a² is even, then a is even. But he showed that if a is odd, then a² is also odd, from which you can conclude that if a² is even, then a is also even.
That part also made me uncomfortable. Maybe I'm just tired, but I'm having trouble untangling the logic, particularly since the conclusions are certainly correct. An important thing to note is that the contrapositive swaps the order of the if/then. "If a is odd, then a^2 is odd." I think it helps to rewrite it as "If a is *not* even, then a^2 is *not* even." This makes it clearer that only an even a could have produced an even a^2. Edit: Just to add a little more clarity -- The proof shows that all odd numbers become an odd number when they are squared. So if we take a random number from the set of all squared numbers and it is odd, based on this proof we *can not* say whether the number that produced it is odd or even. But if the number we take is even, we can immediately rule out all of the odd numbers as potential roots, leaving only even numbers. Therefore, if a^2 is even, then a must also be even.
Think of it this way: suppose a n^2 is even and b n is even. We assert: a -> b The negatio is: Not(a->b) not (not a or b) a and not b not b and a So we can now show that not(a->b) is false since not b (n is not even) always leads to not a (n^2 is not even) and the expression not b and a is always false. Thus by exclusion of a third possibility, a->b is always true qed
And have you? To be fair to you, maybe you know someone who knows someone who knows someone... who said he knew someone who knew someone... WHO COULD FLY!!!
0:31 hey, irrational is not totally the same as not rational, because of complex numbers. Complex numbers with imaginary term ≠0 can't be classified as rational numbers or irrational numbers. So not rational actually included both irrational number and complex numbers with imaginary term ≠0
The square root of a non-negative real is always a real. In fact, the solutions to y^2=x for a real value of x is either purely real (for positive reals) or purely imaginary (for negative reals). This can be shown easily by the fact that all positive reals are of the form a*e^(0+2nπ) for an integer n and all negative reals are of the form a*e^(i*(π +2nπ)) and so any solution to y^2=x would simply raise those to the power of two. In the positive reals case, this results in 2 branches, one with a 0 angle and the other with a π angle, i.e. a positive and a negative branch. For the negative reals case, it results in a branch with a π/2 angle and one with a 3π/2 angle (i.e negative and positive imaginary numbers) TL;DR mathematically the square root of a positive number like 2 (even if you take square root to be a multivalued function) has to be a real and cannot be complex
I have a question Can all irrational numbers be found for their rational approximation values? Example e use Taylor series you can find rational approximation values of e Are number super irational can be exist ?
Yes, the contrapositive of "A implies B" is "Not(B) implies Not(A)". Proof by contrapositive uses the fact that a statement is equivalent to its contrapositive.
Don’t you have to prove that if a is even then a^2 cannot be odd? Proving that a (as an odd) squared is also odd leaves the possibility that a (as an even) squared might result in an odd no? Or instead directly proving that a (as an even) squared can only be even
Wait, I dont understand the contrapositive part. If we prove If A then B, then that also prove if not A then not B??? Or like the example, If a is odd, the a squared is odd also proves If a even the a squared even???. Its like saying If it rains the floor is wet so If it doesnt rain then the floor is not wet?? but this statement is false right?? Ok now I understand, I didntr read properly the statement
Jon Merladet you almost had it right. It goes as follows: A -> B not B -> not A I will give you an example: I hit my toe -> I feel pain I do not feel pain -> I did not hit my toe But you cannot say I hit my toe -> I feel pain I did not hit my toe -> I do not feel pain Since you could also hit your head and feel pain
My bedroom is inside of my house. So in order to be in my bedroom, you have to be in my house in the first place. You cannot be in my bedroom without being in my house first. In other words, being in my bedroom implies that you're in my house: in Twi's bedroom ==> in Twi's house Suppose that my father claims that you are in my bedroom. How can you prove to him that you're not, if you're unable to demonstrate it to him from some reason? Well, you can use the proof by contrapositive ;> It works this way: NOT in Twi's house ==> NOT in Twi's bedroom That is, you swap the assumption and the conclusion (making a _converse_ statement), and negate both. How does it prove the original statement? Well, recall that in order to be in my bedroom, you have to be in my house in the first place. So if you can show that you're NOT in my house, then obviously you can't be in my bedroom either. So just send my father a picture of yourself being somewhere else and he will not break your legs ;) (my father is a reasonable dude, he understands logic).
it would have been enough to say, that when a2=2b2, then on the right side, tue power of 2 is odd, whereas on the left side it's even, which cannot be true. Q.E.D
Well, the human flying parallel doesn't work. It's the are all swans right mistake there - just because any given dude can't fly doesnt mean the others can't. Penguins are birds, and they cant fly, but that doesn't mean other birds can't. The sqrt(2) proof tho...I've always liked this proof, it's so deliciously simple.
The analogy is incomplete. Even if you push every human over a cliff, all you would prove is that none of them _did_ fly, not that none of them _could_ fly. But let's try it anyway!
Best not to use synthetic propositions to demonstrate proofs by contradictions. Basically that whole business works inductively, which uses a process of falsification to "rule out" competing hypotheses.
Because "if P, then Q" is logically eq to "if not Q, then not P". Therefore, "if a^2 is even, then a is even" is logically eq to "if a is NOT even, then a^2 is NOT even". And not even means odd.
blackpenredpen Yes, I see that. I think I was confusing the statement, "If P then Q, is logically equal to, if not Q then not P" with, "If P then Q, is logically equal to, if not P then not Q"
Why do you think that human can not fly? Let them state if they can fly on their own! Don't you know everything is relative? You could harm someone's feelings.
I can prove any number is irrational with this proof Here I am proving 2 as irrational 2=a/b Where A and B are coprime 2b=a (2b)^2=(a)^2 4 (b)^2=(a)^2 So 4 divides a square and also 4 devids a So (a)=(4c) (a)^2=(4c)^2 a^2=16 c^2 Since a square equals to 4 b square 4 (b)^2=16 c^2 b^2=4 c^2 So B square is divisible by 4 A and B has a common factor 4 other than 1 This breaks the fact that A and B are coprime So2 is irrational
"So 4 divides a square and also 4 devids a" This is not true. Just because 4 divides a^2 does _not_ mean that 4 divides a. As an example, let a = 6. Then 4 divides a^2 = 36, but 4 does not divide a. It is true for prime numbers, though. If p is a prime number and p divides a^2, then p divides a. 2 is a prime number, which is why it works. (But you don't need to go into the details about prime numbers to get it for 2.) In general, using the Fundamental Theorem of Arithmetic, you can show that if at least one prime appearing the prime factorization of n occurs an _odd_ number of times, then if n divides a^2, it must be the case that n divides a. On the other hand, if all primes in the prime factorization of n appears an _even_ number of times, then there's some integer a where n divides a^2 but not a.
Filling a full blackboard to prove that "a is even" "a^2 is even" by contrapositive? Come on, it is so easy to prove it right away: Let a be even, that means (by definition) that a can be written as 2*m, where m is integer. Then a^2 = (2m)^2 = 2^2 * m^2 = 2 * (2m^2). Since m is integer then m^2 is integer and 2m^2 is integer, and since 2 times an integer is an even number, 2*(2m^2)=a^2 is an even number. QED
No, I needed to prove that "if a^2 is even, then a is even". And btw, when you write your lines on the blackboard, you will fill a full blackboard too....
It doesn't _have_ to be, but you can always assume it is. The reason is that if a and b have gcd bigger than 1, then you can divide both a and b by their gcd. You still have an equivalent fraction, but the gcd of the numerator and denominator are now 1. :)
To make your 'humans can't fly' proof tighter, consider this => Assume that for any human that is able to fly, when he jumps off a building, he will fly. Now, your proof will be flawless. ;D
Your lemma strikes me as incomplete. You prove that if a is odd, a^2 must be odd, but that doesn’t actually prove that if a is even, a^2 must also always be even. Maybe the squaring function always produces an odd result..(obviously this is not the case, but you haven’t PROVED it)
"You prove that if a is odd, a^2 must be odd, but that doesn’t actually prove that if a is even, a^2 must also always be even." Be very careful about the order of things here. Yes, he proves that if a is odd, then a^2 is odd. But he then uses that to show that if _a^2_ is even, then _a_ is even (NOT if a is even, then a^2 is even).
Could you not say that because a and a^2 are both integers, then a^2 = (a factor 1, a factor 2 .... a factor n) ^2 = (a factor 1)^2 * (a factor 2)^2 .... (a factor n)^2. So if a factor exists in a^2, it must exist at least twice in a^2, and at least once in a. Since a^2 is even, it has 2 as a factor, so it must be a factor of a as well. Or is that relying too heavily on the fact that all integers have unique prime factorization?
if ur prove that a is an odd number thus a^2 is an odd it doesnt mean that if a is even than a^2 is even that is not logical.U have 2 starting condition even or odd u should prove for the 2 condition to conclude a result
You skipped a few very important steps. Proving that there does not exist a rational solution is not sufficient to affirmatively prove that there does exist an irrational solution. You are neglecting to consider that neither a rational nor an irrational solution may exist. Such would be the case if there were no solution of any kind. Consider this analogy: Suppose there is a pond that can (but not must) either be stocked with fish or sharks. You find a pond to test and you want to prove one way or the other so you first assume that it is stocked with fish. Then you drain the pond and look for fish. If you find zero fish, you successfully contradict your assumption and prove it to be false. This still does not prove that there were in fact sharks. The pond could have been empty. The initial assumption has absolutely nothing to do with sharks so it cannot be used to learn about them. Likewise, your assumption about rational numbers has nothing to do with irrational numbers. Proving a claim to be false does not prove a seemingly related claim to be true.
Lex Markkel I think you mean as the binary case that there must be fish XOR sharks in the pond because marine animals represent numbers and the different kinds of animals represent the different kinds of numbers. The fish vs no fish analogy you explained represents number vs no number as the possible outcomes. Either way, the logical difficulties can be examined from another angle as well. Humans did not always know about the existence of irrational numbers. The day before irrational numbers were discovered, what is the conclusion that one would come up with when attempting this proof? Obviously use the term "not rational" in place of "irrational" since those numbers weren't known about at that time. If new types of numbers can be discovered, how can you be so sure that there is not another yet undiscovered third type?
Sqrt(2) is defined as the number that when squared equals 2. We know that number does not exist as a rational solution. That still is not prove that it does exist as an irrational solution. First you need to show that there is a solution and then you can show that it is irrational. Consider this example: x+3=2x+4-x x is defined as the number that when added to three equals twice itself plus four minus itself. Prove that x is irrational. An attempt might go like this: First assume that x is rational and of the form x=p/q Go on to show a contradiction (easy to do) Therefore x must be an irrational number See the problem here? Your definition of irrational is flawed in the sense that you assume existence of the number which is not always true. Getting back to my initial post, the proof step that the video leaves out is the proof of existence. It needs to go: prove not rational, prove number exists, therefore it follows that the number is irrational.
"The number exists and can be described in the form x = a." But it cannot be described in the form x=a/b with lets say for example b=1? Or do you mean a is an irrational number and therefore it is trivial to see that x exists? In which case, why even bother with a proof since you appear to be defining the number into existence? Also, the expression x^2 = 2; x = 2^(1/2) on its own is not sufficient to prove that x exists. It is also not a requirement that all real numbers be expressible in the form x=a.
The "humans can't fly" is a very bad analogy for a proof by contradiction. To beging with, the statement is extremely vague, e.g. humans do fly in planes or other vehicles, and the human that jumped from the building flew once... downwards. You could even send an astronaut to a different planet where he or she would be able to fly, and so on. But the severe flaw here is that the "proof" is not valid: your experiment only shows that a particular human wasn't flying in that specific instance. A valid proof via experimentations like this would require taking every single human (from the past, present and future), put them into every possible environmental condition (repeated times) and check if each human can or can't fly. A more straightforward and proper proof would be accomplished by figuring out the physical properties required for a living being being able to fly (e.g. birds, insects, bats) and stating that humans do not fulfill those properties. But in this way the proof would have very little resemblance to the irrationality of sqrt(2) proof.
+xnick I agree with you in most of what you wrote. But I'm not so sure about the part that the approach you proposed would have nothing to do with proving the irrationality of `√2`. There are certain conditions a number has to fulfil in order to be rational. So if we can show that `√2` cannot fulfil those conditions in any possible way, then we can prove that it is not rational, hence irrational ;) So it might be fun to play with this idea a little more. Who knows, maybe you'll discover a better, more direct proof for the irrationality of `√2` this way? :)
Your proof that humans cannot fly makes no sense to me. We all know it is true but surely the fact that one person or even a thousand or a million hit the deck does not prove it for all humans. On the contrapositive example you say that if a is even then a squared is even and from this statement alone you say that this must mean that if a is odd etc. So what if I say if a is negative then a squared is positive?
Too long . For any natural N and k, root of k power of N if not natural then always irrational. If all prime dividers of N are factored in powers divisible by k then the root equals to product of same prime divisors UK n powers divided by k. If there exists a prime factor with degree not divisible by k then an assumption of rationality of the root leads to easy cobtradiction
Really good example of the contradiction concept. I like the macabre comparison to the flying human 👍
If you can prove "humans cannot fly", then you will understand "proofs by contradiction"
If you can understand why this proof technique breaks down for some humans at certain conditions, then you will understand why proofs by contradiction can sometimes break down for valid reasons (hint: they require the Law of Excluded Middle to be true, which is not always so certain, e.g. in intuitionistic logic) ;>
I can prove to you by contradiction that `1` is the largest natural number. Here it goes:
Assume that `1` is _not_ the largest natural number.
Then let `n > 1` be the largest natural number.
But wait! Then `n² > n` is even larger a natural number, which is a contradiction :q
Therefore the _original_ statement that `1` is the largest natural number must have been true ;>
Can you tell what's wrong with this proof? :>
Don't get me wrong: I liked your analogy, it actually demonstrates this proof technique very well. I like it! :)
It's just that it also demonstrates very well why this proof technique can break down sometimes :J
You know how students often ask "how do we know when to use proof by contradiction"?
My "humans can't fly" was for that.
I think Proof by Contradiction is only used when the given statement says something is *not* true, so you can show the contradictions when that something *is* true to prove that it has to be not true
Sci Twi I can tell you much which is wrong with your proof. You cannot assume that the inference of n^2 > n from n > 1 is valid if n is assumed by hypothesis to be the largest number.
Also, the law of the excluded middle is not what is strictly required for proof by contradiction to work. What you need is the law of non-contradiction instead, because this law allows P and not P to be a default falsum. Then I can state the first premise as “Q implies P and not P”, and since P and not P is a falsum, then it must be the case that the negation of it is true. This demonstrates not Q by the inference of modus tollens. I other words, this is a consequence of the inference rule “A implies B”, “not B” to conclude “not A”, Also known as the law of contrapositives.
Hmm, it doesn't seem like a good answer, because there wasn't any contradiction there (IMHO this statement cannot be proven unless you give a very specific definition of "human" that makes the proof trivial). In fact it seems like a good example for illustrating why something that looks like a proof actually isn't rigorous.
A better advice would be: use proof by contradiction if you can find a contradiction. It doesn't have to be limited to when the statement has a "not"
Everyone is talking about that the proof of humans cannot fly is wrong but I don't think they understand the intention of this "proof"
knochentrocken96 thank you!!
To be fair there are probably better ways to demonstrate the idea (ways which don't involve problems with the actual proof)
An example would be "Prove 3 is not even". Prove it by assuming that 3 is even, which means that dividing it by 2 would produce an integer.. Show that 3 / 2 is NOT an integer, and that proves it. No nitpicking necessary as (I think) there aren't any inherent flaws that aren't just pushing it (I doubt anyone would argue that dividing 2n by 2 would not produce an integer if n is an integer)
I will agree however that the comments are unnecessary
"And that's messed up, right?!" XD
You only proved that humans cannot fly _other than downwards._
:D
And BTW how do you know that you can not fly? Have you ever REALLY tried?
In which case, we call that definition of "fly" as "falling."
you gonna like 6Tenet.
We have been trying to talk sense to sqrt(2), but it just keeps being stubborn and so utterly irrational. It's impossible to talk to it. It won't change its mind no matter what, and no matter how clearly it's shown how wrong it is. A lost case.
Not only that, but it has got some imaginary friends, like `√(-1)` & stuff :P
Whenever it starts, it just never seems to come to an end, always keeps on going like it's forever mannnnn
Personally I prefer "Q.E.D".
You forgot the obligatory "BITCHES!" after the "Q.E.D." ;)
I prefer quod erat demonstradum
I prefer quantum electrodynamics
Thank you so much for this video! I love how you explain things with an enormous joy and passion for math. Thank you again, keep up the good work!!
But humans can fly...
in an airplane.
haha...
Square roots can be represented in fractions...
but not by integers.
"Humans can fly in an aeroplane"?
Surely you do understand what he meant, but you had to NITPICK!!!
All for what purpose?
@@mrjnutube To win the internet
"Humans can't fly" -- Well it looks like one stick figure was dying to prove you wrong.
The story is told that this proof was originally discovered by one of the students in Pythagoras's school. But one of the most strongly held Pythagorean beliefs -- a religious belief, not a rational* one, obviously! -- was that all numbers were rational, that the whole universe consisted of "harmonious ratios". The story continues that they had the student killed, in order to suppress his proof that this wasn't the case. (But I think they had him drowned at sea, rather than throwing him off a building.)
* So, an irrational belief in the rationality of the universe? ;-)
I think the best way to really understand this is to also prove that sqrt(3) is irrational and that sqrt(4) is irrational, and notice where that last proof doesn't work. For 3 and 5, there are several cases in the lemma, but they still prove that the only way a^2 can be a multiple is if a is a multiple. With 4, another case works when it wasn't supposed to, which is how we can have perfect squares.
Can you do one proving the irrationality of e!
it can be done with taylor series
That would be a long video, because he would have to start with a discussion of the extension of the factorial function to non-integers (e.g. the gamma function).
Not necessarily. If you use the Taylor Series it isn't that hard (Mathologer did it)
You need the gamma function to compute e!.
I am not sure whether that exclamation mark was meant as a factorial or not...
Suppose root 2 has rationality
To find a contradiction we must try
to write our root as fraction a on b
but show we can't, for something goes awry
By squaring our equation on both sides
then multiply; a squared is 2b squared
That 2 divides a squared is thus implied
and therefore 4 (squared factors come in pairs)
But be a squared a multiple of 4
Then half that (b squared) must divide by 2
By using the same logic as before
Then 4 divides b squared, it must be true
To share no factors, a and b are bound
But 2 they share, a contradiction found
Very important the explanation of why gcd(a,b)=1. And a lots of teachers skip that part. Practically the contradiction is that, if sqrt(2) is rational than his fraction can be simplified infinitely by 2.
An easy (although less formally strict) way to prove that if a² is even, then a is even: The prime factor of 2 has to come from somewhere, it cannot be a product of multiple prime factors in a×a (because then it would not be prime), so each a must have at least one prime factor 2.
And an alternative second blackboard:
√2×b=2k
b=√2×k
b=a/b×k
1=a×k
1=2k²
0.5=k²
0.25=k
wow you’re so good at explaining things 🤩
Humans can't fly but flies can human.
woow, nice proof! I think the proof of humans can't fly just the "add-on" , the main thing in this video is showing how to use the contradiction-based proof
can you make a video/videos about combinatorics? It will be nice and great if you explain it!
Thank you Azzam.
I don't have a good collection of combinatoric problems at the moment. Maybe later on in the future, yes.
01:15 The fact that it has the "not" in its definition doesn't necessarily mean that one has to prove it by contradiction. One can also prove it by contrapositive. It also doesn't mean that one _cannot_ use direct proof ;) And your other proof (for the lemma) shows exactly that: it also had the word "not" in it ("not odd", a.k.a. even), but you didn't have to prove it by contradiction - you could prove it by contrapositive, and it worked just fine.
01:40 But they _can_ ! I can fly in my dreams :D There's even a song by Astral Projection about that ;)
02:47 Fun fact: that symbol on the end of the proof is called a *tombstone* :D So in case of this particular proof (that people cannot fly), it is _literally_ a tombstone :D
03:07 And what if I want to prove something that has a nut making the statement? :D
04:03 This assumption seems to be superfluous, and it is rarely explained why do we make it at all. And this is bad, because the contradiction in the proof actually only contradicts this assumption and nothing else. Which means that if we relaxed this assumption, then we have no contradiction and the proof breaks down :P
But this is a good thing! Because it shows how the proof depends on it, and how this might be a mistake. Because we actually _can_ express `√2` as a fraction! Here it is:
1414213562…
√2 = ------------------------
1000000000…
It's just that fraction has infinitely many digits in the numerator and the denominator, and they both contain infinitely many factors of `2`, so we can reduce them infinitely many times (I can even demonstrate it geometrically). But we don't want to deal with such fractions, so we don't include them amongst rational numbers and that's why the `GCD(a,b) = 1` assumption is needed. It says that we're not interested in such solutions, and the proof by contradiction tells us (by contradicting this particular assumption): "Well, too bad, because if you want it to be a fraction, it would have to be an infinite one. If you can't allow for that, then no can do." :J
04:39 Since you already assumed that `GCD(a,b) = 1`, you didn't have to go that far ;> You could just square both sides:
√2 = a/b
(√2)² = (a/b)²
2 = a² / b²
and notice that since `GCD(a,b) = 1`, we already know that `a` and `b` don't have any common factors other than `1`, so they cannot be divided to get an integer. But on the left hand side, we have `2`, which is an integer! This requires the right hand side to be an integer as well, but we cannot fulfil this requirement, because `b²` does not divide `a²`!
This is a contradiction we're looking for, so we're done. And it shows even better that the entire proof really depends on the `GCD(a,b) = 1` assumption. You don't even need the lemma for that.
Speaking of the lemma, though, it can be proved in much easier and direct way, from the Fundamental Theorem of Arithmetics: In order to extract a square root of an integer, it has to have each prime factor appearing an even number of times, because raising something to the second power just doubles each prime factor. If `x` is not even, then it cannot have any factor of `2` in it, and taking the square root (if possible at all) won't produce that factor out of thin air. So the resulting number cannot be even either.
10:31 It's interesting to check that proof technique for `√4`, because then we have that `a = 4` and `b = 1`, and they satisfy the condition that `GCD(a,b) = 1`: after all, `GCD(4,1) = 1` :) So we can't get the contradiction. And thanks to the Gods of Mathematics for that! Because `√4` is clearly rational (even better: an integer!), so we would be in deep trouble if our proof said otherwise :q
You don’t need to make the gcd(a, b) assumption explicitly, it’s trivially derived:
Let √2 = a / b and b ≠ 0. Let a′ = a / gcd(a, b) and b′ = b / gcd(a, b). Notice that gcd(a′, b′) = 1. Now perform the rest of the proof as before but with a′ and b′.
In your representation of √2 as a fraction, neither nominator nor denominator is a number.
> and they both contain infinitely many factors of `2`
You don’t know that. Nominator could be odd. You would have to prove what it’s last digit is but of course you cannot since it’s not a number anyway.
> since `GCD(a,b) = 1`, we already know that `a` and `b` don't have any common factors other than `1`, so they cannot be divided to get an integer. […]
If b = 1 then b² divides a² so to go on this path you also have to separately prove that √2 is not an integer.
_"In your representation of √2 as a fraction, neither nominator nor denominator is a number."_
If they are not numbers, then pretty much every number that is defined as a limit of an infinite power series is not a number as well :q But mathematicians seem to treat them as numbers just fine.
When I wrote this infinite fraction, what I really meant is something based on what +blackpenredpen did in the video, but continued indefinitely instead of finishing after just two steps. First he obtained `a²/b²` and observed that they're both even, which gives us the first pair of factors of 2. But then the numerator and the denominator could be rewritten in terms of two other numbers and the process can be continued, which will produce another pair of factors of 2, etc. And if you add up those partial sums, and keep track of the resulting fraction, you will get bigger and bigger numbers in the numerator and the denominator, while their ratio will start approaching `√2`. "In the limit" you should end up with the infinite fraction I wrote.
_"You don’t know that. Nominator could be odd. You would have to prove (...)"_
The proof is in the pudding ;) that is, in the proof for the irrationality of `√2` itself in the video above: when you follow the proof, you get those factors of 2 over and over again, infinitely many times. So they _are_ there indeed.
_"If b = 1 then b² divides a²"_
True, I forgot to mention about this loophole for perfect squares. I do that under another video by +Sen Zen, though. Go figure.
Also, for future discussions, keep in mind that Google doesn't like my comments from some reasons, and 90% of them don't show up to anyone else except myself :( I might have explained this loophole in one of them which you don't see. The one under +Sen Zen's videos seems to be visible.
_"so to go on this path you also have to separately prove that √2 is not an integer."_
Sure, here it goes:
`√2` is definitely more than `1`, because: 1² = 1·1 = 1.
And we know that: (√2)² = (√2)·(√2) = 2.
But it's also definitely less than 2, because: 2² = 2·2 = 4.
So `√2` must have been a number between 1 and 2.
But there is no integer between 1 and 2, so `√2` cannot be an integer.
It could still be a fraction, though, and here comes the classic proof.
But this consideration is usually done _before_ one starts the classic proof, so we can safely assume that it has been done indeed before we start proving it in the way described in the video.
> If they are not numbers, then pretty much every number that is defined as a limit of an infinite power series is not a number as well
What power series does 1000000000… represent?
> And if you add up those partial sums, and keep track of the resulting
fraction, you will get bigger and bigger numbers in the numerator and
the denominator, while their ratio will start approaching `√2`. "In the
limit" you should end up with the infinite fraction I wrote.
The ratio will approach √2, that’s true, but nominator and denominator approach infinity which is not a number.
> But this consideration is usually done before one starts the classic proof
Proof in the video does not require that step.
Sure, 1414213562.../1000000000... is not a valid rational number. But in order to know why (or even whether or not it matters), we need to go in a bit of more detail.
Let's express the statement "square root of 2 is not a rational number" in the language of natural numbers (Peano arithmetic); we get: "There don't exist such non-zero numbers a, b, so that a*a=2*b*b". (It's nice that even though Peano arithmentic knows nothing about roots and fractions, we can in fact make this statement in this language).
Now the proof starts with an assumption that a and b are coprime (i.e. they aren't both even), and results in a contradiction (that they are in fact both even). But do we know that they are coprime? Not necessarily, but we can take them to be coprime. This depends on the statement I have made in another comment: "Every non-empty set of natural numbers has a minimum", or, equivalently, "If a set of natural numbers doesn't have a minimum, then it is empty". Of course, first-order Peano arithmetic knows nothing about sets, either, so let's rephrase it: "Given formula F(x), if F(n) for some n, then there exists such m that F(x) holds for m, but not for any number smaller than m". (I.e. m is the minimum number for which F(x) holds.)
This can be proven from the axiom of induction; again, I'll leave the proof as an exercise for the reader. (In the first-order language, this is an axiom schema: "Given formula F(x), if F(0) and F(n)->F(n+1), then F(x) holds for every x.") Now we can continue the proof: Let A be a minimum number for which there exists the corresponding number B. A and B can't be both divisible by 2. (Otherwise, we could divide them both by 2 and get another pair for which the equation holds. This also depends on the fact that if the number B exists, it is unique.) Then we make the rest of the steps and reach the contradiction that A and B are in fact both even. Therefore, the minimum A and B don't exist. Therefore, neither does any pair of non-zero a and b such that a*a=2*b*b.
So does the claim depend on a and b being finite? Well, not necessarily. It only depends on the axiom of induction. (The first-order Peano arithmetic has many non-standard models with infinite numbers, but that "square root of 2 is not a rational number" holds in all of them.)
> So does the claim depend on a and b being finite?
Yes, it does:
> Let A be a minimum number for which there exists the corresponding number B.
Since infinity is not a number, you assume A and B are finite.
"ISN'T IT" returns!
Yes, isn't it?!
:)
6:22 I don’t see how they’re the same. Assuming we prove that if a^2 is odd then so is a, if a^2 is even that could still mean that a is odd, and vice versa. Neither statement proves the other.
"Assuming we prove that if a^2 is odd then so is a, if a^2 is even that could still mean that a is odd, and vice versa."
Be careful about the order in which things are said. He proves that if a is odd, then a^2 is odd. This is, indeed, equivalent to "if a^2 is even, then a is even."
@@MuffinsAPlenty I don’t know who responds to year old comments with zero likes but thank you
Thanks a lot sir. I have been searching for this.
Great video! However, I don’t quite understand the contrapositive part of the lemma. How does proving that b is odd when b squared is odd prove the case with even numbers. Wouldn’t that still leave the possibility for b to be odd if b squared is even?
it isn’t proving that b is odd when b squared is odd, it’s proving that b squared is odd when b is odd.
Bad day to be an intern assigned to help with proofs.
This proof implicitly depends on the following statement: "Every non-empty set of natural numbers has a minimum". This statement happens to be true, but it's not obvious. (It can be proven using the axiom of induction; I'll leave this as an exercise for the reader. Hint: Try to prove an equivalent statement: if the set has no minimum, then it is empty.)
Can someone explain me why we needed a proof by contrapositive? Would it be wrong to say a=2n => a^2=4n^2=2(2n^2) or a^2=4n^2 => (4n^2-a^2)=0 => (2n-a)(2n+a)=0 => a=2n ?
I am a first year physics student, sorry in advance if the reason is simple or my mistake is blatant.
Besides this uncertainty thank you very much for the video, it was crystal clear and made me understand the proof immediately!
Oh wait i think i understood, is what I said useless because of the direction of my implication? Because I am proving that if a is even then a^2 is even as well, but not the opposite (if a^2 is even then so is a). I think that this is my mistake right?
BTW - video for "proof of infinitely many primes" is broken :(
6612770PLUS I will have it up later
Oh, this gonna be good ;> Because I suppose that you will claim that Euclid proved it by contradiction too ;>
You are a great teacher and you look younger than me haha... How old are you??
I will answer that in my next Q&A video!
Why we have to assume a/b is in its simplest form? I believe its not part of the definition of a rational number?
You're the best proof that there is still reason and rationality at Berkeley. Good job mate!
I wish that only SQRT(2) was irrational over there, but on the scale of irrational behavior the SJW's are better at math. Somehow.
Engineer:why do so much when you can use "CALCULATOR"
But wouldn't you have to prove √(2n+1) is odd in order to prove that if a² is odd, a is also odd?
Wait, how exactly does a and b being equal prove that sqrt(2) is irrational?
Since a/b can still be displayed as a fraction(albeit not in lowest terms), wouldn't that automatically mean that sqrt(2) is rational according to this proof since lowering it to its simplified form would still yield a "a/b" style fraction?
Or am I missing something here?
We only suppose we can write square root of two as a fraction. If we could, then it would be rational and it would have the property of being writable as a/b, where b cannot divide a.
This proof shows that it cannot have this property, otherwise there would be a contradiction, therefore it is irrational.
This is how proof how contradiction works - you assume something is true, make conclusion out of it and if the conclusion is wrong, the hypothesis also must be wrong.
It has to be in reduced form already. By definition, it is in its lowest form already.
That he can fly is not proved. At moment when fell down (or kicked) from the top of the building, he decided not to fly!
I was just wondering what "shading the box" at thee end of a proof means. He seems to do it in a lot of his videos and he always has a cheeky smile on his face. Is it some inside joke or actual mathematical notation?
It's similar to writing "QED". It's just a symbol to denote the end of a proof. It's useful if you're reading a math text, since you will know where the proofs end.
Why is this guy always laughinf 😂😂
Loca so u can laugh too. 😂
Let x= sqrt(2)
or, x^2 = 2
or {(x^2) - 2} = 0
By using rational root theorem, there is no rational root to this equation.
So root to this equation is irrational.
Therefore, x = sqrt(2) is IRRATIONAL
I never took algebra in school (way back in the 80's) but I saw this same proof in a big blue book by Websters dictionary. It is Euclid's proof. I believe that when you get to the step where you square both sides, you are done, because that fraction must equal 2/1. What am I missing here? That a square can never be twice another square? I can understand that easily. All even squares are 4x another square.
And this means all even squares are divisible by 4. So if there was a square that was twice another square, that would cause an infinite decent down to 2. So:
Even/even - no
Even/odd - no
Odd? noooo...
If root 2 = a/b. Then 2 = a^2/b^2.
See what I'm saying?
Hi, is there any chance could do a series of videos focused on functional analysis? (not sure this is your field though).
At the last step sir gcd is 1 you said that contradicts but when we have even divided by even then we would get the simpler fraction with gcd 1 anyone please clarify😢
We started off assuming GCD(1,1). However, we later showed that a/b is divisible (since and a and b are both even). This is impossible by what we first started with, meaning sqrt(2) is not rational.
What you are confused by is the rub we found, that despite GCD(a,b) = 1, a/b is divisible.
What if √2 was the division of two numbers with common factors?
All rational numbers can be "reduced". If they had a common factor, you could cancel it.
@@MuffinsAPlenty what if after canceling that's the result?
@@tomasbeltran04050 If you cancel, then you can do the same argument again, and find out that the fractions have common factors again. But they shouldn't because you already cancelled out all of the common factors.
@@MuffinsAPlenty ok thanks
Proof by contraposition actually blows my mind, so conterintuitive
Yea. But sometimes it's really useful, just like in this problem it was easier with contrapositive
Is it necessary here though? Couldn't you just prove that a^2 is even if a is even like this...
a = 2n => a^2 = (2n)^2 = 4.n^2 = 2(2.n^2) => even.
@@TCWordz are you serious? do you read what you write sometimes?
It's like when they tried to prove people were witches. They'd drown them and if they survived then they were a witch. It's a proof by contradiction by assuming they were a witch before drowning them.
5:34
But there you are showing that if a^2 is odd, then a is also odd. You cannot conclude from that that if a^2 is even, a is also even, right?
Shay It is true that you can't conclude from if a² is odd, then a is odd that if a² is even, then a is even. But he showed that if a is odd, then a² is also odd, from which you can conclude that if a² is even, then a is also even.
How? I must be blind, really.
I think it's easier to say that an integer of the form 2k has a square of the form 4k^2, which is also a even.
That part also made me uncomfortable. Maybe I'm just tired, but I'm having trouble untangling the logic, particularly since the conclusions are certainly correct. An important thing to note is that the contrapositive swaps the order of the if/then. "If a is odd, then a^2 is odd." I think it helps to rewrite it as "If a is *not* even, then a^2 is *not* even." This makes it clearer that only an even a could have produced an even a^2.
Edit: Just to add a little more clarity -- The proof shows that all odd numbers become an odd number when they are squared. So if we take a random number from the set of all squared numbers and it is odd, based on this proof we *can not* say whether the number that produced it is odd or even. But if the number we take is even, we can immediately rule out all of the odd numbers as potential roots, leaving only even numbers. Therefore, if a^2 is even, then a must also be even.
Aaah. When you rewrote the statement I understood.
Thank you!
Think of it this way: suppose a n^2 is even and b n is even.
We assert:
a -> b
The negatio is:
Not(a->b) not (not a or b) a and not b
not b and a
So we can now show that not(a->b) is false since not b (n is not even) always leads to not a (n^2 is not even) and the expression not b and a is always false. Thus by exclusion of a third possibility, a->b is always true qed
It only means that you have not found a person who can fly.
And have you?
To be fair to you, maybe you know someone who knows someone who knows someone... who said he knew someone who knew someone... WHO COULD FLY!!!
This is the Raven Paradox
ruclips.net/video/Ca_sxDTPo60/видео.html
Its prime factorization contains a noninteger; thus its irrational.
0:31 hey, irrational is not totally the same as not rational, because of complex numbers. Complex numbers with imaginary term ≠0 can't be classified as rational numbers or irrational numbers. So not rational actually included both irrational number and complex numbers with imaginary term ≠0
So, after you proved √2 is not rational, you should include that Im(√2)=0 to draw a better conclusion
The square root of a non-negative real is always a real. In fact, the solutions to y^2=x for a real value of x is either purely real (for positive reals) or purely imaginary (for negative reals). This can be shown easily by the fact that all positive reals are of the form a*e^(0+2nπ) for an integer n and all negative reals are of the form a*e^(i*(π +2nπ)) and so any solution to y^2=x would simply raise those to the power of two. In the positive reals case, this results in 2 branches, one with a 0 angle and the other with a π angle, i.e. a positive and a negative branch. For the negative reals case, it results in a branch with a π/2 angle and one with a 3π/2 angle (i.e negative and positive imaginary numbers)
TL;DR mathematically the square root of a positive number like 2 (even if you take square root to be a multivalued function) has to be a real and cannot be complex
I have a question
Can all irrational numbers be found for their rational approximation values?
Example e use Taylor series you can find rational approximation values of e
Are number super irational can be exist ?
Nanoha can fly. Does that mean that on Mid-Childa, sqrt(2) is rational? :-)
Why are you holding the death star?
Why, to have the Force be with him, of course ;>
I have a question: is the contropositive proof the same as:
A implicates B is equivalent to notB implicates notA?
Yes, the contrapositive of "A implies B" is "Not(B) implies Not(A)". Proof by contrapositive uses the fact that a statement is equivalent to its contrapositive.
Was looking for a place that explained why 6|x^2 => 6|x.
Knew I could trust bprp.
Don’t you have to prove that if a is even then a^2 cannot be odd? Proving that a (as an odd) squared is also odd leaves the possibility that a (as an even) squared might result in an odd no?
Or instead directly proving that a (as an even) squared can only be even
If a is odd, a^2 must be odd.
Therefore, if you have an even a^2, you can't have an odd a.
So a must be even.
Wait, I dont understand the contrapositive part. If we prove If A then B, then that also prove if not A then not B??? Or like the example, If a is odd, the a squared is odd also proves If a even the a squared even???.
Its like saying If it rains the floor is wet so If it doesnt rain then the floor is not wet?? but this statement is false right??
Ok now I understand, I didntr read properly the statement
Jon Merladet you almost had it right.
It goes as follows:
A -> B not B -> not A
I will give you an example:
I hit my toe -> I feel pain
I do not feel pain -> I did not hit my toe
But you cannot say
I hit my toe -> I feel pain
I did not hit my toe -> I do not feel pain
Since you could also hit your head and feel pain
knochentrocken96 Thanks, I already understood the logic. Its more or less the same as the proof by reduction.
My bedroom is inside of my house. So in order to be in my bedroom, you have to be in my house in the first place. You cannot be in my bedroom without being in my house first. In other words, being in my bedroom implies that you're in my house:
in Twi's bedroom ==> in Twi's house
Suppose that my father claims that you are in my bedroom. How can you prove to him that you're not, if you're unable to demonstrate it to him from some reason?
Well, you can use the proof by contrapositive ;> It works this way:
NOT in Twi's house ==> NOT in Twi's bedroom
That is, you swap the assumption and the conclusion (making a _converse_ statement), and negate both.
How does it prove the original statement?
Well, recall that in order to be in my bedroom, you have to be in my house in the first place. So if you can show that you're NOT in my house, then obviously you can't be in my bedroom either. So just send my father a picture of yourself being somewhere else and he will not break your legs ;) (my father is a reasonable dude, he understands logic).
Why are you assuming that I cannot fly?
Why are you assuming that you are a human being?
it would have been enough to say, that when a2=2b2, then on the right side, tue power of 2 is odd, whereas on the left side it's even, which cannot be true. Q.E.D
Well, the human flying parallel doesn't work. It's the are all swans right mistake there - just because any given dude can't fly doesnt mean the others can't. Penguins are birds, and they cant fly, but that doesn't mean other birds can't.
The sqrt(2) proof tho...I've always liked this proof, it's so deliciously simple.
The analogy is incomplete. Even if you push every human over a cliff, all you would prove is that none of them _did_ fly, not that none of them _could_ fly.
But let's try it anyway!
It relies on the Axiom of self-preservation.
Best not to use synthetic propositions to demonstrate proofs by contradictions. Basically that whole business works inductively, which uses a process of falsification to "rule out" competing hypotheses.
I don't understand the lemma. How does proving a is odd if a² is odd prove a is even if a² is even? Can someone help me wit this.
Because "if P, then Q" is logically eq to "if not Q, then not P".
Therefore, "if a^2 is even, then a is even" is logically eq to "if a is NOT even, then a^2 is NOT even".
And not even means odd.
blackpenredpen Yes, I see that.
I think I was confusing the statement,
"If P then Q, is logically equal to, if not Q then not P"
with,
"If P then Q, is logically equal to, if not P then not Q"
Why do you think that human can not fly? Let them state if they can fly on their own! Don't you know everything is relative? You could harm someone's feelings.
Helpful 😊
I can prove any number is irrational with this proof
Here I am proving 2 as irrational
2=a/b
Where A and B are coprime
2b=a
(2b)^2=(a)^2
4 (b)^2=(a)^2
So 4 divides a square and also 4 devids a
So (a)=(4c)
(a)^2=(4c)^2
a^2=16 c^2
Since a square equals to 4 b square
4 (b)^2=16 c^2
b^2=4 c^2
So B square is divisible by 4
A and B has a common factor 4 other than 1
This breaks the fact that A and B are coprime
So2 is irrational
"So 4 divides a square and also 4 devids a"
This is not true. Just because 4 divides a^2 does _not_ mean that 4 divides a.
As an example, let a = 6. Then 4 divides a^2 = 36, but 4 does not divide a.
It is true for prime numbers, though. If p is a prime number and p divides a^2, then p divides a. 2 is a prime number, which is why it works. (But you don't need to go into the details about prime numbers to get it for 2.)
In general, using the Fundamental Theorem of Arithmetic, you can show that if at least one prime appearing the prime factorization of n occurs an _odd_ number of times, then if n divides a^2, it must be the case that n divides a. On the other hand, if all primes in the prime factorization of n appears an _even_ number of times, then there's some integer a where n divides a^2 but not a.
Filling a full blackboard to prove that "a is even" "a^2 is even" by contrapositive? Come on, it is so easy to prove it right away:
Let a be even, that means (by definition) that a can be written as 2*m, where m is integer.
Then a^2 = (2m)^2 = 2^2 * m^2 = 2 * (2m^2). Since m is integer then m^2 is integer and 2m^2 is integer, and since 2 times an integer is an even number, 2*(2m^2)=a^2 is an even number. QED
No, I needed to prove that "if a^2 is even, then a is even".
And btw, when you write your lines on the blackboard, you will fill a full blackboard too....
You are right.
I love this guy
Funny prove 😊
Probably no one is gonna see this but can someone explain why does gcd have to be 1
It doesn't _have_ to be, but you can always assume it is. The reason is that if a and b have gcd bigger than 1, then you can divide both a and b by their gcd. You still have an equivalent fraction, but the gcd of the numerator and denominator are now 1. :)
To make your 'humans can't fly' proof tighter, consider this
=> Assume that for any human that is able to fly, when he jumps off a building, he will fly.
Now, your proof will be flawless. ;D
Such an interesting explanation that humans can't fly...
You mean √2 ?
I can fly actually.
Your lemma strikes me as incomplete. You prove that if a is odd, a^2 must be odd, but that doesn’t actually prove that if a is even, a^2 must also always be even. Maybe the squaring function always produces an odd result..(obviously this is not the case, but you haven’t PROVED it)
"You prove that if a is odd, a^2 must be odd, but that doesn’t actually prove that if a is even, a^2 must also always be even."
Be very careful about the order of things here. Yes, he proves that if a is odd, then a^2 is odd. But he then uses that to show that if _a^2_ is even, then _a_ is even (NOT if a is even, then a^2 is even).
You didn't prove he CAN NOT fly, only that he didn't want to!
I thought you was going to use physics.
Krishna Sharma lol!
Could you proof that pi is irrational?
to proof if a is even a² is even can't you just say:
a=2n
=>a²=4n²=2(2n²) with 2n² € Z
That is true.
But I needed to prove if a^2 is even, then a is even.
Could you not say that because a and a^2 are both integers, then a^2 = (a factor 1, a factor 2 .... a factor n) ^2 = (a factor 1)^2 * (a factor 2)^2 .... (a factor n)^2. So if a factor exists in a^2, it must exist at least twice in a^2, and at least once in a. Since a^2 is even, it has 2 as a factor, so it must be a factor of a as well. Or is that relying too heavily on the fact that all integers have unique prime factorization?
I'm not sure... if you try for square root of 4, it must be irrational too...
if ur prove that a is an odd number thus a^2 is an odd it doesnt mean that if a is even than a^2 is even that is not logical.U have 2 starting condition even or odd u should prove for the 2 condition to conclude a result
You skipped a few very important steps. Proving that there does not exist a rational solution is not sufficient to affirmatively prove that there does exist an irrational solution. You are neglecting to consider that neither a rational nor an irrational solution may exist. Such would be the case if there were no solution of any kind. Consider this analogy: Suppose there is a pond that can (but not must) either be stocked with fish or sharks. You find a pond to test and you want to prove one way or the other so you first assume that it is stocked with fish. Then you drain the pond and look for fish. If you find zero fish, you successfully contradict your assumption and prove it to be false. This still does not prove that there were in fact sharks. The pond could have been empty. The initial assumption has absolutely nothing to do with sharks so it cannot be used to learn about them. Likewise, your assumption about rational numbers has nothing to do with irrational numbers. Proving a claim to be false does not prove a seemingly related claim to be true.
Lex Markkel I think you mean as the binary case that there must be fish XOR sharks in the pond because marine animals represent numbers and the different kinds of animals represent the different kinds of numbers. The fish vs no fish analogy you explained represents number vs no number as the possible outcomes. Either way, the logical difficulties can be examined from another angle as well. Humans did not always know about the existence of irrational numbers. The day before irrational numbers were discovered, what is the conclusion that one would come up with when attempting this proof? Obviously use the term "not rational" in place of "irrational" since those numbers weren't known about at that time. If new types of numbers can be discovered, how can you be so sure that there is not another yet undiscovered third type?
Sqrt(2) is defined as the number that when squared equals 2. We know that number does not exist as a rational solution. That still is not prove that it does exist as an irrational solution. First you need to show that there is a solution and then you can show that it is irrational. Consider this example:
x+3=2x+4-x
x is defined as the number that when added to three equals twice itself plus four minus itself.
Prove that x is irrational. An attempt might go like this:
First assume that x is rational and of the form x=p/q
Go on to show a contradiction (easy to do)
Therefore x must be an irrational number
See the problem here? Your definition of irrational is flawed in the sense that you assume existence of the number which is not always true.
Getting back to my initial post, the proof step that the video leaves out is the proof of existence. It needs to go: prove not rational, prove number exists, therefore it follows that the number is irrational.
"The number exists and can be described in the form x = a." But it cannot be described in the form x=a/b with lets say for example b=1? Or do you mean a is an irrational number and therefore it is trivial to see that x exists? In which case, why even bother with a proof since you appear to be defining the number into existence? Also, the expression x^2 = 2; x = 2^(1/2) on its own is not sufficient to prove that x exists. It is also not a requirement that all real numbers be expressible in the form x=a.
Please can you do a video about the ostrogradski method for integration?
I would love you if you do it. u.u
loved it!
What you mean not being able to fly , you don’t know the future.
The "humans can't fly" is a very bad analogy for a proof by contradiction. To beging with, the statement is extremely vague, e.g. humans do fly in planes or other vehicles, and the human that jumped from the building flew once... downwards. You could even send an astronaut to a different planet where he or she would be able to fly, and so on.
But the severe flaw here is that the "proof" is not valid: your experiment only shows that a particular human wasn't flying in that specific instance. A valid proof via experimentations like this would require taking every single human (from the past, present and future), put them into every possible environmental condition (repeated times) and check if each human can or can't fly.
A more straightforward and proper proof would be accomplished by figuring out the physical properties required for a living being being able to fly (e.g. birds, insects, bats) and stating that humans do not fulfill those properties. But in this way the proof would have very little resemblance to the irrationality of sqrt(2) proof.
+xnick I agree with you in most of what you wrote. But I'm not so sure about the part that the approach you proposed would have nothing to do with proving the irrationality of `√2`. There are certain conditions a number has to fulfil in order to be rational. So if we can show that `√2` cannot fulfil those conditions in any possible way, then we can prove that it is not rational, hence irrational ;) So it might be fun to play with this idea a little more. Who knows, maybe you'll discover a better, more direct proof for the irrationality of `√2` this way? :)
I should have said "that person" cannot fly.
I usually prove that sqrt(2) is irrational using proof by shut up and trust me
Lol if someone was actually able to fly, they would show they could fly rather than say they can fly and never show it
Your proof that humans cannot fly makes no sense to me. We all know it is true but surely the fact that one person or even a thousand or a million hit the deck does not prove it for all humans.
On the contrapositive example you say that if a is even then a squared is even and from this statement alone you say that this must mean that if a is odd etc. So what if I say if a is negative then a squared is positive?
After thinking about it for a long time I see that the contrapositive is right.
The proof of humans cannot fly is not recommended for those with depression
Too long . For any natural N and k, root of k power of N if not natural then always irrational. If all prime dividers of N are factored in powers divisible by k then the root equals to product of same prime divisors UK n powers divided by k.
If there exists a prime factor with degree not divisible by k then an assumption of rationality of the root leads to easy cobtradiction
Too long and rambly. Apply the Fundamental Theorem of Arithmetic.
It's in 10 grade book 🤣🤣😂😂
Haha ...
Irrational is that which is not rational lol😁
我相信我能飛
This is so stupid