How to imagine an uncountable set?

    As you know, infinities are of various types. There are countable, there are countless. Countless are divided into sets of power continuum and all the rest. Countable sets are those whose elements can be ordered in a long row and enumerated by natural numbers. With countless such a trick fails. Then how can one imagine an uncountable set, in particular, a set of real numbers [0; 1)? The answer is a tree of infinite height.

    For me, countless sets have always looked like an incomprehensible, foggy cloud of symbols soaring somewhere in the back of the brain. But recently, the
    cloud condenses into a pair of not too neat, but compact crystals. About them, actually.
    To avoid confusion, by an uncountable set we mean a set of power continuum (these include real numbers, irrational numbers, the set of all subsets of natural numbers, and others).


    As is known from Wikipedia and other reliable sources, the power of the real numbers of the interval [0; 1) is a continuum. Real numbers from this segment cannot be counted as natural numbers, i.e. so that one real number corresponds to one real number and vice versa. For unbelievers, we will conduct the Cantor diagonal procedure.

    We represent the numbers of the interval [0,1) in the binary number system and get a set of infinite sequences of ones and zeros.

    Suppose we ordered such a set in the form of an endless list as in the figure. Having ordered, we get a square table in each cell which is either 1 or 0. Consider the cells located on the main diagonal.

    Inverting the diagonal (000010 ...), we get a sequence that does not fall into our list, since the sequence obtained differs from each one in the list by at least one element. The sequence number n is different from the diagonal in the n -th position. Therefore, the diagonal sequence is not in the list.

    Based on the above scheme, an uncountable set can be represented in the form of continuously generated sequences. We inverted one diagonal sequence — inserted it at the top of the list — generated a new one, and so on. Such a carousel looks doubtful.


    Let's now look at the binary tree in the following figure. Root, heirs. In the right heir of each node - 1, in the left -0. Many paths in a tree are paths from the root to each of the leaves. For a tree of height N, the set of maximum paths from the top to the leaves will correspond to the set of all sequences of zeros and units of length N, even if N is infinity.

    Suppose a sequence is found that is not in the tree. Let's try to impose it on one of the tree paths: 0,1,0,1 ... at some point there should be such a fork in which our sequence does not fit. But from each node of the tree either 0 or 1 comes out, so in order not to fit in the path on the tree, the sequence must contain elements other than 0 or 1.

    It turns out that the set of maximum paths in a binary tree of infinite height has a power continuum, which is equivalent to the power of real numbers of the segment [0; 1).

    If we return to the interpretation of binary sequences as binary fractions, then rational fractions of the form 0, x (y) will look like a finite curviline x and an infinite sequence of curvilines y , irrational numbers will look like one infinite non-repeating curvuline x .

    Funny squiggle

    There is one catch in the result: The number of paths of maximum length emanating from the root of a binary tree of infinite height is uncountable. The number of vertices of such a tree can be calculated. This is easy to do by sequentially numbering the vertices from top to bottom.

    For a tree of finite height, the layout is different: The
    number of paths of maximum length emanating from a root in a binary tree of height N is 2 ^ (N-1), and the number of vertices is almost twice as large - 2 ^ N - 1. Tending N to infinity, we get that the countable infinity of vertices is two times “greater” than the uncountable infinity of paths.
    Here is a pseudo-paradox illustrating the work of intuition.

    Effective intuition to us all :).

    Also popular now: