Probability of infinite non-random subsets in an infinite set of random integers

Not really relevant, but fun....

The set of symbols - letters - that make up an alphabet is finite, and therefore countable. In our case it has cardinality 26. Suppose we make use of this fact to enumerate these, and, for reasons I will explain shortly, designate as follows: A = 10, B = 20, C = 30 etc.

Then a word will be of the form 2050140 = BEN. This is clearly a number, i.e. an element in \(\mathbb{N}\). Now I can stick these words together to make a sentence, sentences to make a paragraph, paragraphs to make a book, etc, and I will still have an element in \(\mathbb{N}\).

OK, I simply used zero as a delimiter to avoid under-counting, that is, I know that 1020 = AB and not L = 12, which could happen if 12 = AB or L. So we see there is no word, sentence, paragraph, library, or even collection of libraries (Congress of Libraries??) that cannot be expressed as an element in the countable set \(\mathbb{N}\)]

But, since Cantor showed that the set \(\mathbb{R}\) of real numbers is uncountable, that means there will be uncountably many elements that cannot be given a name using words or sentences or paragraphs, or....

Yikes! But it gets worse. \(\mathcal{P}(\mathbb{N})\) is the powerset on the natural numbers. Cantor's diagonal argument can also be used to show this is uncountable. So, for each element of the powerset there must be at least one true statement (using words, sentences, paragraphs,....) in some theory of numbers, so there must be uncountably many true statements of number theory.

Therefore, there must be uncountably many MORE true statements of number theory than there are words, sentences, paragraphs, books or libraries (since these are countable).

It follows that any system that tries to describe number theory as a complete set of true statements is doomed to failure. This is version of an incompleteness theorem.

 

Log in or Sign up to hide all adverts.

Nice explanation QH.

 

Log in or Sign up to hide all adverts.

I'm thinking more about Fafnir's question and transfinite sequences. Having difficulty, because I don't know the vocabulary. But anyway, here is a different rendering of Fafnir's original question that I think might express his intention. Anyway, it seems more interesting to me than previous interpretations, because I can't figure out the answer.

Consider a set S of random digits with a one-to-one map on to the rationals (if that makes sense. I mean that every member of the set is a random integer in the range 0 to 9, and that for each rational, the set contains a corresponding member.)

What is the chance that there exists two distinct rationals a and b, such that for every rational x between a and b, the member of S corresponding to x is constant?

 

Log in or Sign up to hide all adverts.