My Math Forum > Math Cardinality of the set of binary-expressed real numbers

 Math General Math Forum - For general math related discussion and news

October 9th, 2018, 03:40 PM   #191
Senior Member

Joined: Jun 2014
From: USA

Posts: 479
Thanks: 36

Quote:
 Originally Posted by skipjack That's incorrect. There's no such thing as a last natural number. If your particular list doesn't contain all natural numbers, the last one that it does contain cannot possibly contain just '1's and no '0's.
It takes Cantor's argument to assert that the string of all 1's is not in the sequence. Otherwise, it could hit all 1's, reset back to 0's, and then keep going for all we know. This would be like going from $0.\overline{1}$ to $1.\overline{0}$ and then continuing down the real line towards $\infty$.

October 9th, 2018, 03:48 PM   #192
Senior Member

Joined: Jun 2014
From: USA

Posts: 479
Thanks: 36

Quote:
 Originally Posted by zylo So CDA proves that a sequence of natural numbers has no last member. I knew that.
0 0 0 0
1 0 0 0
1 1 0 0
1 1 1 0
.
.
.

Cantor's diagonal is 1 1 1 1 ...

In the above pattern-based sequence, Cantor's diagonal shows that there is no last element of the sequence perhaps. I've always viewed Cantor's argument that way to be honest. Reaching that last string would imply the end of an infinite sequence, so naturally we should be able to construct a theorem saying we can't do that.

Personally, if the bolded elements result in the sequence 1 1 1 1 ..., then I don't see how we can claim that 1 1 1 1 ... isn't in the list without Cantor's argument. The moment we have enough items in our list to ensure that Cantor's diagonal is complete, we would simultaneously have enough elements in our list to know that the next element is 1 1 1 1 ... .

October 9th, 2018, 06:22 PM   #193
Global Moderator

Joined: Dec 2006

Posts: 20,302
Thanks: 1972

Quote:
 Originally Posted by AplanisTophet It takes Cantor's argument to assert that the string of all 1's is not in the sequence.
Not for the sequence zylo gave, as it was constructed by appending endless zeros to every member of the previous list. Every member in the resulting list has endless '0's added to it, and that means that the resulting list doesn't contain any string that contains endless '1's.

Cantor's diagonal exists if the original list's $n$th string has at least $n$ digits for each finite value of $n$ for which the list contains an $n$th string, and every string in the list has a finite position number in the list. There's no list that contains some strings that have an infinite position number rather than a finite position number, because the definition of "list" makes that impossible.

October 11th, 2018, 04:30 AM   #194
Senior Member

Joined: Apr 2015
From: Planet Earth

Posts: 140
Thanks: 25

Quote:
 Originally Posted by JeffJo We can define an example of the function t(*) by:For every n in |N, t(n) = '0' if n is odd. t(n) = '1' if n is odd. We can represent this function with the string "01010101...". Again, there is no need to find an end, since every character position is defined by the function, in accordance with the axiomatic method defined by the Axiom of Infinity.
Quote:
 Originally Posted by zylo But you can't define it for a random string in |N because you can't get to the end of it, unless you are only defining it for finite or repetitive strings.
There are no "strings" in |N, it is a set of numbers. The definition you can't be bothered to understand defines a single character for every n in |N, including any one you pick randomly. Which you will "get to" even though no end is defined.

The set |T, of all possible such strings, is denumerable if (A) you can define a function s(n) that maps every n in |N to a string in |T, and (B) you can prove that every string in |T is mapped this way. If what you meant to say was "But you can't define a function s(*) that returns a function t(*) in |T for a random n in |N," then you are wrong:
1. s(n)(m) = '1' if (m mod n) = 0
2. s(n)(m) = '1' if (m mod m) ~= 0

Again, there is no n in |N where this does not define an infinite string. This s(*) is not a complete listing of |T of course, because that IS impossible.

+++++

Your continued assertion "you can't do XXX for any n in |N, because you can't get to the end of |N" is not the absolute truth you seem to think it is. It is an axiom you choose to accept, but cannot prove. Cantor chose to accept the Axiom of Infinity, which says you can if XXX(1) is defined, and any XXX(n+1) can be constructed from XXX(n).

Cantor's conclusion was that there are infinite sets which are not denumerable. It wasn't about |R, but does apply to |R. It is true in his mathematics. It may or may not be true in yours - you'd have to define that mathematics for us to tell.

Oh, wait; |N does not exist in yours, either. Which, ironically, means that you can't put |R into a bijection with |N. Gee, isn't that what you think Cantor said?

October 11th, 2018, 05:11 AM   #195
Senior Member

Joined: Apr 2015
From: Planet Earth

Posts: 140
Thanks: 25

Quote:
 Originally Posted by zylo Just referencing your argument in case someone wants to try and follow it. Personally, I found it unintelligible.
As I found yours. The difference is, that I pointed out what was unintelligible, and why it was unintelligible. I also tried to understand yours, which I don't believe you did with mine.

Quote:
 Originally Posted by v8archie That says more about you than it does about JeffJo's post.
