For every n ∈ N, define a set Fn ⊂ P(N) by Fn = {{a1, a2, a3, ..., an} : ai ∈ N for i ∈ {1, 2, ..., n}} ⊆ P(N). Prove or disprove that for every n ∈ N, |Fn| = |N|.

for this question, I thought of using the fact that |P(N)| = | R |. But not too sure where to go from there


Prove or disprove: The set {(a1, a2, a3, . . .) : ai ∈ {0, 1}} of infinite sequences of 0’s and 1’s is countably infinite.

would this be countably infinite since we can list the elements?

  • 1
    $\begingroup$ "since we can list the elements?" Can you list the elements? How would you do that? And as for the first question, $F_n$ seems to be the set of all $n$-tuples of natural numbers. Can you list them? How would you do that? $\endgroup$ – Arthur Mar 26 at 23:10

It seems your intuition and attempts were leading you to the wrong conclusions. $F_n$ will indeed be countably infinite for every $n$ and the set described in the second question is in fact uncountably infinite.

A sketch of a proof for the first: List out all of the ways in which the elements in your $n$-tuple sum to $0$. Then list all of the ways that they sum to $1$. Follow this by the ways in which they sum to $2$ and so on so forth.

For example for $F_3$ this would be $\{(0,0,0),(1,0,0),(0,1,0),(0,0,1),(2,0,0),(1,1,0),(1,0,1),(0,2,0),(0,1,1),(0,0,2),(3,0,0),\dots\}$

Convince yourself that every possible $n$-tuple of natural numbers will eventually be written in this list.

As for the second, the standard argument that is used is Cantor's Diagonal Argument. The punchline is that if you were to suppose that if the set were countable then you could have written out every possibility, then there must by necessity be at least one sequence you weren't able to include contradicting the assumption that the set was countable in the first place.

The sequence that you missed can be described as having first entry different than the first entry of the first sequence, second entry different than the second entry of the second sequence, third entry different than the third entry of the third sequence, and so on. Since the $n$'th entry of our sequence is different than the $n$'th entry of the $n$'th sequence it follows that our sequence is different than the $n$'th sequence for every $n$ and thus not in the list.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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