I love a converse of the mosquito question. Real mosquitoes are not infinitesimal points. On any grid of real mosquitoes there is a 100% chance you’ll hit a mosquito pointing the laser in any direction. In fact, it doesn’t matter how far apart the mosquitoes are. They could be a kilometre apart or billions of light years and you’ll still eventually hit a mosquito. (For every irrational number there is an arbitrary close rational number.)
My intuition is that the coordinates of each mosquito are countably infinite, and thus the number of angles I rotate to hit the mosquito are also countably infinite... but the possible angles my laser can point are uncountably infinite, so there is a set of angles infinitely large that would miss all mosquitoes. I have a 0% chance of hitting the mosquito on any try-and not just because my aim is bad.
My solution Every mosquito sits in a point (x,y) where x and y are integers. So just point in the direction of a line with equation y=rx where r is an irrational
yep secondly, the chance of hitting a mosquito if chosen randomly is 0.000000... as there is an countably infinity number of mosquitos, but an uncountably infinite number of angles
Bonus problems from the video: - What if the submarine also has acceleration? (constant, integer) - What are the odds of missing all mosquitos if picking a direction at random? With rational points instead of integer points? The promised 3rd approach: We want to show (a, b) is countable, using the definition that the natural numbers are countable. Consider integers on the form c = 2^a * 3^b. Since all integers have a unique prime factorization, a given pair (a, b) will yield one unique integer c. So we have a map from (a, b) to a subset of the integers, so clearly (a, b) must be countable. Note: we neglected negative a and b. See if you can formalize this line of reasoning also for those cases! Happy to hear your other ways to see this!
My answers: 1) We'd have to use a 3d space filling curve, with the 3d dimension being acceleration, and with the formula being x0 + t*v + ((t^2)/2) * a. Examples of this could be the peano, or easier, the z-order curve (This would leave space for non-integer results though). 2) Since all mosquitoes are on a Z x Z grid (That can be converted into a Z line, as shown in this video), and all the possible angles are in the realm of R, the chance of hitting a mosquito if aimed randomly is Z/R, or 0 (Not even approximately, just 0 lol). If we used rational instead of integers, the same reasoning applies, just with Q instead of Z, since both sets are infinity 1, whereas R is infinity 2. With this, it's plain to see that any number in R, but not in Z or Q, will result in a miss (For example, pi, e, tau, or any irrational number).
By the way if anyone is wondering about the 3rd infinity here is how to get it: A set of all digits (0-9) has 10 elements. A set of pairs of digits (0-99) has 100 elements. A set of inf_1 digits has inf_2 elements. Real number are after all written as an infinite (inf_1) string of digits, but there is inf_2 many of them. So (a finite set)^(inf_1) is inf_2 big. An (inf_1 sized set)^(inf_1) is still just inf_2 big. In order to construct a "larger" set you would need to raise the power: (a finite set)^(inf_2) is inf_3 big. In other words, instead of being a countably infinite string of digits (real numbers) you would need an uncountably infinite string of digits. Another way to think about it is that an integer holds finite, but unlimited amount of information. A real number holds infinite, but countably information. The next level would need to hould uncountably infinite amount of information.
The solution to the mosquito puzzle (0% chance of hitting a mosquito when setting the laser at a random angle) implies that it is impossible to pick a random real number. The reason is that there are angle values for the laser that will make the laser hit a mosquito, they are just too few among the infinity type 2 angles. The mathematical implication is that the chance (infinity type 1 / infinity type 2) becomes zero, implying that one cannot even pick one of the successful angles (if that were possible, the chance would have to be non-zero). At first glance, this seems paradoxical, but I believe the paradox can be resolved in the following way: Picking an arbitrary real number requires specifying the number with infinity precision. This is simply not possible (provided one wants the pick to conclude in finite time). Although there are effective ways of picking some real numbers, one cannot pick all real numbers in an effective manner, meaning that the ability to randomly pick a real number from all real numbers is an impossible task. In other words, if one wants to set a random laser angle, one has to do it using an angle domain with a cardinality that is not larger than infinity type 1.
So next video is infinite power sets? Or is it mosquitos? That one is easy SPOILER BELOW because all mosquitoes are at rational slopes from origin, so all you need is an irrational slope of laser and no mosquitoes will be harmed
@@TrimutiusTooprobability of not hitting is exactly 100% (or 1), despite it being entirely possible to find arbitrarily many angles that hit. One of the many oddities of infinity.
@ That is why I said "almost" in mathematical sense... in theory of probability "almost 100%" it means that it is possible to not hit it but probability is still 100%
@@TrimutiusToo That's not how 'almost'is used in mathematics. 'Almost all' can mean (in the context of countable sets) all but a finite number, or (in the context of uncountable sets) all but a countable number, but if the probability is 1 then it is not 'almost 1'. If the probability space is uncountable and equiprobable then every individual event has probability zero, and it is not only possible for a probability zero event to happen, it is certain. Probability zero events are happening all the time, but that doesn't mean the probability is 'almost zero'. It's exactly zero.
5:00 there's a lot of room for optimization here because a lot of those sports will have overlapping answers that for each spot you check you can cross off a lot of combinations
For a submarine with a position denoted by N rationals, velocity by N rationals, acceleration by N rationals, etc M levels of rational time derivative; we can express the submarine state with N^M fractions. We map each fraction to a natural number via any space-filling path in the integer grid above the x axis. Sparsely, we could take the first N^M prime numbers and take each one to the power of the corresponding natural number. Densely, we apply the diagonal argument to consecutive pairs of these numbers to repeatedly map pairs of naturals to single natural numbers, and then apply the diagonal argument again and again until all have been condensed down to a single natural number.
This is a really excellent video. Clean and clear videos, great explanation and you have a really nice speaking voice. I can't believe you have under 1k subscribers and I'm very glad I found you.
Thank you so much for the kind words! While getting into making videos I actually checked out your channel to try and see how successful channels do it and I really liked your content too! :)
You can solve the mosquito puzzle by watching a Numberphile video from a few years ago.As I recall, as long as the laser is pointed at a tangent that is irrational, no bug will be hit. Of course, the lase beam has a dimension of a mathematical point.
mosquito puzzle seems easy. just point the Lazer in direction with a slope of any irrational number. because of the fact that irrational numbers can't be represented by the ratio of any two rational numbers there will no possible integer "rise over run" where the Lazer will hit a mosquito. ofc tho ideally we would do a spin with the laser and eliminate as many mosquitoes as possible
Obviously, every mosquito represents some integer pair, like (a,b) which we can call a rational: a/b. Any line that does hit a mosquito must have a slope that intersects with a rational number, i.e. the slope divides a rational. In that case, any irrational number slop will be able to miss every mosquito.
Each mosquito sits a point (x,y), in which both x and y are integers. Thus the angle at which the laser is pointed, equivalent to a hypotenuse, is a rational number. Firing the laser at an angle that is an irrational number is guaranteed never to hit a mosquito
@@nayutaito9421 Make an equation ax + bc + c = 0 of the line, you can then choose a, b and c at random. The chances of choosing c=0 are infinitely small
This is very close to the general so-called Trawler Problem. If you only have as initial conditions a target estimate location at t0 (with or without covariance) and a max target speed Vt the optimal sensor pattern is a logarithmic spiral. But sensor has to be moving pretty fast wrt Vt. It’s simple to derive. Sensor can spiral out from t0 estimate location or in from Vt * time since t0. Inward saves a bit of time and makes the search area a bit smaller. B
I figure that, since the mosquitoes are on a grid, their coordinates are countable, essentially integers, along each axis. The direction from the origin (where you are with the laser pointer) to any given grid point P defines a line with slope Py/Px, which is a rational number. As you point out in the video, these are both of infinity type 1. The way to never hit a grid point would be to have a slope that is not a rational number, like pi. And if there are indeed infinitely more irrational numbers than there are rational ones, it would stand to reason that there's also infinitely many directions in which to shine the laser pointer without ever hitting a mosquito. The laser beam must of course also have 0 width.
nice presentation. None of the daft hype and cartoons that often accompany videos on this topic; your explanations are spot on and the tenor of your voice convincing. Thank you. BTW, your question about the mosquito is irrational.
the diagonalization proof presupposes that you can always do that for a unique number not on the list, but you cannot. you can do it ten times to every digit in the list and then have to do the next real number. which will only result in 10 unique numbers for every 2d integer in the bottom right quadrant. which shows its real easy to make a one to one correspondence.
The mosquito problem is actually easier. 😊 Short answer: Aim at such an angle θ whose tangent cannot be expressed algebraically. For ex. 10°. Or any angle (in degrees) not divisible by 3. Proof by contradiction: If tan(θ) = 9/25 for example, that means you will hit a mosquito every 25 steps horizontally and every 9 steps vertically. Going to ♾️ that's infinitely many mosquitos. Otherwise, nice video! A bit hard to understand, but... Anyway.
Formal explanation(denote the set of all integers by Z): Assume that the start position and the velocity of the submarine is fixed, then we see that at time t, the submarine's location is at f(t)=a+bt for some fixed integers a, b for all non-negative integer time t(the function f is basically a representation of the location of the submarine). So to have a way of searching that will at some point find the submarine, its sufficient to find a sequence of integers(denote the sequence by {a} with a.i being the ith term) such that for all pair of integers (a, b), there exist a non-negative integer t with a.t=a+bt. Here, we treated a searching pattern over Z as a fixed infinite sequence of Z(which is a way to define what a searching pattern is in the first place). Let's first check that the above is indeed correct, assume such a sequence exist, then we will just search the ith term at time i, and by assumption, there exist t such that f(t)=a.t, so the submarine and where we search coincidence. Now, if for every sequence of integers, there exist (a, b) pair of integers such that f(t) = a+bt =/= a.t for all non-negative t, then indeed at least one possible movement of submarine with the given condition can escape the searching pattern. Therefore, the problem we transformed is equivalent to the original problem statement. Lemma: Given a countable set A, and an infinite sequence of functions f.t:A->Z, where t is a non-negative integer, let U:N->A(set of all non-negative integers) be a bijection, let {a} satisfy a.t = f.t(U(t)), then for all elements x of A, there exist t such that f.t(x) = a.t. Proof: This is quite simple, assume x is an element of A, then there exist non-negative integer y such that U(y) = x(since U is a bijection), so we see that a.y = f.y(U(y)) = f.y(x), as desired. Apply the above lemma to the problem with A = Z*Z and f.t(a, b) = a+bt solves the problem(specifically, imagine we mark (0, 0) at time t=0, and we will mark(one by one), all lattice points (x, y) such that |x|+|y| = k, where k=1, 2, 3... in that order(we won't move to the next value of k until we marked all the previous values of k). For example, you can mark them in the following order: (0, 1), (1, 0), (0, -1), (-1, 0), (0, 2), (1, 1), (2, 0), (-1, -1)... This is indeed a bijection between N and Z*Z(any lattice point will eventually appear in this sequence, this is similar to the proof that N and Q has the same cardinality but with a much more clear geometric intuition), call this sequence of lattice points {b}. Now, we let a.t = x+yt for all non-negative integer t, where b.t = (x, y), then since (a, b) is a fixed lattice point, we may choose t such that b.t = (a, b)({b} includes all elements in Z*Z so this must occur at some point), we indeed have a.t = a+bt = f.t(a, b), as desired). There might be some formal mistake inside of the argument, but the overall idea is basically identical.
Btw, Z can probably be replaced with any other countable set, since all we need is to just have the cardinality of the range to be the same as a. usual infinite sequence, which is just countable infinity.
For the x0=0 case I'd have picked the so called twiddled pattern used for textures, personally seen first mentioned on the Sega Dreamcast PowerVR GPU 😛, also called Z-order curve. I'd need to think about it some more to extend to the general case, if possible. Thank you for the puzzle and solution, I was eagerly expecting this video !
Space filling curves perserving locality are truly fascinating! I'm glad to hear you were looking forward to the video and I hope you will like the next one too. Thanks for watching!
amazing video! my intuition tells me that the answer to the mosquito problem is yes, with a 0% chance if random edit: as pointed out, 0% chance of *not* missing
I think my argument is rational enough: Take the distance between any two adjacent mosquitos (not diagonal) and call that 1 Since all mosquitos can be labeled by their distance from the laser along the x axis and along the y axis (a point with 2 coordinates) we can assign each mosquito a slope (it doesnt have to hr unique. Every slope will be a rational number, because each mosquito on an axis is an integer multiple of 1 away from the adjacent ones. All you have to do is point your laser towards a point with an irrational slope (such as the point (1, pi) and the laser will not hit any mosquitos. This is because if that line were to intersect a mosquito, it would imply the rational slope of the mosquito a/b would be equal to the irrational slope of pi/1 (or more generally, any irrational slope). This cannot happen because that would mean an irrational number is equal to a rational one.
No you can’t hit no mosquitoes because if can’t hit no mosquitoes then there will be infinite mosquitoes forever and that means that the universe is broken and meaning has no meaning and that’s not possible.
Grrr so we don't get the solution to the 2D submarine do we... I guess I have to keep thinking for myself then... ;D I'm a little confused about why you said ∞₁ and ∞₂ rather than using aleph. Is there a mathematical difference or is this just notational? SOLUTION SPOILER The mosquito problem seems pretty straightforward. Obviously you have the ∞₂ of possible directions but only ∞₁ points. It's not possible to map every direction to a point unless multiple directions could map to the same point. Furthermore, each point (except for the y-axis) represents some rational number - some slope in the form y/x. An angle of any irrational slope will preserve the mosquito population. I wonder if there's some problem you could come up with that forces us to distinguish between transcendental numbers and other real numbers.
> An angle of any irrational slope will preserve the mosquito population. A truly sad state of affairs. Also reminds me of how an incline of the golden ratio is, in a way, best at missing the mosquitoes. I am too tired to elaborate on that or to check my memory on it.
Not using aleph-notation is purely a notational choice. My goal was to simplify the notation for people who haven't seen it before, and I think it's always fun to use a non-traditional notaton when you've derived something yourself :) As for the 2D puzzle, which variant would you like to know the solution to?
By the way, the notation in the video is more like a variant of beth notation than of aleph notation. Without assuming the Continuum Hypothesis, we don't know which aleph is the cardinality of the continuum, although we can exclude some alephs.
Great video, but there is one mistake. We know that there is nothing between א0 and א1, Continuum hypothesis says that |R| = א1, and this we do not know, because |R| can be greater than א1 Edit: Source en.m.wikipedia.org/wiki/Continuum_hypothesis en.m.wikipedia.org/wiki/Continuum_hypothesis
The ans to the second q is slope must be an iraational no .Now let's say our lazer hit a point (a,b) then the slope of line must be b/a bit if slope is irrational it is not possible
isn't that just map out to the difference between the space of rationals versus reals because hitting a mosquito means that you cross a point in the coordinate grid that maps to a representation of rational number
I must have misunderstood what the submarine problem actually is. If the submarine starts at position 0, and has v=1, then it will move along the positive number line and get out of reach of the search position. The search will eventually reach every position that the submarine has been in the past, but will never reach the submarine.
No, you take starting position, then add the velocity times the number of seconds that have passed. This will eventually get you to the exact location that the submarine is, no matter the starting point or velocity
You understand the problem, but you’re missing a subtle part of the solution. We check every position based on velocity and time that has passed. This is not the same as just checking all positions.
8:33 I have a question: What about situations similar to the trick where 0.(9) = 1? The numbers look different, yet they are equal. So why does having just one different digit in two numbers make them certainly unequal?
If one of those numbers is on the list then you won’t get such a number (such a number referring to one with many nines, and the number you got being the new number), since the new number will be different from any number on the list with infinite nines If such a number isn’t on the list, then either you won’t get one for your new number, in this case, no problem, or you will get one, but that would imply that at some point, there are only numbers that have 8 on the digit you select, then that digit before the 8s will have another +1 added to it, which is no problem since it’s still not equal to the original digit. And it can’t be equal to any number after since you’ll have only 0s (after you remove the 9s) in the digits when the 8s appear up to infinity, and each number has to have an 8 there. I hope I explained it well.
If the newly constructed number tails with an infinite string of nines, there are only finitely many real numbers in the list not containing an 8, so infinitely many numbers not containing an 8 are not in the list.
The easiest way to avoid 0.999 repeating = 1.0 schenanigans is just to add 2 to each digit instead of 1. Now the digit 9 becomes 1 instead of 0, so there's no way to accidentally run into an equivalent representation. Of course, this technique won't work in base 2... Another technique that does actually work in every base is to observe that in order to have a second representation of a number show up, we need something of the form ....0000 repeating forever (note that "9" will represent whatever number comes before "10" in whatever base we happen to be working in) in our constructed number. But this means that every number in our list had a 9 at an appropriate position, which clearly excludes a whole bunch of numbers that don't have a 9 anywhere. Even in base 2, where the only number without a "9" digit (more commonly written as "1" ) is 0, there are many numbers that only have a few "9"s near the beginning, followed by repeating 0s. We can see that we don't have enough room at the beginning of the list for all of them before our changing digit ends up falling in the repeating 0s in the tail.
I'm trying to understand infinity for 10 years now, watching this and that video. Still couldn't make it. 8:51 "You cant make a list of all the Real number, so the Reals must be uncountable". But the same can be said of integers. They too can be made into a list, where you add +1 each time and construct a new number. So why they're called countable then?
The video showed earlier (in the submarine context) that you *can* make a list (though an infinite one) of the integers via the dancer trick: 1. 0, 2. 1, 3. -1, 4. 2, 5. -2, 6. 3, etc. As discussed in this video and many others, you *cannot* do the same for the real numbers. If you thought you had a method to make an infinite list of the real numbers in the same way, then your method must have a flaw revealed via the diagonalization trick.
Integers only have finitely many digits - if you add 1 in every infinite position, the number you get has infinitely many digits, so it is not an integer. If you only add 1 in finitely many positions, the number is not automatically different from every number on the list, so you haven't found a number not on the list.
You actually make an interesting point! At first glance it may seem like we could just make the same diagonalization argument for rational numbers right? And indeed; we would be able to construct a new number not on the list using our diagonalization method. The problem is that that number *would not* be rational. How do we know that? Well, for one, because we just showed the rationals are actuall countable. Another cool realization is that every rational actually has a repeating (or finite) decimal expansion (there are several pretty straightforward ways to see this). The number we construct will most certainly not. Hope this helped!
You never hit a mosquito if the slope of the laser beam is irrational. The best way to avoid all mosquitos is the most irrational slope, namely the golden ratio.
you can’t actually sample it yourself or get a computer to do it, but that’s not to say you can’t determine properties of different distributions over the reals, such as the fact that in a uniform distribution hitting a rational has probability 0.
Excuse me. It may well be that my English is way too bad. However, that unmotivated, superfluous and senseless background music makes it impossible for me to concentrate. Good bye to this channel.
This is all trivial. This video doesnt even start to tackle any real issue related to infinity concept like axiom of choice or real numbers inconsistencies...
To me, it isn't clear why coming up with a clever way of counting all the integers by jumping back and forth across zero is an allowed behavior to count all the numbers
That's not how any of this works. It is possible to make a list of all rational numbers so therefore it is countable. You don't have to make a list /in order/
It all depends on the method of counting. As shown in the video, you can absolutely pick an approach that will not count through, for example, all integers. In fact, we can find a method that does not count through the natural numbers (the very definition of being countable!) Example: Start at 2 and go up. Once done, count 1. This will never get to the 1 since counting up will take forever. This does *not* mean that the natural numbers are uncountable. A set being countable just means that there exists at least one way to count through all the elements in that set, not that all methods need to succeed in that. To see how it works for the rationals it might help to think concretely about the order we go through them. In some sense, we grow both the numerator and denominator in parallel! So we will go "wider" and "deeper" at the same time. Hope this clarified things a bit!
8:40 That approach does not work. 1 = 0.999…, but if you do 0,…,8, 9 → 1,…,9, 0, you map 0.999… to 1.000… which means you don’t get a new number. So if my list is nothing but copies of 0.999…, the “new” number is 1.000… which is already in the list. (If you require the numbers to be unique, use 0.999… as the first number and 0.9, 0.09, 0.009, etc. as the remaining number of the list.
Excellent point! Indeed one of the details of the proof that was left out for time. Can you come up with a method to account for this in the proof? (There are many possible ways) There is a discussion with some good approaches in another comment :)
I love a converse of the mosquito question. Real mosquitoes are not infinitesimal points. On any grid of real mosquitoes there is a 100% chance you’ll hit a mosquito pointing the laser in any direction. In fact, it doesn’t matter how far apart the mosquitoes are. They could be a kilometre apart or billions of light years and you’ll still eventually hit a mosquito. (For every irrational number there is an arbitrary close rational number.)
My intuition is that the coordinates of each mosquito are countably infinite, and thus the number of angles I rotate to hit the mosquito are also countably infinite... but the possible angles my laser can point are uncountably infinite, so there is a set of angles infinitely large that would miss all mosquitoes. I have a 0% chance of hitting the mosquito on any try-and not just because my aim is bad.
Math says your aim is bad.
My solution
Every mosquito sits in a point (x,y) where x and y are integers. So just point in the direction of a line with equation y=rx where r is an irrational
yep secondly, the chance of hitting a mosquito if chosen randomly is 0.000000... as there is an countably infinity number of mosquitos, but an uncountably infinite number of angles
Same
Bonus problems from the video:
- What if the submarine also has acceleration? (constant, integer)
- What are the odds of missing all mosquitos if picking a direction at random? With rational points instead of integer points?
The promised 3rd approach:
We want to show (a, b) is countable, using the definition that the natural numbers are countable.
Consider integers on the form c = 2^a * 3^b. Since all integers have a unique prime factorization, a given pair (a, b) will yield one unique integer c. So we have a map from (a, b) to a subset of the integers, so clearly (a, b) must be countable. Note: we neglected negative a and b. See if you can formalize this line of reasoning also for those cases!
Happy to hear your other ways to see this!
My answers:
1) We'd have to use a 3d space filling curve, with the 3d dimension being acceleration, and with the formula being x0 + t*v + ((t^2)/2) * a. Examples of this could be the peano, or easier, the z-order curve (This would leave space for non-integer results though).
2) Since all mosquitoes are on a Z x Z grid (That can be converted into a Z line, as shown in this video), and all the possible angles are in the realm of R, the chance of hitting a mosquito if aimed randomly is Z/R, or 0 (Not even approximately, just 0 lol). If we used rational instead of integers, the same reasoning applies, just with Q instead of Z, since both sets are infinity 1, whereas R is infinity 2. With this, it's plain to see that any number in R, but not in Z or Q, will result in a miss (For example, pi, e, tau, or any irrational number).
By the way if anyone is wondering about the 3rd infinity here is how to get it:
A set of all digits (0-9) has 10 elements. A set of pairs of digits (0-99) has 100 elements. A set of inf_1 digits has inf_2 elements. Real number are after all written as an infinite (inf_1) string of digits, but there is inf_2 many of them. So (a finite set)^(inf_1) is inf_2 big. An (inf_1 sized set)^(inf_1) is still just inf_2 big. In order to construct a "larger" set you would need to raise the power: (a finite set)^(inf_2) is inf_3 big. In other words, instead of being a countably infinite string of digits (real numbers) you would need an uncountably infinite string of digits.
Another way to think about it is that an integer holds finite, but unlimited amount of information. A real number holds infinite, but countably information. The next level would need to hould uncountably infinite amount of information.
The solution to the mosquito puzzle (0% chance of hitting a mosquito when setting the laser at a random angle) implies that it is impossible to pick a random real number. The reason is that there are angle values for the laser that will make the laser hit a mosquito, they are just too few among the infinity type 2 angles. The mathematical implication is that the chance (infinity type 1 / infinity type 2) becomes zero, implying that one cannot even pick one of the successful angles (if that were possible, the chance would have to be non-zero). At first glance, this seems paradoxical, but I believe the paradox can be resolved in the following way: Picking an arbitrary real number requires specifying the number with infinity precision. This is simply not possible (provided one wants the pick to conclude in finite time). Although there are effective ways of picking some real numbers, one cannot pick all real numbers in an effective manner, meaning that the ability to randomly pick a real number from all real numbers is an impossible task. In other words, if one wants to set a random laser angle, one has to do it using an angle domain with a cardinality that is not larger than infinity type 1.
Huge props for using a light beige background - it helps immensely with not straining eyesight at nighttime.
So next video is infinite power sets?
Or is it mosquitos? That one is easy
SPOILER BELOW
because all mosquitoes are at rational slopes from origin, so all you need is an irrational slope of laser and no mosquitoes will be harmed
additionally, the probability is 0, given by the following 3b1b video: ua-cam.com/video/cyW5z-M2yzw/v-deo.html
@kyleliao4445 probability of hitting one is 0, probability of not hitting is almost 100% actually (by mathematical definition of almost)
@@TrimutiusTooprobability of not hitting is exactly 100% (or 1), despite it being entirely possible to find arbitrarily many angles that hit. One of the many oddities of infinity.
@ That is why I said "almost" in mathematical sense... in theory of probability "almost 100%" it means that it is possible to not hit it but probability is still 100%
@@TrimutiusToo That's not how 'almost'is used in mathematics. 'Almost all' can mean (in the context of countable sets) all but a finite number, or (in the context of uncountable sets) all but a countable number, but if the probability is 1 then it is not 'almost 1'. If the probability space is uncountable and equiprobable then every individual event has probability zero, and it is not only possible for a probability zero event to happen, it is certain. Probability zero events are happening all the time, but that doesn't mean the probability is 'almost zero'. It's exactly zero.
5:00 there's a lot of room for optimization here because a lot of those sports will have overlapping answers that for each spot you check you can cross off a lot of combinations
For a submarine with a position denoted by N rationals, velocity by N rationals, acceleration by N rationals, etc M levels of rational time derivative; we can express the submarine state with N^M fractions. We map each fraction to a natural number via any space-filling path in the integer grid above the x axis. Sparsely, we could take the first N^M prime numbers and take each one to the power of the corresponding natural number. Densely, we apply the diagonal argument to consecutive pairs of these numbers to repeatedly map pairs of naturals to single natural numbers, and then apply the diagonal argument again and again until all have been condensed down to a single natural number.
This is a really excellent video. Clean and clear videos, great explanation and you have a really nice speaking voice. I can't believe you have under 1k subscribers and I'm very glad I found you.
Thank you so much for the kind words! While getting into making videos I actually checked out your channel to try and see how successful channels do it and I really liked your content too! :)
@@IndependentQuark Oh, thanks! It's somewhat surreal to hear that other people know me from my channel.
It's a really nice exposition, worth a subscription. See you around.
Really excellent video.
You can solve the mosquito puzzle by watching a Numberphile video from a few years ago.As I recall, as long as the laser is pointed at a tangent that is irrational, no bug will be hit. Of course, the lase beam has a dimension of a mathematical point.
mosquito puzzle seems easy. just point the Lazer in direction with a slope of any irrational number. because of the fact that irrational numbers can't be represented by the ratio of any two rational numbers there will no possible integer "rise over run" where the Lazer will hit a mosquito. ofc tho ideally we would do a spin with the laser and eliminate as many mosquitoes as possible
OHHHH WAIT A MINUTE! JUST POINT THE LASER SPIN AND CLOSE YOUR EYES THEN TURN ON THE LASER. THERE'S A ZERO PERCENT CHANCE OF HITTING A MOSQUITO
Obviously, every mosquito represents some integer pair, like (a,b) which we can call a rational: a/b. Any line that does hit a mosquito must have a slope that intersects with a rational number, i.e. the slope divides a rational. In that case, any irrational number slop will be able to miss every mosquito.
Each mosquito sits a point (x,y), in which both x and y are integers. Thus the angle at which the laser is pointed, equivalent to a hypotenuse, is a rational number. Firing the laser at an angle that is an irrational number is guaranteed never to hit a mosquito
For the mosquito problem, just pick a direction at random, it will certainly work ;)
Wait you might be onto something actually, since the irrationals are uncountable infinity and the rationals are only countables
It will never work because you have already stepped on the mosquito at the origin
@@nayutaito9421 Make an equation ax + bc + c = 0 of the line, you can then choose a, b and c at random.
The chances of choosing c=0 are infinitely small
only almost certainly :)
*almost-certainly
This is very close to the general so-called Trawler Problem.
If you only have as initial conditions a target estimate location at t0 (with or without covariance) and a max target speed Vt the optimal sensor pattern is a logarithmic spiral. But sensor has to be moving pretty fast wrt Vt. It’s simple to derive.
Sensor can spiral out from t0 estimate location or in from Vt * time since t0. Inward saves a bit of time and makes the search area a bit smaller. B
I figure that, since the mosquitoes are on a grid, their coordinates are countable, essentially integers, along each axis. The direction from the origin (where you are with the laser pointer) to any given grid point P defines a line with slope Py/Px, which is a rational number. As you point out in the video, these are both of infinity type 1. The way to never hit a grid point would be to have a slope that is not a rational number, like pi. And if there are indeed infinitely more irrational numbers than there are rational ones, it would stand to reason that there's also infinitely many directions in which to shine the laser pointer without ever hitting a mosquito. The laser beam must of course also have 0 width.
nice presentation. None of the daft hype and cartoons that often accompany videos on this topic; your explanations are spot on and the tenor of your voice convincing. Thank you.
BTW, your question about the mosquito is irrational.
Thank you, glad you enjoyed it!
the diagonalization proof presupposes that you can always do that for a unique number not on the list, but you cannot. you can do it ten times to every digit in the list and then have to do the next real number. which will only result in 10 unique numbers for every 2d integer in the bottom right quadrant. which shows its real easy to make a one to one correspondence.
I rarely subscribe to anyone nowadays, but you got it this time. I’ll remember I was here when you were still under 1k subs.
The mosquito problem is actually easier. 😊
Short answer: Aim at such an angle θ whose tangent cannot be expressed algebraically. For ex. 10°. Or any angle (in degrees) not divisible by 3.
Proof by contradiction:
If tan(θ) = 9/25 for example, that means you will hit a mosquito every 25 steps horizontally and every 9 steps vertically. Going to ♾️ that's infinitely many mosquitos.
Otherwise, nice video! A bit hard to understand, but... Anyway.
Point it at an irrational angle. Irrational can't be expressed with a fraction so it won't ever hit any rational coordinate.
Formal explanation(denote the set of all integers by Z): Assume that the start position and the velocity of the submarine is fixed, then we see that at time t, the submarine's location is at f(t)=a+bt for some fixed integers a, b for all non-negative integer time t(the function f is basically a representation of the location of the submarine). So to have a way of searching that will at some point find the submarine, its sufficient to find a sequence of integers(denote the sequence by {a} with a.i being the ith term) such that for all pair of integers (a, b), there exist a non-negative integer t with a.t=a+bt. Here, we treated a searching pattern over Z as a fixed infinite sequence of Z(which is a way to define what a searching pattern is in the first place).
Let's first check that the above is indeed correct, assume such a sequence exist, then we will just search the ith term at time i, and by assumption, there exist t such that f(t)=a.t, so the submarine and where we search coincidence. Now, if for every sequence of integers, there exist (a, b) pair of integers such that f(t) = a+bt =/= a.t for all non-negative t, then indeed at least one possible movement of submarine with the given condition can escape the searching pattern. Therefore, the problem we transformed is equivalent to the original problem statement.
Lemma: Given a countable set A, and an infinite sequence of functions f.t:A->Z, where t is a non-negative integer, let U:N->A(set of all non-negative integers) be a bijection, let {a} satisfy a.t = f.t(U(t)), then for all elements x of A, there exist t such that f.t(x) = a.t.
Proof: This is quite simple, assume x is an element of A, then there exist non-negative integer y such that U(y) = x(since U is a bijection), so we see that a.y = f.y(U(y)) = f.y(x), as desired.
Apply the above lemma to the problem with A = Z*Z and f.t(a, b) = a+bt solves the problem(specifically, imagine we mark (0, 0) at time t=0, and we will mark(one by one), all lattice points (x, y) such that |x|+|y| = k, where k=1, 2, 3... in that order(we won't move to the next value of k until we marked all the previous values of k). For example, you can mark them in the following order: (0, 1), (1, 0), (0, -1), (-1, 0), (0, 2), (1, 1), (2, 0), (-1, -1)... This is indeed a bijection between N and Z*Z(any lattice point will eventually appear in this sequence, this is similar to the proof that N and Q has the same cardinality but with a much more clear geometric intuition), call this sequence of lattice points {b}. Now, we let a.t = x+yt for all non-negative integer t, where b.t = (x, y), then since (a, b) is a fixed lattice point, we may choose t such that b.t = (a, b)({b} includes all elements in Z*Z so this must occur at some point), we indeed have a.t = a+bt = f.t(a, b), as desired).
There might be some formal mistake inside of the argument, but the overall idea is basically identical.
Btw, Z can probably be replaced with any other countable set, since all we need is to just have the cardinality of the range to be the same as a. usual infinite sequence, which is just countable infinity.
For the x0=0 case I'd have picked the so called twiddled pattern used for textures, personally seen first mentioned on the Sega Dreamcast PowerVR GPU 😛, also called Z-order curve.
I'd need to think about it some more to extend to the general case, if possible.
Thank you for the puzzle and solution, I was eagerly expecting this video !
Space filling curves perserving locality are truly fascinating! I'm glad to hear you were looking forward to the video and I hope you will like the next one too. Thanks for watching!
I semi-resonate with these lemniscates... ;)
What does the independent quark logo at 0:01 symbolize?
They look like different kinds of orbitals, but i'm not sure
Great stuff, thanks 😊
Easy. Just point the laser in any random direction. The probability of hitting a mosquito is exactly 0.
amazing video! my intuition tells me that the answer to the mosquito problem is yes, with a 0% chance if random
edit: as pointed out, 0% chance of *not* missing
Do you mean 0% chance of not missing? Because the video asks for the chance of missing, which is 100% if you pick a random angle.
@@cannot-handle-handles yeah lol, thx for correction
I think my argument is rational enough:
Take the distance between any two adjacent mosquitos (not diagonal) and call that 1
Since all mosquitos can be labeled by their distance from the laser along the x axis and along the y axis (a point with 2 coordinates) we can assign each mosquito a slope (it doesnt have to hr unique.
Every slope will be a rational number, because each mosquito on an axis is an integer multiple of 1 away from the adjacent ones.
All you have to do is point your laser towards a point with an irrational slope (such as the point (1, pi) and the laser will not hit any mosquitos.
This is because if that line were to intersect a mosquito, it would imply the rational slope of the mosquito a/b would be equal to the irrational slope of pi/1 (or more generally, any irrational slope). This cannot happen because that would mean an irrational number is equal to a rational one.
No you can’t hit no mosquitoes because if can’t hit no mosquitoes then there will be infinite mosquitoes forever and that means that the universe is broken and meaning has no meaning and that’s not possible.
Amazing stuff!
3blue1brown, Joseph newton ahh video pull
Grrr so we don't get the solution to the 2D submarine do we... I guess I have to keep thinking for myself then... ;D
I'm a little confused about why you said ∞₁ and ∞₂ rather than using aleph. Is there a mathematical difference or is this just notational?
SOLUTION SPOILER
The mosquito problem seems pretty straightforward. Obviously you have the ∞₂ of possible directions but only ∞₁ points. It's not possible to map every direction to a point unless multiple directions could map to the same point. Furthermore, each point (except for the y-axis) represents some rational number - some slope in the form y/x. An angle of any irrational slope will preserve the mosquito population.
I wonder if there's some problem you could come up with that forces us to distinguish between transcendental numbers and other real numbers.
> An angle of any irrational slope will preserve the mosquito population.
A truly sad state of affairs.
Also reminds me of how an incline of the golden ratio is, in a way, best at missing the mosquitoes. I am too tired to elaborate on that or to check my memory on it.
Not using aleph-notation is purely a notational choice. My goal was to simplify the notation for people who haven't seen it before, and I think it's always fun to use a non-traditional notaton when you've derived something yourself :)
As for the 2D puzzle, which variant would you like to know the solution to?
And further more: since infinity_2 is infinitely larger than infinity_1, pointing in a random direction results in 0 probability to hit any mosquito.
By the way, the notation in the video is more like a variant of beth notation than of aleph notation. Without assuming the Continuum Hypothesis, we don't know which aleph is the cardinality of the continuum, although we can exclude some alephs.
Just turn it one radian, or turn it 60 degrees.
Great video, but there is one mistake. We know that there is nothing between א0 and א1, Continuum hypothesis says that |R| = א1, and this we do not know, because |R| can be greater than א1
Edit:
Source en.m.wikipedia.org/wiki/Continuum_hypothesis en.m.wikipedia.org/wiki/Continuum_hypothesis
Great video!
Cool video!
I'm guessing that because the density of rational numbers in the reals is 0% that the mosquitoes are all completely safe from the laser.
The ans to the second q is slope must be an iraational no .Now let's say our lazer hit a point (a,b) then the slope of line must be b/a bit if slope is irrational it is not possible
Hi, no soulution exists because at the origin there is a mosquito and the laser gun also....
isn't that just map out to the difference between the space of rationals versus reals because hitting a mosquito means that you cross a point in the coordinate grid that maps to a representation of rational number
These "infinity types" are called beth numbers
I am putting this here before he get famous
What would Heisenberg say?
I must have misunderstood what the submarine problem actually is. If the submarine starts at position 0, and has v=1, then it will move along the positive number line and get out of reach of the search position. The search will eventually reach every position that the submarine has been in the past, but will never reach the submarine.
No, you take starting position, then add the velocity times the number of seconds that have passed. This will eventually get you to the exact location that the submarine is, no matter the starting point or velocity
You understand the problem, but you’re missing a subtle part of the solution. We check every position based on velocity and time that has passed. This is not the same as just checking all positions.
8:33 I have a question: What about situations similar to the trick where 0.(9) = 1? The numbers look different, yet they are equal. So why does having just one different digit in two numbers make them certainly unequal?
If one of those numbers is on the list then you won’t get such a number (such a number referring to one with many nines, and the number you got being the new number), since the new number will be different from any number on the list with infinite nines
If such a number isn’t on the list, then either you won’t get one for your new number, in this case, no problem, or you will get one, but that would imply that at some point, there are only numbers that have 8 on the digit you select, then that digit before the 8s will have another +1 added to it, which is no problem since it’s still not equal to the original digit. And it can’t be equal to any number after since you’ll have only 0s (after you remove the 9s) in the digits when the 8s appear up to infinity, and each number has to have an 8 there.
I hope I explained it well.
If the newly constructed number tails with an infinite string of nines, there are only finitely many real numbers in the list not containing an 8, so infinitely many numbers not containing an 8 are not in the list.
@ Wow, that much more straightforward than my explanation 😅
Excellent point and indeed a caveat I didn't cover for the sake of time. Some good explanations here :)
The easiest way to avoid 0.999 repeating = 1.0 schenanigans is just to add 2 to each digit instead of 1. Now the digit 9 becomes 1 instead of 0, so there's no way to accidentally run into an equivalent representation. Of course, this technique won't work in base 2...
Another technique that does actually work in every base is to observe that in order to have a second representation of a number show up, we need something of the form ....0000 repeating forever (note that "9" will represent whatever number comes before "10" in whatever base we happen to be working in) in our constructed number. But this means that every number in our list had a 9 at an appropriate position, which clearly excludes a whole bunch of numbers that don't have a 9 anywhere. Even in base 2, where the only number without a "9" digit (more commonly written as "1" ) is 0, there are many numbers that only have a few "9"s near the beginning, followed by repeating 0s. We can see that we don't have enough room at the beginning of the list for all of them before our changing digit ends up falling in the repeating 0s in the tail.
Nice puzzle but music in the background very off putting.
I'm trying to understand infinity for 10 years now, watching this and that video. Still couldn't make it.
8:51 "You cant make a list of all the Real number, so the Reals must be uncountable".
But the same can be said of integers. They too can be made into a list, where you add +1 each time and construct a new number. So why they're called countable then?
The video showed earlier (in the submarine context) that you *can* make a list (though an infinite one) of the integers via the dancer trick: 1. 0, 2. 1, 3. -1, 4. 2, 5. -2, 6. 3, etc. As discussed in this video and many others, you *cannot* do the same for the real numbers. If you thought you had a method to make an infinite list of the real numbers in the same way, then your method must have a flaw revealed via the diagonalization trick.
Integers only have finitely many digits - if you add 1 in every infinite position, the number you get has infinitely many digits, so it is not an integer.
If you only add 1 in finitely many positions, the number is not automatically different from every number on the list, so you haven't found a number not on the list.
You can’t have a natural number with infinite digits going to the left. So you can’t just keep adding 1 for each digit infinitely
You actually make an interesting point! At first glance it may seem like we could just make the same diagonalization argument for rational numbers right?
And indeed; we would be able to construct a new number not on the list using our diagonalization method. The problem is that that number *would not* be rational.
How do we know that? Well, for one, because we just showed the rationals are actuall countable. Another cool realization is that every rational actually has a repeating (or finite) decimal expansion (there are several pretty straightforward ways to see this). The number we construct will most certainly not.
Hope this helped!
You never hit a mosquito if the slope of the laser beam is irrational. The best way to avoid all mosquitos is the most irrational slope, namely the golden ratio.
You can actually not make a list of even 1 real number.
i dont even know if i can 'randomly' choose a real number
Choose π
You cannot chose a real with a uniform distribution. But you can with e.g. a normal distribution.
you can’t actually sample it yourself or get a computer to do it, but that’s not to say you can’t determine properties of different distributions over the reals, such as the fact that in a uniform distribution hitting a rational has probability 0.
@@nboothhow would you go about sampling a real number from a normal distribution? I’m not sure it can be done
@ i asked to my friend, turned out it has something to do with measure idk
Excuse me. It may well be that my English is way too bad. However, that unmotivated, superfluous and senseless background music makes it impossible for me to concentrate. Good bye to this channel.
Infinity is both a concurrently a singularity and an inverse of a universe pre big bang singularity. Existing in inverted dimensions of spacetime.
This is all trivial. This video doesnt even start to tackle any real issue related to infinity concept like axiom of choice or real numbers inconsistencies...
If it's all trivial to you, that means it's for people at a lower level. At some point in your life, this would have been new to you too.
If I could give this video 2 thumbs down, I would. Very poorly explained
Any particular part that you think could have been explained more clearly? :) Any feedback is much appreciated!
To me, it isn't clear why coming up with a clever way of counting all the integers by jumping back and forth across zero is an allowed behavior to count all the numbers
Actually, the rational numbers would be uncountable infinity, since you can always go up by a smaller amount. You would never make it past 1!
That's not how any of this works. It is possible to make a list of all rational numbers so therefore it is countable. You don't have to make a list /in order/
It all depends on the method of counting. As shown in the video, you can absolutely pick an approach that will not count through, for example, all integers. In fact, we can find a method that does not count through the natural numbers (the very definition of being countable!) Example: Start at 2 and go up. Once done, count 1.
This will never get to the 1 since counting up will take forever. This does *not* mean that the natural numbers are uncountable.
A set being countable just means that there exists at least one way to count through all the elements in that set, not that all methods need to succeed in that. To see how it works for the rationals it might help to think concretely about the order we go through them. In some sense, we grow both the numerator and denominator in parallel! So we will go "wider" and "deeper" at the same time. Hope this clarified things a bit!
8:40 That approach does not work. 1 = 0.999…, but if you do 0,…,8, 9 → 1,…,9, 0, you map 0.999… to 1.000… which means you don’t get a new number. So if my list is nothing but copies of 0.999…, the “new” number is 1.000… which is already in the list. (If you require the numbers to be unique, use 0.999… as the first number and 0.9, 0.09, 0.009, etc. as the remaining number of the list.
Excellent point! Indeed one of the details of the proof that was left out for time. Can you come up with a method to account for this in the proof? (There are many possible ways) There is a discussion with some good approaches in another comment :)