Proving that a set is countable

[georgetown13]

Homework Statement

Let U be a countable set. For j=1, 2, 3, ... define
F_j= {(x₁, x₂, ... , x_j): x_i \in U for all i=1,2,...,j}

Prove that j=1,2,3,...,F_j is countable.

Homework Equations

The Attempt at a Solution

I'm having trouble understanding what the set F_j contains.
F₁={x₁}
F₂={x₁, x₂}
And so on...

But as x_i for all i=1,2,3,...,j is in U, does that mean F_j is a subset of U?

Does this mean that I have to prove that if a set is countable, its subset is countable?

If so, how would I go about doing that?

Please help! I would greatly appreciate it. I'm having a hard time just understanding the question at all.

 

[georgetown13]

Do I have to use induction for this proof?

 

[eczeno]

edit: oops, misunderstood the the definition of Fj (the post from hallsofivy below is correct), the following comment does not make sense. :)
your question is not clear. what set are you trying to show is countable?

if you are trying to show that for all j, Fj is countable, then that makes sense. but then you would showing that any finite subset of a countable set is also countable, and that is not impressive because any finite set is countable.

so, i am still not quite clear what you want to show.

 

[HallsofIvy]

F_j is the set of "ordered j-tuples" with entries in U. No, F_j is NOT a subset of U. For example, it we take U= R, then F_2= R\times R. R if we think of R as the number line, then F_2 is represented by the plane, all points of the form (x, y). (Yes, I know R is not countable. My point is to explain what F_j is.)

If you already have the theorem "If A and B are countable, then A\times B is countable" this is simple- use induction on j.

If not- prove it! If A is countable, we can list its members: a_1, a_2, a_3, \cdot\cdot\cdot. If B is countable, we can list its members: b_1, b_2, b_3, \cdot\cdot\cdot. Now, imagine writing the members of A, horizontally, along the top of a sheet of paper, and B, vertically, along the left side. Where the ith row meets the jth column is the pair (a_j, b_i). We can count all such members by "zigzagging" through that array: (a_1, b_1), (a_2, b_1),(a_1, b_2), (a_1,b_3), (a_2, b_2), (a_3, b_1), (a_4, b_1),\cdot\cdot\cdot).