4 ms·

Not a mathematician, but "uncountably many" sounds like a loaded phrase unique to the field of mathematics. How does "uncountably many" differ from "infinitely

Not a mathematician, but "uncountably many" sounds like a loaded phrase unique to the field of mathematics. How does "uncountably many" differ from "infinitely many"? Are we not sure that it goes on forever or do we know that it's just an extremely large finite set?

srl 13y ago
The natural numbers (1, 2, 3, etc.) are of course "infinite" - however, they are also "countable". (For any natural number you pick, if you count long enough, you'll eventually get to it.) That doesn't mean you'll ever have counted /all/ the natural numbers, but you can count to any arbitrary one. For contrast, the real numbers, although also infinite, are "uncountable" - any way you start counting, there are real numbers that you will /never/ reach.
nairteashop 13y ago
This is indeed a "technical" term in math. Wolfram has a good definition for what a "countably" infinite set is: http://mathworld.wolfram.com/CountablyInfinite.html http://mathworld.wolfram.com/CountablyInfinite.html
ColinWright 13y ago
It is a precise term with a precise meaning. You can look it up and found many, many explanations online, some of which will be right, few of which will be truly helpful. Let me add to them. If you can put a set into one-to-one correspondence with the counting number (which are 1, 2, 3, and so on) then we call the set "countable" or "countably infinite". Examples include (but are not limited to): * The even counting numbers: 2, 4, 6, 8, 10, and so on; * The integer squares: 0, 1, 4, 9, 16, 25, and so on; * The primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, and so on; * The rational numbers (fractions); * Finite strings made from a finite collection of symbols; ... and more. You may choose to think about how matchings can be made between each of these and the counting numbers, or each with the others - some ingenuity required. However, there are infinite collections that cannot be put into one-to-one correspondence with the counting numbers. Examples include: * Infinite non-terminating strings of 0s and 1s; * The reals; * All sets (finite and infinite) of counting numbers; ... and more. Such infinite collections, since they cannot be matched up with the counting numbers, are called "Uncountably Infinite Sets". To prove that such collections can never be matched up with the counting numbers is a typical exercise for 1st year undergrads in mathematics, or for precocious mathematics enthusiasts. I first met it when I was about 8 years old and reading Martin Gardner. The usual proof is Cantor's "Diagonalisation Argument"[0][1], and you can find a version of that here: http://www.solipsys.co.uk/new/CantorVisitsHilbertsHotel.html http://www.solipsys.co.uk/new/CantorVisitsHilbertsHotel.html That includes a genuine proof of the existence of a set that is infinite, and cannot be put in one-to-one correspondence with the counting numbers. Still, many people find that unconvincing. I personally prefer Cantor's first argument that there exist transcendental numbers, which is equivalent. Here it is, adapted to show that any list of numbers is incomplete. You'll need to concentrate: Take any list of numbers: c_0, c_1, c_2, etc. Take any interval [a0,b0], and cross out numbers from your list until you find one, say, c_i, in the interval (including an endpoint). Take some strict sub-interval [a1,b1] within [a0,b0] such that a0<a1, b1<b0, and c_i is not in [a1,b1]. Now continue crossing off numbers, and each time you find one in your current interval, take a sub-interval to exclude it. The left hand end-points, a0, a1, a2, etc, form a strictly increasing sequence of points. This sequence is bounded above, so it has an upper bound. Consider the least upper bound. This cannot be on your original list, because everything was, at some point, excluded. Hence your original list cannot be complete. And in case you think I can only ever construct one missing number, I can actually construct infinitely many missing numbers. At each stage instead of taking just one sub-interval, I take two subintervals, each excluding the number from your list. I'm intending to write all this up soon, so if you're interested, I can let you read a draft as a way of improving your understanding, and giving me an attentive proof-reader. [0] Not to be confused with the diagonal path in the argument that the fractions are countable. [1] http://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument http://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument
xyzzyz 13y ago
For a set S being uncountable means that for any list of elements s_1, s_2, ... of S, there will always be some element of S that's not on the list. For instance, infinite sequences of bits are uncountable: for suppose that there's any list s_1, s_2, ... of infinite sequences of zeroes and ones. Let x be a sequence that has 0 on i-th position if i-th sequence on the list has 1 on the i-th position, and 1 otherwise. Then x is not on the list: for suppose x would be on the list as some s_n. Then by definition, x has 0 on n-th position if s_n has 1 on n-th position, and 1 otherwise, but s_n is x, a conradiction. For example, if you consider a list: 1: 01011001010100... 2: 01110001001001... 3: 11010110100110... 4: 10010110101010... and further elements, then x would start with 1010...
hondje 13y ago
Everyone has already answered with what a countable set is, so I would just add that the answer to your second question is uncountable sets are always infinite in size. Any extremely large set would be finite and so countable.
ColinWright 13y ago
In addition to my other reply, see also this: https://news.ycombinator.com/item?id=5232822 https://news.ycombinator.com/item?id=5232822

srl 13y ago

The natural numbers (1, 2, 3, etc.) are of course "infinite" - however, they are also "countable". (For any natural number you pick, if you count long enough, you'll eventually get to it.) That doesn't mean you'll ever have counted /all/ the natural numbers, but you can count to any arbitrary one. For contrast, the real numbers, although also infinite, are "uncountable" - any way you start counting, there are real numbers that you will /never/ reach.

nairteashop 13y ago

This is indeed a "technical" term in math. Wolfram has a good definition for what a "countably" infinite set is: http://mathworld.wolfram.com/CountablyInfinite.html http://mathworld.wolfram.com/CountablyInfinite.html

ColinWright 13y ago

It is a precise term with a precise meaning. You can look it up and found many, many explanations online, some of which will be right, few of which will be truly helpful. Let me add to them. If you can put a set into one-to-one correspondence with the counting number (which are 1, 2, 3, and so on) then we call the set "countable" or "countably infinite". Examples include (but are not limited to): * The even counting numbers: 2, 4, 6, 8, 10, and so on; * The integer squares: 0, 1, 4, 9, 16, 25, and so on; * The primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, and so on; * The rational numbers (fractions); * Finite strings made from a finite collection of symbols; ... and more. You may choose to think about how matchings can be made between each of these and the counting numbers, or each with the others - some ingenuity required. However, there are infinite collections that cannot be put into one-to-one correspondence with the counting numbers. Examples include: * Infinite non-terminating strings of 0s and 1s; * The reals; * All sets (finite and infinite) of counting numbers; ... and more. Such infinite collections, since they cannot be matched up with the counting numbers, are called "Uncountably Infinite Sets". To prove that such collections can never be matched up with the counting numbers is a typical exercise for 1st year undergrads in mathematics, or for precocious mathematics enthusiasts. I first met it when I was about 8 years old and reading Martin Gardner. The usual proof is Cantor's "Diagonalisation Argument"[0][1], and you can find a version of that here: http://www.solipsys.co.uk/new/CantorVisitsHilbertsHotel.html http://www.solipsys.co.uk/new/CantorVisitsHilbertsHotel.html That includes a genuine proof of the existence of a set that is infinite, and cannot be put in one-to-one correspondence with the counting numbers. Still, many people find that unconvincing. I personally prefer Cantor's first argument that there exist transcendental numbers, which is equivalent. Here it is, adapted to show that any list of numbers is incomplete. You'll need to concentrate: Take any list of numbers: c_0, c_1, c_2, etc. Take any interval [a0,b0], and cross out numbers from your list until you find one, say, c_i, in the interval (including an endpoint). Take some strict sub-interval [a1,b1] within [a0,b0] such that a0<a1, b1<b0, and c_i is not in [a1,b1]. Now continue crossing off numbers, and each time you find one in your current interval, take a sub-interval to exclude it. The left hand end-points, a0, a1, a2, etc, form a strictly increasing sequence of points. This sequence is bounded above, so it has an upper bound. Consider the least upper bound. This cannot be on your original list, because everything was, at some point, excluded. Hence your original list cannot be complete. And in case you think I can only ever construct one missing number, I can actually construct infinitely many missing numbers. At each stage instead of taking just one sub-interval, I take two subintervals, each excluding the number from your list. I'm intending to write all this up soon, so if you're interested, I can let you read a draft as a way of improving your understanding, and giving me an attentive proof-reader. [0] Not to be confused with the diagonal path in the argument that the fractions are countable. [1] http://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument http://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument

xyzzyz 13y ago

For a set S being uncountable means that for any list of elements s_1, s_2, ... of S, there will always be some element of S that's not on the list. For instance, infinite sequences of bits are uncountable: for suppose that there's any list s_1, s_2, ... of infinite sequences of zeroes and ones. Let x be a sequence that has 0 on i-th position if i-th sequence on the list has 1 on the i-th position, and 1 otherwise. Then x is not on the list: for suppose x would be on the list as some s_n. Then by definition, x has 0 on n-th position if s_n has 1 on n-th position, and 1 otherwise, but s_n is x, a conradiction. For example, if you consider a list: 1: 01011001010100... 2: 01110001001001... 3: 11010110100110... 4: 10010110101010... and further elements, then x would start with 1010...

hondje 13y ago

Everyone has already answered with what a countable set is, so I would just add that the answer to your second question is uncountable sets are always infinite in size. Any extremely large set would be finite and so countable.

ColinWright 13y ago

In addition to my other reply, see also this: https://news.ycombinator.com/item?id=5232822 https://news.ycombinator.com/item?id=5232822