🔒 Locked

Set Cardinality

Started by Croc Apr 30, 2005 at 2:42 PM 6 replies 3k views

Original Post

Apr 30, 2005 at 2:42 PM

This is not a homework question, but a question from a past paper at university which I would like to check my thoughts and working with everyone. The following question is stated here verbatim. Recall that the set of all languages S_å with the alphabt å is an uncountable set. Let U Í S_å, where U is uncountable. What is the cardinality of the complement of U? (a) Countable (b) Uncountable (c) Dependant on choice of U My thought is that the answer is (c) Dependant on the choice of U for the following reasons. If U = S_å, then the complement of U is the empty set, which is countable. There is however the possibility that if U is not S_å then the complement can be uncountable. This can be demonstrated by considering the uncountable set, the real numbers and the subset, the set of decimal numbers between 0 and 1. The complement of this subset is still uncoutable. However, a friend has spoken to the lecturer who said that while the above is generally true, in this case the answer is always uncountable but refused to go into details (uni policy on no solutions to past papers). Thus my question is what in this particular situation am I missing? - Oscar [smile]

higherspeed

Apr 30, 2005 at 5:40 PM

Well I've never met the terms alphabet or language before, but I would guess certainly (c). Although in some situations where U is not just a set, but something less general, ie it has some sort of structure, then it could be (b).

Punty50

May 1, 2005 at 12:48 AM

The answer is it can be both. For example, let U be the complement of the language of all strings of the form a, aa, aaa, etc. Then U is uncountable as it contains every singleton letter except a, and there are uncountably many of those. It's complement is countable.

Similarly, let U be the complement of set of letters. This is uncountable, as it contains the words aa, bb, cc, and so on (doubles of letters). Its complement is Sigma, which is uncountable.

white skies

May 3, 2005 at 2:04 PM

I'd say (c).
take U=S - in this case its complement is the empty set - countable.
take U='A' where 'A' belongs in S - in this case its complement is S\'A' - uncountable.
[smile]

alvaro

1,980

alvaro

May 4, 2005 at 6:33 AM

At least two of the posters above didn't understand that U is a set of languages, not a language. All languages are finite or countable. Languages don't have additional restrictions, despite what an AP said; any set of words is a language (there are however interesting classes of languages that have more structure). As for the other AP, the cardinality of sigma is finite, so your contribution doesn't help much either.

Here is what I suggest. The set of all words is countable (easy to prove, since you can just enumerate all words of length 0,1,2,...), so we can assign a natural number to each word. Then a language corresponds to a set of natural numbers, through that assignment. Now just prove that if X is a set of sets of natural numbers, the complement of X can be countable or uncountable.
* if X is the set of all sets of natural numbers, its complement is empty (finite)
* if X is the set of all sets of natural numbers that have more than one element, its complement is countable
* if X is the set of all sets of even numbers, its complement contains the set of all sets of odd numbers and therefore it's uncountable

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.