GRECS ETS #70 Question

[n3urodron3]

70. Let N be the set of all natural numbers. Which of the following sets are countable?

I. The set of all functions from N to { 0,1 }

II. The set of all functions from { 0,1 } to N

III. The largest subset of N

 

(A) None (B) I and II only © I and III only (D) II and III only (E) I, II, and III

 

Ans:

D

 

 

Can anyone please explain me this. I had an opinion which was contradicted by my friend, so I wanted to know how exactly to proceed while working on such type of questions (i.e. countable sets).

 

Thanks! :)

[azk]

70. Let N be the set of all natural numbers. Which of the following sets are countable?

I. The set of all functions from N to { 0,1 }

II. The set of all functions from { 0,1 } to N

III. The largest subset of N

 

THEOREM: Every subset of a countable set is countable. In particular, every infinite subset of a countably infinite set is countably infinite. (1)

THEOREM: (Assuming the axiom of countable choice) The union of countably many countable sets is countable. (2)

THEOREM: The set of all finite subsets of the natural numbers is countable. (3)

THEOREM: The Cartesian product of finitely many countable sets is countable.(4)

 

Countable set - Wikipedia, the free encyclopedia

 

I. N -> {0,1} (countable)

let A be a subset of N, A is countable because of theorem 1

let B be a subset of N, B and A are disjoint, B is also countable

-consider sets of functions f: A -> {0} and g: B -> {1}

-because A is countable and {0} is finite with cardinality of 1 -> the cartesian product between this two sets is countable (theorem 4)

-because B is countabl and {1} is finite --> Cartesian product of this two sets is countable.( thereom 4)

-Also the union of two countable sets is countable( theorem 2)

Therefore, the mapping from N -> {0,1} is countable ( which contradicts the answer, please correct this for me !!!!)

 

II. {0,1} -> N (countable)

well, this mapping is injective, 0 can be mapped to at most one integer and so can 1.

so {0} -> N is countable ( we can even enumerate this)

{1) -N is also countable ( ditto)

the union of the two countable sets of functions should be countable.

so i am sure about this.

 

III. theorem 3 --> countable.

please correct me

[bounce] bounce !!!

[n3urodron3]

Yes, even I am arriving at the same above scenario. Could there be any other way to do the first part?

 

Like, we know that for any function f:A -> B to be injective, cardinality(A) S ?

(assuming S = {0,1})

[azk]

Yes, even I am arriving at the same above scenario. Could there be any other way to do the first part?

 

Like, we know that for any function f:A -> B to be injective, cardinality(A) S ?

(assuming S = {0,1})

 

because the function can be non-continuous so not all points in N are mapped into S={0,1}. This kind of function can either be surjective and injective( injective if cardinality of the function's domain

 

I found the mistake i made though,

we know that the function f maps subset of N -> {0,1}

Even though the subset of a countable set is countable, the NUMBER of subset is not. The theorem doesnot say anything about the NUMBER of subsets, it only guarantees that the subsets themselves are countable.

so answer I is False according to me

 

[bounce] bounce!!

[krkq35]

First off, I came up with the same answer (that all three are true) when I went through this problem. I'm still not quite sure why (I) is false.

 

I found the mistake i made though,

we know that the function f maps subset of N -> {0,1}

Even though the subset of a countable set is countable, the NUMBER of subset is not. The theorem doesnot say anything about the NUMBER of subsets, it only guarantees that the subsets themselves are countable.

so answer I is False according to me

 

The number of subsets in any given set S is 2^cardinality(S). So, if cardinality(S) is countable, then won't a set with 2^cardinality(S) elements also be countable?

 

It seems like it would be possible to enumerate the sets mapping N to {0,1}:

f_1 maps all of N to {0}

f_2 maps 1 to {0}, N\{1} to {1}

f_3 maps 2 to {0}, N\{2} to {1}

...

f_m maps all of N to {1}

which would make the number of functions countable. That's definitely not a proof, but I would think there would be some obvious counterexample if this were false.

[azk]

The number of subsets in any given set S is 2^cardinality(S). So, if cardinality(S) is countable, then won't a set with 2^cardinality(S) elements also be countable?

with f: N->{0,1},

function f always map any subset of N to a finite set {0,1}. The number of functions f existing is proportionate to number of subsets that we can derive from N. Then the number of subsets of N is the cardinality of a power set. And the power set is strictly greater than the superset that it is derived from( which is N in this case)

And the power set is not countable. We can use diagonalization to prove this through contradiction.

There is a neat proof here ( it is just diagonalization leading to contradiction) - please read if interested:

www.cs.rpi.edu/~drinep/modcomp/class17.ppt ( nice)

www.cs.xu.edu/csci250/06s/Theorems/powerSetuncountable.pdf (ok proof)

 

Excellent question n3urodron3 !!!

[bounce] bounce!!

[n3urodron3]

Okay, this helps to clear it up in a better manner. The argument which krkq35 used was the exact same one my friend used against the sum, which even I had thought to be true (till azk's post). Thanks for clarifying it with those links azk! and thanks krkq35 for participating in this! :)

[cjlax26]

Here is an easy way of looking at this problem:

 

I. The set of all functions mapping N to {0,1} are all of the different functions that you can imagine for mapping the Naturals to a set of 2 elements. Consider a function from N to {0,1} to be a subset of N (lets just say a subset of elements of N that map to 0). Imagining all of these subsets equates to the Power set of N which has cardinality equal to the Reals which is uncountable.

 

II. Here, we are dealing with functions that map {0,1} to N. This would be all of the subsets of N that have 2 elements. This in turn can be thought of as the set of all rational numbers (1/2, 1/3, 4/16, ...., etc.) The set of rational numbers is countable (there's a cool proof of this in Sipser) therefore this set is countable.

 

III. The largest subset of N is N itself so this is kind of trivial as it is, but any subset of a countable set is also countable. A subset is always less than or equal in size.