Can you transform a countably infinite set to an uncountable one?

  • I
  • Thread starter BWV
  • Start date
  • #1
BWV
1,467
1,783
Is a simple one to one mapping from ℤ to ℝ such as exp[ℤ] countable?

If so, what about a one to many mapping like the set of all integer roots of ℕ, either for a finite set of integers (say 1 to 100) or the entire infinite set?

at the extreme would be the set of all non-transcendental irrational numbers - is this uncountable?
 
Mathematics news on Phys.org
  • #2
BWV said:
Is a simple one to one mapping from ℤ to ℝ such as exp[ℤ] countable?
Yes, what you're describing as exp[Z] is a countably infinite set.
BWV said:
If so, what about a one to many mapping like the set of all integer roots of ℕ, either for a finite set of integers (say 1 to 100) or the entire infinite set?
The roots of a finite number of integers form a finite set. As for the roots of all of the positive integers, that seems to me to be a countably infinite set. To confirm this you would need to come up with a scheme for numbering the roots, possibly akin to the way the rational numbers between 0 and 1 are paired with the positive integers.
BWV said:
at the extreme would be the set of all non-transcendental irrational numbers - is this uncountable?
Seems likely to me.
 
  • Like
Likes BWV
  • #3
Mark44 said:
The roots of a finite number of integers form a finite set.
Thanks, what I meant is a finite number of roots of all of ℕ, vs the set of all ℕ of ℕ

Which I am guessing is countable as you could create an ℕ x ℕ matrix where the columns are the n-root of the number in the first column
 
Last edited:
  • #4
BWV said:
Is a simple one to one mapping from ℤ to ℝ such as exp[ℤ] countable?
That's a surprising question: what definition of countability are you using that does not make this trivial?

BWV said:
If so, what about a one to many mapping like the set of all integer roots of ℕ, either for a finite set of integers (say 1 to 100) or the entire infinite set?
Are you familiar with the normal proof of the cardinality of the positive rationals (not just those less than one) e.g. https://math.oxford.emory.edu/site/math125/rationalEnumeration/ ? Simply consider ## a^{1/b} ## instead of ## \frac a b ##.

BWV said:
at the extreme would be the set of all non-transcendental irrational numbers - is this uncountable?
What is the definition of a transcendental number? Hint: a number that is not an (...) number.
So a number that is non-transcendetal is not(not an (...) number) i.e. it is an (...) number.
What is the cardinality of the (...) numbers?
 
  • Informative
Likes BWV
  • #5
BWV said:
Can you transform a countably infinite set to an uncountable one?
Yes: take its power set.

This was Cantor's first application of the diagonal argument to prove the existance of sets with cardinality greater than that of the natural numbers, the more familiar application to the reals using strings of decimal digits came later.
 
  • Informative
  • Like
Likes e_jane, BWV and jbriggs444
  • #6
pbuk said:
Are you familiar with the normal proof of the cardinality of the positive rationals (not just those less than one) e.g. https://math.oxford.emory.edu/site/math125/rationalEnumeration/ ? Simply consider ## a^{1/b} ## instead of ## \frac a b ##.

"All roots of natural numbers" might also include, for example, [itex]i[/itex], [itex]-1[/itex] and [itex]-i[/itex] as fourth roots of 1, so its not that simple. Even if we restrict attention to real roots, we should also include -1.
 
  • #7
pasmith said:
Even if we restrict attention to real roots.
Which we should, per the OP:
BWV said:
Is a simple one to one mapping from ℤ to ℝ...

pasmith said:
we should also include -1.
I am not sure that is what the OP had in mind, my guess is that he was talking about principal real roots. But even if not this clearly only adds a countable number of elements into the range (the negative of all the even roots).

Even if we include complex roots, we still only end up with a countable subset as our range because we start with ℕxℕ and then we have less than |ℕ| mappings for any element.
 
  • #8
Of course if you could find a mapping to an uncountable set smaller than the power set mapping you would have solved the continuum hypothesis - in the negative, which would be a surprise.
 
  • Haha
Likes e_jane
  • #9
Ok another dumb question beyond my pay grade:

take ℚ on (0,1) as A then let B be the set of all the permutations of digits for each element of A (so, for example, the element .12 in A, B would consist of {.12, .21})

