Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

One such tuple is [2, 45, 342 ... onwards to infinity]. Another such tuple is [0, 1, 2, 3 ... onwards to infinity].

I think this set is countable because we can lay all of these sets out one below another in order. We can then order them one by one, which is a bijection to the natural numbers.

share|improve this question
    
You might take a look at this question. Your question seems to only focus on the infinite subsets of $\mathbb{N}$, but it might still be helpful. –  Carl Morris Oct 1 '12 at 3:10
    
The word "tuple" generally denotes a finite sequence. The set of all tuples (finite sequences) of natural numbers is countable; the set of all sets of natural numbers, or of all sequences of natural numbers, is not. –  mjqxxxx Oct 1 '12 at 3:19
    
You can order these sequences, certainly. You can't write them out one-by-one in order. If you try, you will end up missing some. –  user22805 Oct 1 '12 at 3:32
    
@DavidFaux If you can lay out these sets one below one another, tell me which tuple is the next one after $[0, 1, 2, 3, \ldots]$? –  Erick Wong Oct 1 '12 at 3:37
add comment

2 Answers

up vote 3 down vote accepted

It is critical that tuples are of finite length, while your examples seem to be infinite. If you consider only finite ones, they are countable. If you consider infinite ones, you have all the subsets of $\mathbb N$, which is uncountable by Cantor's theorem

share|improve this answer
    
Thanks, but how is the set of infinite tuples the power set? Or perhaps how is there a bijection from the set of infinite tuples to the power set of natural numbers? –  David Faux Oct 1 '12 at 3:24
    
I'm sure you can find a surjection from what you've called the infinite tuples, onto the power set (or maybe the power set minus a single element), if you think hard enough. And that would be enough, right? –  user22805 Oct 1 '12 at 3:27
    
Each infinite tuple corresponds to the subset of $\mathbb N$ which is its elements. This gets all the subsets except the countable set of finite subsets (including the empty set). –  Ross Millikan Oct 1 '12 at 3:36
    
Actually König's lemma proves this one, rather than Cantor's theorem. –  Asaf Karagila Oct 1 '12 at 7:00
add comment

A famous proof of the uncountability of $\mathbb{R}$ can be applied to your set too.

If your set had an ordering $\{s_1,s_2,s_3,\ldots\}$ with each $s_i=[s_{i1},s_{i2},s_{i3}, \ldots]$, then we can construct an $s$ that is not in your ordering. Just define $s$'s $i$th entry to be something other than $s_{ii}$, and also something greater than all of the preceding entries of $s$ (to keep your condition of distinct natural numbers, and even keep the sequence sorted, if that is your intent). Then for all $i$, $s$ disagrees with $s_i$ in the $i$th position, and so $s\neq s_i$ for any $i$. So there never was an ordering that contained everything in your set in the first place.

share|improve this answer
    
The tuple $[1, 4, 1, 5, 9, \ldots ]$ does not appear in the described set, because it is not sorted (what the OP apparently means by "ordered"). –  Erick Wong Oct 1 '12 at 3:36
    
@Erick I think my mistake was omitting the word distinct from my reading of OP's question. But I've edited my answer accordingly. –  alex.jordan Oct 1 '12 at 3:41
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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