--- title: "Countable and Uncountable Sets" description: "Compare infinite sets by pairing their elements. The rationals pair with the naturals; the reals do not, and the diagonal argument shows why." canonical: https://lightmysky.com/learn/mathematics/countable-and-uncountable-sets-mt_VTHPloNBbJ source: https://lightmysky.com/learn/mathematics/countable-and-uncountable-sets-mt_VTHPloNBbJ.md retrieved: 2026-11-12 --- > **Agent view.** This is the Markdown twin of the page, for tools and assistants. > When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md > API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md > Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt > Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json > Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`. # Countable and Uncountable Sets Compare infinite sets by pairing their elements. The rationals pair with the naturals; the reals do not, and the diagonal argument shows why. Subject: Mathematics · Area: Mathematical Thinking · Ages 18 to 19 Page: https://lightmysky.com/learn/mathematics/countable-and-uncountable-sets-mt_VTHPloNBbJ ## Ready when they can - Build an explicit bijection showing a set is countable - Present the diagonal argument for the reals - Explain why a finite set cannot pair with a proper subset, and why the power set of N is uncountable ## Lesson: Pairing up infinite sets Use N={1,2,3,...}. Here, countable means finite or admitting a sequence that covers every member. Countably infinite means having a bijection with N. A bijection is both injective, so distinct inputs have distinct outputs, and surjective, so every target is reached. A finite set is countable but cannot have a bijection with the infinite set N. Let E={2,4,6,...}. The function f(n)=2n pairs N with E. Equal outputs 2a=2b force a=b, proving injectivity. Every e in E has the natural-number preimage e/2, proving surjectivity. Thus f is a bijection. For example, 6 maps to 12. Dividing by 2 gives the inverse pairing. *(drawing: These are the first four pairs. The formula n -> 2n defines the pairing for every n in N.)* List the integers as 0,1,-1,2,-2,3,-3,... . Position 1 holds 0. For positive k, position 2k holds k and position 2k+1 holds -k. This reaches every integer exactly once, so the integers are countably infinite. For positive rationals, scan p/q with positive integers p,q by increasing p+q, then increasing p within each total. Skip values already listed. Each total has finitely many pairs, so every fraction is reached. For instance, 4/2 is skipped once 2 has appeared. Put 0 first, then each retained positive value followed by its negative, to list all rationals. A proper subset leaves out at least one member of its whole set. If a finite set has m members, its proper subset has fewer than m. A bijection cannot pair these unequal finite counts. Infinite sets can behave differently: E is a proper subset of N, yet doubling pairs E with all of N. Imagine a full hotel with rooms 1,2,3,... . Moving every guest from room n to n+1 frees room 1. There is no last room. To take countably many newcomers, instead move current guest n to room 2n and newcomer k to room 2k-1. Even and odd rooms never overlap. For odd room r, its newcomer number is (r+1)/2. A full finite hotel cannot add a guest without sharing or removing someone. The interval (0,1) contains the reals strictly between 0 and 1. Decimal expansions need care: 0.3999... equals 0.4000... . Different digit strings can name the same number. For each listed real, use its expansion without an endless tail of 9s. Given rows r1,r2,r3,..., construct d=0.d1d2d3... . For digit dn, inspect digit n of row rn. Write 2 if that digit is 1; otherwise write 1. For rows beginning 0.414..., 0.381..., 0.671..., the diagonal is 4,8,1, so d begins 0.112... . Later rows determine later digits. Suppose the rows list every real in (0,1), using the decimal convention above. The constructed d uses only 1s and 2s, so it lies in (0,1) and has no alternate terminating expansion. For every n, d differs from rn at position n. Thus the list misses d. This works for every proposed list, so no surjection from N onto (0,1) exists. The interval, and hence the reals, is uncountable. Apply the same digit rule to a complete list of rationals in (0,1), again using expansions without a tail of 9s. It constructs a real d in the interval that is absent from the list. Since every rational there is listed, d must be irrational. Constructing decimal digits does not guarantee a rational result. The power set P(A) contains all subsets of A, including the empty set and A itself. For finite A with m members, each member can be included or excluded, giving 2^m subsets. Requiring one specified member to be included leaves m-1 choices, giving 2^(m-1) subsets. For {u,v,w}, requiring u leaves two choices each for v and w. For any function f:N -> P(N), define D={n in N: n is not in f(n)}. This is a subset of N. For every k, membership of k in D is opposite to membership of k in f(k). Thus D differs from every output f(k). No function from N can reach every subset of N, so P(N) is uncountable. A proposed list can miss subsets even when its outputs keep growing. The function f(n)={1,2,...,n} reaches every nonempty finite initial segment of N. Every output contains 1, so it misses the subset {3}. One missed target disproves surjectivity. Every infinite subset of N is countably infinite. Repeatedly choose its least unused member to list it increasingly. The process never runs out. Any member a has at most a-1 smaller naturals, so only finitely many members can come before it. It is therefore reached. No member is repeated or missed. **Recap.** Countable sets are finite or listable. Bijections compare sizes. A safe decimal diagonal defeats real-number listings; opposite membership defeats listings of all subsets of N. *This lesson, its questions and its flashcards were written for this dataset.* ## Practice 18 questions on this page, each with its working shown. ## Needs first - [Equivalence Relations and Partitions](https://lightmysky.com/learn/mathematics/equivalence-relations-and-partitions-mt_wgEupYwEUF) - [Sets and Functions in the Language of Proof](https://lightmysky.com/learn/mathematics/sets-and-functions-in-the-language-of-proof-mt_XAcHX_3DVz) ## Optional connections - [Statements, Quantifiers and Negation](https://lightmysky.com/learn/mathematics/statements-quantifiers-and-negation-mt_S5NvyPxEZ_) ## Opens up - [Sigma-Algebras and Measurable Sets](https://lightmysky.com/learn/mathematics/sigma-algebras-and-measurable-sets-mt_cpvegazufk) - [Open Problems as a Genre](https://lightmysky.com/learn/mathematics/open-problems-as-a-genre-mt_qBWcaUWG9J)