The Most Important Counting Concept You’ve (Probably) Never Heard Of
HTML-код
- Опубликовано: 9 июн 2024
- To see an example of how bijections can transform a hard problem into an easier one, check out the previous video of the series: • This Counting Problem ...
If you want to see some more examples of where these ideas can be applied, try these problems: • How Simple Counting Pr...
My Patreon: / zhulimath
0:00 Chapter 1: The Concept
1:10 Chapter 2: Why are bijections important?
5:00 Chapter 3: An Example Application
7:59 Chapter 4: Conclusion
Intro riff taken from: Nikolai Kapustin - 8 Concert Etudes, Op. 40: III. Toccatina
Music Credit:
Megan Wofford / Elegance
La plume volante / Franz Gordon
Anna Landstrom / Driftwood
Sayuri Hayashi Egnell / Lupi
courtesy of www.epidemicsound.com
30 years of programming using zero-indexed arrays makes the '+1' concept second nature. ;-)
Also makes watching someone starting to count a list from one feel strangely wrong
Second nature ok. But for the wrong reason, I think. Here the spaces between the numbers were counted.
@@dirkreisig4465 It would actually be for the right reason!
A C/C++ programmer would likely know that ptr[i] is a shortcut for *(ptr+i). ptr points to the first element in the array, and i is the number of spaces to go forwards from that pointer. This is why most languages have zero-indexed arrays.
@@Josh-yr6my exactly
@@veto_5762 yes, like living in the 21st century, but having to pre-pend our dates with a 20...
Guess what is the most common bug when writing code involving iterative loops?
One-off errors.
Thank god for modern compiler optimizations, the use of iterators over indices went to no significant loss and in many cases to actually 0 loss of performance, avoiding the risk of one-off errors.
It depends on your language, compiler and optimizations used of course, but when you want to loop over entire collection, don't be afraid of foreach - the intent is much clearer.
I believe there are cases in c# ~around version 6 and up, where foreach is faster than for loop - when you specify you will read-only access the members.
Sometimes you can achieve code that is easier to read and is faster at the same time, while old purists would guess it would be slower.
Was going to say, that’s not been true for a while!
@@Beesman88 Modern coding rule: trust the compiler. It can't pick your logic for you, but it can optimize your codeflow for you behind the scenes.
because everyone is taught that counting starts at 1, because math teachers are idiots.
As the saying goes: "There are two hard problems in computer science: cache invalidation, naming things, and off-by-one errors."
Something to note: Bijection is a combination of injection and surjection, which is why it's bi(2)jection. Injection is pairing one list to another in such a way that all the members of the target list are paired no more than once, and surjection is pairing one list onto another such that each member of the target list is being paired with atleast once. The combination of "no more than once" and "atleast once" is "exactly once", which is what bijection is.
Yep. Using the kind of language and concepts that I introduced in my video, another way of saying it is:
Injections are one-to-one and guarantee no overcounting has occurred.
Surjections are onto and guarantee no undercounting has occurred.
I thought it meant it was 2-way because they were invertible.
@@asdfasdfasdf1218 This is also true, it's just another way of viewing the same ideas!
@@n0k0m3 exp : R -> R is not invertible at all, for example exp^-1(-2) is not defined. On the other hand, exp : R -> (0,infinity) is bijective, and thus invertible, notably with inverse ln : (0,infinity) -> R. A map being bijective is equivalent to it being invertible.
@@asdfasdfasdf1218 That is a byproduct. Potato, potahto.
Having not studied maths proper, and struggled with identifying errors in my cognition and proving basic counting, this is a beautiful day as I have a starting point for long awaited knowledge. Thank you
i've never had that formula explained to me in the context of sets, so seeing it in this light is pretty interesting.
It is a formula I think most people would just derive by intuition, perhaps with the occasional omission of the '+1' though. No one with even a surface level of maths would ever have to actually memorize that formula.
@@dekippiesipNo one with even a surface level understanding of maths thinks that intuition alone is enough to validate solutions, which is what the video is talking about.
@@dekippiesip I think that a lot of what we might call 'intuition' in maths is actually application of bijections/set theory without having been formally taught this. It's hard to come up with an example where this isn't true!
@CosmoVibe true, but still, people and even some freaking animals understand that 1+1 = 2 without any form of formal proof. My point was that the formula derived here almost falls into that category of easyness.
@Alex Gibson yeah sure. If you ask anyone weather a theater has as many chairs as people even toddlers will immediately say 'no' if they see empty chaits. Set theory is very deeply engrained in our intuition.
Doesn't mean our intuition always tells us the truth, as the banach tarski paradox clearly shows. But it does guide us correctly in lots of other sutuations.
I have dyscalculia, it's basically like dyslexia with numbers. I've struggled with math my whole life, because I get stuck on counting and basic operations, but I can follow formulas and solve problems just fine. It's just that I don't transcribe numbers correctly, and they appear to "change" in front of me.
Regardless, because of this issue, I fiercely and repetitively check my counts and redo counts. And this familiarity means that I wasn't very surprised by what this video described, despite my weakness in math.
In an odd way, my dyscalculia has forced a familiarity with counting concepts that it appears most people need to be taught.
I find that rather interesting
Are you full of crap?
You don't have any issue with numbers except that your brain rejects meaningless numbers.
@@imonkai5210That's not how dyscalculia works, and numbers aren't meaningless.
I’m not a mathematician and I approve this message because I can actually follow. Thank you!
Bijections was one of the more beautiful concepts in my combinatorics course in college. Your explanations are very clear and very well motivated.
“Focused, guided practice.” Straight wisdom for so many things in life.
Yes. I don't remember when, but I learned that at some time in my formal education because as soon as you reason about non-finite sets, you need this. The most famous case is probably Cantor's diagonal lemma that's used to show there are more real than natural numbers.
It also lets you understand highly counterintuitive but fundamental things, like how there are as many rational numbers as integers.
@@Oneiroclast Except there aren't… It's what OP is saying. There're literally more numbers between 0 and 1 than there are integers (which include all natural numbers too). That's why the rationals are uncountably infinite but the integers are countably infinite and uncountably infinite > countably infinite.
@Louis Robitaille Rationals are countably infinite, reals are uncountable. There's a bijection between rationals and natural numbers, make a list that consists of every positive rational number A/B where A+B = 1 in ascending order, then every rational number A/B where A+B=2, and so on, skipping any number equivalent to one that is already on the list. If you want to include negatives, just follow each number by its negative counterpart. Now you have a list where every rational number is the nth on the list, and every natural number n corresponds to a rational number, proving they're the same cardinality.
@@louisrobitaille5810No. The *real numbers* are uncountably infinite. This is what OP said. OP said nothing about the _rational numbers._ The _rational numbers_ are countably infinite, and constructing a bijection between the natural numbers and the _rational numbers_ is very straightforward.
@@OneiroclastThe way to make it intuitive is to realize that if we want to classify sets solely in terms of how they are equivalent with respect to invertible functions (or as a category-theoretician would put it, in terms of isomorphism classes, which are the cardinality classes), which later in your education, becomes a rather natural thing to want to do, then you will find that, just as there are multiple classes of finite sets, there are also multiple classes of infinite sets, and these classes happen to just be different sizes.
I've not watched the video yet but big ups for using kapustin music in that little opening, so incredibly basedd
This also reminded me of how foundational Set Theory is.
It slightly buged me that you didn't explicitly explained bijection, but watching till the end shows you explained it implicitly, which is a different way of explaining, but still valid!
I'd argue the undercounting vs overcounting example was it (bi if sur and in). This video was quite unrigorous though. It was not designed for a mathematical audience.
At 3:40 it's said "it is *NEVER* enough to check for *only* under counting or overcounting, whereas, at 3:05 it's given a example where it is enough to check for under counting only!
Checking for mistakes doesn't imply that you will find a mistake. Regardless of whether or not there is a mistake, you still have to check.
I love the technique of manipulating sequences to derive a general formula for any sequence. It's a very powerful technique that could help a lot, if only it was taught more.
Bijections and the overcounting/undercounting segment reminded me of something I've wondered in the past: when I balance my checkbook, if I can't reconcile my ending balance with my checkbook, I have to go back and recheck everything. However, when I get the balances to match on the first try, I never go back and double check my arithmetic, though I've wondered why that is so. Now I know that I should!
I waste time watching this
I sort of learned this, but never had a formal name for it when we learned counting problems in math class
A concise video that carries so much invaluable information presented in a comprehensible manner. That is perfection!
No, it's designed specifically to make people with acuity and neurological disorders literally ill to the point of vomiting.
06:20 blew my mind bro what a great way to visualize a formula. This is the stuff they need to teach in high school algebra.
Any video I find that emphasizes problem solving over all else is a video I am grateful for stumbling upon.
Seemed trivial until I saw the demonstration of 'to count how many terms are in a sequence, biject until they're just the natural numbers' and then I was like HMM, that's cool
Well, there are cases where you can't get to "just the natural numbers", such as "how many real numbers are there" ... but that is of course part of the conclusion.
Very cool! I thought you were going to go into different infinities, then I thought it was going to be arithmetic and geometric formulas, but you surprised me with this technique I've never seen before.
I'll be saving this video for sure!
I love how they were like, formulas are so messy! With bijections, you don't even need formulas.
It's real easy, all you gotta do is recreate the same formula using your head!
As a student this was something that really surprised me. When you understand biyective applications you notice them everywhere in math
Wow, this was delivered excellently, very impressive, especially considering this is a small channel. I was very surprised to see this channel to be small. Great work and i hope you keep it up!
How are you a "Rep"?
I so hate it and love it when something hasn't made sense for 10+ years and now seems obvious. The "memorize the formula" way of teaching is so common, learning how to think so much more powerful.
I learned this as a small child as part of the basis of arithmetic, though they didn't use the term "bijection"--I think they used "one-to-one correspondence" though technically what was meant was one-to-one and onto. Probably it was because I grew up in the aftermath of the New Math of the 1960s, which was very set-theory-oriented.
I hope you make more videos, this is an excellent style YT needs more of.
When you cut up a donut and you only cut to the middle in each cut, you get as many pieces as you made cuts. When you cut up a sausage, you get one more piece than you made cuts. It's as if you cut the donut first and laid it out straight, then went on to cut off one new piece per cut. That's one way to visualize the difference of 1.
You cut a bridge into two parts? You need three bearings. You want to cut a log into five segments? Make four marks. You put 10 rivets around a water tank? Divide the circumference by 10.
Woah, I have never thought this before.
Lovely video, very well explained. Thank you for the lesson.
Massively underrated channel
The fast sum of 1..100 made me understand counting and reducing sets. Very nice video
Reminds me of my days as a cricket rancher in the vast plains of Eastern Delaware. We used to count the legs and divide by six. I remember one old field hand, guy by the name of Squinty McClintock - old Squinty, he never could tell the difference between legs and antennas so we had to tell him to divide by eight.
😂
Good video. I look forward to your other videos. Subscribed. Thanks. Cheers.
After such N excellent explanation of a concept i already knew, i liked and smashed the notification bell. Great job man.
I striped parking lots for years and when you need to determine how many parking spaces will fit an area, you can't just make them 8' wide and whatever left over. We tried at first to guess the spacing but after seeing the problem differently we decided to break the total width of the parking area down into inches instead of feet. So easy after that.
Among the videos explaining math concepts, this is one of the most beautiful I have ever seen. It has it all: short, clear, exciting, explaining a fundamental concept, and with a practical example that blows your mind. Super fantastic!! 🤗
Amen. And his nice voice doesn't hurt either.
I didn't realise i took bijections for granted all these days. I would refrain from solving combinatorial problems using bijections from one sets to others thinking it was too abstract. But it seems more fun than i realised. Cool video
So that’s how Georg Cantor showed that there are infinities of different sizes, e.g., the set of real numbers and the set of natural numbers. It’s not possible to form a bijection between them.
Cantor wanted to count infinite sets. To do this he formalized the concept of counting as a bijection onto the natural numbers. He then wanted to know if there was any infinite set the natural numbers couldn’t count. There was of course and the best example is R.
Cantor used binary numbers. He had a set, T of n infinite binary strings, s.
T = {s1,s2,s3...,sn}.
s1 = (0,0,...)
s2 = (1,1,...)
s3 = (1,0,...)
etc.
Cantor found that if we write n of these arbitrary sequences, one can always construct another unique sequence.
This happens by taking the diagonal numbers (1st position of s1, 2nd pos. of s2), inverting them and making a new infinite list.
If T were countable one could list all its elements {s1,s2...sn}. But as we showed we can make a new element from this list with the diagonal complementary algorithm, let’s call it sd. sd belongs to T but is not in the list, which is a contradiction. Therefore, T is uncountable.
And if any set X is countable this means that there is an injective function between X and the set of natural numbers.
This is dope. Ngl, at first I was annoyed, because it took a while of listening to things I already understand to realize you were saying it in ways I could have understood well before I understood them. Math is hard. Teaching math is so much harder, and I would argue, so much more important.
This is such a nice video. The topic is not too difficult, yet very useful if the presented methods not only applied, but studied, and the music makes this learning experience a calming and pleasant one.
I just think of the 7 as a section of fence and the count as fence post. You always need sections of fence + 1 number of fence post. On a single lined fence of coarse.
Thanks for bringing complexity to simplicity...
And making clear sense of bijection..
I needed this video during my Discrete Programming course 6 years ago... those proofs were always an unintuitive nightmare
I wish you did some less trivial examples, I feel like I didn't really come away with any understanding of how this perspective (key word, since the arithmetic sequence formula can be found easily via the same argument without even thinking about bijections) is helpful for solving very hard counting problems. I also didn't feel like I learned a whole lot about how to check whether or not I over or undercounted in a counting problem
Thanks, this is excellent feedback that I will take into account.
I will be visiting a lot more counting concepts in future videos which will apply this idea.
I've never heard of the term "bijection," but I know this concept as "one-to-one correspondence." It's one of the earliest things we watch for teaching our kids.
Reminds me of "Another Roof" and his series on defining what numbers are.
Another Roof is a fantastic channel!
loved every second of this video. especially at the end. because before i saw the end i said this to my friend and i've been saying stuff like that for years. the conclusion portion that is... i'm subbed. can't wait to see more!!!
this is such a high-quality video. keep em coming man!
I dissociated from school and kept the bare min gpa in order to stay eligible for sports. This is my instinctive method. Emphasis on memorization as the primary metric for intellect is not the vibe. This video is the vibe.
Very well explained
"There are two types of mistakes that can be made while counting"
There are apricot many circles on screen.
_There are three types of mistakes you can make while counting_
This is so cool!!!!! The whole “should I add one or not” issue always confused me.
this is the kind of stuff that seems frivolous and petty at first and then you realise how essential it is in proof
As a programmer; that is one of the most common errors: "ObO" errors; "Off By One" errors.
As a platonist mathematician holding to the intangibility of numbers existing only as symbols assigned to tangible objects, i put forth that the "mistakes" in Ch 2 are merely a sloppy assignment of those symbols to the given set of objects. 🤓🤭
Fun vid! 👊🏼
so clearly structured and applicable! loved it thanks~
awesome video, a few days after a first watched it, my dad was telling me how the interval (0,100) must have more real numbers in it than (0,1). i remembered this video and came up with the bijection f x -> 100x
I just subscribed, I'm not sure of your limitations, but I'm positive that if you post more your channel will do well. Keep up the good work.
The use of Computer Modern font makes this so "sexy" :) Very subtle, I love it !
I figured out another way to do this. If you minus 30 from the total number 849 you get a number that when divided bt 7 gets you 117.
The reason you would minus 30 is because when you convert 37 into 0 for your count start..you are representing zero with your first set of 7..so we keep that 7 for that zero start.. and only minus 30 from 849... not 37... to get to the start of the count. Then divide by 7 because that's how many numbers apart these appear to be.
The axiomatic theory of sets looks nice in the beginning. As you progress toward Russell antinomies and paradoxes, and eventually toward the Gödel incompleteness theorem, you realise the need for the same amount of faith as of the ability of reason...
At first I was not getting what you were saying. Then my granddaughter came to mind, who is 3 yrs old. When she counts something, she either does too many or too few. Of course, she's little. But now I understand what is happening when I am counting. I understand now what it is I'm actually doing and what my granddaughter will do and well some day.
Got this video recommended by the youtube algorithm, quite interesting!
I think it would be great if at the end of the video, where you make the final recomendation of practicing this, you left a few exercises where this can be practiced.
As someone who's watching you for the first time and hasn't been doing any deliberate math problem solving since high school, I am not sure where and how I would further practice this.
Please consider including a few problems for viewers when you recommend practicing/applying something, to take away and practice.
Also, for extra points, leave some keywords that can be used to find more relevant exercises/problems.
Thanks for the feedback, I'll try my best to implement this at the next opportunity!
mind blown. I wish I had you as my math professor in college.
I've been getting a lot of similar comments, so I decided to compile some of most frequently asked questions.
Q: You tricked me! You corrected for undercounting and it was correct. Why did you say we fell for a trap?
A: I probably could've been a bit more clear, but the key concept i wanted to highlight is that you must actively remember to check BOTH undercounting and overcounting. This is a matter of building habits to actively do this every time you count. In the example with 5 circles, it is very obvious by simple observation, but this is definitely not generally the case. To see some examples where this can be fatal if not considered properly, check out my follow-up video: ruclips.net/video/LUVKuyfpe2I/видео.html
Q: You say that using bijections, you don't need to memorize the formula, but then you used the formula anyways. Why don't I just memorize the formula?
A: Suppose you didn't know the formula. If you just played around with your bijections, you can simultaneously derive the formula and prove that it is correct. If you just memorized the formula, you didn't guarantee that it is correct. In addition, the formula is very limited in application. To see how bijections can be more powerful, try using them to derive the number of terms in a geometric sequence.
Q: I don't need a bijection, I can just look and see there are 5 circles!
A: This video is about mathematical rigor and not human psychology and intuition. If I asked you to prove to me that there are indeed 5 circles, you are now forced to use a bijection to do so.
Q: Why can't you count by simply weighing the objects and dividing?
A: Weighing the total and dividing is still forming a bijection between weight ranges and each object. For example, suppose each marble weighs 5 grams. A weight of 15 grams means there are 3 marbles because there is a bijection between grams 0-5 with the first marble, grams 5-10 with the second marble, and grams 10-15 with the third marble.
Q: This video is boring and useless.
A: I'm sorry you feel that way. I cannot make math interesting for everyone, and the purpose of this video is not about sensationalization or mind-shattering epiphanies, but to fill what I believe is a gap in the way we teach math, by building foundations and good habits. If you have an open mind, perhaps you could give this video a try and maybe it will convince you otherwise: ruclips.net/video/LUVKuyfpe2I/видео.html
Q: I don't need to learn counting, I already know how to count.
A: Counting problems in math are deceptively tricky. Here's a few simple examples: ruclips.net/video/LUVKuyfpe2I/видео.html
If on the other hand, you'd like to understand why one should care about counting problems, they are applicable to a wide range of real world applications, not just in specialized industries, but in day-to-day experiences of most people, which is so rich that it should be the subject of its own video.
This is an astonishing and beautiful video! It catches by its powerful simplicity on presenting more complex concepts. Having only watched this video and your previous one, I can say that your work is of great relevance on the spreading of math as something to like, enjoy and even love. I will never think on counting problems the same way. Thank you so much for the enlightenment and, please, keep doing it!
I couldn't help to wonder in what other case I could apply what I've just learned. I was working on a specific example you gave in the video about the sequence that doesn't behave like a arithmetic sequence: 1, 4, 9, 16, 25, 36, ..., 900. It's relatively easy to see that the pattern follows another sequence (this time an arithmetic one). I couldn't find the number of terms using the concept of bijections, but I was able to find it by constructing a general rule of the n'th term by combining the sequence itself with the sequence from it's pattern. I wonder if there's an easy way to do it as you did in the video...
Anyways, congratulations for the amazing video! Hope to see you again soon.
The easy way is to pair each number with its square root. This will immediately give you the list of counting numbers in one bijection!
Thank you, I wish teachers would be more like you
Intuitively absolutely fantastic!! Thank you, God bless you, keep going...
The thing about over- or undercounting is that you typically don't know which item is being counted twice or skipped, so the only way to fix an error is to do a fresh count. There is usually no way to "check for" over- or under-counting.
That example was kind of nonsense, in the example there was no under counting as you can't see "lines of thought" to begin with when checking the answer. All you see is 5 dots and the answer was 6 to check against.
Hello! If you're interested in an example application of this idea, where you can actually check for overcounting and undercounting, please check out my previous video: ruclips.net/video/3B-D3w292TI/видео.html
Counting by comparing a sequence with another sequence is actually deep in our nature because that's how children count when they need to compare how much marbles they have for example. What we would do is just count them normally and get a number. But children funnily understand this important mathematical topic quite well. (Also important for Cantor's proof on countable/uncountable infinities)
Very beautiful introduction to fundamental concepts of set theory.
Very informative video.
That's a new thing i learned today : bijection.
Really good explanation.
Even found a way to remember arithmetic formula without revision.
You gained my sub man. Great work.
"The right mentality and habits.."
I liked that line the most.
This is awesome 👌
Thanks for sharing!
This is Great! It reminds me of 3blue1brown, and I have no higher praise for a math video.
You may have heard of the advise: "Don't give up your day job." My advise to you is to "Do give up some of your 'other' work, and devote the time to doing more of these."
The turning of complex problems into simpler ones is a great talent. Explaining HOW to turn complex into simpler is the mark of a truly superior teacher. DON'T STOP! (I hope that you're young enough to be doing this for many years.)
Thanks so much for the positive encouragement and the generous tip! Words cannot express how much it means to me. You give me the motivation to create content like this, and the confirmation and confidence that I'm headed in the right direction. I will try my best to produce as much content as I possibly can at the highest possible quality I can!
In a programming context, I've heard omitting the "+1" term called a fencepost error. Its name is derived from the statement of a problem which goes something like, you're putting up a fence which is 20 meters long with a fencepost every 2 meters. You think, simple, divide 20 by 2 to come up with 10. But doing it practically, this gets you a fence only 18 meters long, because you can think of it as missing a fencepost on one end or the other.
Similarly in your example, subtracting 37 off each member of your list gets you 0 for the first term...but we don't count the first thing as the zeroeth thing, it's the first thing, or cardinally one. So each member has to have that +1 term.
Very nice explaination!
THIS IS USEFUL! THANKS!
amazing! tysm for this!!! perfection
I love this video. Upvoted & subscribed!
Wonderful classic counting sequence so nicely
simple concept but a beautiful exposition
needed this video before taking combinatorics course lol... awesome video
Thanks for this zen moment of learning man
What a video!!!!!this kind of videos really motivates me to study math,what a beauty.
This is very helpful!😊
gonna be honest here. i sometimes use images to count.
for example 5 apples. if its in the most common group image i can just glance and know it's 5. same for groups of 3 objects. you can just glance and say, '3'. not even individually count them.
but apart from that, this video is AMAZING!!! i learned a bunch!!!
Great concepts and content.
Excelent explanations!
Great video as always
I love these sorts of math videos, one's that even a layman like myself can understand.
The one-to-one correspondence between all members of one set with all members of another set is how Russell defines the concept of number in "Principia Mathematics"
This is amazing!
I used to work in sheet metal fabrication. When I would shear blanks of sheet metal and stack hundreds of them on a pallet, I would use a quick and very safe trick. The sheet metal was 1 mm thick and I had a metric steel ruler with me. I would hold the ruler on the side of the stack, with the 0 mark aligned with the bottom of the stack. I would then slide my vision along the height of the stack to watch for an offset between the ruler and the stack. Since the metal was never exactly 1 mm thick and it would have dust and things in between, I would always have to move the ruler very slowly to keep it aligned with the metal sheets as I went along. At the end I would just read the number off the ruler, without having to deal with numbers other than that. It would work brilliantly and quickly for 1mm sheet metal, for sheets that were 2mm thick I would have to divide by two and for uneven thicknesses it would not work unfortunately. If the stack wasn't too high, you could still get away with measuring the height and dividing by the thickness.
I love watching videos that explain something I already do/know, only to explain it in a completely different way, to show an application that I never thought of before, or to explain it much more thoroughly than anywhere else 😁. I already instinctively knew the 1-to-1 thing, [#1], but the generalisation of bijections is really interesting 😋.
[#1] which is why I understand how complicated it is to define what is "1" thing (or just counting in general) as if I had to explain it to an alien because "pointing at something" is basically making a bijection between words and objects/concepts
You earned yourself a subscriber!
Love the background music
Bijections can also be used to demonstrate that there are the same amount of numbers in N, I and Q but not R
You made me finally understand what "numbers" are - seems "numbers" are "bijection classes" =D
This is true for the natural numbers, the counting numbers, but other numbers, like negative numbers and real numbers, aren't defined in this way!
Such a high quality and just 7.4k subs?
Wow!