Simple Principle Solves Seemingly IMPOSSIBLE Math Problems
Vložit
- čas přidán 16. 05. 2024
- Sign up to Brilliant to receive a 20% discount with this link! brilliant.org/upandatom/
Recommended course: Infinity brilliant.org/courses/infinity/
Hi! I'm Jade. If you'd like to consider supporting Up and Atom, head over to my Patreon page :)
/ upandatom
Visit the Up and Atom store
store.nebula.app/collections/...
Subscribe to Up and Atom for physics, math and computer science videos
/ upandatom
For a one time donation, head over to my PayPal :) www.paypal.me/upandatomshows
00:00 - Intro
01:00 - Hair twins
02:45 - Data Compression
08:34 - Different sizes of infinity
A big thank you to my AMAZING PATRONS!
Jonathan Koppelman, Michael Seydel, Cy 'kkm' K'Nelson, Rick DeWitt, Thorsten Auth, AndrewA, Izzy Ca, Richard O McEwen Jr, Scott Ready, John H. Austin, Jr., Brian Wilkins, Thomas V Lohmeier, David Johnston, Thomas Krause, Lynn Shackelford, Ave Eva Thornton,
Andrew Pann, Anne Tan, Millennial Glacier, Viktor Lazarevich, Keith Lazarus, Tyler Simms, Michael Geer, James Mahoney, Jim Felich, Fabio Manzini, Jeremy, Sam Richardson, Robin High, KiYun Roe, DONALD McLeod, Ron Hochsprung, Aria Bend, James Matheson, Kevin Anderson, Alexander230, Michael Martin, Tim Ludwig, Alexander Del Toro Barba, Corey Girard, Justin Smith, Emily, A. Duncan, Mark Littlehale, Tony T Flores, Dagmawi Elehu,
Jeffrey Smith, Alex Hackman, bpatb, Joel Becane, Michael Hunter, Paul Barclay, 12tone,
Sergey Ten, Damien Holloway, Mikely Whiplash, John Lakeman, Jana Christine Saout, Jeff Schwarz, Yana Chernobilsky, Louis Mashado, Michael Dean, Chris Amaris, Matt G,
Dag-Erling Smørgrav, John Shioli, Todd Loreman,Susan Jones, James N Smith, Shane ODea, Roland Gibson, Joe McTee,, Dean Fantastic, Bernard Pang, Oleg Dats, Max Isenholt, John Spalding, Simon J. Dodd, Tang Chun, Michelle, Richard Vallender, William Toffey, Michel Speiser, Rigid Designator, James Horsley, Craig Tumblison, Cameron Tacklind, 之元 丁, Kevin Chi, Paul Blanchard, Lance Ahmu, Tim Cheseborough, Markus Lindström, Steve Watson, Midnight Skeptic, Kyle Higgins, Dexter Scott, Potch, Indrajeet Sagar, Markus Herrmann (trekkie22), Gil Chesterton, Alipasha Sadri, Pablo de Caffe, Taylor Hornby, Mark Fisher, Colin Byrne, Nick H, Jesper de Jong, Loren Hart, Sofia Fredriksson, Phat Hoang, Spuddy, Sascha Bohemia, tesseract, Stephen Britt, KG, Hansjuerg Widmer, John Sigwald, O C, Carlos Gonzalez, Thomas Kägi, James Palermo, Gary Leo Welz, Chris Teubert, Fran, Robert J Frey, Wolfgang Ripken, Jeremy Bowkett, Vincent Karpinski, Nicolas Frias, Louis M, kadhonn, Moose Thompson, Andrew, Pedro Paulo Vezza Campos, S, Sam Ross, Garrett Chomka, Bobby Butler, Rebecca Lashua, Pat Gunn, George Fletcher, RobF, Vincent Seguin, Shawn, Israel Shirk, Jesse Clark, Steven Wheeler, Philip Freeman, Jareth Arnold, Simon Barker, Lou, ans Simon Dargaville.
Creator - Jade Tan-Holmes
Script - Raphael Rosen and Jade Tan-Holmes
Cinematography and Fact checking - Simon Mackenzie
Animations - Daniel Kouts
Music - epidemic sound - Věda a technologie
Sign up to Brilliant to receive a 20% discount with this link! brilliant.org/upandatom/
Recommended course: Infinity brilliant.org/courses/infinity/
4:33 Whoops it's actually 22 characters, not 18! Seems like I can't count :)
14:14 Also the cardinality of the Reals is only aleph 1 if you assume the continuum hypothesis is true. Otherwise it’s 2^aleph 0. Video about that coming soon :)
Does Brilliant have Ramanujan Physics !? 🥺🌈
I was searching for glory hole and i got recommend this video 😂😂😂
By the way, if that company instead stated, that their algorithm is able to compress 80% of files to 80% of their original size, this pigeon hole algorithm would say “yes, it’s possible”, but this is not true
7:35 the answer is simple: different (de)compression algorithms -> different original files mapped to the same compressed file images. And vice versa
Speaking of corrections, isn’t cardinality of real numbers Aleph One only if one assumes continuum hypothesis?
Regarding compression, if it could really compress *any* file to 80% of its original size, then you could run it multiple times to get even smaller.
Someone might claim that their data compression algorithm works for any files that large enough.
Hahaha, Yeah, you could technically compress everything into almost nothing. Wait 🤔that sounds like the reverse of the big bang.
By the way, if that company instead stated, that their algorithm is able to compress 80% of files to 80% of their original size, this pigeon hole principle would say “yes, it’s possible”, but this is not true
@@llMarvelous The pidgeon hole principle would not say that's possible. Take the example with a 100 bit file, there are 2^100 possible combinations. 80% of all 100 bit files, 0.8 * 2^100, is still a much larger number than 2^80.
@@albin7475 actually not even 1 bit can be compressed when using 80% of the original files. You'd be able to compress 50% (2^-1) of the files to 99% of their original size which is pretty useless. That's why compression only really works for very low entropy files compared to the maximum entropy of a file (highly patterned data instead of a random bit distribution). That would be like staying i can compress losslessly one quadrillionth of all 100bit files to about 50% of their size.
I think it's interesting that the only reason lossless data compression works at all is that the files we work with are HIGHLY atypical. The vast majority of possible bit strings are so close to purely random that a lossless compression algorithm will actually make them longer. But files we actually use are generally among the astronomically tiny fraction that have fairly reliable patterns throughout.
So here's a thought: the data sets that look the most meaningless (pure random noise) actually contain the most information.
Which is why it (information density) is called "entropy".
@@michaelmicek Yep, that's why compression works in the first place
Yep. A video file with a still face, or a standing building, or a parked car - contain a lot of redundant information, and is the basis of the MPEG2 compression algorithm used in DVD, and some streaming formats - including H323 for videoconferences.
In non technical words, the algorithm sends a still frame and successively only transmit the changes; in the case of a newsreader, there are only the lips moving.
It is the nature of our constructed world that contain a large number of redundancies. The white noise of the sea contains from 10 to 100 times more unique information than the sound of a violin...
@@ChemEDan but it seems to me most people (who? well, I reread the Shannon paper again the other day to explain why evolution works and it crystallized, so me and the other guy) confuse information with meaning, so that random, high entropy noise contains no meaning, hence no information.
Atypical in terms of what's possible overall, yes, but thankfully typical of what's likely in the real world. Stuff tends to naturally fall into patterns.
14:06 ℵ1 is not defined as the cardinality of the real numbers, it is defined as the smallest cardinality bigger than ℵ0.
The cardinality of the real numbers is denoted with 𝔠 (for continuum) or with ℶ1 (beth numbers).
The question of wether bet numbers and aleph numbers are the same is called Generalised Continuum Hypothesis.
Interesting explanations of math concepts! 🤓
Made a bee like for the comments to say this. Glad to know I didn't somehow miss the continuum hypothesis being proved 😂
What's the use of all this jargon? Is there any real world use of this ??
There are quite a few good CZcams channels covering science and mathematics, but Jade's presentation is the clearest and most logical. It's one of the few covering complex topics that I don't have to "rewind" muttering "Eh?"
I think vsauce or veritasium had a video about the pigeonhole principle where they showed the diagonalization solution and I was completely lost. In Jade's video - it just makes sense.
Jade's presentation is also among the most enthousiastic and engaging.
The small sketches in this video were absolutely hilarious, gives such a charm to an otherwise really educational video. Great format.
Is the dude in the park a giant or is she a gnome? He's taller sitting down than she is standing up.
Otherwise?!?
"...I don't think it means what you think it means."
👍 Really enjoyed it, made the maths more entertaining and easier to understand!
@@aceichner Well English isn't my first language so I probably misused the word. Judging by the votes and replies I'd say the intended meaning came across just fine.
Another unexpected place the pigeonhole principle pops up is optical illusions. A lot of them work because there are more three-dimensional scenes than there could be two-dimensional viewpoints of them, therefor some two-dimensional views must map to the same three dimensional scene.
*The Holographic Principle* "And I took that personally"
You probably meant to say "some three dimensional scenes must map to the same two dimensional view"
This is a mind-blowing perspective that I had not considered until just now.
And because we depend A LOT on our own experience with 3D to intuit what sorts of 3D imagery are suggested by pure 2D shots. That's how we see, say, a circle with off-oriented facial features as a spherical head or a hand disproportionately larger than the rest of someone's body as outstretched even without more objective depth cues like lighting changes or slower panning of more distant imagery. Sometimes these assumptions are supposed to be right and sometimes not.
@@piotrarturklos Doh, yes I did. A medium sized image of a ball could be a small one very close to you or a big one very far away.
As a math PhD, it sort of feels obvious. But the way you tell it's story is brilliant; I'll recommend it to anyone who wants to know more about it. Thanks Jade!
thanks to brilliant for sponsoring today's episode!
Wow, thanks! 😊
God bless you
Went over this principle a couple times in Book of Proofs and *sort of* understood it. I always love when Jade comes along with a brilliant and timely explanation.
"Entirely agree! 🤗👏"
Jade: 14:06
The Continuum Hypothesis: Am I just a joke to you?
I really enjoyed this video.
I studied Maths and Physics at university - 60 years ago!
I still find the ideas I learned are useful in everyday life.
The Pigeonhole Principle is an example. Thank you. 😀
i wish you had been my maths teacher, not till i got to about 45 did i realise just how interesting it can be. you make learning interesting that is a super power right there.
Thank for all of your videos, they are just great! Great presentation, I also like the background with the equations that you describe in some of your videos! My favorite quote from this video (14:18): ...the pigeonhole principle shows how far we can get by just thinking... That's such an important thing to teach others and you do it very well!
As always, I love your videos, I'm in my 70's so I need to keep my mind sharp and I learn something new almost every time. Thank you helping keep my brain keep working.
Nice work, Up and Atom 🔥😊👍
I've read and heard this so many times. But no one has made it so easy to understand without oversimplification. Great job! Thank you so much ❤️
I LOVE your videos. I really like science, but am not very good at math and appreciate how you’re able to take complicated/advanced ideas and simplify it in a way that I can actually understand the basic principles. I’m not going to be an astronaut or a mathematician any time soon, but I definitely can appreciate things a bit more thanks to how you explain everything. Thank you!
Love your production and I appreciate your effort, the topic becomes very clear!
In the final year of my undergraduate maths course, the lecturer said he would have to invoke a principle that we had not seen before. We all groaned assuming that this meant we were going to have to either look it up or have to prove it for ourselves. However, the lecturer then went on to explain the principle ,saying that if N objects are placed in M boxes and N>M, then that would imply that at least one box would have more than one item in it. This was called, he said, "Dirichlet's Box Principle". We were slightly aghast that someone had managed to get their name recorded for posterity by stating something so clearly evident. It wasn't the last time we invoked Dirichlet's Box Principle aka the pigeonhole principle.
👍 Thanks for your insight! Interesting use of the principle!
So there are fewer mathematical principles than there are names for mathematical principles, so some principles must have more than one name.
@@brasshopper Some mathematical principles have multiple names. You have a name. Does that prove that your name is linked to a mathematical principle?
Even only Presh on CZcams who called Phytagoras Theorem "Gougu Theorem"
Just discovered this channel. You are so precise and easy to understand. I love it! Thank you!
your enthusiasm for mathematics is the cutest thing I saw for a long time. Glad I found your channel. Keep it up please
Great video! Really loved the simple visual explanation of lossless data compression.
Alright might as well write out my thought***. I don't know how to do a math proof of anything. So bear with me.
Ok getting to 1 is a divergent infinity, Integers counting is converging infinity. So both infinity. But one is heading towards it, one is heading away... although it gets infinity closer, it won't ever meet, so infinite Uncountable. But Integers counting would theoretically meet infinity. Countable. Numbers are bounded by a set of infinities. To me, it makes more sense the primes. Integers that only can be divided by itself (a fraction prime/prime is 1.) And 1 itself. Which would equal that Integer itself. Primes are like the only true Integers. They are ,Ike bounded by the same rules as counting to 1 (zero is positive because it begins positive Numbers, isn't negative, and it's even, this part makes zero positive because why is zero even? The summation of all factorial until 1, is -1/12... 1/(12 is special. 1/1 is 1, opposition isn't -1, 0/1 is zero... shift forward. 1/2, but we are in base 10 AND base 2. 1 over 11 11 is 2 in base 2, 10 to 11, shift forward 11 to 12 because you are really saying 1/(Uncountable infinity divergent) 12, the denominator is base 10 Integer. Now 1/12 has opposing -1/12. And since we are defining a summation that is Uncountable, we must use its countable opposite so that's why negative 1/12, which then follows that zero is now part of this set of positive Numbers used to sum to 1. So first prime is 1. You can't divide 1 by zero in base 10. But you can divide 1 by 1 (1 is also itself). 2 by one is 2. 2/2 is 1. 3/1 is 3 4 you can divide by 2, so not prime. 5 prime 6 divide by 3 not prime. 7 prime 8 not, 9 not, 10, not, 11, YES. 12 FIRST NOT PRIME AFTER 10. AND FIRST NUMBER YOU CAN USE As the denominator in base 10 that is divisible by an Integer up until thus point. 12 is most reduced then, in base 10, beyond 10, so now we satisfy the boundaries of a number by both infinities. 1/12 and we need -1/12 to make it real. So. Yeah. Also this alludes to why primes have to be found. You have to kinda "prove" everything before any prime. You can't simply use a list of primes to know the next. Cuz the next countable integers need the primes. Until the next prime. You can't know the next prime with some formula because it's like asking for knowledge of the numbers AFTER the next prime but before the prime after the next. How can you solve for some prime when it's intrinsically connected to the integers in between it and the next (and next(and next...))?
--------
***Because when I was explaining "why 17" as a solution to another problem, I was like this would apply to compression and error correction. I wish I mentioned it. Also how to describe something. It's more efficient to go up a dimension and transform to something that projects down to what is solvable with the rules of the lower dimension. Like linking points in a circle thst don't appear possible to use lines to do it without crossing... as a sphere you can rotate it with those points mapped to surface so projection now has points all where lines easily connect without crossing. Then transform back. The lines won't appear straight. But it's only perspective.
thank you so much Jade for putting in your work to making this amazing content
5cy it s
"👏 You're amazing too, Clara! 🔥"
I love that you recognized implicitly in this video that the pigeonhole principle is really a statement about the cardinality of sets with surjections between each other. And I love the stuffed animal pigeons!!
To answer your question proposed: For any set A, the power set of A is the set of all possible subsets. That is,
P(A) = {B | B ⊆ A}
You can actually show (via the pigeonhole principle, essentially ;) ) that the power set of any set must always have a cardinality strictly greater than the cardinality of the original set. Here's an off the cuff proof:
Suppose A is a set. We know that for each x in A, {x} in P(A). Hence there's an injection f:A -> P(A) defined by f(x) = {x}, so |A| P(A). Now define the set U such that
U = {x in A | x not in g(x)}
Clearly U ⊆ A, so U in P(A). Thus since g is a bijection, there must exist a y in A such that g(y) = U. Now here's the question: Is y in U? Suppose y is not in U. Then y is in U as y is not in g(y). But then if y is U, then y is in g(y), so y is not in U by definition. Thus in either case, we reach a contradiction. Thus it must be |A| ≠ |P(A)|. Since we know |A|
Two of the most vivid memories and profound realizations I had while studying math was proving/learning that the cardinality of (a, b) where a and b are real numbers is the same as the cardinality of the real numbers … and then that P(N) is equinumerous with R.
I can't read this without latex bro I swear I'm blind
@@NoorquackerInd Lol I wish CZcams supported LaTex ha ha!!
@@NoorquackerInd if only!
@@briangronberg6507 Dint they teach you ow to draw a graph of something asymptotic to x=1 where by the whole Y axis is in 1-1 correspondence with X?
I really love how you explained lossless compression in the simplest way!!!!!
This principle looks so simple but so amazing. Thanks for the information jade 😁😁
The cardinality of the real numbers is not called aleph_1:
aleph numbers count infinities in increasing order of size, starting at aleph_0 being countable infinity. The continuum hypothesis, which was painstakingly proven to be independent of ZFC, is what states that the cardinality of the real numbers is equal to aleph_1, i.e. that there are no lesser uncountable infinities.
12:08 is my favourite part, i love it. The way she cross her arms is no telling
This is absolutely brilliant. Apart from the clarity of argument, it uncovers the real beauty of mathematics
"Wow! I'm so impressed. 🤩👏🏼"
Keep it up, I'm majoring in astrophysics and I love your content.
Fun thing of lossless compression is that it is quite possible to send in a set of input data, and have the compressed lossless file output actually be larger than the original, despite the lossless compression actually being able to find redundant information in the file stream to allow compression. Just that the amount of compression is less than the amount of extra metadata you have to send to allow the extraction to work.
It's very easy to imagine given example in the video. Just think about files were B and W alternates. Presented algorithm will make the file twice as big.
Technically, aleph1 is the smallest cardinal number greater than aleph0. It might be the cardinality of the real numbers, but it might be smaller than that: we can't actually prove nor disprove that.
Interesting! 🤯 That must be pretty tough to prove!
@@cyrileo It's more than that: it has been proven that it's impossible to prove nor disprove that fact with the tools of "regular mathematics".
The set of all subsets of any set always has higher cardinality than the original set. Its called the power set.
Pigeon holes 👍🏿
Wow! 👍 That's incredible!
Fantastic. The best explanation on this I've found. Regarding the principle applied to compression, to take that further, it sounds like if you could compress *any* file by a fixed amount, even really small like 0.0001%, that would still apply to a file that was just compressed, and you could then repeat until you reach whatever level of compression you desire, so that is not possible. (*Edit*: As already noted in the comments). It's possible to calculate the minimum number of incompressible strings in a string of length N, for example, so that sets an upper bound on the fraction of strings (or files) that could be compressed at all, but it seems that there's no clear lower bound - in other words we can't say that there are at least 10% of strings/files that are compressible. Clearly its not zero based on direct observation. I wonder if a probability could be assigned - for example, there is a x % chance of compressing any given string/file of length n by y %? I find this endlessly fascinating - there's clearly some order in every random collection, and there's a nonzero probability of finding any string (such as the text of "A Tale of Two Cities" in english) in a random collection of the alphabet (including punctuation) in a big enough collection, and it approaches 100% as the size of the collection approaches infinity. It would also include next year's as yet unpublished bestseller, and so on. So it seems that there's some magical degree of order in randomness that can appear, but which does not allow us to to efficiently extract any useful work, since if it was allowed we could simply iterate that process to achieve whatever level of efficiency we want. The pigeonhole principle does appear to allow us to extract some useful information from completely random collections - I guess the difference is that it's not an iterative process - we can only use it once. It seems very similar to other statistical principles that allow us to make general statements about collections of numbers and things like that, such as Benford's law.
The reals are actually beth-1.
The beth numbers are each 2 to the power of the previous one, and beth-0 is aleph-0.
Beth-1 vs Aleph-1 is known as the continuum hypothesis, and it's known to be unsolvable.
It's early Sunday morning here in Kentucky and I awoke to a great new video of something I still find hard to fathom. Thanks for the great video
Wait, the cardinality of the reals being equal to Aleph one is called the continuum hypothesis, which is famously undecidable.
Undecidable within ZFC, not, strictly speaking, undecidable altogether.
Nice video! But I'm afraid I have to complain that the cardinality of the reals is 2^aleph0, not aleph1. Aleph1 is (roughly) the second-smallest infinite cardinality, and whether or not this equals 2^aleph0 is the Continuum Hypothesis! :)
came say this, and obviously there are someone else who thought the same
Even better, whether or not there are any infinities 'smaller' than Continuum but 'larger' than countably infinite is apparently undecidable without including at least one new axiom of the system that pushes it one way or the other.
If you want to construct sets that are larger than the Continuum measure, there are some fairly accessible, 'easy' ways. Consider the Power Set of the Real Numbers - that is, the set of all proper subsets of the Real Numbers, which would have measure 2^(2^Aleph_0).
For a really trippy journey down the infinite rabbit hole, consider the extended Surreal numbers, which add transfinite and infinitesimal ordinals to the number line, and all of the numbers they imply, packing each real number with an infinitely dense neighborhood of infinitesimally close neighbors that are closer to them than any other Real number would be, while at the same time extending the number line with transfinite numbers larger than any finite number... only to have each of *those* numbers blossom into their own continued Surreal neighborhood and points beyond. The Surreal Numbers have a 'size' so large that it is actually larger than *any* other definable infinite size - that is, there are more surreal numbers than any other possible infinite set.
the best of these videos is that I could learn even more in the comment section.
@@HeavyMetalMouse the Surreal numbers is not a set is a proper class, so cardinality and therefore "size" lose sense when you describes them
That's only partially true -- you and Jade are both right. The cardinality of the reals = ℵ₁ = 2^ℵ₀. Some kinds of operations on ℵ₀, like ℵ₀*n or ℵ₀^n, will still result in ℵ₀, but some kinds of operations do produce larger cardinalities. See the Wikipedia page on aleph numbers for more info.
Quick show of hands. How many people noticed 00:21? I showed the video to my 9 year old and had to skip back several times and point it out before it clicked for him and he laughed profusely. I was surprised not everyone saw this straight away and it’s still a nice touch
This was an awesome watch. Thankyou
Can you do a video about quaternions. I bet you would do a great job!! I can wait until you do it . I watch every possible video that you put out. I studied set theory at IIT in Chicago but you are much better at explaining mathematical concepts better then all my professors put together!!
All a quartermion is a scalar and a bivector, rather than only one complex variable, two additional hypercomplex variables are added to describe 3d vectors.
For me, the most mind-blowing thing I learned from this video was the fact that people from Sydney are called Sydneysiders.
5:23 - absolutely my favourite part. Why is Jade's particular brand of digressions so relatable?
Mine too!
very good explanation of data compression!
You should give names to the other 'Jade' characters so they can appear in other videos. I can't remember the video but I sort of remember one 'Jade' character that you call 'Blade'.
czcams.com/video/34FNWQ9trY8/video.html
Sunglasses = Shade
Viking helmet = Rade
Kitty costume = Spade
Mafia outfit = Made
Fish costume = Filade
why did you break their necks 😟
Its a sad sad situation
Average physics major
Breakneck science~
Because they're flying rats
To stop them from spreading their wings and taking up too much space, of course.
I just discovered this channel, and I love it. This video was funny, interesting, and informative; it really helped me understand the Pigeonhole Principle for my discrete math class. I just subscribed for more!
Thanks buddy for simplifying the theory. It really caused my mind some serious trouble. Thanks again.
Jade over here filling up the boxes for each number of hairs up to a million. Really appreciating the effort you put into these videos.
There once was a village of barbers who wondered if there was a way of assigning each barber a group of villagers to shave in such a way that every possible group of villagers was shaved by some barber. A travelling salesman said they had come up with a list of doing it but the chief barber, who took set theory in undergraduate school, had their doubts.
The chief took the fancy list and considered the group of barbers who don't shave themselves (the selfless barbers). If the travelling salesman was telling the truth, there should be some mysterious villager who shaved the selfless barbers. Unfortunately because the list was infinitely long and the chief was getting tired after figuring out the selfless barbers they didn't want to look through any more paperwork.
Instead the chief asked the question "does the mysterious villager shave themselves"?
1) If they shaved themselves, then they should be a selfless barber but that doesn't make sense
2) If they don't shave themselves, then they aren't a member of the selfless barbers but that also doesn't work.
And just like that the fancy list disappeared in a puff of logic [and the chief barber who was actually Cantor all along proved card( X ) < card( 2^X )].
Awesome video btw :)
"does the mysterious villager shave themselves"?
Not if they are 3) a hairless selfless barber.
Sorry bald people.
Jade, there's a mistake near the end: Aleph_1 is not necessarily the cardinality of the real numbers. Whether or not that is true, is dependent on the answer to the continuum hypothesis, which is Hilbert's first problem. It was proved that this is independent of ZFC set theory. en.m.wikipedia.org/wiki/Continuum_hypothesis
Wow, nice explanation and it is a master piece. Thanks for making this video.
Great video as always! This time I have one small nit to pick:
13:20 I think this is a potentially confusing way to explain the argument. By saying you subtract 1 this time, it gives the impression that you will go back and forth with them: they add your new number to the list, and you use a different operation to generate a new number, etc. The shrewd may then ask: "but what if you run out of different kinds of operations to do on each digit?". But that would be missing the point: it's not the specific operation done to each digit (add 1 or subtract 1) that matters, simply that it changed each diagonal digit.
Instead, I think it would have veen cleaner to say "you can just do the same procedure again". And number they jusy added, in list position X with be different from your new number in digit position X. This immediately puts it into an infinite loop without worrying about whether you will run out of different operations to use to alter the digits.
Jade, you've done it again: educated a guy with a degree in computer science in computer science. I remember some of this from my math classes in university, but to be honest, never it has been presented so well and rememberable to me. Thank you!
That was an excellent use of Cantor's Diagonalization proof .According to Russell,in his History of Western philosophy,Cantor's set theory was the new branch of math that finally buried for good Kant's assertion that math is synthetic (proposition whose truth or falsity is to be proved by recourse to experience.)
Excellent video by the way.
I claim it’s analytic a posteriori 😎
Here’s my reasoning: clearly, mathematical theorems are derived from definitions, so it’s analytic. But ever since Gödel, we know that no matter how many (first order) axioms you add, you’ll never capture everything that is true about something as simple as the natural numbers. The true „thing“ is out there, not in the physical world, but it is independent of us and our clumsy human language. It needs to be discovered through experience, but this experience isn’t gathered with our senses, but on paper.
@@markuspfeifer8473 so your view of mathematics is platonic ? Knowledge to be discovered is an abstract realm of sort ,if I understand you well .
@@mutabazimichael8404 sure it is! I think that’s the only way math makes any sense. Or anything for that matter
@@markuspfeifer8473 I kind of agree with you .
I learned something from this video. Thank you❤
Not the first CZcams video discussing cardinality. But certainly the one with the shiftiest characters. Love it!
Love the notion that someone would be going door-to-door selling data compression software. I don't know why, but I am still giggling like an idiot about that, and I am not even stoned. Thank you for brightening my day!
Someone did. Look up for the story of Phil Katz and PKZIP...
I wonder if they'd bump into the doo-to-door encyclopaedia sellers. Maybe they could compress the encyclopaedias and make them easier to lug around.
Jade is brilliant as a presenter! She is the most watchable presenter on CZcams (for many obvious reasons!) 🥰
couldn't help yourself, could you. 🙄😉
Love the title! It's really ridiculous how powerful this method is in practice, despite being so simple it's almost trivial.
So grateful for these videos. You're a brilliant educator.
I thought it was unprovable that aleph one was the cardinality of the set of real numbers? In fact it can be taken as an axiom to either be or not be aleph one and both produce consistent mathematics with their own uses (to this date).
Correct. Cardinality of real numbers should be 2^aleph0
Not quite. aleph_0 is countable, aleph_1 is defined to be the cardinality of the reals. The continuum hypothesis it needs to be an axiomatic choice if there exists a cardinality between a_0 and a_1.
@@manumben5241 "aleph_1 is defined to be the cardinality of the reals."
No, this is incorrect. It's a common misconception, but it is a misconception nonetheless. Aleph_1 is defined to be the smallest cardinal number larger than Aleph_0. You can look up "aleph numbers".
Both the comments in this thread before yours are correct.
Yeah, came to say that.
And for this reason you don't actually see aleph_1 very frequently; the cardinality of the reals is called c (continuum).
I take hair example personal, my count seems to be changing daily. Lots of opportunities to pair up.
A great teacher can make seemingly obscure knowledge experienceable. This video does that!
Love the pigeons! and zero and infinity are my favorite math subjects, always enjoy your videos. they inspire a day of thinking about something interesting
I would imagine that the achievable compression for each subsequent compressed file becomes less. Using Jade's example the first compression gives..
12W1B12W3B12W3B12W3B8W
So looking for the patterns if you then assign 12W=a 1B=b 12W3B=c 8W=d (and store those assignments in a lookup table)
you could get to
abcccd
then assign ccc=e
gives
abed
and finally assign abed = f
gives
f
and that's about it, plus storage for the lookup table of course, which has the potential to shove the total number of bits required back to close to the original.
You can design an algorithm that losslessly compresses any *specific* file to exactly one bit, just by saying, "I've stored a record of this whole file somewhere and if you show me a single bit then I'll give you the file." But it's no longer a general-purpose compression algorithm - it only works for that one file and produces nonsense for any other file. The corollary to the pigeon principle for compression is that any general-purpose lossless compression algorithm that can make one file smaller will make another file larger. If this were not true, then you could compress any file down to one bit by repeatedly feeding the compressed file back into the algorithm. The practical implication for software engineers is that we have to choose the best compression algorithm for the *kind* of data we want to compress. Not all algorithms are suitable for all kinds of data.
@@StrollHikes exactly, I put in a comment earlier, if the pre compressed data was WBWBWBWBWBWBWBWBWBWBWBWB then the compressed file will ALWAYS be larger using that method
@@jamescrawford1534 This was my first thought as well. Storing text that way would be terrible, as each bit is seemingly random, and you get a lot of back and forth.
However, with your example, that would be 1B1W1B1W1B1W1B1W1B1W1B1W[etc] which you could take up 1 notch, to 12[1W1B], or some other notation like, 12c1a1b, and if that alternated 12c1a1b1,8c2a3b,12c1a1b1,8c2a3b,12c1a1b1,8c2a3b,12c1a1b1,8c2a3b you could then say 4d12c1a1b18c2a3b, or maybe some other algorithm that generalizes better up the alphabet.
The thing you forgot is that you might’ve compressed a ≈20 caracther chain into 1, but you need about that many to note it in the reminder table. And now if we take 11W2B11W4B11W4B11W4B7W1B, you need to use letters h, i, j, k and m to compress it because a, b, c, d, e and f are already used and means different things.
You can compress a 30-bit sequence into a 15 caracther chain if you use 4 different digits (00->0, 01->1, 10->2 and 11->3), so 001110100100 becomes 032210, but then you need 16 digits to compress it again. Your compression idea will imply the lookup table to have billions of letter if you want this to work for every possible chains
I used to think you could compress files as much as you want just by dividing them by the same number over and over, but then I realized that wouldn't work because you'd need extra bits to contain the remainders.
You also need extra bits to tell how many times you divided it
If one compression algorithm was absolutely the best in every general case ("any file", "every possible file") then we wouldn't have a whole zoo of them to choose from for each specific file type.
And if a compression algorithm could indeed compress "any" file then it would be able to (re)compress files it had already compressed.
Jade: A slight correction: the cardinality of the reals may or may not be aleph-1. Strictly speaking, aleph-1 is the smallest cardinal bigger than aleph-0. The statement that aleph-1 is the cardinality of the reals is the continuum hypothesis, which is known to be independent of the standard axioms of set theory, ZFC. However, there is another sequence of infinite cardinals using the second letter of the Hebrew alphabet, beth, where beth-0 is the cardinality of the natural numbers, beth-1 is the cardinality of the reals, and in general beth-(n+1) is the cardinality of the power set of a set of cardinality beth-n.
One of my favorite math concepts I ever learned.
Power Sets. Can't be sure, but I recall working with the Power Set of any set, and that Power Set is larger than the original set. So I recall there being an infinite number of infinitely larger sets.
"Interesting! Thanks for the insight 🤔😊"
The argument is similar to the one shown in the video.
Your explanation of data compression is phenomenal! Any chance you might cover the Weissman score in your TPS reports?
aha fellow Silicon Valley appreciator here i see , I also wonder what the WEISSMAN score would be in this ;)
I loved that scene where they got a really really good score at the competition.
@@LT.dans_new_legs i wish weissman score really existed but I dont even know anything equivalent to that
I'd be interested in seeing this into a series.
One important physics application of the Pigeonhole principle is in Quantum mechanics, specifically with the Pauli exclusion principle, which states that no two fermions can share the same set of eigenvalues in the same quantum system at once.
The pigeonhole principle is used to prove that the exclusion principle (no two fermions have the same set of eigenvalues) means that each fermion in a quantum system must occupy its own unique quantum state (possessing its own set of quantum numbers).
In the context of electrons in an atom, this explains how electrons occupy a unique atomic orbital, in turn explaining the origin of elements, why matter has structure, and chemistry's periodic table.
Thanks PROF👏
Really good video! I just want to say something about infinities because I already see people arguing: Don't take it too seriously and be polite.
It's very important to remember that "infinity" is not a number, it is a concept. There are no infinities in real life, it's more or less a pigment of our imagination. Don't get me wrong, I really do love the concept of infinities, but they always lead to bunch of paradoxes, like the Hilbert's hotel. Look it up, but basically there is a hotel with infinite rooms that is full with infinite people. With simple proof you can show that you can fit another 1, 50, or infinite people in the hotel despite being already full. Again, I do love this kind of paradoxes that mess with your mind, but it only happens because all of them are contradicting something in someway, because we made them up...they don't and can't exist and nearly everyone forgets that.
Zeno's paradox isn't real?
Infinities *might* exist in the real universe, because it's possible that the universe itself is infinite.
And future time might be infinite.
Nobody ever forgets that infinities aren't concrete reality. Everybody knows that it's a mathematical concept.
Everything to do with infinity and real numbers is basically philosophy. The channel Insights into Mathematics is great if you want to know more.. 🙂
I asked ChatGPT if there could be real countable infinites in the physical world, and it said nobody knows. While infinite sets do create paradoxes like Hilbert's hotel, nobody has been able to show that these paradoxes are actually contradictions. Is there any way to deduce a contradiction from a countable infinity?
Even more obvious argument that a perfect lossless compression algorithm wouldn't exist: feed it a 100-bit file, it gives you 80 bits, give its 80-bit output back to it as input, it gives you a 64-bit file. Repeat until you get to just 1 bit. Now you only have 2 possible files. (Although, if you round up at each step (because you need a whole number of bits) you can't get lower than 4 bits with an 80% compression ratio.)
Thank you for explaining things in an easy to understand, fun way ❤.
I always learn a lot from your videos.
Regarding the aleph null, you can have an infinite set of aleph nulls.
Which is a bit like the hotel paradox.
This set of infinite is larger than the individual infinities which blows my mind. Infinite < infinite 😁😁.
Very interesting video. Although the principal makes sense, I had not heard of it before. I definitely enjoyed learning about it.
Excellent, Jade. Could you make a video on qubits?
maybe, maybe not
The video already exists, it just goes away whenever you look for it ;)
Great video, Jade! You've done it again. Your visual explanations always spark more interest from people like me to your topic. Cheers! 🥰🤓😍
You should have a disclaimer saying "No pigeons were hurt or abused in the making of this video."
Hi Jade
Wonderful video
Thank you
👋😁
For the Cantor diagonalization you cannot just add or subtract a number. Since the individual digits have maximum and minimum values. For example there is no single digit greater than 9 in a decimal system oh, and there's no single-digit less than 0. You have to use some sort of modular system so that for example nines map to 0. Also on adding a new number to the number list, changing your algorithm is not necessary. You simply add the new number on to the list and repeat the process.
She may not have said it, but wrapping between 9 and 0 is exactly what she did in her example.
I actually saw that Vsauce did a video on this too a while ago, he simply subtracted 1 when the number was 9, I can't remember which one that was but he definitely did one on infinities too and this video did a pretty good job on it too
Also I can't understand why the 'list' is not infinite. The infinite set suddenly became finite to prove there was another number not on it.
@@ploppyploppy The list IS infinite. But since it's a list, the following statement is true: Any real number x has an entry on the list. And list entries we can count, so let it be the nth entry. Now compare the new number we created to the nth entry: Can they be the same? Answer: No, they must differ at least at the nth position.
@@reamick that's good, I was listening, not watching
Hi, Jade!
Brilliant video, as always!
Though, there are small moments where you should be a little more careful with proofs.
1) In the diagonal argument, when you find a number that is not in the list and you add it to the list, you don't have to change the procedure to generate a new number. An updated list will give you a new number.
2) Real numbers are tricky in a way that they might have two representations as a sequence of decimal digits. This can break the simplest procedure when you add 1 to diagonal digits.
For example, if my list of numbers is:
0.099999999999999...
0.090000000000000...
0.009000000000000...
0.000900000000000...
0.000090000000000...
0.000009000000000...
Then your procedure gives 0.1000000000000.. which is on the list (in the first row)
3) You can't say that aleph 1 is the cardinality of real numbers, this is Continuum hypothesis which you can't prove or prove the negation of it.
Holy crow! I have been wondering about how to get around this specific issue with that common "proof" for a long time. I typically thought of it in terms of binary, because the arguments are easier to think about the consequences, but exactly the same argument using the usual that the diagonal isn't on the list while mapping the reverse of the digits used as the post binary point digit:
0.0000...
0.1000...
0.0100...
0.1100...
0.0010...
etc.
Then also using the fact that any 0. ... 01111 ... = 0. ... 10000 ...
There must be a way, else it wouldn't been dismissed. I've just always figured I hadn't stumbled across it yet.
2) The easiest fix is to, instead of adding 1 to each digit, write only 5s or 6s, making sure to make it different in the relevant spots.
3) The cardinality of the real numbers is commonly called beth1 rather than aleph1. Aleph1 and beth1 are incomparable (you need the axiom of choice or something similar to even establish that they can be compared)
on representative compression, which you used as the example, there is the pigeon whole limit. True algorithmic encryption is a using a core function and a seed value, similar to how random game world generation works, but in reverse. You have a function, a multiplier and a remainder. Mind you, these have a minimum of their own which is often somewhat large. but really larger data, it works amazingly well. Basically where an image is a plot of a curve, you don't need all the points of the plot, just the function of the curve( or a generic that will make any curve such as a complex sin wave series) a floating point value exponent, and a remainder(offset). the result will is smaller that every point of the curve for a sufficiently finely drawn curve. Expanding to a second or third dimension gets you more fine detail on even larger sets. Due to digital repetition, the degree of accuracy is tied to the the degree of expression, making it always complete and accurate. This is also how hashing works, which is a step less, often skipping either the exponent to use just the remainder, a case of unique enough to pick apart to similar sets. As far as a bigger infinite, that would be the complete complex numbers. As it uses two reals at once, each unique complex matches to two real ones. Adding to this are all points in space which take 3 real numbers. and all points in space time which take 4.
I'm glad that I know this chennal, I never knew that those proves can be learnt in so much interesting way
I literally told everyone you posted a new video lol i was so excited!!
brilliant delivery of concepts...... tough question having a simple answer
This is awesome, keep up the good work
Very nice. I can hardly wait for your next video on the Goedel incompleteness theorem,
Goedel's incompleteness theorem is my favorite theorem in all of mathematics! I CAN'T WAIT!!! Hopefully she ties in the Halting Problem and Russel's Paradox. The topic of undecidability is earth shattering!
My favorite Pigeon Hole Problem:
You have a set of 5 points on a sphere.
Show that 4 of those points exist on a closed hemisphere. (Half the sphere including the boundary/"equator")
Three points make a circle. I think that’s the key.
@@Xonatron on a sphere, two points make a great circle.
@@marytooker956 The largest circle possible? That's true!
I love the pigeon Hole Principle. I learned about it when I was also learning minesweeper and it really speed up my play. it so common sense but to make a name for it is amazing.
Best explanation and visuals for the pigeon hole principal. Great job.
Nice explanation. Bravo!
awesome presentation !
Cool. I've been solving nonogram puzzles on my phone lately and I've always considered them to be constraint puzzles. But in a way it is also uncompressing the image.
Context of the pigeonhole principle really helps with the diagonal argument!
Thanks a lot 🔥🔥🔥
Fantastic explanation!
As always a great video. Loved it.
Infinites and infinitesimals hurt my brain so much and yet they intrigue me to no end (pun retroactively intended). I've always wondered about the uses for transfinite mathematics and what the practical applications of epsilon numbers and beyond even are but it gets so incredibly dense and uses such foreign terminology and symbols at a certain point that it is very hard to break into much less confirm that there is a proper understanding. I would love a series that gets deep into the weeds of the infinite where most are afraid to go because I feel like just as thing start to get to the true extremes of knowing if you comprehend what is going on (Veblen hierarchy?) many times information becomes very hard to find in a digestible form.
Great video!
The bgm in the credits tho! banger!!
Great vid, numberphile did a good one on this too a few weeks back if people are looking for more videos on the subject. The cardinality of the reals is scary big, like you can't even get a 1:1 mapping of just the reals between 0 and 0.1, in fact you can't do it with any 2 reals no matter how close they are.