# Mathematical proofs involving countable and uncountable sets

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

secondly

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?

• "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? – 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.
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.