Jump to content

Cardinality of the set of binary-expressed real numbers


pengkuan

Recommended Posts

Cardinality of the set of binary-expressed real numbers

This article gives the cardinal number of the set of all binary numbers by counting its elements, analyses the consequences of the found value and discusses Cantor's diagonal argument, power set and the continuum hypothesis.

1. Counting the fractional binary numbers

2. Fractional binary numbers on the real line

3. Countability of BF

4. Set of all binary numbers, B

5. On Cantor's diagonal argument

6. On Cantor's theorem

7. On infinite digital expansion of irrational number

8. On the continuum hypothesis



You can read the article in the pdf below or the link below



Cardinality of the set of binary-expressed real numbers


or



Edited by pengkuan
Link to comment
Share on other sites

If you want to discuss this, then you need to present your argument here. (Then we can see how many people spot the error in paragraph 2 that makes the rest or your argument moot. Or even wrong.)

What is "paragraph 2"? "Counting the fractional binary numbers" or "Fractional binary numbers on the real line"?

Link to comment
Share on other sites

 

The one that begins "The binary expansion of a real number ... "

 

See how much easier it would be if you presented your ideas here as the rules require.

 

Thanks. Here is the paragraph "The binary expansion of a real number is a sequence of 0 and 1 with a point. On the right of the point is the fractional part and on the left the integer part. As every real number has at least one binary expansion, the set of all binary numbers must have the same cardinality than the real numbers. In fact, we can actually count the elements of this set which will be denoted by B."

 

What is the flaw that you see? It's ok for me.

Link to comment
Share on other sites

 

Thanks. Here is the paragraph "The binary expansion of a real number is a sequence of 0 and 1 with a point. On the right of the point is the fractional part and on the left the integer part. As every real number has at least one binary expansion, the set of all binary numbers must have the same cardinality than the real numbers. In fact, we can actually count the elements of this set which will be denoted by B."

 

What is the flaw that you see? It's ok for me.

You need to include a statement that different real numbers do not have the same binary expansion.

Link to comment
Share on other sites

You need to include a statement that different real numbers do not have the same binary expansion.

This is true. one real number has more than one binary expansion, one binary expansion have only one real number. But this does not change the cardinality.

Link to comment
Share on other sites

 

Thanks. Here is the paragraph "The binary expansion of a real number is a sequence of 0 and 1 with a point. On the right of the point is the fractional part and on the left the integer part. As every real number has at least one binary expansion, the set of all binary numbers must have the same cardinality than the real numbers. In fact, we can actually count the elements of this set which will be denoted by B."

 

What is the flaw that you see? It's ok for me.

 

There are several flaws. One is that you are just choosing a representation of the reals in binary. This is no different from representing them in base 10 or base 423. Therefore, it is trivially true that the set of numbers represented this way has the same cardinality as the set of reals, because it is the same thing.

 

Also, by using the undefined term "the set of all binary numbers" you try to imply that this cardinality is the same as some set of integers (represented in binary). However, this is obviously not true as the binary representation of a real number is (potentially) infinitely long. And therefore not a member of the set of integers.

 

Following paragraphs appear to build on these errors and introduce other errors due to this sort of informal reasoning.

Link to comment
Share on other sites

 

There are several flaws. One is that you are just choosing a representation of the reals in binary. This is no different from representing them in base 10 or base 423. Therefore, it is trivially true that the set of numbers represented this way has the same cardinality as the set of reals, because it is the same thing.

 

Also, by using the undefined term "the set of all binary numbers" you try to imply that this cardinality is the same as some set of integers (represented in binary). However, this is obviously not true as the binary representation of a real number is (potentially) infinitely long. And therefore not a member of the set of integers.

 

Following paragraphs appear to build on these errors and introduce other errors due to this sort of informal reasoning.

I present that "binary numbers has the same cardinality as the real numbers" as the present situation of knowledge, this is not my point.

 

