Significance of Countable set with no nth Term

71 Views Asked by At

When we approach infinite sets we may come across with three types of cases

1)Countable with nth term 2) Countable with no nth term 3) Non countable sets.
Some examples are given below

Case 1:

Set of infinite positive even integers { 2,4,6,,,,,,,}. We can say it has nth term as $S_n= 2n$

Case 2:

Set of rational numbers can be counted using diagonal method. An illustration is given here . It says we can figure out a counting method for the infinite set by using diagonal procedure and if we encounter the same number during the procedure we omit it. We may not have any nth term solution here. But it is countable

Case 3:

By diagonal method itself we can prove it is not possible to count the real numbers in the interval (0,1). An illustration is given here

Doubts

1) What is the importance of counting of infinite set in mathematics. Could you suggest some uses of it in theorem proving etc?
2) If we can figure out nth term of a finite series then we can figure out the limit etc. So we can say there is use of counting procedure if we can figure out nth term. But what is the use of proving an infinite set countable if we cant figure out nth term
3) Suppose I have two countable sets and it has intersection too. Is it possible to prove intersection of two countable infinite set also countable.

1

There are 1 best solutions below

0
On

A set $S$ is countably infinite if there is a bijection $\phi$ from $\mathbb{N}$ to $S$. So, from this definition, a countable set will always have an $n$th term: $\phi(n)$.

Your observation is just that we can sometimes easily explicitly specify this function, as in your even number example, and other times we deduce that such a function must exist but we don't bother to explicitly calculate it. The rational numbers are an example of this. We could, with a little more effort than usual, calculate an explicit bijection but that is generally seen to be of no interest. In other cases, e.g. the Algebraic numbers, it will be even harder but still possible. Writing these functions explicitly is probably always possible in the countable cases (1) but very messy. A computer program (2) to calculate the $n$th term would be more practical.

(1) More in a moment.

(2) An idealised Turing Machine like computer with no memory or run time constraints.

Note that even when there is an obvious function it won't be unique. We could give many other functions. The function is not required to have any properties beyond being a bijection (one to one and onto).

There is some disagreement as to whether the natural numbers include $0$. Let's say that a set is $\mathbb{N}_0$-countable if there is a bijection to the natural numbers with $0$ and $\mathbb{N}_+$-countable if there is a bijection to the natural numbers without $0$. It turns out that they are the same and so the difference is unimportant.

So, most mathematicians don't see any particular interest in an explicit formula, just that there is one.

A particularly useful theorem is Schröder–Bernstein (Wikipedia). This means that it is enough to find an injection each way to prove that there is a bijection. So, it is common to find an injection both ways, quote this theorem, and then stop.

When you go beyond countable infinity, e.g. the real numbers, then finding explicit bijections becomes even harder and less common.

If you want to see some serious weirdness about infinity then study the Continuum hypothesis (Wikipedia).

Addition: I noticed that I did not answer your final doubts.

1) There does not need to be a use for something to be of interest to a mathematician. However, knowing whether an infinite set is countable or not is often useful. It is sometimes used in impossibility proofs: e.g. $S$ is countable and $T$ is not then a bijection between them does not exist. For example, the set of possible programs for a Turing Machine is countable yet the real numbers are not. So not every real number can be calculated by a Turing Machine. Computable number (Wikipedia)

2) I hope that I have addressed this above. Since a bijection between the set and the natural numbers is not unique anyway, there is no particular significance to the $n$th term. Also, there will often not be a limit. Is $\mathbb{N}$ itself countable? Of course with the obvious sequence $a_n = n$. What's the limit of that? Is $\mathbb{Z}$ (the integers) countable? Yes, you can arrange them: $0, 1, -1, 2, -2, 3, -3, ...$. What's the limit of that? Maybe you prefer the sequence: $0, -1, 1, -2, 2, -3, 3, ...$. Does it matter?

3) Yes, the intersection of two countable sets will be countable or maybe finite. Less obviously, so is the union. This is still true even if all of the elements are distinct and the union naively has size $\infty + \infty$. Possibly more surprisingly, the Cartesian product of two countable sets (the set of all pairs) is also countable even though naively it has size $\infty \times \infty$. You might start to think that you cannot get bigger but the set of all subsets of a set (called its power set) is always bigger than the set itself. So, there is no biggest infinity.

Note that the symbol $\infty$ is not normally used in this context. Countable infinity is usually indicated by the Hebrew letter Aleph with subscript $0$: $\aleph_0$; this often called "aleph null". It is also equal to "beth null": $\beth_0$. Other subscripts indicate bigger infinities but after $0$ they might or might not be the same. See the Continuum Hypothesis that I mentioned above.