Countable and Uncountable Infinity

This training explores countable and uncountable infinity, helping learners distinguish between different sizes of infinite sets and understand their mathematical significance.

A digital instructor presents all 14 pages. Hold “Ask” at any point and ask out loud — the answer comes from this course. No sign-up needed.

28 minFree to watchDownloads

What you’ll learn

01Sizes of Infinity: Countable and UncountableWelcome. I'm glad you're here. Today we're going to explore one of the strangest and most beautiful ideas in all of mathematics. Some infinities are bigger than others. I know that sounds impossible, so let's slow down and unpack it together. Our goal is simple. By the end, you'll understand what it means to compare the sizes of infinite sets. Here's our roadmap. We'll start with matching, the universal tool for comparing sizes. Then we'll visit Hilbert's Hotel, a thought experiment about infinite rooms. After that, we'll meet Cantor's diagonal argument, look at the continuum, climb a tower of infinities, and finally touch on the continuum hypothesis. The core example is this. The natural numbers, one, two, three, and so on, can be listed. The real numbers, every point on a number line, cannot. Cantor showed this in eighteen seventy four, and the famous diagonal argument came in eighteen ninety one. No formal proofs today. Just concrete examples, tables, and plain language reasoning. Let's begin by asking a simple question. How do you count without counting?doi.org mathshistory.st-andrews.ac.uk jamesrmeyer.com+22 min
02Counting Without Counting: Matching as the Universal ToolLet's start with the tool that makes all of this possible. A bijection is a pairing. Every element of one set gets matched with exactly one element of another set, with nothing left over on either side. Think about a theater. You don't need to count the seats and you don't need to count the people. If every seat is taken, and every person is sitting, you already know the two groups are the same size. Same with shoes and shoelaces. Now here's the definition. Two sets have the same cardinality exactly when a bijection exists between them. That's it. Notice what we did not say. We did not say same number. In fact, matching, not listing, is the right definition, because it extends cleanly to infinite sets. And here's the early warning. For finite sets, a proper subset is always smaller. Hold onto that intuition loosely. Because once infinity enters, that rule breaks, and it breaks beautifully. Next, let's see what happens when everything can be listed. Countably Infinite: When Everything Can Be Listed.encyclopediaofmath.org mathematics.interactiveatlas.org en.wikipedia.org+22 min
03Countably Infinite: When Everything Can Be ListedSo we have a way to measure infinity. Now let's name the first size. A set is countably infinite when its elements can be listed, and matched one to one with the natural numbers. In plain terms, you can give every element a position: first, second, third, and onward, with nothing skipped. Here is the surprise. The integers are countable. We can list them as zero, one, negative one, two, negative two, and so on, so every whole number gets a spot. The positive fractions are countable too. Picture a grid with numerators across and denominators down, then sweep the diagonals. The fractions are dense, meaning between any two there is another. And yet all of them can still be listed. That density does not break the list. Now let's see what an infinite list can do for a busy hotel.math.uh.edu strauss.hosted.uark.edu math.colorado.edu+21 min
04Hilbert's Hotel: Infinity Always Has RoomNow let's step into a strange hotel. It has rooms numbered one, two, three, and so on, forever. Every room is occupied. Yet the manager promises there is always room. Here is the trick. When one new guest arrives, every current guest moves from room n to room n plus one. Room one is now free, and nobody lost a room. Now imagine infinitely many new guests. Move each current guest to room two times n. All the even rooms are filled, and every odd room is open. What about countably many buses, each carrying countably many guests? Number each guest by a pair: bus and seat. Then sweep through all those pairs in a diagonal list, and a countable union of countable sets is still countable. But here is the limit. If guests were indexed by every infinite sequence of zeros and ones, no such room assignment could ever fit them all. That collection is uncountable. Next, we will see the clever diagonal argument that proves it: Diagonalization: Building a Number That Escapes Any List.math.uh.edu strauss.hosted.uark.edu math.colorado.edu+22 min
05Diagonalization: Building a Number That Escapes Any ListNow let's see how Cantor actually builds a number that escapes any list. Start by assuming, just for the sake of argument, that every real number between zero and one is written in a list: r one, r two, r three, and so on. Each one is an infinite decimal. Now walk down the diagonal, and build a new number, r. Make its first digit different from the first digit of r one, its second digit different from the second digit of r two, and keep going. Then r differs from every listed number in at least one place, so it cannot be on the list. One small care: avoid using the digits zero and nine, so that the familiar ambiguity of zero point nine nine nine equals one point zero zero zero cannot create a hidden match. The takeaway is that no listing can be complete. And that is true, not just for this one attempt, but for any possible listing at all. Next, we'll see what this means for the real numbers as a whole, in The Reals Cannot Be Listed: The Uncountable Continuum.en.wikipedia.org dcproof.com whitman.edu+22 min
06The Reals Cannot Be Listed: The Uncountable ContinuumNow we reach the heart of the matter. The real numbers cannot be listed. There is no bijection, no perfect pairing, between the natural numbers and the reals. In other words, the reals are uncountable. The size of the naturals has a name, aleph-null, written with the Hebrew letter aleph and a small zero. The size of the reals is called the continuum, and it is strictly larger. So aleph-null is less than the continuum. Here is a surprise. A small interval between a and b, the entire number line, and even n-dimensional space all have the same cardinality, the continuum. Cantor proved this twice. His 1874 nested-interval proof and his 1891 diagonal argument reach the same conclusion by different routes. And many thin-looking sets share this size, including the irrationals, the transcendentals, and the Cantor set. That set is nowhere dense, yet as large as the whole line. Next, we build an endless tower of ever larger infinities.doi.org mathshistory.st-andrews.ac.uk jamesrmeyer.com+22 min
07An Endless Tower: Power Sets and Cantor's TheoremNow we go one level deeper. Take any set A, and a power set, the collection of all its subsets. Cantor's theorem says that power set is strictly larger than A. In symbols, the size of A is less than two raised to the size of A. Here is the diagonal idea. Pair each element a with a subset S of a. Then define D as the set of all elements a that are not inside their own paired subset. This D escapes every pairing, just as the diagonal number escaped every listed real. So there is no largest infinity. Aleph null, then two to the aleph null, then two to that, and the tower climbs forever. That is the beth numbers, a ladder of infinities. And two to the aleph null is exactly the continuum, the size of the real line. So infinity is not one destination. It is a whole hierarchy of sizes. Next, we look at cardinal arithmetic, when infinity plus infinity changes nothing.encyclopediaofmath.org mathematics.interactiveatlas.org en.wikipedia.org+22 min
08Cardinal Arithmetic: When Infinity Plus Infinity Changes NothingNow let's do some arithmetic with infinity. Remember Hilbert's Hotel? That's cardinal arithmetic in disguise. Aleph null plus aleph null equals aleph null. And aleph null times aleph null also equals aleph null. Adding or multiplying countable infinities gives you nothing new. But exponentiation is different. Raising two to the power aleph null gives a strictly larger infinity, and that is exactly what uncountability means. The continuum, the size of the real line, satisfies the same rule: c times c equals c. Two copies of the real line, or the whole plane, are no bigger than the line itself. Here's a striking example. All continuous functions from the reals to the reals come to only c many, but all functions, with no continuity required, form a larger set of size two to the c. And one final distinction worth keeping. The order type omega and the size aleph null describe the same set of natural numbers, but they answer different questions. One is about arrangement, the other about quantity. Next, is there anything in between? The Continuum Hypothesis.encyclopediaofmath.org mathematics.interactiveatlas.org en.wikipedia.org+22 min
09Is There Anything in Between? The Continuum HypothesisSo now the big question. Is there anything in between? Between the size of the counting numbers, aleph null, and the size of the real numbers, the continuum, which we write as two to the aleph null. The Continuum Hypothesis says no. Nothing in between. Equivalently, two to the aleph null equals aleph one, the very next infinity after aleph null. Cantor posed this in eighteen seventy eight. Hilbert made it problem number one in nineteen hundred. Then came two surprises. Gödel, in nineteen forty, built a tidy universe called L, where the hypothesis holds. So the standard axioms of set theory, ZFC, cannot disprove it. Cohen, in nineteen sixty three, invented forcing, which builds models where the hypothesis fails. So ZFC cannot prove it either. The verdict. The Continuum Hypothesis is independent of ZFC, just like the parallel postulate in geometry. You can choose either world, and both are consistent. Next, let us see why this matters, in a slide called Why It Matters: Computation, Logic, and the Real World.encyclopediaofmath.org mathematics.interactiveatlas.org en.wikipedia.org+22 min
10Why It Matters: Computation, Logic, and the Real WorldSo why does any of this matter outside of pure mathematics? Here is one striking reason. Programs, like proofs, can be written down as finite strings of text. So all possible programs can be listed, one, two, three. That means there are only countably many programs. But the functions from numbers to numbers form an uncountable set. Most functions, then, cannot be computed by any program at all. Turing's halting problem, from nineteen thirty-six, uses the same diagonal move in disguise. Gödel's incompleteness theorem leans on the same technique too. And a practical note: the floating-point numbers in your computer are just a countable sliver of the continuum. Discovering bigger infinities was a genuine mathematical discovery, not a trick. Next, let's look at common traps and quick exercises.1 min
11Common Traps and Quick ExercisesNow let's clear up some common traps, then try a few quick exercises. Trap one: infinity is not a number. Aleph null and c, the continuum, are sizes of sets, not values you can add or multiply. Trap two: not all infinite sets are the same size. The natural numbers and the real numbers are both infinite, but no bijection exists between them. Trap three: you can compare infinities. Bijections give a rigorous ordering, so some infinities really are bigger than others. Now the exercises. Are the finite subsets of the natural numbers countable? Yes. Group each subset by its largest element, and within each group there are only finitely many. Are the real algebraic numbers countable? Yes. Order polynomials by a height measure, then list their roots. Is the Cantor set uncountable? Yes. Each point has a base-three expansion using only zeros and twos, and swapping those digits for zeros and ones gives a bijection with the unit interval. So the pattern is always the same: find the bijection, or prove none can exist. Next, where set theory is today.doi.org mathshistory.st-andrews.ac.uk jamesrmeyer.com+22 min
12Where Set Theory Is TodaySo where does that leave set theory today? Here is the surprise: independence did not close the field. It opened it. Researchers now work with three big families of new axioms. Large cardinals, which say that very large infinities exist. Forcing axioms, which say the universe is rich and hard to change. And determinacy, which says certain infinite games always have a winner. But a key result, the Levy-Solovay theorem, tells us large cardinals alone cannot settle the continuum hypothesis. Think of it as a toolbox that cannot open one particular lock. So the frontier moves elsewhere: inner models, descriptive set theory, and a realm called HOD, the sets you can define using ordinals. Two competing visions, Ultimate L and Sealing, are now pushing the field forward. And this work reaches far beyond set theory, into topology, algebra, and even operator algebras. Now, let us step back and recap the core ideas: matching, listing, and diagonalization.2 min
13Recap: Matching, Listing, DiagonalizationLet's bring the pieces together. First, size means matching. Two sets are the same size when a bijection pairs every element, with nothing left over. Second, countably infinite sets can be listed: the natural numbers, the integers, the rationals, pairs, and finite strings all fit on one list. Third, diagonalization escapes any list. No matter how you list the reals, the diagonal builds a number that isn't on it, so the reals are uncountable, and aleph null is strictly less than the continuum. Fourth, power sets climb forever, from aleph null to two to the aleph null, and onward. There is no largest infinity. Fifth, the Continuum Hypothesis asks whether anything sits between aleph null and the continuum. Godel showed in nineteen forty that it's consistent with the standard axioms, and Cohen showed in nineteen sixty three that its negation is consistent too. So it's independent of ZFC. The takeaway is simple: every infinity can be outgrown. Next, let's open it up for questions and talk about where to go from here.encyclopediaofmath.org mathematics.interactiveatlas.org en.wikipedia.org+22 min
14Close: Q&A and Where to Go NextSo, before we close, let me leave you with two questions to sit with. Which surprised you more: that we could list all the rationals in a neat row, or that the reals refuse every such list? And does the independence of the continuum hypothesis, proven by Gödel and Cohen, change what we mean when we say there are as many reals as? Sit with those. If you want to go deeper, three doors open naturally. Set theory, where infinite sizes get names. Computability, where the same diagonal trick shows some problems can never be solved, like the halting problem. And real analysis, where uncountability becomes a working tool. You could also read Cantor's 1874 paper itself, and overviews of Gödel in 1940 and Cohen in 1963. The real takeaway is this. Matching, listing, and diagonalizing are simple moves that reach far beyond set theory. Thank you for thinking alongside me through all of this. Keep asking which list could hold everything, and which idea cannot fit. You now have the tools.doi.org mathshistory.st-andrews.ac.uk jamesrmeyer.com+22 min

Take the deck with you

Download this course as a file — free, no sign-up needed.

PDF handoutEvery slide page, ready to print or share.15 pages · 3.1 MBDownload
Narrated PowerPointThe deck that presents itself — every slide carries the digital human's narration video.15 pages · 12.8 MBDownload
PowerPoint slidesThe full deck as a .pptx — open it in PowerPoint, Keynote, or Google Slides.15 pages · 3.0 MBDownload

Free to use in your own training — please keep the PersonWise credit page at the end.

Have your own deck? Turn it into a course

Sources consulted

Web sources consulted while building this course.