The bijections of a countably infinite set form an uncountable set. Partition an enumeration into disjoint pairs and encode an infinite binary sequence by independently fixing or swapping each pair.
If is a countably infinite set and is a finite set with at least two elements, the set of surjective functions is uncountable. Fix finitely many values to cover , then encode an arbitrary infinite binary sequence using two values of on the remaining inputs.
Articles by others on the same topic
An uncountable set is a set that cannot be put into a one-to-one correspondence with the set of natural numbers (i.e., it cannot be counted by listing its elements in a sequence like \(1, 2, 3, \ldots\)). This means that the elements of an uncountable set are too numerous to match with the natural numbers.