Remove ads

Introducing the LemonFools Personal Finance Calculators

Circle

UncleEbenezer
Lemon Quarter
Posts: 3065
Joined: November 4th, 2016, 8:17 pm
Has thanked: 310 times
Been thanked: 443 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: 2660
Joined: November 4th, 2016, 1:17 am
Been thanked: 1291 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: 69
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: 2660
Joined: November 4th, 2016, 1:17 am
Been thanked: 1291 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: 3065
Joined: November 4th, 2016, 8:17 pm
Has thanked: 310 times
Been thanked: 443 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: 2660
Joined: November 4th, 2016, 1:17 am
Been thanked: 1291 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: 791
Joined: November 4th, 2016, 3:36 pm
Has thanked: 110 times
Been thanked: 176 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: 791
Joined: November 4th, 2016, 3:36 pm
Has thanked: 110 times
Been thanked: 176 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: 3065
Joined: November 4th, 2016, 8:17 pm
Has thanked: 310 times
Been thanked: 443 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: 791
Joined: November 4th, 2016, 3:36 pm
Has thanked: 110 times
Been thanked: 176 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: 69
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: 791
Joined: November 4th, 2016, 3:36 pm
Has thanked: 110 times
Been thanked: 176 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: 791
Joined: November 4th, 2016, 3:36 pm
Has thanked: 110 times
Been thanked: 176 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.


Return to “Games, Puzzles and Riddles”

Who is online

Users browsing this forum: No registered users and 2 guests