Sets

I’ve referred to sets informally several times above. All of the sets involved were finite, which is why all the questions we considered were decidable, again in a theoretical sense. There are infinite sets lurking in the background though. The set of all possible statements in our language is infinite. It is in some sense only mildly infinite though. More specifically, it is countable, a term we’ll define later. We actually considered multiple different languages built from the same set of tokens. The infix, prefix and postfix languages are distinct languages. How many languages are there? This requires a definition of language, which we haven’t given yet, but there are infinitely many, and even uncountably many, even if we restrict to those based on the same finite set of tokens. There are however only countably many grammars so there are languages which cannot be described by a grammar. There are also only countably many Turing machines so there are languages which can’t be recognised by any Turing machine, i.e. are not recursively enumerable.

Later we’ll see a formal language to describe the theory of sets. As we’ve just seen though, it can’t describe each individual set, because there will only be countably many statements and the number of sets can’t be countable. Set theory is nice and intuitive as long as we restrict ourselves to finite sets but rapidly becomes weird when we have to consider infinite sets.