 |
|
|
|
|
|
||
|
|
||
|
|
||
|
|
|
|
|
|
||
|
|
||
|
|
||
|
|
|
|
|
|||||||||||||||||
Add Forum to Favorites | Send Topic To a Friend | View Forum FAQ | Track this topic |
Last Thread Next Thread |
| Set Cardinality |
|
 |
Croc Member since: 6/12/2003 |
|||
 Posted - 4/30/2005 3:42:49 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  |
||||
|
||||
|
higherspeed Member since: 4/18/2003 From: Cambridge |
|||
 Posted - 4/30/2005 6:40:12 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 Member since: 11/5/2002 From: Pittsburgh, USA |
|||
|
Posted - 5/1/2005 1:48:39 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. |
||||
|
||||
|
Anonymous Poster |
|||
Posted - 5/3/2005 1:15:16 AM |
||||
| What you're missing is that he said it's true of the "general" case. That means that this is a special case. Languages have additional restrictions. Check out mathworld.com |
||||
|
||||
|
Anonymous Poster |
|||
Posted - 5/3/2005 12:43:20 PM |
||||
| The cardinality of the set sigma is aleph-1. One can show that there is a surjection from the language made from the alphabet sigma into the powerset of sigma. Thus the cardinality of the language is bigger than or equal to aleph-2 by theorem. Therefore if a subset of the language has size aleph-1 by the pidgeonhole principle the complement must have cardinality aleph-2, which is uncountable. |
||||
|
||||
|
white skies Member since: 4/10/2005 |
|||
|
Posted - 5/3/2005 3:04:27 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. |
||||
|
||||
|
alvaro Member since: 3/7/2002 From: USA |
|||
|
Posted - 5/4/2005 7:33:12 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 |
||||
|
||||
|
Anonymous Poster |
|||
Posted - 5/4/2005 6:31:18 PM |
||||
Quote: http://mathworld.wolfram.com/FormalLanguage.html http://mathworld.wolfram.com/Grammar.html Sounds like more restrictions to me. Of course, you may be working with a different definition of "language", but I would guess that the paper is refering to the sorts of languages described above. In fact, saying that languages are finite or countable is a restriction on what qualifies as a language. Quote: Maybe you have more information on what the paper in question covers, but there was nothing in the initial post stating that the alphabet was finite. Some people were confused by the wording and thought it was uncountable, but "uncountable" was refering to the set of all languages. No information was given about the cardinality of the alphabet. Now, the languages described above place the additional restriction that the alphabet is finite. On the other hand, you said that languages don't impose additional restrictions. Which is it? Quote: If the lecturer is correct, my guess is that there are additional restrictions on U that we weren't informed of. Is the paper legally available on the internet? I'd be interested to see it. |
||||
|
||||
| All times are ET (US) |
Last Thread Next Thread |
|
