The Most Important Counting Concept You’ve (Probably) Never Heard Of
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
Пікірлер: 810
30 years of programming using zero-indexed arrays makes the '+1' concept second nature. ;-)
@veto_5762
Жыл бұрын
Also makes watching someone starting to count a list from one feel strangely wrong
@dirkreisig4465
Жыл бұрын
Second nature ok. But for the wrong reason, I think. Here the spaces between the numbers were counted.
@Josh-yr6my
Жыл бұрын
@@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.
@IqweoR
Жыл бұрын
@@Josh-yr6my exactly
@Dbsabzbzb
Жыл бұрын
@@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.
@Beesman88
Жыл бұрын
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.
@lawrencejob
Жыл бұрын
Was going to say, that’s not been true for a while!
@dojelnotmyrealname4018
Жыл бұрын
@@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.
@sumdumbmick
Жыл бұрын
because everyone is taught that counting starts at 1, because math teachers are idiots.
@paoloposo
Жыл бұрын
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.
@zhulimath
Жыл бұрын
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.
@asdfasdfasdf1218
Жыл бұрын
I thought it meant it was 2-way because they were invertible.
@zhulimath
Жыл бұрын
@@asdfasdfasdf1218 This is also true, it's just another way of viewing the same ideas!
@stevend285
Жыл бұрын
@@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.
@ellenmarch3095
Жыл бұрын
@@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.
@dekippiesip
Жыл бұрын
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.
@CosmoVibe
Жыл бұрын
@@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.
@edumaker-alexgibson
Жыл бұрын
@@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!
@dekippiesip
Жыл бұрын
@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.
@dekippiesip
Жыл бұрын
@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
@BlueBeeMCMLXI
Жыл бұрын
Are you full of crap?
@imonkai5210
Жыл бұрын
You don't have any issue with numbers except that your brain rejects meaningless numbers.
@angelmendez-rivera351
9 ай бұрын
@@imonkai5210That's not how dyscalculia works, and numbers aren't meaningless.
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!
@zhulimath
Жыл бұрын
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.
“Focused, guided practice.” Straight wisdom for so many things in life.
Bijections was one of the more beautiful concepts in my combinatorics course in college. Your explanations are very clear and very well motivated.
I’m not a mathematician and I approve this message because I can actually follow. Thank you!
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!
@ffc1a28c7
Жыл бұрын
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.
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!
@przemo3651
Жыл бұрын
I waste time watching this
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.
I've not watched the video yet but big ups for using kapustin music in that little opening, so incredibly basedd
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.
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.
@Oneiroclast
Жыл бұрын
It also lets you understand highly counterintuitive but fundamental things, like how there are as many rational numbers as integers.
@louisrobitaille5810
Жыл бұрын
@@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.
@Oneiroclast
Жыл бұрын
@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.
@angelmendez-rivera351
9 ай бұрын
@@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.
@angelmendez-rivera351
9 ай бұрын
@@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 sort of learned this, but never had a formal name for it when we learned counting problems in math class
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!
Any video I find that emphasizes problem solving over all else is a video I am grateful for stumbling upon.
A concise video that carries so much invaluable information presented in a comprehensible manner. That is perfection!
@kell_checks_in
Жыл бұрын
No, it's designed specifically to make people with acuity and neurological disorders literally ill to the point of vomiting.
I hope you make more videos, this is an excellent style YT needs more of.
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!
@BlueBeeMCMLXI
Жыл бұрын
How are you a "Rep"?
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.
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
@KaiHenningsen
Жыл бұрын
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.
As a student this was something that really surprised me. When you understand biyective applications you notice them everywhere in math
Lovely video, very well explained. Thank you for the lesson. Massively underrated channel
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.
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!! 🤗
@Ritercrazy
Жыл бұрын
Amen. And his nice voice doesn't hurt either.
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 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!
After such N excellent explanation of a concept i already knew, i liked and smashed the notification bell. Great job man.
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.
@syed--2023
Жыл бұрын
Woah, I have never thought this before.
The fast sum of 1..100 made me understand counting and reducing sets. Very nice video
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
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.
@zhulimath
Жыл бұрын
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!
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...
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! 👊🏼
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.
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!
Thanks for bringing complexity to simplicity... And making clear sense of bijection..
so clearly structured and applicable! loved it thanks~
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.
@travelswithted
Жыл бұрын
😂
I needed this video during my Discrete Programming course 6 years ago... those proofs were always an unintuitive nightmare
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.
Very beautiful introduction to fundamental concepts of set theory.
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.
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.
Intuitively absolutely fantastic!! Thank you, God bless you, keep going...
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.
@zhulimath
Жыл бұрын
Thanks for the feedback, I'll try my best to implement this at the next opportunity!
Good video. I look forward to your other videos. Subscribed. Thanks. Cheers.
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
@zhulimath
Жыл бұрын
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 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.
This is awesome 👌 Thanks for sharing!
amazing! tysm for this!!! perfection
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
Thank you, I wish teachers would be more like you
You gained my sub man. Great work.
mind blown. I wish I had you as my math professor in college.
This is so cool!!!!! The whole “should I add one or not” issue always confused me.
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.
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 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.)
@zhulimath
Жыл бұрын
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!
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.
@TheUndeadFish1
Жыл бұрын
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.
@zhulimath
Жыл бұрын
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: kzread.info/dash/bejne/ZXZhppWwYpyYhKw.html
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.
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.
Great concepts and content.
Wonderful classic counting sequence so nicely
Thanks for this zen moment of learning man
"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_
I love this video. Upvoted & subscribed!
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.
Very well explained
What a video!!!!!this kind of videos really motivates me to study math,what a beauty.
needed this video before taking combinatorics course lol... awesome video
The use of Computer Modern font makes this so "sexy" :) Very subtle, I love it !
THIS IS USEFUL! THANKS!
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!!!
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.
@aaAa-vq1bd
Жыл бұрын
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 very helpful!😊
Reminds me of "Another Roof" and his series on defining what numbers are.
@zhulimath
Жыл бұрын
Another Roof is a fantastic channel!
Great video as always
As a programmer; that is one of the most common errors: "ObO" errors; "Off By One" errors.
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)
Excelent explanations!
A collection of heterogeneous items (numbers, strings, text) listed in a contiguous set of rows in Excel also represents a natural bijection between them and the row labels. That is the scenario I usually use in teaching students the rationale for the '+1'.
This is amazing!
"The right mentality and habits.." I liked that line the most.
Thank you. Practical explanations of technical math concepts are very valuable. I learned some new insights from your explanation. I wonder if it might be more precise to say bijections define 'sameness of count'. I usually think of bijections as maintaining information content (no gain or loss of info).
great video dude =] subbed
super clear video. in undergrad combinatorics was one of my favorite math class haha
this is the kind of stuff that seems frivolous and petty at first and then you realise how essential it is in proof
Nice video, thanks :)
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!
5:14 I've started studying Math as a hobby, and came up with an alternative solution (so I don't know if this is the standard solution or not, or even if it's actually correct or just a coincidence that I came up with the right end result): We can write down the numbers in a single column: first row = 37, second row = 37+1*7=44 (because we add 7 to 37 once), third row = 37+2*7=51 (because we add 7 to 37 twice), fourth row = 37+3*7=58 (because we add 7 to 37 three times), (...) last row = 37+z*7=849 (because we add 7 to 37 "z" amount of times). Solving the equation 37+z*7=849, we get (849-37)/7= z = 116. Which means that after the first row (where 37 is located), there are 116 additional rows, so in total there are 117 rows. Because every row = one number in the list, this means that there are 117 numbers in this list. Is this also a correct way of solving it? Thanks.
@zhulimath
Жыл бұрын
Yep, this is also a way of solving the problem! Most importantly, we can verify that this solution is correct by constructing our bijections in the reverse direction, starting with the list of counting numbers and working towards the list in the stated problem!
I love these sorts of math videos, one's that even a layman like myself can understand.
Really good video!
Banger video fr 💯