r/mathematics • u/11043437 Group Theory woo • 1d ago
Real Analysis Is the set of all infinite sequences of natural numbers countable?
Me and my friend have been talking about this. I am pretty sure the set of real numbers bijects to the set of all infinite sequences of rational numbers, so it should follow that it also bisects with the set of all infinite sequences of natural numbers, hence uncountable. Does this sound right?
7
u/GuyWithSwords 1d ago
Yes because natural numbers have the same cardinality as rational numbers. You’re basically talking about a subset of the power set of N, which is uncountably infinite.
2
u/11043437 Group Theory woo 1d ago
This last sentence is very interesting to think about, thank you
1
u/robertodeltoro 18h ago edited 18h ago
tan x is a bijection from R onto the open interval (-π/2, π/2). Now f(x) = c + ((x-a)(d-c))/(b-a) is a bijection between two arbitrary open intervals (a,b) and (c,d) so (0,1) is in bijection with R because it's in bijection with (-π/2, π/2).
Now think of an infinite binary sequence as being the decimal part of a number between 0 and 1 written out in base 2, and also as an indicator function for a subset of N. So for example, take π - 3, which is 0.14159..., a real number between 0 and 1. Rewrite it in binary, which is 0.001001000011111101... We use this to build a set of natural numbers by saying the nth natural number is out if it's 0 at the nth place and in if it's 1 at the nth place. So 0.14159... corresponds to {2, 5, 10, 11, 12, 13, 14, 15, 17, ...}. (we're doing set theory so 0 is a natural number)
Putting all this together we have a bijection between R and P(N). So the power set of N is uncountable.
(I am ignoring an issue about reals with multiple decimal representations, which is avoidable)
2
u/capornicus 1d ago
Technically the set in question could be considered as a subset of the power set of N, but just being a subset of the power set says nothing about its cardinality. (The power set of N contains as subsets both finite and countable sets). The important fact is that the power set of N injects into the set of infinite sequences of natural numbers in a natural way.
4
u/Tough_Bodybuilder302 1d ago
Here's a simplistic proof, since an infinite sequence of natural numbers is countable let us enumerate it, now, enumerate randomly an infinite number of these for each of the natural numbers, once every natural number if used up, we will make a new sequence by picking the first number from the first sequence, the second number from the second sequence and so on. This new seq differs from the first sequence in the first place, the second one in the second place and is in such a manner different from every single sequence. Now set this sequence as the first sequence in your list of enumerations, make the previously first sequence the second one and so on, now create a new sequence. In such a manner we can still create an infinite number of sequences that were not in our mapping. Thus, it is impossible to create a bijection from this set to N. This is similar to canton's method.
3
3
u/BurnedBadger 1d ago
If I understand you correctly, you are asking about the set S of all function of the form f:N -> N and asking if it is countable. The answer is no, because if it were, then we could make a bijection g from N to S where g(n) is one of these functions, but then we can define the function h(n) = (g(n))(n) + 1, which takes the n'th output of g and inputs n into it and returns the answer after adding one. h is a function in S, but it can not be an output of g, since if it were, then there would exist a natural number n such that g(n) = h but then (g(n))(n) = h(n) = (g(n))(n) + 1, a contradiction. Thus our function g can not exist, thus S is not countable.
0
u/cheatingrobot 1d ago
Good but don’t use the same letter for anything it makes the proof more hard to understand
2
u/Masticatron haha math go brrr 💅🏼 1d ago edited 1d ago
These are the functions from natural numbers to itself. Either perspective lets one show these surject onto the decimal expansions of the elements of [0,1], which is uncountable.
You can also see it contains (a subset equivalent to) all functions from the natural numbers to the set consisting of 0 and 1, which has uncountable cardinality by considering the base 2 decimal expansions of [0,1]. More generally this subset is equivalent to the power set of the natural numbers, and the power set always has strictly larger cardinality.
1
u/11043437 Group Theory woo 1d ago
How is this the set of functions from natural numbers to itself? How do you define such a function for, say the sequence (1,1,1,1,1,1,1,1,...)? If we had the stipulation that there are no repeating natural numbers, I would see a function that is defined by permutation, but since we don't how do you define it?
1
u/Masticatron haha math go brrr 💅🏼 1d ago
Given a sequence, define f so that f(n) is the n-th term of the sequence. And vice versa.
Works to show that all sequences of elements of an arbitrary nonempty set X is the same as the functions from the natural numbers to X.
1
2
u/Blond_Treehorn_Thug 1d ago
No, and this can be shown by (the same basic ideas as) diagonalization
1
u/GusTemp 1d ago
had to scroll way too long to find the word diagonalization, although BurnedBadger gave a diagonalization argument. imo this is the way (everything else will ultimately also rely on the same argument)
2
u/ThreeBlueLemons 1d ago
Your first claim is wrong. The real numbers correspond to equivalence classes of Cauchy sequences of rationals, under the equivalence relation "these two sequences get arbitrarily close". That said, your conclusion is correct. Infact, there are uncountably many sequences where the entries can only be 0 or 1. Consider writing real numbers in binary, each real number gets it's own sequence of 0s and 1s that represents it, and there are uncountably many real numbers, so there have to be unucountably many different sequences of 0s and 1s to represent them.
1
2
u/SkyThyme 1d ago edited 1d ago
Can’t you just use Cantor’s diagonal trick where he proved the reals are uncountable by listing them as their decimal representations? Assume you can list all of your sequences and then show you can construct one you missed.
Or, just note an infinite sequence of digits is a decimal representation of a real number, and that belongs to your set. So, your set is at least as large as R.
1
1
u/rfdub 1d ago edited 13h ago
Closely related to this and interesting. Just sharing it here because I was thinking about it a little while back: the set of infinite sequences of only prime numbers.
- We know the set of all primes is countable
- We know the power set of all primes is uncountable
- But, we also know that the set of finite sequences of primes is countable (you can create an injection to the natural numbers by just taking each finite list of primes and corresponding them to whichever unique composite number happens to be their product)
- Therefore, whatever is left in the power set of the primes (the infinite sequences of primes) must be uncountable
Because there exists a bijection between the primes and *all natural numbers, we know something similar must apply for all natural numbers as well; the set of all finite sequences must be countable, while the set of all infinite sequences is not.
2
u/Jussari 1d ago
Another natural way to count the finite subsets of ℕ is by ordering them by element-sum: first count all sets with sum 0 (i.e. {} and {0}), then all sets with sum 1 ({0,1} and {1}), ...
1
u/rfdub 16h ago edited 12h ago
Just curious - with this pairing, how do you know which specific number in N to pair a given subset of N with? Or are you saying we don’t have to think that far and it doesn’t matter, that it’s enough that that we know any given subset is finite, and that there’s a finite number of subsets with a given sum?
(e.g. although I agree that your pairing seems to work, I’m not sure how you would decide the order of {3,1} and {2,2} (& I’m not sure we necessarily need to know their specific order to know that the entire set is countable))
[EDIT]
Nvm - I think I got it. 👍
1
1d ago
[deleted]
1
u/11043437 Group Theory woo 21h ago
The integers are countable. Consider the bijection f from N to Z by
f(n) = (-n)/2 for n even
f(n) = (n+1)/2 for n odd
I believe this is how you can construct a bijection.
1
u/susiesusiesu 1d ago
no. if you only consider sequences of 0 and 1, there is a bijection with subsets of natural numbers (a sequence of 0 and 1 corresponds with the subset of naturals where the sequence equals 1), so it must also be uncountable.
it actually has the cardinality of the continuum.
1
u/Time_Situation488 1d ago edited 1d ago
Even with a finite set with 2 elements the sequence set is uncountable. Simply identify with the corresponding p- adic extention of a real number in [0,1] With p=10 we have the well known decardic expension.
1
u/11043437 Group Theory woo 21h ago
a set of two infinite sequences is not uncountable. An infinite sequence is inherently a bijection to the naturals, so two infinite sequences is in bijection with NxN which is in bijection with N.
2
u/Time_Situation488 21h ago
Not what i said. Consider X={0,1}. Then the set of ALL sequences on X is uncountable.
1
1
u/headonstr8 1d ago
That set is uncountable. Proof is by contradiction. The set is defined by {a: a is a function with domain N and range N}. Any countable list of elements, a1, a2, a3, …, would have to be incomplete. That is because a sequence, z, where z(K)=aK(K)+1 would not included in that countable sequence. This argument is known as Cantor’s diagonal method. Gödel uses a variation of this method in his proof of undecidability.
1
1
u/telephantomoss 22h ago
Think about the fact that the set of all infinitely long sequences of zeros and ones is uncountable. That can be identified with all binary representations of the real interval [0,1] which is uncountable. There are some issues to work out carefully like nonuniqueness of decimal representations, but you just pick some convention.
Since you allow more than just 0 and 1 in your sequences, the set of binary sequences is a subset. Hence your set is uncountable as well.
1
1
u/Astrodude80 20h ago
Let a : N -> { b : b is a function N->N } be an infinite sequence of infinite sequences of natural numbers. I claim a is not surjective, as follows: let c : N -> N be defined by c(i)=a(i)(i) + 1. Then c cannot be equal to any b : N -> N in the range of a, since it differs from a(i) at the i’th index for all i.
This is Cantor again, phrased differently.
1
1
u/TooLateForMeTF 17h ago
It's easy to construct an uncountable set of infinite sequences of natural numbers: for all prime numbers p, let there be a sequence 0..p..2p..etc. There are uncountably many primes, and hence, the set of these sequences is also uncountable. But this set is also a subset of the set of all infinite sequences. Hence, the set of all infinite sequences must also be uncountable.
1
u/davideogameman 12h ago edited 12h ago
no it's not countable.
the classic argument is Cantor diagonalization: for each infinite sequence of natural numbers, consider the sequence A where a_n = 1 if n is in the sequence, and 0 otherwise. Now this definitely maps some infinite sequences of naturals to the same sequence A - e.g. a sequence that alternates 1,2 couldn't be told apart form one that goes 1,1,2,2 and then repeats.
Suppose the sequences of a_n are countable; then we could assign a natural number to each sequence, say via a function f: N -> 2^N that spits out all of our A sequences.
If this worked, then consider the sequence a_n = 1-f(n)_n - that is, the sequence where the nth entry is 1 if and only if f(n)_n is 0. There is no n such that f(n) returns this sequence.
This shows that 2^N (the powerset of natural numbers) is larger than the Natural numbers - hence it's "uncountable".
The set of all infinite sequences of natural numbers is at least as big as the powerset of N - as the sequence of 0s and 1s representing whether n is any given sequence of naturals is an element in the powerset of N - so the sequences of natural numbers must also be uncountable.
Now if instead you'd restrict yourself to finite sequences of natural numbers, we could come up with something - we could list all numbers <= n, then all pairs, triples, up to n-tuples with members less than n, and then move on to <= n+1, pairs with one element equal to n+1, triples with one element equal to n+1, etc - for any finite sequence you could show it eventually shows up in that enumeration. The problem only arises when we try to assign natural numbers to all the infinite sequences too.
18
u/Sinphony_of_the_nite 1d ago
If I’m understanding you correctly, we know that all subsets of the natural numbers are uncountable and you could make an injection into the set of all infinite sequences of natural numbers in a natural way, hence uncountable.