วีดีโอ

Oh, it could potentially be minimized, for sure! In fact, DFA minimization technically gives us a way to algorithmically check that two DFA's accept the same language: do the product construction for "M if and only if N", remove inaccessible states, and minimize---the DFA's are equivalent just when the result is a one-state DFA accepting everything!

@@pauselab5569 Everyone's entitled to their opinion! The point of this proof is that it's elementary and analytic, though; most would consider these results to be algebraic, so algebraic proofs are rather expected.

Oh...this all started during COVID until I couldn't keep up with the class schedule, and I sort of forgot about it since then. Maybe I should put it on my to-do list! 😊

⁠@@frankswenton3177 thank you 🙏

I'm not sure I understand your comment, the sequence (1/2)+(1/n) (so p_n=n+2, q_n=2n)positive integer n approximates 1/2 arbitrarily well. Maybe you mean that if in any such sequence the denominators have to grow without bound, then the 'target number' is irrational (as otherwise you could keep using p/q itself and be as close as was needed). And for the second part, the rational number p/q is the root of the polynomial qx-p (though admittedly, this isn't monic), so any non-algebraic number is irrational. I assume I'm misinterpreting something here.

Ha! Yeah, I was pretty active a while back! Only pop in occasionally now. :)

For better or worse, I use the Adobe suite of products: * Audition for audio editing * Illustrator for static graphic elements * After Effects to put together the video itself. I type up the text and symbols in MiKTeX/LaTeX (which is free, at least!) and bring them into Illustrator to color, arrange, etc. Would all of that be worth sort of meta-video? It takes some practice and it's not a super quick process, but it gets somewhat smoother the more you do it! Still have an audio issue to work out apparently, though! .:)

@@frankswenton3177 Wow, thanks for sharing your setup! I love the clean aesthetic of your videos and formatting style. You can also annotate on these slide instead of animating for some content I guess which could faster then animating. You put a great amount of effort you put into your videos, and it really shows. :) Thanks again!

Thanks! Can't figure out why the Product Construction video gets so much traffic but not the Subset Construction one! :)

​@@frankswenton3177well I m watching this couse I have exams soon :)

@@gkhack In that case, sorry more aren't finished yet! I want to do at least a few more in the NFA/DFA area (to/from RegExp, minimization, and Pumping Lemma), but they haven't been high priority because I'm not teaching this again until next spring!

@@frankswenton3177 No worries, will watch even after exams :)

Agreed, 2020 was a bad year. :( The "logs" bit goes essentially like this: we first have to suppose that the distance z = | sqrt 2 - 1 | is not zero (if it is, we're done!). Then for any target size T (e.g., 1/q), we can solve z^n < T by taking the log of both sides: log(z^n) < log T, so n log z < log T, i.e., n > (log T)/(log z). So any power n bigger than this will work (careful, dividing by log z switches the < to > because log z id negative!). Easier to see on paper than in a text comment, but that's the outline!

@@frankswenton3177 above and beyond. Absolutely fantastic :)

Here goes for square roots (will be a little messy in a comment!): call z = sqrt(N) - A for convenience (the first example is N = 2, A = 1). We want to show that for n >= 1, z^n = k sqrt(N) + l for some integers k,l. Base case [n = 1]: take k = 1 and l = -1, then k sqrt(N) + l = sqrt(N) - 1 = z^1, done. Inductive step [true for n ==> true for n+1]: Suppose z^n = k sqrt(N) + l. Then z^(n+1) = z^n • z = (k sqrt(N) + l)(sqrt(N) - A). FOILing out, this gives kN - kA sqrt(N) + l sqrt(N) - lA = [-kA+l] sqrt(N) + [kN - lA], which is again an integer [-kA+l] times sqrt(N) plus an integer [kN - lA]. (These would be your "new" k and l.) Might be easier to follow copied onto paper, but that's how the induction could go!

With the integers being ordered and consecutive integers being one unit apart, we don't have to work quite so hard for that, but it's a good thing to be concerned about!

​@@frankswenton3177 I'm not so sure it is so trivial from an elementary standpoint! Who says numbers fit on a line? Who is to say a huge pair of positive and negative integers don't sum to a number in that so so important gap? That would be such a pain in the neck! Besides, the WOP is not very hard I think. It is a one or two-liner, and it is crucial to the proof in the video... What can I say, I like my axioms!

​@@frankswenton3177 My thoughts arose mainly because prime factorisation relies on the WOP (at least in proving the GCD algorithm terminates)... I felt it had to sneak back in elsewhere! Otherwise, all of set theory might crumble and I won't stand for it 😁

​@@xatnuOh, I have nothing against WOP or even prime factorization. :) My thought is that because the integers are ordered, once you have consecutive integers 0 and 1 (say), every other integer is either greater than one or less than zero, so we can deduce there are none between. It seems like the construction of the integers from the natural numbers should allow an inductive proof of all of that, but I honestly haven't thought it through in detail!

