At some point I started saying "BWOC" out loud like a chicken whenever it's written on the board and I'm so glad I waited to pick up that habit until after I left university
proofs by descent are actually equivalent to proofs by strong induction. *strong induction:* prove P(1) is true, and prove that if P(1) and P(2) and ... and P(k-1) are true, then P(k) is true. then P(n) is true for all n. *descent:* prove P(1) is true, and prove that if P(k) is false, then P(j) is false for some j < k. then P(n) is true for all n.
The standard proof that sqrt(2) is irrational - where the assumption to contradict is that the fraction is non reducing is really just infinite descent , in disguise. Like spiraling into Dante's Inferno.
It is just to yield the nice equation a^2 + b^2 = 3c^2. Like what @asparkdeity8717 said, assuming that they do not have a common denominator still yield that same equation after some substitution Plus, it is safe to let x=a/c y=b/c WLOG as we did not put any constraint on a nor b
Why do we not assume x = a/c and y = b/d (different denominators in the second example, with c,d minimal)? Is it because: a^2 / c^2 + b^2 / d^2 = 3 ==> a^2 d^2 + b^2 c^2 = 3 c^2 d^2; so (ad)^2 + (bd)^2 = 3(cd)^2. So then label a' = ad, b' = bd and c' = cd returns us back to the original problem you wrote, where c' is still assumed minimal as c,d were assumed to be?
One question: When we start with this line of proof, we are reasoning using variables. While it's clear that _at some point_ you'd have to reach 1 with this infinite decent, how would you actually get there? Wouldn't you have to use concrete numbers at some point, in which case you could just numerically confirm that they do not meet the desired criterion?
A rare video where I got it all. While I know there are more economical ways to prove these things, this was a great way to demonstrate the power of this fully operational space station I MEAN proof technique.
6:40 I don't understand why a-b < b contradicts the minimality of b. For example, let's say we were representing the rational number 5/3, a=5 b=3, gcd(5,3) = 1. In this case, a-b is 2, and 2 is indeed less than 3, but this doesn't prove that 5/3 is irrational, because there is no way to represent the rational number 5/3rds with a 2 in the denominator (and a natural number in the numerator), so this doesn't violate the minimality condition. What am I missing?
5/3 canot be written as a fraction with 2 in the denominator , so no contradiction here.. In his example a-b< b and a/b can be rewritten as a fraction with a- b in the denominator which contradicts minimality.
It's because 3b-a/a-b = a/b a/b is already the simplest from of the fraction (gcd(a,b)=1, which equivalently means b is the smallest) having the same fraction with denominator a-b (
@@diniaadil6154 Oh. Somehow even after watching this twice, I missed the construction where a/b can be rewritten with a-b in the denominator. My bad, thanks for the explain!
7:50 I also don't understand why we're assuming that, if X and Y are both rational, their minimal representation would have the same denominator. As a random example, x could be 3/2 and y could be 5/3rds. Both are rational numbers with minimal denominators but they do not have the same denominator. In fact, if you wrote them to have the same denominator, x would be be 4.5/3, contradicting a being a natural number. Between this and my other question I'm beginning to wonder if I don't understand what exactly 'minimal' means in this context
here it means that C is the minimal natural number such that both rational numbers are expressed as fractions of the same number, in your example 9/6 and 10/6 with c being 6 such that both rational numbers can be expressed and no smaller natural number existing that can be the denominator of both rational numbers.
3/2 and 5/3 are irreductible already, but we can express them in terms of the lcm(denominators), that is 9/6 and 10/6. This is the minimal expression they can have with a common denominator.
Why can't we prove irrationality of square root of 9 the same way, assuming we don't know that it's 3^2? Or 2.25, or some other non-obvious rational square?
I don't think I've seen a proof use so many variables as the 3rd one: x, y, z, w, p, q, r, a, b, c, d, e=x0, f =y0, so 13 out of 26 letters, that's half the alphabet ;-)
The second Proof is technicaly incomplet w has to be a perfekt square while a does not But you can argue that by the same logik as Shown in the Video no a exsists. Which implies no a that is a square number exsists
Alright, now how do we apply it to Catalan's constant or the Euler-Mascheroni constant? Using an integral representation, then show that this becomes integer × the function - integer × power of x integrates to 0, then...?
At some point I started saying "BWOC" out loud like a chicken whenever it's written on the board and I'm so glad I waited to pick up that habit until after I left university
I will now be saying this too
@@alexbush9250 I think we ought to.
proofs by descent are actually equivalent to proofs by strong induction.
*strong induction:* prove P(1) is true, and prove that if P(1) and P(2) and ... and P(k-1) are true, then P(k) is true. then P(n) is true for all n.
*descent:* prove P(1) is true, and prove that if P(k) is false, then P(j) is false for some j < k. then P(n) is true for all n.
1
The standard proof that sqrt(2) is irrational - where the assumption to contradict is that the fraction is non reducing is really just infinite descent , in disguise. Like spiraling into Dante's Inferno.
It's so baked in that I'm always disappointed by the direct contradiction proof.
10:00 r^2+s^2 can only be 0, 1, 2, 4, 5 or 8, which 0 is the only one of to be a multiple of 3.
For proving x^2+ y^2= 3 has not rational roots, we assumed that x=a/c and y=b/c. But why should they have same denominator c?
It is just to yield the nice equation a^2 + b^2 = 3c^2. Like what @asparkdeity8717 said, assuming that they do not have a common denominator still yield that same equation after some substitution
Plus, it is safe to let x=a/c y=b/c WLOG as we did not put any constraint on a nor b
Why do we not assume x = a/c and y = b/d (different denominators in the second example, with c,d minimal)? Is it because:
a^2 / c^2 + b^2 / d^2 = 3 ==> a^2 d^2 + b^2 c^2 = 3 c^2 d^2; so (ad)^2 + (bd)^2 = 3(cd)^2. So then label a' = ad, b' = bd and c' = cd returns us back to the original problem you wrote, where c' is still assumed minimal as c,d were assumed to be?
One question: When we start with this line of proof, we are reasoning using variables.
While it's clear that _at some point_ you'd have to reach 1 with this infinite decent, how would you actually get there? Wouldn't you have to use concrete numbers at some point, in which case you could just numerically confirm that they do not meet the desired criterion?
18:45 You should explain why it is impossible that q=c^2-d^2, and y=2cd in this case.
21:22
A rare video where I got it all. While I know there are more economical ways to prove these things, this was a great way to demonstrate the power of this fully operational space station I MEAN proof technique.
6:40 I don't understand why a-b < b contradicts the minimality of b. For example, let's say we were representing the rational number 5/3, a=5 b=3, gcd(5,3) = 1. In this case, a-b is 2, and 2 is indeed less than 3, but this doesn't prove that 5/3 is irrational, because there is no way to represent the rational number 5/3rds with a 2 in the denominator (and a natural number in the numerator), so this doesn't violate the minimality condition. What am I missing?
5/3 canot be written as a fraction with 2 in the denominator , so no contradiction here.. In his example a-b< b and a/b can be rewritten as a fraction with a- b in the denominator which contradicts minimality.
It's because 3b-a/a-b = a/b
a/b is already the simplest from of the fraction (gcd(a,b)=1, which equivalently means b is the smallest)
having the same fraction with denominator a-b (
@@diniaadil6154 Oh. Somehow even after watching this twice, I missed the construction where a/b can be rewritten with a-b in the denominator. My bad, thanks for the explain!
7:50 I also don't understand why we're assuming that, if X and Y are both rational, their minimal representation would have the same denominator. As a random example, x could be 3/2 and y could be 5/3rds. Both are rational numbers with minimal denominators but they do not have the same denominator. In fact, if you wrote them to have the same denominator, x would be be 4.5/3, contradicting a being a natural number.
Between this and my other question I'm beginning to wonder if I don't understand what exactly 'minimal' means in this context
here it means that C is the minimal natural number such that both rational numbers are expressed as fractions of the same number, in your example 9/6 and 10/6 with c being 6 such that both rational numbers can be expressed and no smaller natural number existing that can be the denominator of both rational numbers.
3/2 and 5/3 are irreductible already, but we can express them in terms of the lcm(denominators), that is 9/6 and 10/6. This is the minimal expression they can have with a common denominator.
This proof technic is the combination of proof by induction and proof by counter example
cool - infinite descent is a specific type of proof by contradiction and a more general version of induction
10:11 But that's 4 each, their sum can be as big as 8.
Would be fun to reference this video if you ever presented solutions to this year's putnam problems (namely A1)
Doesn't a have to be a perfect square for this to be a contradiction?
Please i need to know the geometric meaning of the trace of animatrix
I'm assuming for this to work, the ordering we use must be well-founded?
3 divides r^2+ s^2 but the sum is less than 8, so other than 0 or 6 is a possibility ( than can like 3 be eliminates afterwards ) Great video!😊
This part just needed a proof by exhaustion to see which of the 9 cases it could be.
Why can't we prove irrationality of square root of 9 the same way, assuming we don't know that it's 3^2? Or 2.25, or some other non-obvious rational square?
Vieta's descent method?
Pierre de Fermat's infinite descent. Vieta's jumping is for special cases of Diophantine equations
I don't think I've seen a proof use so many variables as the 3rd one: x, y, z, w, p, q, r, a, b, c, d, e=x0, f =y0, so 13 out of 26 letters, that's half the alphabet ;-)
The second Proof is technicaly incomplet
w has to be a perfekt square while a does not
But you can argue that by the same logik as Shown in the Video no a exsists.
Which implies no a that is a square number exsists
You need a spell checker
Alright, now how do we apply it to Catalan's constant or the Euler-Mascheroni constant? Using an integral representation, then show that this becomes integer × the function - integer × power of x integrates to 0, then...?
❤