In the following, I showed that the set of binary numbers, including infinite digits numbers, has the cardinality 2^aleph0. This is also the present knowledge.

 

But in the "2. Fractional binary numbers on the real line" and "3. Countability of BF", I showed that this is not the case, that the set of binary numbers, including infinite digits numbers, has the cardinality aleph0.

Link to comment
Share on other sites

 

Strange

One is that you are just choosing a representation of the reals in binary. This is no different from representing them in base 10 or base 423. Therefore, it is trivially true that the set of numbers represented this way has the same cardinality as the set of reals, because it is the same thing.

 

pengkuan

I present that "binary numbers has the same cardinality as the real numbers"

 

Easy there.

 

There are real numbers that cannot be expressed in decimal.

 

There are different real numbers that cannot be expressed in binary.

 

Decimal numbers are (i think) countable, but real numbers are not.

 

https://en.wikipedia.org/wiki/Irrational_number

 

You need the Schroeder Bernstein theorem to compare cardinality of these infinite sets.

 

https://www.google.co.uk/search?q=schroeder+bernstein+theorem&hl=en-GB&biw=&bih=&gbv=2&oq=schroeder+ber&gs_l=heirloom-serp.1.0.0l4j0i22i30l6.2735.7485.0.9953.13.13.0.0.0.0.172.1735.0j13.13.0....0...1ac.1.34.heirloom-serp..0.13.1735.P-9FaKSEh3w

Link to comment
Share on other sites

.....But in the "2. Fractional binary numbers on the real line" .... I showed that this is not the case, that the set of binary numbers, including infinite digits numbers, has the cardinality aleph0.

In "2" you say

"Because the intervals are always empty when n→∞, the set of all fractional binary numbers is not continuous but discrete"

 

I suspect you implicitly mean by n→∞ that n is or becomes larger than any given finite number but n is still finite.

 

You then have 2^n +1 discrete points which maps to a subset of the rational numbers.

 

Only if n=aleph-null are all the real numbers (from 0 to 1) represented and there are are then no intervals between numbers.

 

I agree that "binary numbers has the same cardinality as the real numbers" but by keeping n finite you are only listing a countable, finite set.

 

You can create an aleph-null set of real binary numbers by mapping to eg an infinite set of integers.

You can create from that set an aleph-one set using Cantor's diagonal method.

 

There are real numbers that cannot be expressed in decimal.

 

There are different real numbers that cannot be expressed in binary.

I think all real numbers can expressed as a binary or decimal mixed number or mapped to a finite range of values eg 0 to 1.

Decimal numbers are (i think) countable, but real numbers are not.

pi eg can be expressed in decimal or binary but it's not a countable number.

 

tnx pengkuan: this was a useful learning experience for me and I hope you.

Link to comment
Share on other sites

In "2" you say

"Because the intervals are always empty when n→∞, the set of all fractional binary numbers is not continuous but discrete"

 

I suspect you implicitly mean by n→∞ that n is or becomes larger than any given finite number but n is still finite.

 

You then have 2^n +1 discrete points which maps to a subset of the rational numbers.

 

Only if n=aleph-null are all the real numbers (from 0 to 1) represented and there are are then no intervals between numbers.

 

I agree that "binary numbers has the same cardinality as the real numbers" but by keeping n finite you are only listing a countable, finite set.

 

Very nicely explained. Thank you.

Link to comment
Share on other sites

 

Easy there.

 

There are real numbers that cannot be expressed in decimal.

 

There are different real numbers that cannot be expressed in binary.

 

Decimal numbers are (i think) countable, but real numbers are not.

 

Your are right. Real numbers are uncountable. I have tried to prove that binary numbers are countable. By the same reasoning, decimal numbers are countable.

Link to comment
Share on other sites

I have tried to prove that binary numbers are countable..

 

Define what you mean by "binary number". It sounds like you mean a set of integers (or, equivalently, rational numbers).

 