Come to think of it, induction is equivalent to the WOP for integers anyway, so with all of the suppressed induction, we're on the same page!

Well, formally you need induction for all of that, as this is how.powers are defined---but all of it is obvious enough not to bother.

@@frankswenton3177 Formally you need induction for all proofs involving integers, rationals or reals as integers are defined by induction.

@@frankswenton3177 you need induction for everything involving integers, rationals, reals since natural numbers are defined through induction

By definition of the square root, every even power comes out to an integer, and thus every odd power comes out to an integer times root 2 (an even power times one more root 2)...does that help? With that in mind, we can inductively FOIL stuff or use the binomial theorem and be assured that k root 2 plus j is all that we'll see.

Yep---I was between discussing the estimates and not, didn't put a lot of thought into a more complete discussion there! :)

Glad you enjoyed it!

Certainly!

I feel like this is the normal proof but a little more rigorous lol because it actually mentioned the TTOA that makes it work

Indeed, this would substitue for that spot! Once you've had the idea to subtract the nearest integer and take powers, there are apparently multiple ways to get the rationality to give you something. Would definitely work for the algebraic integers as well, nice!

Oh, though one little thing! We can't eliminate 0, either, so you'd have to say that the difference is 0 or 1...but it still gets what you need! :)

Oh, I forgot to thank you for presenting such a wonderful proof about the irrationality of √2 without involving prime numbers or lowest terms. I always found the method of 'assuming any rational number can be represented in lowest terms and then showing that √2 cannot be expressed in lowest terms' a bit awkward. It felt like I was just assuming and contradicting the same argument. But I couldn't think of the proof that does not involve the lowest term by myself. This new proof (it's new to me) really resolved my curiosity.

​@@frankswenton3177 You're right... Clearly I have mistakes there not considering 0... Anyway thanks for your reply and videos!

​@@임한준-d7vNo problem at all, great idea and thanks for watching!

That's a fair point. To show that sqrt(2) exists in the first place you need a bit of real analysis. For example, you can let c be the least upper bound of the set of real numbers x such that x^2 <= 2, then show that c^2 = 2. Or you can show that the map x -> x^2 is continuous, so since 1^2 < 2 < 2^2 we know x^2 = 2 has a solution by the intermediate value theorem.

​@@martinepstein9826I wish I knew more about p-adic norms but I think there is a totally different concept of sqrt(2) in those number systems, so it is a very fair critique.

Not a single result in this is claimed to be new...the curiosity is in the method of proving them, which is (to me) interesting and, apparently, little-known.

@@frankswenton3177 as to „little known“: my engineering students all learn it in first year linear algebra. An a student just gave a presentation on Lambert‘s proof this morning in a seminar.

I think there is a miscommunication here. As I said, none---zero---of the _results_ here are claimed to be new. The point is about the cute argument of subtracting the nearest integer and taking powers, that's all.

Agreed to a great extent---though the transcendentals in R and C are the only inherently [metric] topological bits, which is where the topology is forced to come into play. All that Pure Algebra can see are the algebraics. :)

What does "integral" here mean? The closest thing I know of in this context is an integral ring: a*b=0 => a=0 or b=0, but that doesn't fit what you're saying

@@الْمَذْهَبُالْحَنْبَلِيُّ-ت9ذFrom the Wikipedia article for “Integral element”: In commutative algebra, an element b of a commutative ring B is said to be integral over a subring A of B if b is a root of some monic polynomial over A. In this case we take B to be Q and A to be Z. Being an integral element is a rather valuable property in algebraic number theory.

The proof in the video explicitly constructs a Cauchy sequence of rational numbers whose squares converge to 2 (the approximations mentioned at the end). By the construction of the real numbers from Cauchy sequences, the existence of the Cauchy sequence means the existence of the number it converges to.

No, algebraic number theory is the study of number fields, I.e. finite extensions of Q (as well as some other fields like p-adic fields and related fields). In particular, of great interest are their rings of integers which encode very useful information about how to factor numbers if you allow more exotic factors. E.g. 6 = 2 * 3, but also 6 = (1+sqrt(-5))(1-sqrt(-5)). The contents of this video are more closely related to diophantine approximation.