My Math Forum  

Go Back   My Math Forum > College Math Forum > Topology

Topology Topology Math Forum


Thanks Tree11Thanks
Reply
 
LinkBack Thread Tools Display Modes
August 13th, 2016, 10:51 AM   #141
Senior Member
 
Joined: Aug 2012

Posts: 1,527
Thanks: 364

Quote:
Originally Posted by JeffM1 View Post
I'll try reading the article though I find that math articles at wikipedia frequently lose me: I don't have the background in terminology or notation or concepts to follow them very far.
That's why I called that particular article enlightening/confusing. You may not understand all if it (I don't either). But at least you'll see that if you argue that your mathematical objects must be constructible, you run into logical difficulties with Cantor's proof.

Quote:
Originally Posted by JeffM1 View Post
I was assuming that the set C JeffJo was discussing in his response to me was the same set T that he was discussing back in posts 111 and 112.
Back then he was talking about the set of all binary strings. At some point he started claiming that they must be "definable" and that's when he veered off track into unsupportable statements.


Quote:
Originally Posted by JeffM1 View Post
That set T was the set of all imaginable infinite strings of two symbols. Now if we choose those symbols as 0 and 1, imagine a radix point preceding them all, and set up a rule to prevent dual representations, I had always been under the impression that this interpreted set T contained the (infinite) representation in binary form of every real number in the interval (0, 1). Is this impression inconsistent with standard math?
No, that IS standard math. (I would leave out "imaginable" since the human brain is finite and the number of humans who ever lived is finite so it's not clear that we can really imagine very many individual numbers or strings. But mathematically we can imagine all of them.)

The set of all binary strings is what we're talking about. It includes both the strings that can be described by algorithms ("Start with 1 then alternate 0's and 1's," or "The decimal part of pi in binary") plus all the strings that have no algorithmic description.


Quote:
Originally Posted by JeffM1 View Post
Because I think (but am not sure) that JeffJo has the same impression (though I now greatly prefer the bit string approach as far simpler), and this may be where you and he disagree.
I think you're back to the string/number distinction, which is not relevant since it's the same either way once we wave our hands at the dual-representation issue.


Quote:
Originally Posted by JeffM1 View Post
Or JeffJo may indeed have used C to represent a completely different set than T, and I have lost the gist of his argument completely.
At one point T was the set of all bitstrings and at some point he started talking about C as the set of all finitely-describable strings, which is a much more restrictive set.


Quote:
Originally Posted by JeffM1 View Post
Or you may be objecting to his use of the words "constructable" and "definable" to characterize C or T or whatever set he is now talking about.
I don't object to finite describability in general, only in this context. Constructivism is a perfectly valid philosophy of math. But I do object to using constructible bitstrings in the discussion of Cantor's diagonal argument, since limiting to constructible strings breaks the argument, or at least plunges the argument into fine points of logic as in the Wiki page that I'm URGING you to read, confusing or not. The confusion itself is enlightening because Cantor's argument regarding unrestricted strings is clear and simple; and the same argument regarding constructible strings is hopelessly confusing.


Quote:
Originally Posted by JeffM1 View Post
In any case, I think we may be arguing around each other by not seeing what others are saying. I have spent a whole career dealing with that sort of muddle.
Very simple to summarize this.

Let C be the set of all bitstrings that can be described or generated by an algorithm. An algorithm is a finite-length string of symbols, like "Alternate 0's and 1's" or "Pi minus 3 in binary." That set of bitstrings is countable. It's missing all the random bitstrings. It's a tiny subset of all the bitstrings Cantor considered. I don't know where JeffJo got the idea to restrict bitstrings like this.

[Why countable? If our alphabet for writing down algorithms is at most countable, there are only countably many algorithms of length 1; countably many of length 2; dot dot dot. Countable union of countable sets is countable. Hence there are only countably many algorithms].

Now since C is countable we can enumerate it and form the anti-diagonal. Since the anti-diagonal is not on the list, it's not in C. Therefore the anti-diagonal is NOT finitely expressible. But the procedure for forming the anti-diagonal ("change the n-th digit of the n-th string") is obviously a simple algorithm. So something went wrong earlier.

Evidently (this is the murky part) the bijection itself can not be finitely describable. The bijection itself is not part of our finitely-describable universe. So Cantor's argument doesn't apply. A constructivist will not allow us to form the bijection even though C is countable.

Constructivist mathematicians (of which there are some) have to jump through hoops to get math to work. It's a tremendous limitation to demand that everything is finitely describable.

But then again, in standard math we posit the existence of things we cannot possibly construct. So philosophically the constructivists have a point.

Last edited by Maschke; August 13th, 2016 at 11:17 AM.
Maschke is offline  
 
August 13th, 2016, 11:22 AM   #142
Senior Member
 
Joined: May 2016
From: USA

Posts: 785
Thanks: 312

I did read the article. I do see that there are logical or at least very serious semantic difficulties using the word "constructable" in the context of Cantor's proof. The only thing that I ever said was constructable (even then not intending to imply anything about physical time and space) was the anti-diagonal itself because, although the number of steps is endless, the procedure for each step can be completely and finitely specified.

I don't think I shall completely reject "imaginable" because if we are talking about something we necessarily are referring to something in either our imaginations or the physical world. Since I don't believe in the physical existence of infinities, I need some word to characterize concepts that have and never have had any physical existence. But this is not a math argument; in fact it is not worth having an argument about at all.

Again I appreciate your taking the time to clarify for me what your position is despite having done it before. Maybe this time I shall retain it.
JeffM1 is offline  
August 13th, 2016, 12:01 PM   #143
Senior Member
 
Joined: Aug 2012

Posts: 1,527
Thanks: 364

Quote:
Originally Posted by JeffJo View Post
Say X(0) is a real number between 0 and 1.
  1. If X(0)>=1/2, then B(1)=1; otherwise, B(1)=0. Then, let X(1)=(X(0)-B(1))*2
  2. If X(1)>=1/2, then B(2)=1; otherwise, B(2)=0. Then, let X(2)=(X(1)-B(2))*2
  3. In general, If X(N-1)>=1/2, then B(N)=1; otherwise, B(N)=0. Then, let X(N)=(X(N-1)-B(N))*2
Ahhhhhhh, I see what you are saying. Yes you are right, any real number in [0,1] may be located by a downward telescoping sequence of nested intervals based on which half of the previous interval it's in.

However, this is not an algorithm. That's because it never terminates in finitely many steps. We have to carry out infinitely many steps in order to arrive at the final result.

When we talk about definability or computability, we are required to get our result in finitely many steps. For example Euclid's algorithm to find the GCD of two integers terminates after finitely many steps.

Quote:
Originally Posted by Wiki
An algorithm is an effective method that can be expressed within a finite amount of space and time and in a well-defined formal language for calculating a function. Starting from an initial state and initial input (perhaps empty), the instructions describe a computation that, when executed, proceeds through a finite number of well-defined successive states, eventually producing "output" and terminating at a final ending state.
https://en.wikipedia.org/wiki/Algorithm

With your telescoping intervals idea, we can indeed describe an infinitary procedure with finitely many symbols, but the algorithm never terminates (unless we happened to start with a finite binary expression).

Your algorithm never halts to produce an answer in a finite number of steps. This is a good point. I hope I haven't confused this issue further but I do see what you are getting at.

Note that to say a real number is computable means that we have an algorithm that cranks out the n-th digit after a finite number of steps.

Of course if we allowed infinitary procedures that took infinitely many steps we could indeed describe all the real numbers, not just the computable ones, in exactly the manner you indicate.

I think I understand your point now. You are not restricting to computable numbers, you are allowing the full set of standard real numbers. Those can not all be described by (finitary) algorithms; even though there is an infinitary procedure to locate any point by halving intervals.

Am I understanding you correctly now? If so, then we're all in agreement on Cantor's proof. In fact if you are reading Cantor's original papers I can see exactly where your idea came from, since Cantor's original proof of the uncountability of the reals used nested intervals exactly as you have.

Conclusion: If by constructible you mean an infinitary process of telescoping intervals, we are in agreement that we're all talking about the standard set of ALL possible binary sequences, for which Cantor's proof is valid.

But if you are meaning constructible in the limited sense of a (finitely terminating) algorithm, we still have trouble ...

Last edited by Maschke; August 13th, 2016 at 12:19 PM.
Maschke is offline  
August 13th, 2016, 08:12 PM   #144
Math Team
 
Joined: Dec 2013
From: Colombia

Posts: 6,939
Thanks: 2266

Math Focus: Mainly analysis and algebra
Quote:
Originally Posted by Maschke View Post
An algorithm is a finite-length string of symbols, like "Alternate 0's and 1's" or "Pi minus 3 in binary."
There's a little more to it than that in the description of "computable numbers" on wiki. In there, the algorithm has to be capable of approximating the given number to any desired accuracy. Your two examples do that (assuming that we have a suitable algorithm for $\pi$, which we do), but it is this stipulation that causes the problem in terms of using Cantor on the set of computable numbers as $T$.

The problem as I understand it is that although we can order all sets of instructions by length, and then lexically, we cannot know which of these sets of instructions are valid algorithms. In particular, by Turing's Halting Problem, we don't know which of these sets of instructions will end and which of them will not.

We therefore have a problem in that our diagonal string is not well defined because we don't know whether the $n$th algorithm will ever produce an $n$th digit.

I suspect that what we are dealing with here is the difference between a set being "countable" (i.e. that there exists an injection from it to the natural numbers) and a set being "computably enumerable" (i.e. there exists an algorithm that enumerates the members of the set).

This is a pretty subtle existence problem. Mathematically, since all the possible sets of instructions are countable, any subset of them is countable. In particular, the subset containing all algorithms is countable. We know this because there exists an injection $f$ from the set of instructions to the natural numbers and we create an injection from the subset containing all algorithms simply by restricting the domain of $f$.

But that does not mean that we have any practical (or even theoretical) way of actually carrying out this restriction of the domain to exhibit the injection from the subset containing the algorithms to the natural numbers.

And this is the key point, because Cantor requires us to enumerate elements of $T$ and he creates his anti-diagonal using this enumeration. The fact that the enumeration is not computable means that the anti-diagonal is not a member of $T$ because it is not computable. Thus Cantor is unable to tell us that the computable numbers are uncountable (thankfully).

References:
Wikipedia: Computable Numbers - Countable but Not Computably Enumerable
Stack Exchange: Is there such a thing as a countable set with an uncountable subset?
Wikipedia: Recursively Enumerable Set
Wikipedia: Enumeration in Computability Theory
v8archie is offline  
August 14th, 2016, 06:15 AM   #145
Senior Member
 
Joined: Apr 2015
From: Planet Earth

Posts: 121
Thanks: 23

Quote:
Originally Posted by Maschke View Post
However, this is not an algorithm. That's because it never terminates in finitely many steps. We have to carry out infinitely many steps in order to arrive at the final result.
And this is the "finite thinking" I mentioned. The concept of infinity in Cantor's proof requires that a set can be considered to be complete, without terminating. It's the third misconception I mentioned.

Quote:
When we talk about definability or computability, we are required to get our result in finitely many steps.
Computability, I agree. Definability, I do not. Not if you are talking about infinite sets.

The set of natural numbers can be defined as a set that contains the number 1 and, if it contains the number n, it also contains n+1. This fails you definition of definability, yet it is the concept behind the Axiom of Infinity.

Without it, we can't even show that the natural numbers N are countable, so any discussion of whether another infinite set is, or is not, countable is complete nonsense.
JeffJo is offline  
August 14th, 2016, 07:19 AM   #146
Math Team
 
Joined: Dec 2013
From: Colombia

Posts: 6,939
Thanks: 2266

Math Focus: Mainly analysis and algebra
The set of natural numbers shouldn't be considered to "never terminate". It's a set, an unmoving object. It has neither beginning nor end.

This is distinct from the concept of a sequence which does start and may (finite) or may not (infinite) terminate.

The concept of computability is set out in Wiki (see links above). The algorithm must be finite, but also needs only to approximate the required number to any given accuracy in that finite number of steps.

The idea of definability is that a number can be completely and uniquely specified even if an infinite number of steps are necessary. However, the definition must contain only finitely many characters or symbols.

Last edited by skipjack; August 14th, 2016 at 11:51 AM.
v8archie is offline  
August 14th, 2016, 07:50 AM   #147
Senior Member
 
Joined: Aug 2012

Posts: 1,527
Thanks: 364

Quote:
Originally Posted by v8archie View Post
The idea of definability is that a number can be completely and uniquely specified even if an infinite number of steps are necessary. However, the definition must contain only finitely many characters or symbols.
Yes thanks, I should not have mentioned definability in my response to JeffJo.
Maschke is offline  
August 14th, 2016, 07:40 PM   #148
Banned Camp
 
Joined: Jun 2014
From: Earth

Posts: 945
Thanks: 191

Quote:
Originally Posted by v8archie View Post
The set of natural numbers shouldn't be considered to "never terminate". It's a set, an unmoving object.
It has neither beginning nor end.

This is distinct from the concept of a sequence which does start and may (finite) or may not (infinite) terminate.
Some sequences don't "start." They don't have a beginning nor an end.


"Normally, the term infinite sequence refers to a sequence that is infinite in one direction, and finite in the other—the
sequence has a first element, but no final element. Such a sequence is called a singly infinite sequence or a one-sided
infinite sequence when disambiguation is necessary. In contrast, a sequence that is infinite in both directions—i.e. that
has neither a first nor a final element—is called a bi-infinite sequence, two-way infinite sequence, or doubly infinite
sequence. A function from the set Z of all integers into a set, such as for instance the sequence of all even integers
( …, −4, −2, 0, 2, 4, 6, 8… ), is bi-infinite. "

Source: https://en.wikipedia.org/wiki/Sequence


.

Last edited by Math Message Board tutor; August 14th, 2016 at 07:44 PM.
Math Message Board tutor is offline  
Reply

  My Math Forum > College Math Forum > Topology

Tags
argument, cantor, diagonal, infinity, number



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Cantor's Diagonal Argument zylo Math 22 January 26th, 2016 08:05 PM
Help! Cantor's Diagonal Argument mjcguest Applied Math 9 July 25th, 2013 07:22 AM
Cantors diagonal argument netzweltler Applied Math 191 November 7th, 2010 01:39 PM
Cantor's diagonal argument - "disproof" Reckhard Abstract Algebra 11 July 31st, 2010 12:05 PM
Cantor diagonal functions Barbarel Number Theory 2 April 10th, 2009 02:59 PM





Copyright © 2017 My Math Forum. All rights reserved.