my guess would be this is uncountable like the power set? As there are arbitrarily large repeating decimals and Cantor's diagonalization would apply, this procedure would map to ℝ?
 
  • #10
BWV said:
Ok another dumb question beyond my pay grade:

take ℚ on (0,1) as A then let B be the set of all the permutations of digits for each element of A (so, for example, the element .12 in A, B would consist of {.12, .21})

my guess would be this is uncountable like the power set? As there are arbitrarily large repeating decimals and Cantor's diagonalization would apply, this procedure would map to ℝ?
My guess is that B is countable. It would be a nice exercise to prove this. One way or the other.
 
  • Like
Likes e_jane and BWV
  • #11
BWV said:
take ℚ on (0,1) as A then let B be the set of all the permutations of digits for each element of A (so, for example, the element .12 in A, B would consist of {.12, .21})

my guess would be this is uncountable like the power set? As there are arbitrarily large repeating decimals and Cantor's diagonalization would apply, this procedure would map to ℝ?
If we had, for instance, 0.12121212... = ##\frac{12}{99}## then the set of all permutations of those digits would seem to be an uncountable set. That particular set would be a subset of ##\mathbb{R}## but it would share the cardinality of ##\mathbb{R}##.

If you wanted to get fancier, ##\frac{123456789}{9999999999}## has a set of permutations that is more inclusive, though it still misses some.
 
  • Informative
  • Like
Likes PeroK and BWV
  • #12
jbriggs444 said:
If we had, for instance, 0.12121212... = ##\frac{12}{99}## then the set of all permutations of those digits would seem to be an uncountable set. That particular set would be a subset of ##\mathbb{R}## but it would share the cardinality of ##\mathbb{R}##.

If you wanted to get fancier, ##\frac{123456789}{9999999999}## has a set of permutations that is more inclusive, though it still misses some.
But is there any irrational number that could not be generated by a permutation of the digits of a rational number?
 
  • #13
PeroK said:
My guess is that B is countable. It would be a nice exercise to prove this. One way or the other.
The guess was wrong. As shown above.
 
  • Like
Likes jbriggs444
  • #14
BWV said:
But is there any irrational number that could not be generated by a permutation of the digits of a rational number?
As long as we handwave away the pesky details of the decimal point and the minus sign, every irrational number is accounted for, yes.

Consider an arbiterary irrational number. Express it as a decimal digit string. For each of the ten possible digits, this string will have:

1. No matching digits. [For instance, it might lack any 2's and 3's]
2. Infinitely many matching digits. [The usual case]
3. Only finitely many matching digits. [For instance, it might have a grand total of seven 7's]

We construct a matching rational number by beginning with a decimal expansion which includes all of the digits that occur only finitely many times, each with the appropriate count.

We then tack on a repeating sub-sequence consisting of those digits which appear infinitely many times.
 
  • Like
Likes BWV and PeroK
  • #15
Top tip: when considering problems in number theory it is often helpful to remember that there is nothing special about our familiar decimal numbering system and it can sometimes be clearer to work with the simplest system of all: binary.

The question in #9 then becomes "is there any real number that cannot be represented by a (possibly infinite) string of binary digits?" and the answer is obvious.
 
  • Like
Likes jbriggs444, BWV and PeroK
  • #16
pbuk said:
Top tip: when considering problems in number theory it is often helpful to remember that there is nothing special about our familiar decimal numbering system and it can sometimes be clearer to work with the simplest system of all: binary.

The question in #9 then becomes "is there any real number that cannot be represented by a (possibly infinite) string of binary digits?" and the answer is obvious.
Indeed. Every irrational number has a binary expansion containing both infinitely many zeroes and infinitely many ones.

It suffices to pick one rational number whose binary expansion contains infinitely many of both digits. Every rational number whose binary expansion is non-terminating will have this property. In particular, we could use ##\frac{1}{3}## = 0.010101... (base 2).

Every irrational will have a binary expansion which is a permutation of those digits.
 
  • Like
Likes PeroK and BWV

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
8
Views
2K
Replies
4
Views
724
  • Calculus and Beyond Homework Help
Replies
1
Views
552
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
1K
Replies
5
Views
2K
Replies
6
Views
1K
  • Set Theory, Logic, Probability, Statistics
2
Replies
55
Views
5K
  • Set Theory, Logic, Probability, Statistics
Replies
8
Views
2K
Back
Top