Accepting the gauntlet thrown, here is Cantor's proof in modern language. You can compare it to the text at Cantor's Diagonal Argument. If zylo still can't understand it, he can't claim to disprove it. But he can ask for a clarification, and I will provide it. I will use the characters '0' and '1' instead of 'm' and 'w', and change some names.
1. A Cantor String is a function t(*) (see note 1, and note 2) whose domain is |N and whose codomain is the two-element set {'0','1'}.
• No element of |N is a string of any kind, or "contains" a string.
2. Let |T be the set of all Cantor Strings.
3. Let s(*) be any function (see note 2) whose domain is |N and whose codomain is |T.
• Note that this means that s(n)(*) is a function whose codomain is {'0','1'}; that is, a Cantor String.
4. Define the function d(*), with domain |N and codomain {'0','1'}, to be a '1' if s(n)(n) is a '0', and a '0' if s(n)(n) is a '1'.
5. The string d(n) differs any string s(n), in position n.
6. There is a Cantor String d(*) in |T that is not mapped by s(*).
7. |T is denumerable iff there is a function s(*) that maps every Cantor string in |T.
8. Steps 1 thru 6 proved that there cannot be such a function (see note 3), so |T is not denumerable.

+++++

Notes:
1. A function is a mapping from one set, called the domain, to another, called the co-domain. I use "A(*)" to represent the string named "A", and "(*)" as a placeholder to indicate this is a function. Being a function means that every member of the domain is paired with exactly one member of the codomain; but not that every member of the codomain is mapped, or that the mappings are unique.
2. I have shown valid definitions of such functions. So they exist in ZFC.
3. This is where Cantor used the words for "contradiction." He didn't mean that the proof itself was a "proof by contradiction," which would place restrictions on the assumed function s(*).

Last edited by JeffJo; October 11th, 2018 at 05:35 AM.

October 11th, 2018, 05:21 AM   #196
Senior Member

Joined: Apr 2015
From: Planet Earth

Posts: 140
Thanks: 25

Quote:
 Originally Posted by v8archie A non-repeating infinite string that is perfectly well defined "to the end": 1 0 11 0 111 0 1111 0 11111 0 ...
Nitpick: the point that zylo refuses to accept, is that a set can be defined without having an "end." I think it is counterproductive to pander to that misconception by referencing "the end" in any way, even in sarcastic quotes.

You provided a well-formed definition, that can identify the character at any position n in |N. Zylo would call this a "random position," and seems to include "n=infinity" as a random selection that we must reach, but obviously can't. I have no hope that we ever will, but to change his mind we need to dispel that notion.

October 11th, 2018, 05:28 AM   #197
Senior Member

Joined: Apr 2015
From: Planet Earth

Posts: 140
Thanks: 25

Quote:
 Originally Posted by zylo 333....... occurs in the list of natural numbers no matter how many digits you have because the list of natural numbers doesn't end.
No, the number represented by a string with n '3's occurs in the list of natural numbers, no matter what n is. Because the list of such strings, like the list of natural numbers, doesn't end.

That doesn't mean that we can't define the endless string "333...". We can. As you are fond of pointing out, its end cannot ever be reached, so it does not represent a natural number. Just like "infinity" or "aleph0" are not natural numbers.

October 15th, 2018, 11:11 AM   #198
Banned Camp

Joined: Mar 2015
From: New Jersey

Posts: 1,720
Thanks: 124

Quote:
 Originally Posted by zylo So you want to see CDA with infinite binary sequences?: 0) 0 0 0 0 0 0 0 0 ........... 1) 1 0 0 0 0 0 0 0 ........... 2) 0 1 0 0 0 0 0 0 ........... 3) 1 1 0 0 0 0 0 0 ........... 4) 0 0 1 0 0 0 0 0 ........... 5) 1 0 1 0 0 0 0 0 ........... 6) 0 1 1 0 0 0 0 0 ........... 7) 1 1 1 0 0 0 0 0 ............ ...................................... Cantor's diagonal string is 1 1 1 1 1 1 1 1 ....... which is the last number in a sequence of natural numbers. So CDA proves that a sequence of natural numbers has no last member. I knew that.
It's interesting to consider the natural number representations on the left by n-place segments.
0
.
3
.
9
10
.
33
.
99
100
.
333
.
999
1000
.
3333
.
9999
..
100000.......
..
333333......
..
999999........

The last segment is simply symbolic for infinity- where you are going but never get to. Note 999999....... ("Cantor String")

 October 15th, 2018, 12:18 PM #199 Global Moderator   Joined: Dec 2006 Posts: 20,302 Thanks: 1972 Every string in that list you quoted contains "endless" zeros, so any other endless strings are missing.
October 15th, 2018, 02:38 PM   #200
Banned Camp

Joined: Mar 2015
From: New Jersey

Posts: 1,720
Thanks: 124

Quote:
 Originally Posted by skipjack Every string in that list you quoted contains "endless" zeros, so any other endless strings are missing.
No. I am counting in binary sequence so eventually the zero places fill up. Perhaps you would be more comfortable with Cantor's Diagonal argument:

Cantor's Diagonal Argument
Assume the set of all infinite binary sequences can be enumerated:

S1) 0 0 1 0 1 1 0......
S2) 0 1 0 0 1 0 0.......
S3) 1 1 0 1 0 0 1......
..............

CDS = 1 0 1............

CDS is an infinite binary sequence that is different from every member of the enumeration and therefore not in the enumeration. Contradiction. Therefore The set of infinite binary sequences is not enumerable,

PROBLEM
CDS has no predecessor in the list and therefore can only be the last member of the list, which doesn't exist because the list of infinite binary sequences has no last member. There is no contradiction and the sequence of infinite binary strings is enumerable.

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post topsquark Abstract Algebra 54 August 17th, 2015 08:46 AM Tau Applied Math 4 January 18th, 2014 01:40 PM mente oscura Number Theory 7 June 1st, 2013 03:48 AM farleyknight Applied Math 3 December 20th, 2008 09:01 PM johnny Computer Science 6 October 18th, 2007 11:29 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top