Remove ads

Introducing the LemonFools Personal Finance Calculators

Circle

UncleEbenezer
Lemon Quarter
Posts: 3400
Joined: November 4th, 2016, 8:17 pm
Has thanked: 352 times
Been thanked: 544 times

Re: Circle

#190296

Postby UncleEbenezer » December 31st, 2018, 8:24 pm

forlesen wrote:
No, I'm afraid your example only has a countably infinite number of points in it


D'oh! Yes, it's obviously countable! I think an extension of your argument probably rules out any generalization of my idea too.

Indeed. A set you define by enumerating numbers is going to be countable!
Suppose we have a set X of positive reals such that for all w in X, the subset Xw of all y in X such that y>w is countable, and X-Xw is uncountable. This is basically a less ambitious version of what I was aiming for with my specific construction, only asking for countable to the right, not necessarily finite.

I think we can count all of X, by considering the sequence w1, w2, w3, ... = 1/2, 1/4, 1/8, ... as before. For each of these wi, the set of points to the right is countable, and by taking the wi's far enough, for any X in X, there will be some wi less than x, so that x is in Xwi, and is hence counted, so X must (I think) be countable.

You're thinking countably. If the above works, it also disproves Xeno's construction.

Intuition and infinity are a dangerous mixture. Exercise to set you on the way: how would you extract finite or countable subsets of a Cantor set? It's (surprisingly) easy, but can challenge intuition.

Gengulphus
Lemon Quarter
Posts: 2806
Joined: November 4th, 2016, 1:17 am
Been thanked: 1413 times

Re: Circle

#190350

Postby Gengulphus » January 1st, 2019, 11:29 am

forlesen wrote:If this is correct, we would seem to end up with for any uncountable subset X of R*R, there is a line that partitions X into two uncountable halves (plus some points on the line).

I think that conclusion is correct, but your argument is a bit lacking. The way I would argue for it is, for U an uncountable subset of RxR:

For any real number r, we can partition U into the sets Tr, Ur and Vr whose X co-ordinates are < r, = r, and > r respectively. If Tr and Vr are both uncountable for any r, then the line x=r does the job and we're done.

Otherwise, for any real number r, at least one of Tr and Vr is countable (for the avoidance of doubt, I am using 'countable' to mean either finite or countably infinite - i.e. it doesn't imply infinite, and I'll more specifically say 'countably infinite' when needed).

Suppose there is no r such that Vr is countable. Then Tr is countable for any r, and in particular every one of the countably infinite sequence of sets ..., T(-2), T(-1), T0, T1, T2, T3, ... is countable. Therefore the union of all the sets in that sequence is countable - but U is that union (every point in U is in Ti for all values of i > its X co-ordinate). That contradicts U being uncountable, and therefore we can conclude that there is an r such that Vr is countable.

A symmetrical argument shows that there is an r such that Tr is countable. So there exist real numbers r1 and r2 such that Tr1 and Vr2 are both countable. Those numbers must be such that r1 <= r2, because if r1 > r2, then every point of U has X co-ordinate < r1, > r2 or both, making U equal to the union of Tr1 and Vr2 and so again contradicting its uncountability.

Consider the set S of r such that Tr is countable. It is non-empty, as it contains r1, and it has the upper bound r2 (since if s >= r, Ts is a superset of Tr and so also uncountable, so s is not in S), so it has a least upper bound l. This has the properties that:

* if r > l, Tr is uncountable (since if Tr were countable, r would be in S and so l would not be an upper bound of S);

* if r < l, Tr is countable (since if Tr were uncountable, then for any s > r, Ts would be a superset of Tr and also uncountable, so r would be a smaller upper bound of S).

Symmetrically, the set of r such that Vr is countable is non-empty (containing r2) and has the lower bound r1, so has a greatest lower bound m that has the properties if r < m, Vr is uncountable, and if r > m, Vr is countable.

If l > m, then r = (l+2m)/3 and s = (2l+m)/3 (the 1/3rd and 2/3rd points between them) have the properties that m < r < s < l, so Ts and Vr are both countable. But the union of Ts and Vr contains all points of U whose X co-ordinate is < s, > r or both, which is the whole of U, which again contradicts U's uncountability.

If l < m, then r = (l+m)/2 (the halfway point between them) has the properties that l < r < m, so Tr and Vr are both uncountable. That means that the line x=r has the property that there are uncountably many points of U on either side of it, so we're done in that case.

The only possibility that we're left with is that l = m. In that case, we can use an argument along your lines: l-1, l-1/2, l-1/4, l-1/8, ... are all less than l, so T(l-1), T(l-1/2), T(l-1/4), T(l-1/8), ... are all countable, and so the union of all those sets is countable, being a countable union of countable sets. But that union is Tl (any X co-ordinate that is less than l is also less than l-1/2^n for sufficiently large n), so that implies Tl is countable. Symmetrically, Vl = Vm is countable.

