Countability of finite subsets of a countable set
ID: countability-of-finite-subsets-of-a-countable-set
A finite subset of the natural numbers, numbered from one, has the binary code . Distinct finite subsets give distinct codes, because the largest differing exponent exceeds the sum of all smaller powers of two. Thus the finite subsets form a countable set, although the entire power set is an uncountable set by the Cantor diagonal argument. An enumeration transfers this coding to any countable set.
New to topics? Read the docs here!