Władysław Homenda - Automata Theory and Formal Languages

De Gruyter Textbook

ISBN 9783110752274

e-ISBN (PDF) 9783110752304

e-ISBN (EPUB) 9783110752311

Bibliographic information published by the Deutsche Nationalbibliothek

The Deutsche Nationalbibliothek lists this publication in the Deutsche Nationalbibliografie; detailed bibliographic data are available on the Internet at http://dnb.dnb.de.

2022 Walter de Gruyter GmbH, Berlin/Boston

This chapter offers all required prerequisites and elaborates on the notation used throughout the book. As such, the content presented here becomes helpful in the systematic exposure of the material covered in the consecutive chapters.

Finite sets include a finite number of members. The empty set, that is, the set which includes no members, is also finite. The empty set is denoted by . Infinite sets include infinitely many members. Infinite sets are countable or uncountable.

We say that a set is countable if and only if its members could be arranged in a particular sequence. In other words, a set is countable if and only if we can enumerate (list) its members assigning natural numbers to them. Such an arrangement guarantees to find a number assigned to any of its members. Of course, finite sets are also countable. Thus the conclusion that any subset of a countable set is countable becomes obvious.

A set is uncountable if and only if there is no enumeration of its members. Any set including an uncountable subset is uncountable.

Note that all but the last set of numbers are countable. The last one is uncountable. The following notes concerning the above sets show arrangements of their elements in sequences, that is, justify countability of these sets:

• comparing Example , it is straightforward that the set of prime numbers and the set of natural numbers are countable;

• the following enumeration of the set of integer numbers Z={0,1,1,2,2,3,3,} shows its countability;

• an intuitive depiction of Cantor enumeration of the set of pairs of natural numbers is shown in . This intuition can be explicitly expressed by the formula (x,y)=(x+y)(x+y+1)/2+x , where (x,y) is an enumerated pair of natural numbers.

The Cantor enumeration of pairs of natural numbers reveals some interesting characteristics. We note that any rational number can be represented as a fraction of two integer numbers. Any nonnegative fraction is formed by taking a columns label as the numerator and treating a label of a row (except the first one) as its denominator. In this enumeration, any fraction appears once in irreducible form and infinitely many times in reducible form. Cantor enumeration of pairs of natural numbers could be adapted to an enumeration of nonnegative rational numbers by skipping reducible fractions. On the other hand, since the set of rational numbers is a (proper) subset of pairs of natural numbers, the countability of the set of non-negative rational numbers is a direct result of the countability of the set of pairs of natural numbers. Finally, we can apply the way of enumeration of the set of integer numbers to all rational numbers.

Let us consider the unit interval of real numbers. Any member of this set could be represented in the form of infinite expansion. Assume that all real numbers are arranged in the following sequence:

The following real number of the unit interval does not appear in this sequence, where b is the binary digit opposite to the digit b, that is, b=0 if and only if b0 :

Therefore, the assumption that all real numbers of the unit interval could be arranged in a sequence is false.