The subject of this lecture is the concept of  "the power of set". This notion generalises the idea of "the number of elements" in finite sets. Unfortunately, the intuitions that concern finite sets are not always proper for infinite sets. For example, if we imagine an infinite box full of natural numbers, then there is still enough room to put in a new element. Moreover we can put in all rational numbers and there is enough room for all of them!
Moreover, in spite of the infinity of natural numbers' set, it is so tiny in comparison with the set of real numbers that it can be stored in every arbitrary small interval of real numbers. On the other hand, the set of real numbers, although extremely large (we can not even enumerate its elements), may be immersed in every proper, even very small own interval. Really amazing!

It crucial for understanding this lecture to get the grasp of the concept of equipotence. In the set of all subsets of some universe, equipotence is an equivalence relation the abstraction classes of  which are exactly the powers (or cardinality) of sets. Using the notion of equipotence, we introduce three basic types of sets: finite, enumerable (countable) and not enumerable (uncountable).

In practise we usually deal with finite sets. Computer implementation of both natural numbers' set and real numbers' set are strictly finite. All sets of data and information which we store in files, data bases or information systems are also finite structures. But sometimes we walk very close to infinity. For example, if a program with the "while" loop is executed long enough, it can print on the computer's screen any freely large set. Furthermore, if we set incorrect loop condition, then our program (theoretically) may execute for ever. This observation also applies to recursion based computer programs. Definition of class in object programming languages, i.e. every pattern of creating objects, is a definition of a hypothetically infinite enumerable set.

In this lecture we present several examples of enumerable and not enumerable sets. We also present one of the most important theorems of set theory which states that cardinal number of the power set is always larger then the cardinal number of the source set. This implies that there are infinitely many cardinal numbers that are powers of infinite sets. 

« previous section

next section »