But we know that U is uncountable and is the disjoint union of Tl, Ul and Vl. Since Tl and Vl are countable, Ul must be uncountable. And that is as far as we can get by considering lines of constant X co-ordinate, because if we consider the example of a U that consists of a vertical line segment plus a countable number of points not on that line segment, it's easy to see that every line x=c (with c a constant) has the property that there are either a countable number of points to its left or to its right (or both in the case that it has the same X co-ordinate as the line segment). So for that example U, there is no line of constant X co-ordinate (i.e. vertical line) with an uncountable number of points of U on either side of it (and possibly some on it).

We have however concluded that given that U is uncountable, there is such a vertical line unless there exists an l such that Tl is countable, Ul is uncountable and Vl is countable. Now restrict our attention to Ul: this is an uncountable set of points all of whose X co-ordinates are all equal to l. Apply the same argument as above, apart from swapping the roles of the X and Y co-ordinates, and we can conclude that there is a line of constant Y co-ordinate (i.e. a horizontal line) such that the sets below it and above it are both uncountable, unless there is a unique such line y=c such that Ul consists of an uncountable number of points with Y co-ordinates = c, a countable number of points with Y co-ordinates < c and a countable number of points with Y co-ordinates > c. But that's impossible, because the set of points in Ul with Y co-ordinate = c consist at most of the single point (x,y) = (l,c).

So there is a horizontal line such that Ul contains an uncountable number of points above it and an uncountable number of points below it. Since Ul is a subset of U, U too has an uncountable number of points above it and an uncountable number of points below it - and so in all cases, there is either a horizontal or a vertical line (or both, of course) such that U contains an uncountable number of points on each side of it (plus possibly some on it).

Whew!

Gengulphus

forlesen
Lemon Pip
Posts: 73
Joined: November 4th, 2016, 11:14 pm
Has thanked: 3 times
Been thanked: 15 times

Re: Circle

#190441

Postby forlesen » January 1st, 2019, 6:03 pm

As you say, Whew!

I've checked your logic, and I think it's fine, although I think your bracketed subclause in para 6 establishing r2 as an upper bound for S needs refinement. I think the correct argument for this is that if s in S > r2, then U = union of Ts and Vr2 and is hence countable, i.e. simply repeating the argument of para 5.

It's a perhaps little surprising that we arrive at a different answer for the uncountably infinite case compared to the countably infinite case, but quite satisfying.

Gengulphus
Lemon Quarter
Posts: 2806
Joined: November 4th, 2016, 1:17 am
Been thanked: 1413 times

Re: Circle

#190487

Postby Gengulphus » January 2nd, 2019, 12:18 am

forlesen wrote:I've checked your logic, and I think it's fine, although I think your bracketed subclause in para 6 establishing r2 as an upper bound for S needs refinement. I think the correct argument for this is that if s in S > r2, then U = union of Ts and Vr2 and is hence countable, i.e. simply repeating the argument of para 5.

Well spotted - I missed that particular piece of nonsense (*) despite previewing the post quite a few times! And yes, your correction does the job - though it would have been better still to have phrased paragraph 5 as a general argument that if r > s, then it's impossible for Tr and Vs to both be countable (as U is the union of Tr and Vs, leading to the contradiction that U would be countable as well). Then use that conclusion twice, once in paragraph 5 to conclude that r1 <= r2 and then again in paragraph 6 to conclude that r2 is an upper bound of S.

(*) And yes, "(since if s >= r, Ts is a superset of Tr and so also uncountable, so s is not in S)" really is nonsense. That's partly the result of an incompletely-performed variable name change - it was supposed to have been edited to "(since if s >= r2, Ts is a superset of Tr2 and so also uncountable, so s is not in S)" - but that's more fundamentally wrong because I hadn't established that Tr2 is uncountable. And in my own example of a vertical segment of the line x=r plus only countably many other points, I can choose r2 = r and then Tr2 is definitely countable rather than uncountable.

Gengulphus

UncleEbenezer
Lemon Quarter
Posts: 3400
Joined: November 4th, 2016, 8:17 pm
Has thanked: 352 times
Been thanked: 544 times

Re: Circle

#190490

Postby UncleEbenezer » January 2nd, 2019, 12:58 am

Gengulphus wrote:
forlesen wrote:If this is correct, we would seem to end up with for any uncountable subset X of R*R, there is a line that partitions X into two uncountable halves (plus some points on the line).

I think that conclusion is correct, but your argument is a bit lacking.

You both seem to be on the same page there, but my gut says it kind-of feels like arguing to prove an axiom. The axiom of choice would seem appropriate here ;)

