Which is bigger?: Set cardinality, injective functions, and bijections

academics computer science math
By Tom

Screen Shot 2019-09-23 at 2.19.05 PMComparing finite set sizes, or cardinalities, is one of the first things we learn how to do in math. From a young age, we can answer questions like “Do you see more dogs or cats?” Your reasoning might sound like this: There are four dogs and two cats, and four is more than two, so there are more dogs than cats. In other words, the set of dogs is larger than the set of cats; the cardinality of the dog set is greater than the cardinality of the cat set.

This reasoning works perfectly when we are comparing finite set cardinalities, but the situation is murkier when we are comparing infinite sets. Are there more integers or rational numbers? More rational numbers or real numbers? Are all infinitely large sets the same “size”? To answer these questions, we need a way to compare cardinalities without relying on integer counts like “two” and “four.

A different way to compare set sizes is to “pair up” elements of one set with elements of the other. Returning to cats and dogs, if we pair each cat with a unique dog and find that there are “leftover” dogs, we can conclude that there are more dogs than cats.

Screen Shot 2019-09-16 at 1.41.04 PM

Another way to describe “pairing up” is to say that we are defining a function from cats to dogs. In a function, each cat is associated with one dog, as indicated by arrows. The figure on the right below is not a function because the first cat is associated with more than one dog.

Screen Shot 2019-09-16 at 1.41.52 PM

If a function associates each input with a unique output, we call that function injective.

Screen Shot 2019-09-16 at 1.42.58 PM

Since we have found an injective function from cats to dogs, we can say that the cardinality of the cat set is less than or equal to the cardinality of the dog set. Take a moment to convince yourself that this makes sense.

In formal math notation, we might write: if f : A → B is injective, then |A| ≤ |B|. In other words, if there is some injective function f that maps elements of the set A to elements of the set B, then the cardinality of A is less than or equal to the cardinality of B.

Let’s add two more cats to our running example and define a new injective function from cats to dogs.

Screen Shot 2019-09-16 at 1.43.51 PM

Now we can also define an injective function from dogs to cats.

Screen Shot 2019-09-16 at 1.44.47 PM

We see that each dog is associated with exactly one cat, and each cat with one dog.

Since we have found an injective function from cats to dogs, and an injective function from dogs to cats, we can say that the cardinality of the cat set is equal to the cardinality of the dog set. We might also say that the two sets are in bijection. In formal math notation, we would write: if f : A → B is injective, and g : B → A is injective, then |A| = |B|.

Now we have a recipe for comparing the cardinalities of any two sets. If we can find an injection from one to the other, we know that the former is less than or equal; if we can find another injection in the opposite direction, we have a bijection, and we know that the cardinalities are equal.

The important and exciting part about this recipe is that we can just as well apply it to infinite sets as we have to finite sets. For example, we can ask: are there strictly more integers than natural numbers? The natural numbers (1, 2, 3…) are a subset of the integers (..., -2, -1, 0, 1, 2, …), so it is tempting to guess that the answer is yes. But in fact, we can define an injective function from the natural numbers to the integers by mapping odd numbers to negative integers (1 → -1, 3 → -2, 5 → -3, …) and even numbers to positive ones (2 → 0, 4 → 1, 6 → 2). From the existence of this injective function, we conclude that the sets are in bijection; they are the same cardinality after all.

A surprisingly large number of familiar infinite sets turn out to have the same cardinality. (Can you compare the natural numbers and the rationals (fractions)?) This begs the question: are any infinite sets strictly larger than any others? In the late 19th century, a German mathematician named George Cantor rocked the math world by proving that yes, there are strictly larger infinite sets. One example is the set of real numbers (infinite decimals). Cantor’s Theorem builds on the notions of set cardinality, injective functions, and bijections that we explored in this post, and has profound implications for math and computer science.

Comments

topicTopics
academics study skills MCAT medical school admissions SAT expository writing college admissions English MD/PhD admissions strategy writing LSAT GMAT GRE physics chemistry math biology graduate admissions academic advice ACT interview prep law school admissions test anxiety language learning premed MBA admissions career advice personal statements homework help AP exams creative writing MD study schedules test prep computer science Common Application summer activities history mathematics philosophy organic chemistry secondary applications economics supplements research 1L PSAT admissions coaching grammar law psychology statistics & probability legal studies ESL CARS SSAT covid-19 dental admissions logic games reading comprehension engineering USMLE calculus PhD admissions Spanish mentorship parents Latin biochemistry case coaching verbal reasoning DAT English literature STEM excel medical school political science skills AMCAS French Linguistics MBA coursework Tutoring Approaches academic integrity chinese letters of recommendation Anki DO Social Advocacy admissions advice algebra art history artificial intelligence astrophysics business cell biology classics diversity statement gap year genetics geometry kinematics linear algebra mechanical engineering mental health presentations quantitative reasoning study abroad technical interviews time management work and activities 2L DMD IB exams ISEE MD/PhD programs Sentence Correction adjusting to college algorithms amino acids analysis essay athletics business skills careers cold emails data science dental school finance first generation student functions graphing information sessions international students internships logic networking poetry resume revising science social sciences software engineering tech industry trigonometry writer's block 3L AAMC Academic Interest EMT FlexMed Fourier Series Greek Health Professional Shortage Area Italian Lagrange multipliers London MD vs PhD MMI Montessori National Health Service Corps Pythagorean Theorem Python Shakespeare Step 2 TMDSAS Taylor Series Truss Analysis Zoom acids and bases active learning architecture argumentative writing art art and design schools art portfolios bacteriology bibliographies biomedicine brain teaser campus visits cantonese capacitors capital markets central limit theorem centrifugal force chemical engineering chess chromatography class participation climate change clinical experience community service constitutional law consulting cover letters curriculum dementia demonstrated interest dimensional analysis distance learning econometrics electric engineering electricity and magnetism escape velocity evolution executive function freewriting genomics harmonics health policy history of medicine history of science hybrid vehicles hydrophobic effect ideal gas law immunology induction infinite institutional actions integrated reasoning intermolecular forces intern investing investment banking lab reports linear maps mandarin chinese matrices mba medical physics meiosis microeconomics mitosis mnemonics music music theory nervous system neurology neuroscience object-oriented programming office hours operating systems

Related Content