If real numbers are uncountable, it doesn't matter how you represent them. That can't change their countability.

Link to comment
Share on other sites

In "2" you say

"Because the intervals are always empty when n→∞, the set of all fractional binary numbers is not continuous but discrete"

 

I suspect you implicitly mean by n→∞ that n is or becomes larger than any given finite number but n is still finite.

Yes.

When n→∞, it has to start from 1, then +1 then +1 ...... At each step, n is a finite number.

 

Only if n=aleph-null are all the real numbers (from 0 to 1) represented and there are are then no intervals between numbers.

This is THE problem. How can n become aleph_0 without first has been a finite number? One cannot leap to aleph_0, one just go the old way, 1+1, then +1, then +1 . During the process, the intervals are all empty. At the end, since there is no end, the intervals will never be filled. There will be empty intervals between numbers, binary or decimal or in any base.

 

I agree that "binary numbers has the same cardinality as the real numbers" but by keeping n finite you are only listing a countable, finite set.

 

In fact, n is not kept finite, but cannot be infinite, that is, never n=aleph_0. So, real number cannot be mirrored by digital numbers.

You can create from that set an aleph-one set using Cantor's diagonal method.

 

I think all real numbers can expressed as a binary or decimal mixed number or mapped to a finite range of values eg 0 to 1.

pi eg can be expressed in decimal or binary but it's not a countable number.

 

tnx pengkuan: this was a useful learning experience for me and I hope you.

As never n=aleph_0, even in theory, the set of real numbers cannot be created from natural numbers using power set. This why Cantor's diagonal argument is not true.

 

Define what you mean by "binary number". It sounds like you mean a set of integers (or, equivalently, rational numbers).

 

If real numbers are uncountable, it doesn't matter how you represent them. That can't change their countability.

 

For me, binary number is 0.101011110011..................... and there is no end to the digits. A real number can be expressed in base 2 this way. When I count the binary number, I count those having finite digits and infinitely many digits. So, the set that I count is normally the set of real numbers.

Link to comment
Share on other sites

Then how do you show that the set of binary numbers is countable?

 

I have shown this in 4 ways.

1 By cutting the interval [0, 1]. You can cut this interval in 2, then the second rank interval in 2, then the third in 2.................. The intervals are never fill with binary number. This is shown in figure 1

 

2 By connecting the cutting points with arrows and make a path like the zigzag for rational. This path goes in a single line forever passing through all binary numbers. This is a one-to-one correspondence with the natural numbers. Figure 3

 

3 By counting the number of n digits binary numbers. There are 2^n of them. When we let n go to infinity, there are a countable number of them.

 

4 By noting that all finite binary numbers are rational. Then when n, the number of digits go to infinity, the binary numbers stay rational. So, the set of binary numbers is a subset of rationals and they are countable.

Link to comment
Share on other sites

As I understand the reasoning

 

Every decimal number of length (after the point) n can be expressed as a fraction by adding n zeros to 1 on the bottom.

In other words the cardinality of the decimals is the same as that of the rationals.

 

But there are real numbers which are irrational. That is they cannot be expressed as a rational fraction.

 

So there are additional real numbers that cannot be paired with a rational so there are more real numbers than rational numbers.

 

So the cardinality of the reals is greater than that of the rationals.

Link to comment
Share on other sites

As I understand the reasoning

 

Every decimal number of length (after the point) n can be expressed as a fraction by adding n zeros to 1 on the bottom.

In other words the cardinality of the decimals is the same as that of the rationals.

 

But there are real numbers which are irrational. That is they cannot be expressed as a rational fraction.

 

So there are additional real numbers that cannot be paired with a rational so there are more real numbers than rational numbers.

 

So the cardinality of the reals is greater than that of the rationals.

Yes. this what Cantor have proven.

Link to comment
Share on other sites

Yes.

When n→∞, it has to start from 1, then +1 then +1 ...... At each step, n is a finite number.

 

