MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Maybe I'm being dense here, but can someone give me a subset of the set of all languages which is uncountable and the subset is easy to describe? (Some natural subset -- not like "take the set of all languages and remove a few.")

For instance, I thought of the set of recursive or recursively enumerable languages, but these are countable. Perhaps some set in the arithmetic hierarchy?

This is probably a very easy question, and I'm just being silly.

share|cite|improve this question
"Perhaps some set in the arithmetic hierarchy?" Wouldn't this be countable by what you just said about recursive languages? – Akhil Mathew Nov 3 '09 at 0:34
There are many easy answers, as the answers coming in so far demonstrate. What is far harder, I think, is to come up with a set of languages that arises naturally and is uncountable for a nontrivial (and interesting!) reason. – Harald Hanche-Olsen Nov 3 '09 at 1:08
Yes, that is a good question. A natural language that isn't constructed for the purpose of making it uncountable. – Rune Nov 3 '09 at 1:21
May I point you to my humble questions concerning "naturality":…, very much in the vein of your "remove a few"? – Hans Stricker Mar 5 '10 at 16:22
up vote 5 down vote accepted

One way to take the question is to ask for a set of languages, for instance a complexity class, which is uncountable "for a good reason". In other words, that people study the class for some substantially different reason, and it's clearly convenient for it to be uncountable.

Probably the most common example is the class P/poly. This can be defined as polynomial-time computations with polynomial-length advice strings. (An advice string is any extra information that depends on the length of the input, but not on the specific value of the input.) By a famous structure theorem, it is also computations performed by polynomial-sized circuits on n input bits, without the requirement that the circuits can be built quickly by a Turing machine. This is clearly not a countable set of langauges, because anything recursive or non-recursive can be done with the input length.

On the other hand, it is a very useful class and construction. A stronger version of the P vs NP problem, inspired by circuit formulations of P vs NP, conjectures that NP is not contained in P/poly. And it is a theorem that BPP (randomized polynomial time) is contained in P/poly.

share|cite|improve this answer
Very nice! Although I couldn't express exactly what I was looking for, you've answered what I wanted. I guess P/poly doesn't have any complete problems under any sort of Turing reduction, since there are just countably many reductions to go around. – Rune Nov 3 '09 at 13:32

Remember that the set of definitions writable in a finite alphabet is countable. So any set of languages where a language can be specified with a finite amount of data is countable. For example, a recursive language is specified by the Turing machine which accepts it, so the set of recursive languages is countable.

In order to get uncountable, you are going to have to allow a lot more freedom than that. For example, take any infinite language L and consider the set of all languages which are subsets of L. I'm not sure what kind of example you'd find nice, so I don't know what kind of example to give you.

share|cite|improve this answer

The set of all languages which accept the empty word. Or all even words. Or all languages encoding all pairs of integers (a,b) such that a

You're not being silly, but if you want an uncountable number of languages, this means that you need to have some parameter ranging over an uncountable set. In the first two examples it was the set of all languages, in the third it was the real line.

share|cite|improve this answer

The Turing degrees are an uncountable collection of sets of languages (equivalence classes under Turing reduction). So if you choose one representative (canonical in some way) language from each degree, you've got an interesting uncountable set of languages.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.