Does there exist an uncountably infinite language?

1.4k Views Asked by At

If an alphabet $= \{a, b\}$

I believe an example of a finite language over that alphabet with positive cardinality would be the set equal to $(a+b)^4$

An example of a countably infinite language over the alphabet would be ${a}^*$

But do uncountably infinite languages even exist? Each item (string) of the language is finite, so I believe you could make a one-to-one relationship with the set of integers.

1

There are 1 best solutions below

0
On

In elementary computability theory, we usually work with languages that are subsets of $\mathbb{N}$, or which are in bijection with subsets of $\mathbb{N}$, such as languages consisting of finite words over a finite alphabet.

In more advanced levels of computability theory we also look at more general collections, such as collections whose elements are infinite sequences from a finite or countable alphabet. Like countable languages, we can use Turing machines to define what it means for one of these uncountable "languages" to be decidable, semidecidable, etc. The more general analogy is via the arithmetical hierarchy. This allows us to make similar definitions for subsets of $\mathbb{N}$, subsets of $\mathbb{2}^\mathbb{N}$, and subsets of $\mathbb{N}^\mathbb{N}$.

However, it may may not be very common to call these uncountable collections "languages". For example, we are often interested in a "language" consisting of all infinite paths through some computable subtree of the complete binary tree. Rather than calling these "languages", we typically call them "$\Pi^0_1$ classes".