This is THE problem. How can n become aleph_0 without first has been a finite number? One cannot leap to aleph_0, one just go the old way, 1+1, then +1, then +1 . During the process, the intervals are all empty. At the end, since there is no end, the intervals will never be filled. There will be empty intervals between numbers, binary or decimal or in any base.

 

In fact, n is not kept finite, but cannot be infinite, that is, never n=aleph_0. So, real number cannot be mirrored by digital numbers.

 

 

As never n=aleph_0, even in theory, the set of real numbers cannot be created from natural numbers using power set. This why Cantor's diagonal argument is not true.

Bertrand Russell opposed this view saying, (approximately) that such a series can be defined and used.

 

There's a good discussion of this issue, which I won't/can't attempt to argue, on page 29 of

 

Philosophy of Science Vol. 32, No. 1 (Jan., 1965). (free registration on site required to read it)

 

 

 

Even if you don't accept this, I think there is another flaw.

 

I have shown this in 4 ways.

 

2 By connecting the cutting points with arrows and make a path like the zigzag for rational. This path goes in a single line forever passing through all binary numbers. This is a one-to-one correspondence with the natural numbers. Figure 3

 

3 By counting the number of n digits binary numbers. There are 2^n of them. When we let n go to infinity, there are a countable number of them.

If n can't ever reach aleph-null, then you similarly can't ever reach even an (aleph-null)th member of the above counts ie you can only make an unbounded finite count.

 

If you argue that you can calculate what the result would be if you could count up to aleph-null, then are you not accepting you can similarly calculate the result of n reaching aleph-null?

Link to comment
Share on other sites

I have shown this in 4 ways.

1 By cutting the interval [0, 1]. You can cut this interval in 2, then the second rank interval in 2, then the third in 2.................. The intervals are never fill with binary number. This is shown in figure 1

How does that show that there are countably many "binary number"s?

 

If you're going to refer to figure 1, please post it here.

2 By connecting the cutting points with arrows and make a path like the zigzag for rational. This path goes in a single line forever passing through all binary numbers. This is a one-to-one correspondence with the natural numbers. Figure 3

If you're going to refer to figure 3, please post it here.

 

