Proving that a set is countable

  • Thread starter georgetown13
  • Start date
  • Tags
    Set
That covers every pair in A\times B. Now repeat this idea for A\times B\times C, etc. You can even use induction to get all of them together.
  • #1
georgetown13
7
0

Homework Statement



Let U be a countable set. For j=1, 2, 3, ... define
Fj= {(x1, x2, ... , xj): xi [tex]\in[/tex] U for all i=1,2,...,j}

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

Homework Equations


The Attempt at a Solution



I'm having trouble understanding what the set Fj contains.
F1={x1}
F2={x1, x2}
And so on...

But as xi for all i=1,2,3,...,j is in U, does that mean Fj 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.
 
Physics news on Phys.org
  • #2
Do I have to use induction for this proof?
 
  • #3
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.
 
Last edited:
  • #4
[itex]F_j[/itex] is the set of "ordered j-tuples" with entries in U. No, [itex]F_j[/itex] is NOT a subset of U. For example, it we take U= R, then [itex]F_2= R\times R[/itex]. R if we think of R as the number line, then [itex]F_2[/itex] 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 [itex]F_j[/itex] is.)

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

If not- prove it! If A is countable, we can list its members: [itex]a_1, a_2, a_3, \cdot\cdot\cdot[/itex]. If B is countable, we can list its members: [itex]b_1, b_2, b_3, \cdot\cdot\cdot[/itex]. 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 [itex](a_j, b_i)[/itex]. We can count all such members by "zigzagging" through that array: [itex](a_1, b_1)[/itex][itex], (a_2, b_1),[/itex][itex] (a_1, b_2), (a_1,b_3), (a_2, b_2), (a_3, b_1), (a_4, b_1),\cdot\cdot\cdot)[/itex].
 

1. What does it mean for a set to be countable?

Countable sets are those that have a finite number of elements or can be put into a one-to-one correspondence with the positive integers. This means that each element in the set can be assigned a unique number, starting from 1.

2. How do you prove that a set is countable?

To prove that a set is countable, you can either show that it has a finite number of elements or construct a one-to-one correspondence between the set and the positive integers. This can be done by listing out the elements in a specific order and assigning them a unique number.

3. Can an infinite set be countable?

Yes, an infinite set can be countable as long as it can be put into a one-to-one correspondence with the positive integers. This means that even though the set has an infinite number of elements, each element can still be assigned a unique number.

4. What are some common examples of countable sets?

Some common examples of countable sets include the set of natural numbers, integers, rational numbers, and even some infinite sets such as the set of even or odd numbers. These sets can be put into a one-to-one correspondence with the positive integers, making them countable.

5. Is every subset of a countable set also countable?

No, not every subset of a countable set is countable. For example, the set of real numbers is uncountable, but it contains subsets such as the set of rational numbers which is countable. So, it is not always true that a subset of a countable set will also be countable.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
458
  • Calculus and Beyond Homework Help
Replies
1
Views
909
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
  • Calculus and Beyond Homework Help
Replies
6
Views
2K
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
139
  • Calculus and Beyond Homework Help
Replies
1
Views
3K
  • Calculus and Beyond Homework Help
Replies
5
Views
3K
  • Topology and Analysis
Replies
2
Views
970
  • Topology and Analysis
Replies
2
Views
3K
Back
Top