# Do all uncountable sets contain elements with infinite Kolmogorov complexity?

Otherwise, if all the elements in a set can be represented by a at most n symbols (finite Kolmogorov complexity), I could count them by creating a n dimensional pairing function. Or atleast, that is my assumption.

Any thoughts?

Edit: as @Carl has pointed out the correct term for sequences that have no finite representation is Kolmogorov Random not infinite as I used in my title.

-
This is a little imprecise, because sets can contain anything, such as other sets, and symbols such as Heart, Elephant, and Galaxy - and I don't mean the string representation of those things, but those actual things. Kolmogorov complexity is about strings only. It is unclear what the Kolmogorov complexity of an Elephant is. If you're talking about sets of finite strings, like Rune states below, those are always countable. If you're talking about sets of infinite strings, it's also unclear what the Kolmogorov complexity of infinite strings are. –  Henry Yuen Jul 12 '10 at 17:40
This question reveals a basic misunderstanding about cardinalities. It does not look appropriate for MO. –  Andres Caicedo Jul 12 '10 at 17:50
@Andres could you elaborate on your comment for my own edification? –  Jonathan Fischoff Jul 12 '10 at 18:17
The question is not well posed. Kolmogorov complexity is defined for finite strings from some (finite or countable) alphabet. There are two issues with the question. (1) Every string has finite Kolmogorov complexity: there is no definition of "infinite Kolmogorov complexity". (2) Since any finite or countable alphabet makes only countably many finite strings, there are never uncountably many strings to put into a set. –  Carl Mummert Jul 12 '10 at 19:40
Even if you change the terminology, I don't understand where the "at most n symbols" issue arises, or how a pairing function is related to the question. If you are asking whether every uncountable set of infinite binary sequences must contain a Kolmogorov random element, the answer is no. One example if the set of sequences that have a 0 in every even position but no constraints on the odd positions. This set has the cardinality of the continuum but contains no random sequences. –  Carl Mummert Jul 12 '10 at 22:01

Contrary to what some of the commenters said, there's no great difficulty in generalizing Kolmogorov complexity to infinite strings. For example, given a language L⊆{0,1}*, we could let K(L) be the length of the shortest program that decides L, or K(L)=∞ if L is undecidable. (Or we could also talk about programs that recognize L, in which case even the language HALT would have a finite complexity.)

In either case, the OP's intuition is essentially correct: if a set S of languages is uncountable, then since there are only countably many decidable or recognizable languages, clearly there must exist a language L∈S such that K(L)=∞.

-

I'm not sure if I understand your question, but the set of all finite strings is countable, thus a set in which every element has a name (i.e., a finite description) is countable.

-