How about if I construct something akin to Zeno's convergent sequence, not from integers as he did, but from infinite binary sequences? I haven't succeeded in producing anything of interest in Euclidean space without invoking a third dimension. But I'm thinking Singularity Theory, in which I once took a keen interest but is alas all gone in my dotage.

Gengulphus
Lemon Quarter
Posts: 2806
Joined: November 4th, 2016, 1:17 am
Been thanked: 1413 times

Re: Circle

#190494

Postby Gengulphus » January 2nd, 2019, 3:27 am

UncleEbenezer wrote:You both seem to be on the same page there, but my gut says it kind-of feels like arguing to prove an axiom. The axiom of choice would seem appropriate here ;)

I'm not certain why you think that - the Axiom of Choice is only needed for arguments involving making an infinite number of arbitrary choices, effectively to allow one to make them all simultaneously. I don't see any such argument here.

UncleEbenezer wrote:How about if I construct something akin to Zeno's convergent sequence, not from integers as he did, but from infinite binary sequences? I haven't succeeded in producing anything of interest in Euclidean space without invoking a third dimension. But I'm thinking Singularity Theory, in which I once took a keen interest but is alas all gone in my dotage.

My argument extends quite easily to three dimensions - its basic structure is to use the supposition that:

"there is an uncountable set in N dimensions that cannot be divided into two uncountable sets to either side of some (N-1)-dimensional hyperplane selected by setting one co-ordinate to a constant, plus some points on the hyperplane"

to argue that there is such a hyperplane with an uncountable intersection with the original set, and that a similar supposition with N smaller by one must apply to that intersection. That's used in two stages to drop from dimension 2 (the original U) to dimension 1 (for the subset of U I called Ul) and then to dimension 0 in my argument, leading to the contradiction that a 0-dimensional subspace (a single point) can contain an uncountable set of points.

Using it similarly in three stages, one can argue that for any uncountable set in three dimensions, there is a plane that splits it into uncountable sets on either side of the plane (plus possibly some points on the plane). And analogous statements for any finite number of dimensions can be proved similarly, essentially by induction on the number of dimensions.

So feel free to go into three dimensions for your example, or four, or five, or ... Any finite number of dimensions will do. Just beware of infinite-dimensional examples - complications with transfinite induction, the Axiom of Choice, etc, become considerably more of a risk for them!

Gengulphus

jfgw
Lemon Slice
Posts: 829
Joined: November 4th, 2016, 3:36 pm
Has thanked: 121 times
Been thanked: 188 times

Re: Circle

#192871

Postby jfgw » January 11th, 2019, 7:37 pm

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.

Decimal numbers are a subset of rational numbers and are countable. Decimal numbers are easy to count:
0, 0.1, 0.2 ... 0.8, 0.9,
0.01, 0.02, ... 0.98, 0.99,
0.001... etc.

Here is a simpler example from the one in the video:
Take three numbers from 0 to 1 (but not 1 itself) with three decimal places:

0.159
0.722
0.683

Prove that at least one other such number exists by creating another number thus:
Take the first digit of the first number and add 1,
Take the second digit of the second number and add 1,
Take the third digit of the third number and add 1:

0.234

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.

Many countable sets cannot be counted in numerical order. Take the end points of the Cantor set as an example (which, unlike the Cantor set itself, are countable). If I give you two end points, you will always be able to find another one in between. It is, however, possible to count these end points in the order in which they are generated.

Julian F. G. W.

jfgw
Lemon Slice
Posts: 829
Joined: November 4th, 2016, 3:36 pm
Has thanked: 121 times
Been thanked: 188 times

Re: Circle

#192917

Postby jfgw » January 12th, 2019, 12:33 am

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.

Julian F. G. W.

UncleEbenezer
Lemon Quarter
Posts: 3400
Joined: November 4th, 2016, 8:17 pm
Has thanked: 352 times
Been thanked: 544 times

Re: Circle

#192921

Postby UncleEbenezer » January 12th, 2019, 1:09 am

Julian, I confess I haven't followed the link, and I'm not going to try and get my head around anything while it's fuddled with the lurgy that's been gripping me since New Year.

Could your counting attempt be an effort, valid or otherwise, to introduce the Axiom of Choice, as you deal with infinite numbers of those decimal sequences? That's what it looks like to me when you state it.

jfgw
Lemon Slice
Posts: 829
Joined: November 4th, 2016, 3:36 pm
Has thanked: 121 times
Been thanked: 188 times

Re: Circle

#192952

Postby jfgw » January 12th, 2019, 9:21 am

UncleEbenezer wrote:I'm not going to try and get my head around anything while it's fuddled with the lurgy that's been gripping me since New Year.

I hope you get better soon. It does dull the brain somewhat and it takes a while to fully recover.