If it does pass through all binary numbers, and (as you've said) binary numbers includes numbers with infinitely many binary digits, then when does it pass through 1/3 = 0.01010101... (in base 2)?

3 By counting the number of n digits binary numbers. There are 2^n of them. When we let n go to infinity, there are a countable number of them.

That shows that the number of binary numbers that can be expressed with a finite number of digits is countable. You've already accepted that there are "binary numbers" with an infinite number of digits.

4 By noting that all finite binary numbers are rational. Then when n, the number of digits go to infinity, the binary numbers stay rational. So, the set of binary numbers is a subset of rationals and they are countable.

Why does the fact that all finite-length binary numbers are rational imply that all infinite-length binary numbers are rational? Edited by uncool
Link to comment
Share on other sites

Bertrand Russell opposed this view saying, (approximately) that such a series can be defined and used.

 

There's a good discussion of this issue, which I won't/can't attempt to argue, on page 29 of

 

Philosophy of Science Vol. 32, No. 1 (Jan., 1965). (free registration on site required to read it)

 

 

 

Even if you don't accept this, I think there is another flaw.

An infinitely long sequence of digits to the left has to be proven to exist before use. If a notion exist in mathematics, it have to be created properly. Creation of real numbers. https://en.wikipedia.org/wiki/Construction_of_the_real_numbers

 

If real numbers are self evident, why did Cauchy invent his sequences and Dedekind his cuts? So, infinitely many sequence of binary digits must be created properly. Before this, infinitely many digits to the right is just an assumption, an assertion that has not been proven.

 

Can root 2 be properly defined? Let root 2= s_n+s_oo, where s_n is the first n digits and s_oo the left infinite long string of digits. For computing the digits of root 2, we can do:

(s_n+s_oo)^2=2

We have s_oo=root 2-s_nx

 

Or solving the order 2 equation

s_oo^2+2*s_nx*s_oo+s_nx^2-2=0

Solving this equation gives:

s_oo=(-2*s_nx+root(2*s_nx*2*s_nx-4*s_nx+4)/2

We have the same result.

 

So, for knowing the right infinite long string of digits, you have to know the right infinite long string of digits before you compute. Thus, you cannot know at all.

 

If you cannot create root 2 from a known string of digits, you will not be able to get it anyway, even in theory.

 

BTW, How to write symbole here?

 

 

If n can't ever reach aleph-null, then you similarly can't ever reach even an (aleph-null)th member of the above counts ie you can only make an unbounded finite count.

 

If you argue that you can calculate what the result would be if you could count up to aleph-null, then are you not accepting you can similarly calculate the result of n reaching aleph-null?

 

In the beginning g of my article, I counted the number of elements of binary numbers till aleph_null just to show what is the state of knowledge now. Then in the other sections, I show that in fact, binary numbers can be counted using intervals cutting. This technique only count finite binary numbers, but it goes to infinity of digits. This counting do not reach aleph_null. Because binary numbers do not included infinitely long sequence of digits, my counting is complete.

How does that show that there are countably many "binary number"s?

 

If you're going to refer to figure 1, please post it here.

If you're going to refer to figure 3, please post it here.

 

If it does pass through all binary numbers, and (as you've said) binary numbers includes numbers with infinitely many binary digits, then when does it pass through 1/3 = 0.01010101... (in base 2)?

That shows that the number of binary numbers that can be expressed with a finite number of digits is countable. You've already accepted that there are "binary numbers" with an infinite number of digits.

Why does the fact that all finite-length binary numbers are rational imply that all infinite-length binary numbers are rational?

Here are the figures

post-69199-0-18667200-1449313125_thumb.jpg

 

The counting does pass through 1/3 for every finite digits and goes forever. But actual infinitely many digits to the right cannot exist, as I explain in the post above. If the infinity of digits does not exist, finite binary numbers going to infinity of digits completely list all binary numbers.

Link to comment
Share on other sites

One thing to remember in what you are attempting is the difference between fractions and rational numbers.

 

A fraction, say 2/3 is different from the fraction 40/60.

 

In fact there are infinitely many fractions with that same value.

 

But they all represent the same rational number, because the rational number is an equivalence relation that forms a proper partition of the set, indifidual fractions are not.

 

I have not studied the effect of this in binary (or any other base for that matter), but I am sure it will be present.

Edited by studiot
Link to comment
Share on other sites

One thing to remember in what you are attempting is the difference between fractions and rational numbers.

 

A fraction, say 2/3 is different from the fraction 40/60.

 

In fact there are infinitely many fractions with that same value.

 

But they all represent the same rational number, because the rational number is an equivalence relation that forms a proper partition of the set, indifidual fractions are not.

 

I have not studied the effect of this in binary (or any other base for that matter), but I am sure it will be present.

Yes. They are not the same set. Many people cross off the same fractions in their zigzag counting.

 

In fact, the fractions with all the ratios, even identical value, is equivalent to the 2D natural numbers, which is equinumerous to the natural numbers. rational is a subset of the 2D. So, is equinumerous to the natural numbers.

Link to comment
Share on other sites

Here are the figures

attachicon.gifCapture.JPG

 

The counting does pass through 1/3 for every finite digits and goes forever.

When? When does it "pass through" 1/3? If we label the "binary numbers" as xi (for example, x1 = 1/2, x2 = 1/4, x3 = 3/4), for which i is xi equal to 1/3?

But actual infinitely many digits to the right cannot exist, as I explain in the post above. If the infinity of digits does not exist, finite binary numbers going to infinity of digits completely list all binary numbers.

You have not explained it whatsoever. You've simply denied it. Edited by uncool
Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.