Logical Foundations of Mathematics and Computational Complexity by Pavel Pudlák

Author:Pavel Pudlák
Language: eng
Format: epub
Publisher: Springer International Publishing, Heidelberg

This informal rule enables us to derive various facts about G. We will start with proving that both G and its complement are infinite. Indeed, suppose that we have already constructed g(0), g(1), g(2),…,g(n) and we wonder if there will be some m>n such that g(m)=1. We know that the property of being generic does not depend on initial segments of g, hence there is nothing that prevents us from defining g(m)=1 for m=n+1 or any larger number. Thus it can happen that g(m)=1 for some m>n, hence by the rule g(m) must be equal to 1 for some m>n. Now we can repeat this argument again and again, whence we conclude that there must be infinitely many numbers m such that g(m)=1. By the same token, there must be infinitely many numbers m such that g(m)=0. Hence both G and its complement are infinite.

What about prime numbers, does G contain infinitely many primes? Exactly the same argument shows that G does contain infinitely many primes. Furthermore, the number of primes that G does not contain is also infinite. In particular, G is never equal to the set of prime numbers P. Notice that the only property of P that was used in this argument was that P was an infinite subset of natural numbers in the model M. Hence we can apply the same argument to any infinite subset of the natural numbers in M. Since G is infinite, this proves that G is not in the model M. Thus a generic set for a model M is never present in the model.

Let us try some other properties. Does a generic G contain two consecutive numbers? It surely does. Given an initial segment g(0), g(1), g(2),…,g(n) we may define g(m)=1 and g(m+1)=1 for any m>n and still this sequence can be completed to a generic one. Hence there must be an infinite number of such pairs. By the same token, there infinitely many segments in G which are equal to the binary file of this book. This may suggest that we should imagine a generic sequence s as a random sequence. It is true that g shares some properties with random infinite sequences of zeros and ones (for example, there are also infinitely many copies of this book in every random sequence), but g is not random. Consider the frequency of ones in r(0), r(1), r(2),…,r(n) for a random sequence r. As n goes to infinity this frequency very quickly approaches 1/2. In contrast to that the frequency of ones in g(0), g(1), g(2),…,g(n) unpredictably oscillates. To see that consider the following property of m:

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.