This reply to jfgw's questions is very late, I'm afraid - but hopefully better late than never!
jfgw wrote: cinelli wrote:
As a belated Christmas present for those who would like an entertaining and thought-provoking explanation of countable and uncountable infinities, I give you Eddie Woo:https://www.youtube.com/watch?v=cgpDVOZpyrI
Am I missing something or is this complete bunkum? Mr. Woo is creating a list with lots of gaps in it and is proving that there are gaps in it.
To state the obvious, I already knew that the list of three numbers was not a complete list of all of the 1000 possible such numbers that exist.
With a list of length n, you need n decimal places. The number of numbers (of value at least 0 but less than 1) that exist with n decimal places is 10^n. As n increases, 10^n increases a lot faster. As n increases, your list of n numbers becomes an increasingly small fraction of the entire set of 10^n numbers that exist. There are (10^n)-n numbers not on your list.If n is infinity, there will be an infinite number of numbers not on your list.
Always being able to find one of them does not prove that the list is uncountable.
While the sentence I've emboldened looks very plausible, I'm afraid the idea that it follows from what the previous paragraph says is wrong - it doesn't. The flaw is that it assumes that the answer about the limiting infinite case (i.e. infinite-length lists of infinite-place decimal numbers) is equal to the limit of the answers about the finite cases (i.e. length-N lists of N-place decimal numbers), and that isn't necessarily true.
As an example in which the emboldened statement is not just an invalid deduction, but actually false: consider pairs
of integers in the range 0-N, rather than length-N sequences
of integers in the range 0-9. If I look at a list of N such pairs, it's easy to see that the list can only contain N of the pairs, while there are (N+1)^2 possible pairs. Therefore the list must always be missing (N+1)^2 - N = N^2 + N + 1 of the possible pairs (or more if the list contains duplicates), which increases without limit as N rises. And the fraction of the pairs that it includes is N/((N+1)^2) < (N+1)/((N+1)^2) = 1/(N+1), which is an increasingly small fraction.
All of that exactly parallels your argument in the paragraph before the emboldened sentence, so if the emboldened sentence followed from it, it would be just as valid a deduction about listing pairs of non-negative integers as about listing sequences of decimal digits - the growth rates of (10^N) - N and N^2 + N + 1 aren't identical, but both increase without limit very satisfactorily as N rises. So the limit of the answers about the finite cases is infinite in both cases... But the answers about the limiting infinite case are different: at least when written out fully and correctly (Eddie Woo's talk contains a bit of handwaving that skates over some details, which I'll get onto), Cantor's diagonal argument shows that no matter what infinite list of infinite-length sequences of decimal digits one proposes, there is a procedure to construct an infinite-length sequence of decimal digits that isn't in the list, but it is easy to construct an infinite list of pairs of non-negative integers that contains every pair of non-negative integers - formatting it with line breaks to show how it is constructed, it starts:
(0,2), (1,1), (2,0),
(0,3), (1,2), (2,1), (3,0),
(0,4), (1,3), (2,2), (3,1), (4,0),
(0,5), (1,4), (2,3), (3,2), (4,1), (5,0),
So there are two cases (listing sequences of decimal digits, and listing pairs of non-negative integers) in which everything you've stated in the preceding paragraph is true (apart from the exact function of N that increases without limit as N rises), and yet the deduction you try to make leads to a true statement in one case (it is impossible to list all sequences of decimal digits) and a false statement in the other (it is not impossible to list all pairs of non-negative integers). The only resolution of that is that no matter how plausible the deduction looks, it's not a valid deduction.
Looked at another way, a summary of the problem is that infinity is not actually a number (*), but instead usually shorthand for statements about limiting behaviour. It has properties that mean it can be treated like an actual number in some circumstances, but those properties do not include being able to substitute it in all formulas that are true about actual numbers. Things one says involving infinity therefore ultimately need justification in terms of arguments about limiting behaviour.
(*) Or at least, it's not actually a number in any of the usual number systems such as the integers, the rationals, the real numbers or the complex numbers. There are number systems such as the cardinal numbers, the ordinal numbers and the surreal numbers (I kid you not!) in which it is an actual number - or more precisely it's many actual numbers, not just one of them. But those systems have rules of their own about arithmetic and algebraic manipulations.
jfgw wrote:Another possible refutation is that some numbers may be represented in different ways. For example, is 0.368199999999999... = 0.368200000000... ? If so, there are an infinite number of numbers which may be represented in two different ways.
Yes, it is the case that 0.368199999999999... = 0.368200000000... There are various standard arguments and counterarguments about that - e.g.:
"If a=0.368199999999999... is different from b=0.368200000000..., then their average (a+b)/2 is a number that lies strictly between them. How do you write that down?"
"Easy, nought point three six eight one, then nines going on for ever, then a final five."
"How on earth do you have something that comes after
something else that goes on forever???"
"Why shouldn't I? Think of the classic race between Achilles & the tortoise argument - that looks at a sequence of stages in the race that goes on forever, but the endpoint of the race comes after all of them."
etc, etc, etc.
But the proper resolution of the problem IMHO lies in recognising that the 'infinite decimal ellipsis' notation used in "0.368199999999999..." and "0.368200000000..." involves infinity, and it's no exception to what I say above about statements involving infinity generally being shorthand for stuff about limits. I.e. "0.368199999999999... = 0.368200000000..." is shorthand for:
"the limit of the sequence 0.3, 0.36, 0.368, 0.3681, 0.36819, 0.368199, 0.3681999, 0.36819999, 0.368199999, ... is equal to the limit of the sequence 0.3, 0.36, 0.368, 0.3682, 0.36820, 0.368200, 0.3682000, 0.36820000, 0.368200000, ..."
Showing that those two limits are equal involves deep-diving into the definitions of limits and of real numbers in analysis, and I don't propose to give the required course in analysis here! But it can be done...
So what that comes down to is basically that 0.368199999999999... = 0.368200000000... is a consequence of what we define the notations "0.368199999999999..." and "0.368200000000..." to mean. It's actually a property of the notation rather than of the number - as an example, written in ternary representation, 1/3 has two representations "0.02222..." and "0.10000...", while written in decimal notation, it only has one representation "0.33333...". And the involvement of infinity and limits is also a property of the notation - all of those involve infinity and limits because of the ellipses in them, but written as a rational number "1/3" (or "2/6" or "3/9" or many other possibilities) or as a finite-length ternary number "0.1" (or "0.10" or "0.100" or many other possibilities), it doesn't involve infinity or limits.
Distinctions between notations and the numbers they represent tend to get blurred by the shorthand in the language we use - an adjective in front of the word can refer to either (e.g. "Roman number", "binary number" and "decimal number" are all describing the notation, while "rational number", "real number" and "complex number" are all describing the number itself). The shorthand is necessary, as phrases like "numbers written in binary notation" and "the limit of the sequence 0.3, 0.36, 0.368, 0.3681, 0.36819, 0.368199, 0.3681999, 0.36819999, 0.368199999, ..." are far too cumbersome for normal use - but occasionally one has to expand it for a particular purpose. The purpose of working out whether "0.368199999999999... = 0.368200000000..." is one of those occasions...
Anyway, the fact that some numbers have more than one decimal representation is indeed an awkward point about Cantor's diagonal argument as Eddie Woo presents it. There are various ways to fix the awkwardness, but I think the simplest one is probably to construct the number that isn't in the proposed list by adding 2 (rather than 1) to the digit in the Nth decimal place of the Nth number of the proposed list (ignoring carry-outs, so 8 becomes 0 and 9 becomes 1). Basically, it is fairly straightforward to produce an argument about the limits involved that any number x with decimal representation starting 0.3681... lies in the range 0.3681 <= x <= 0.3682, so adding 2 puts 'clear air' between the number you're constructing and the Nth number of the proposed list, while adding 1 doesn't and so needs more complex arguments to fully prove that the constructed number isn't in the list.
jfgw wrote:I understand the concept of proof by contradiction:
1. Make an assumption;
2. Use sound mathematical procedures to show that the assumption leads to a contradiction;
3. Infer that, due to the contradiction, the assumption must be wrong.
Let's do it:
1. Make an assumption:
I will cheat here and choose a countable set and see if the "proof" fails.
Make a complete list of all of the non-negative decimal numbers less than 1 by counting up and reversing the digits:
Assume that this list is countable (which, in this case, it clearly is as it is derived directly from the list of non-negative integers).
2. Use sound mathematical procedures to show that the assumption leads to a contradiction:
Cantor's diagonal argument may be applied to the above list and will produce a number not on that list. (I have stated previously why I do not think that this is a sound mathematical procedure but let's stick with it.)
3. Infer that, due to the contradiction, the assumption must be wrong:
Conclude that, since the "complete" list is not actually complete, that there is a contradiction and the original assumption (that the list is countable) must be wrong.
This countable list has been shown to be uncountable!
From the above, it appears that "proof by contradiction" may be used to prove that Cantor's argument is a load of squit.
No. The problem is that you've misidentified the assumption that you made in step 1. You didn't assume
that your list is countable - you constructed
it to be countable. The assumption you made but failed to identify is that your list is complete - that it includes every
number in the range 0 to 1.
Cantor's diagonal argument as presented by Eddie Woo constructs the number 0.111111... That number is indeed not in your list - it is not a digit-reversed integer followed by infinitely many zero digits. So the proof by contradiction works, but its conclusion is not that your constructed-to-be-countable list is actually uncountable, but rather that your assumed-to-be-complete list is actually incomplete.
jfgw wrote:Apart from the requirement that n >= 10^n when n is infinity for the diagonal argument to work, there is also the problem of making a complete list of an infinite set. I suggest that an infinite set is, by definition, one that can never be completed.
the complete list is Someone Else's Task - Cantor's argument is about showing that it's impossible, even for someone like Achilles who can complete as infinite set of subtasks in a finite period! ;-