Countable and Uncountable 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.

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.

This finite example illustrates the counting argument; the argument applies to every finite size m.

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.