He states that there are an uncountably infinite number of numbers from 0 to 1, which I understand to be true. He then attempts to prove that this is the case. I believe that this attempt at proof is flawed.

Julian F. G. W.

forlesen
Lemon Pip
Posts: 73
Joined: November 4th, 2016, 11:14 pm
Has thanked: 3 times
Been thanked: 15 times

Re: Circle

#202146

Postby forlesen » February 18th, 2019, 4:35 pm

Sorry to resuscitate this long-dead thread, but I've been away for a while, and on catching up, noticed that Julian has not really had a satisfactory response to his questions. I hope Uncle E is recovered from his lurgy, by now anyway!

I made myself look at the bulk of the linked video, and the speaker is simply giving an informal presentation of the standard Cantor diagonal argument for the uncountability of the real numbers.

Rather than trying to critique such an informal and hand-wavy presentation, I suggest googling "Cantor diagonal argument" - there are many rather clearer / more formal presentations of this well-known and standard proof.

The key thing to grasp is that it is a proof by contradiction. It starts with the assumption that the reals (between 0 and 1) are countable, and shows that this leads to a contradiction.

If the reals are countable, then every real number can be written in one infinite list, in the order that you count them. So, write the first real number in line 1, the second in line 2, and so on. Each real number is expressed as an infinite decimal. The "adding 1 to the nth digit" procedure is one particular way of constructing a different real number that cannot possibly appear anywhere in the list, giving the contradiction - the list was supposed to contain all real numbers.

Julian is right that strictly, you do need to give some thought to the fact that some real numbers have more than one valid representation as infinite decimals. And for my money, the "add 1" procedure needs some extra reasoning to ensure this does not affect the validity of the argument, and this is often omitted in short presentations on this topic. An alternative procedure that (I believe) does avoid such issues is as follows: suppose Dn is the nth digit of the nth real number in our list.
Then let En = 2 if Dn = 1,
and let En = 1 otherwise (i.e. if Dn = 0, 2, 3,...,9).

Then the real number E = 0.E1E2E3...En... has a unique representation as an infinite decimal (it only has 1's and 2's after the decimal point, so it cannot fall foul of 0.368199999999999... = 0.368200000000... type ambiguities), and cannot appear anywhere in the list.

(Of course, there are many, many other ways of constructing such a missing number.)

So, in a nutshell, the linked video is not complete bunkum, but YMMV on how helpful it is in motivating the key ideas in Cantor's proof.

jfgw
Lemon Slice
Posts: 829
Joined: November 4th, 2016, 3:36 pm
Has thanked: 121 times
Been thanked: 188 times

Re: Circle

#203349

Postby jfgw » February 23rd, 2019, 1:26 am

Thank you for your response, forlesen.

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:
0.0000000...
0.1000000...
0.2000000...
...
0.8000000...
0.9000000...
0.0100000...
0.1100000...
0.1200000...
...
0.7900000...
0.8900000...
0.9900000...
0.0010000...
0.1010000...
etc.

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.

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.

Julian F. G. W.

jfgw
Lemon Slice
Posts: 829
Joined: November 4th, 2016, 3:36 pm
Has thanked: 121 times
Been thanked: 188 times

Re: Circle

#203593

Postby jfgw » February 24th, 2019, 8:24 pm

jfgw wrote:Cantor's diagonal argument may be applied to the above list and will produce a number not on that list.

After a bit of reading, I am aware that this may not be a contradiction. The list contains numbers that terminate with an infinite string of zeroes but the number generated is an infinite string of 1s and does not belong in the set.

I did find this, however,
something on the order of 90% or so of working mathematicians accept Cantorian set theory both in theory and in practice, to some extent. (Source: The Mathematical Experience, Davis/Hersh)
https://en.wikipedia.org/wiki/Talk%3ACantor%27s_diagonal_argument/Arguments

That is certainly not universal acceptance and I am uncertain as to the full implications of the term "to some extent".

The point I raised about a list with the same number of elements as decimal places not being complete is raised elsewhere. I have not found a resolution to this.

Julian F. G. W.

Gengulphus
Lemon Quarter
Posts: 2806
Joined: November 4th, 2016, 1:17 am
Been thanked: 1413 times

Re: Circle

#228908

Postby Gengulphus » June 12th, 2019, 11:54 am

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,0),
(0,1), (1,0),
(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:
0.0000000...
0.1000000...
0.2000000...
...
0.8000000...
0.9000000...
0.0100000...
0.1100000...
0.1200000...
...
0.7900000...
0.8900000...
0.9900000...
0.0010000...
0.1010000...
etc.

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.

Making 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! ;-)

Gengulphus


Return to “Games, Puzzles and Riddles”

Who is online

Users browsing this forum: No registered users and 1 guest