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 8th, 2018, 07:48 AM   #161
Banned Camp

Joined: Mar 2015
From: New Jersey

Posts: 1,720
Thanks: 125

Quote:
 Originally Posted by JeffJo My translation of Cantor's argument:A Cantor String is a function t(*) whose domain is the set of all natural numbers |N, and whose co-domain is the set of characters {'0','1'}. Note that we can use the strings of characters t(0),t(1),t(2),etc., to represent the function.
{'0','1'} is either finite (ends) or infinite (doesn't end). If it doesn't end, you can't get to the end of it.
You can't get to the end of |N.

Your set of characters {'0','1'} IS the set of natural numbers, regardless of any word games. You can't operate on infinite things because they don't end.

List the natural numbers as a column of increasing binary numbers on the left and {'0,'1'} on the right. They are identical. I'll simplify your argument: I say there are sequences of binary digits on the right that are not on the left.
Or even easier: Cantor says the real numbers are not countable.

It's like Relativity. If you push a physicist up against the wall on the speed of light is constant, the last thing he says is: it's an axiom.

Last edited by skipjack; October 8th, 2018 at 11:58 AM.

October 8th, 2018, 11:13 AM   #162
Senior Member

Joined: Jun 2014
From: USA

Posts: 525
Thanks: 40

Quote:
 Originally Posted by zylo Last statement is not true. A is an infinite sequence.
Ok, for the sake of argument, let's assume that $k \in A$ (where $k = 0.\overline{1}_2$ and $A = (\frac{2^i-1}{2^i})_{i=0}^\infty$ ).

Since we're assuming that $A$ contains the elements $a_0$ through $a_\omega = k$, we should be able to have a similar sequence that contains all of the elements of $A$ except $k$. Let $A'$ contain $a_0$ through $a_{\omega-1}$ then and revisit the table from my original post so I can ask you a question:

Does $\bigcup B = \bigcup B'$?

$$\begin{matrix} \underline{A \text{ & } A'} & \underline{\text{function } f} & \underline{B \text{ & } B'} & \underline{\{ x \in f(k) : x \notin \bigcup_{j=0}^i b_j \}} \\ a_0 = 0.\overline{0}_2 & \rightarrow & b_0 = \{ 0.0, 0.00, 0.000, \dots \} & \{ 0.1, 0.11, 0.111, \dots \} \\ a_1 = 0.1\overline{0}_2 & \rightarrow & b_1 = \{ 0.1, 0.10, 0.100, \dots \} & \{ 0.11, 0.111, 0.1111, \dots \} \\ a_2 = 0.11\overline{0}_2 & \rightarrow & b_2 = \{ 0.1, 0.11, 0.110, \dots \} & \{ 0.111, 0.1111, 0.11111, \dots \} \\ a_3 = 0.111\overline{0}_2 & \rightarrow & b_3 = \{ 0.1, 0.11, 0.111, \dots \} & \{ 0.1111, 0.11111, 0.111111, \dots \} \\ \\ \text{Standard sequence } \uparrow & \vdots & \text{Nonstandard 'end of sequence' } \downarrow & \text{Is } f(k) \subset \bigcup B' \text{ ?}\\ \\ a_{\omega-2} = 0.\overline{1}00_2 & \rightarrow & b_{\omega-2} = \{ 0.1, 0.11, 0.111, \dots, 0.\overline{1}0, 0.\overline{1}00 \} & \{ 0.\overline{1}1, 0.\overline{1}11 \} \text{ or } \{ 0.\overline{1}1 \} \text{ ?} \\ a_{\omega-1} = 0.\overline{1}10_2 & \rightarrow & b_{\omega-1} = \{ 0.1, 0.11, 0.111, \dots, 0.\overline{1}1, 0.\overline{1}10 \} & \{ 0.\overline{1}11 \} \text{ or } \{ \text{ } \} \text{ ?} \\ a_\omega = k \in A, k \notin A' & \rightarrow & b_\omega = f(k) \in B, f(k) \notin B' & \{ \text{ } \} \\ \end{matrix}$$

What about my original question for you Zylo?:

Quote:
 Originally Posted by AplanisTophet Let’s summarize: 3) Some might be tempted to agree that $k \notin A$, but because there is no index $j \in \mathbb{N}$ such that $f(k) \subset \bigcup_{i=0}^{j} b_i$, conclude $f(k) \not\subset \bigcup B$.
In closing, I will point out that $[0,1]$ would be enumerable if summary item #3 were true. That is, where $\bigcup f([0,1]_2)$ is an enumerable set of finite strings, a listing of $f([0,1]_2)$ could be created via an enumeration of $\bigcup f([0,1]_2)$ because the union of the listing of $f([0,1]_2)$ would not equate to $\bigcup f([0,1]_2)$ unless the listing contained all of the elements of $f([0,1]_2)$. Do you see why this is Zylo (anybody)?

October 8th, 2018, 12:34 PM   #163
Senior Member

Joined: Apr 2015
From: Planet Earth

Posts: 141
Thanks: 25

Quote:
 Originally Posted by zylo Your set of characters {'0','1'} IS the set of natural numbers, ...
My set {'0','1'} is a finite set with two members. The character '0', and the character '1'.

The set of all natural numbers, |N, is something else entirely. And it exists in ZFC because an axiom says it does.

Quote:
 You can't operate on infinite things because they don't end.
Please, tell me what you mean by "operate on", that you think I tried to do. And why anything I said needs an "end."

The axiom that defines |N does not "end," and has no need to. We simply accept that an endless definition is a valid way to describe a complete set. If you don't want to utilize the axioms that Cantor's proof does, don't claim that you have disproved it. Proofs are based in axiomatic systems, because mathematics has no absolute truths.

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:
 List the natural numbers as a column ...
Why? Yes, that is one way to represent these definitions. But the representation is not the definition. So even if you think the representation "has to end," the definition is still valid.

Quote:
 ... of increasing binary numbers on the left and {'0,'1'} on the right.
If you can't understand what it means for t(*) to be a function whose domain is |N, and whose co-domain is {'0','1'}, please ask and I'll try to explain further. Just don't try to tell me what it is without that understanding.

October 8th, 2018, 01:40 PM   #164
Banned Camp

Joined: Mar 2015
From: New Jersey

Posts: 1,720
Thanks: 125

Quote:
 Originally Posted by AplanisTophet you see why this is Zylo (anybody)?
You can't compare infinite strings unless you can get to the end.

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.
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.

Last edited by zylo; October 8th, 2018 at 01:57 PM.

October 8th, 2018, 01:59 PM   #165
Senior Member

Joined: Jun 2014
From: USA

Posts: 525
Thanks: 40

Quote:
 Originally Posted by zylo You can't compare infinite strings unless you can get to the end. But you have the germ of an interesting question: Is the set of natural numbers minus an infinite (unending) string a subset of the natural numbers?
$$\text{Let } P = \mathbb{N} \setminus \{x \in \mathbb{N} : x \text{ is odd} \}$$
$$P = \{x \in \mathbb{N} : x \text{ is even} \} \subset \mathbb{N}$$
$$|P| = |N|$$

October 8th, 2018, 02:11 PM   #166
Global Moderator

Joined: Dec 2006

Posts: 20,616
Thanks: 2072

Quote:
Originally Posted by zylo
Quote:
 Originally Posted by skipjack Each position in the "list" has to be identified by a finite integer, but the string that corresponds to an irrational real value would necessarily be endless and wouldn't provide the necessary finite integer when its radix point is removed.
A list of n-place decimal digits with a radix point contains all irrational numbers rounded off to n-places.
That's correct, and not in dispute. Note that each such truncated irrational has a position in the list identified by a finite integer, whereas the original irrational doesn't.

Quote:
 Originally Posted by zylo As you expand the list by decimal places, some digit patterns repeat and others do not. Since n increases indefinitely, you can never be sure which members of the list will have repeating patterns and which won't.
Neither limited repetition in a single list member nor repetition across different list members is relevant to this discussion. Every n-place truncation of, say, pi-3, occurs in your list, but this doesn't assist your argument at all, as each of these is also a truncation of infinitely many other irrationals as well, and each of those irrationals fails to have a corresponding specific position in the list identified by a finite integer. Each irrational has a corresponding infinite sublist of your list (for example pi-3 corresponds to the infinite sublist comprising .1, .14, .141, 1415, and so on), but that isn't disputed and doesn't imply that the irrationals are countable.

Quote:
 Originally Posted by zylo Are you saying that in a list of natural numbers, as the list gets larger, only repeating patterns of digits appear?
No, I'm not. I didn't mention patterns at all.

Quote:
 Originally Posted by zylo An interesting case is .3333.... 4. Adding 1 to the last decimal place turns it into a non-repeating decimal (irrational) no matter how many 3's you have.
By definition, there isn't a "last decimal place" to add 1 to if your .3333.... is endless. If it's not endless, the result of changing the last '3' to '4' is rational, not irrational.

October 8th, 2018, 04:07 PM   #167
Senior Member

Joined: Jun 2014
From: USA

Posts: 525
Thanks: 40

Quote:
 Originally Posted by zylo You can't compare infinite strings unless you can get to the end.
I picked a sequence that turned an infinite string of zeros into an infinite string of ones, one-by-one. The sequence has a clear beginning, that of all zeros, and a clear end, that of all ones, given the nonstandard assumption that it could end. The elements of the sequence seem quite "comparable" to me.

Induction tells us that the first element of $f(k)$ is in $b_1$, the second in $b_2$, and so on. That seems reasonable and is the standard way of showing that $f(k) \subset \bigcup B$. It doesn't seem possible to challenge this view. We might quibble with it though. Asserting that $f(k) \subset \bigcup B \iff f(k) \in B$ would be to throw out the proof by induction and in doing so be left with the interpretation that $f(k) \not\subset \bigcup f([0,1)_2)$ because $f(k) \notin f([0,1)_2)$ (equivalently, there is an element of $f(k)$ that is not in $\bigcup f([0,1)_2)$). A function $t$ from $\bigcup f([0,1]_2)$ to $f([0,1]_2)$ would be surjective simply by stipulating that $x \in t(x)$ for all $x \in \bigcup f([0,1]_2)$, thus the reals would be countable.

We would have other issues too. For example, if $v$ was a function from $f([0,1]_2)$ to $\mathcal{P}(\bigcup f([0,1]_2))$, then we could define a set $C$:

$$\text{Let }C = \bigcup \{ x \in f([0,1]_2) : x \not\subset v(x) \} \in \mathcal{P}(\bigcup f([0,1]_2))$$
$$\text{Let } v(q) = C, \text{ where } q \in f([0,1]_2)$$
$$q \subset v(q) \implies q \not\subset C = v(q)$$
$$q \not\subset v(q) \implies q \subset C = v(q)$$
$$\not\exists q \text{ such that } v(q) = C \implies \text{ function } v \text{ is not surjective}$$

This is a problem because the cardinality of the two sets are equal, so there must exist a surjection from $f([0,1]_2)$ onto $\mathcal{P}(\bigcup f([0,1]_2))$.

October 9th, 2018, 12:38 AM   #168
Global Moderator

Joined: Dec 2006

Posts: 20,616
Thanks: 2072

Quote:
 Originally Posted by zylo You can't compare infinite strings unless you can get to the end.
That's merely an assertion, given without any mathematical justification. If it were correct, it would be meaningless to assert that the reals are countable.

October 9th, 2018, 03:32 AM   #169
Banned Camp

Joined: Mar 2015
From: New Jersey

Posts: 1,720
Thanks: 125

Quote:
 Originally Posted by skipjack Each position in the "list" has to be identified by a finite integer, but the string that corresponds to an irrational real value would necessarily be endless and wouldn't provide the necessary finite integer when its radix point is removed.
A list of n-place binary digits exists and is countable no matter how large n is. The larger n is, the closer you get to irrational real numbers in the list. But you can't get to the end of increasing n.

The end of increasing n and beyond are figments of the imagination.

Quote:
 Originally Posted by skipjack That's merely an assertion, given without any mathematical justification. If it were correct, it would be meaningless to assert that the reals are countable.
To compare two strings, they have to be of the same length. Infinity is not a length.

October 9th, 2018, 03:53 AM   #170
Senior Member

Joined: Apr 2015
From: Planet Earth

Posts: 141
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...".
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.
What is the "it" that you think I can't define?

The functions I called t(*)? I defined an example. An infinite example. Any real number in [0,1) can be used to define another, using binary representation. Did you miss the part where the Axiom of Infinity makes it acceptable to define an object via an algorithm that has no end?

The string "01010101..."? Did you miss the part where that is just a way to represent the function on paper? That has nothing to do with whether the function exists?

Something derived from the set |N? That is the set of natural numbers. It is not a string, and contains no strings. Every number in |N is finite. Yes, there are binary representations of those numbers; and yes, every one has a finite length. Do you think Cantor ever claimed otherwise? The set itself is endless (i.e., infinite), so its cardinality is not a natural number. You seem to think that Aleph0 is what Cantor imagined he would find at the end of the endless process that defines |N. The "limit of n as n approaches infinity." IT IS NOT.

Did you mean I can't define a function s(*) as a function whose domain is |N and whose co-domain is |T? I can define one as easily as I defined the example of t(*), but I don't need to. What Cantor's Diagonal Proof shows, is that for any such function s(*) that anybody can define, it cannot be a surjection. The proof doesn't need to define the function s(*), it says that one can't be defined as a surjection. It proves it by using the same, valid technique where an endless process is applied to a set of objects that is known, or assumed, to exist.

 Thread Tools Display Modes Linear Mode

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

 Contact - Home - Forums - Cryptocurrency Forum - Top