Are Some Real Numbers Countable and Others Uncountable?

[jbriggs444]

Any set of finite elements is countable. Which also means that even unions of uncountably many disjoint subsets of finite objects would be countable, if there were an uncountable number of disjoint subsets of finite elements.

I am having trouble parsing what you are saying here.

There is no such thing as uncountable family of disjoint subsets of a finite set. The power set of a finite set is finite. Since anything follows from a contradiction, the rest of your claim trivially follows from an assertion that there is such a thing.

In any case, I do not see anyone arguing about disjoint subsets.

 

[Jarvis323]

There is no such thing as uncountable family of disjoint subsets of a finite set. Since anything follows from a contradiction, the rest of your claim trivially follows from an assertion that there is.

I didn't say subsets of a finite set, I said subsets. For example the subsets of the negative integers, the positive integers, Turing machines, English language statements, structures made out of leggos, etc. It becomes an interesting thing to think about, because each of these sets obviously can be put into one to one correspondence with the natural numbers, but their elements are uniquely meaningful respective to some body of knowledge we hold, the same as 1 is distinguished from 0.

Actually, I am not certain how to proceed in this analysis. If you wanted to think about a hypothetical set of all subsets of finite elements, you need to tackle this question of how to distinguish elements and the question about when the amount of information needed to give each element a unique meaning approaches infinity.

I never asserted there is an uncountable set of disjoint subsets of finite elements, only that if there were, its union would be countable, which actually implies I think that there isn't.

 

[jbriggs444]

I didn't say subsets of a finite set, I said subsets. For example the subsets of the negative integers, the positive integers, Turing machines, English language statements, structures made out of leggos, etc. It becomes an interesting thing to think about, because each of these sets obviously can be put into one to one correspondence with the natural numbers, but their elements are uniquely meaningful respective to some body of knowledge we hold, the same as 1 is distinguished from 0.

Actually, I am not certain how to proceed in this analysis. If you wanted to think about a hypothetical set of all subsets of finite elements, you need to tackle this question of how to distinguish elements and the question about when the amount of information needed to give each element a unique meaning approaches infinity.

I never asserted there is an uncountable set of disjoint subsets of finite elements, only that if there were, its union would be countable, which actually implies I think that there isn't.

Why use the word "subset" if what you mean is "set". I do not know what you mean by a "subset of finite elements". Possibly you mean "finite set". i.e. a set whose cardinality is equal to some natural number n.

Clearly there is such a thing as an uncountable family of disjoint finite sets. For instance the set of singleton sets whose only member is an irrational number.

Note that one wants to be very careful when reasoning about things like the set of all sets. That way lies Russell's paradox. You are treading dangerously close. There are blade guards that should be used.

 

[Jarvis323]

Why use the word "subset" if what you mean is "set". I do not know what you mean by a "subset of finite elements". Possibly you mean "finite set". i.e. a set whose cardinality is equal to some natural number n.

Clearly there is such a thing as an uncountable family of disjoint finite sets. For instance the set of singleton sets whose only member is an irrational number.

I used the term subset, because it matches the intuition about there being uncountably many of them even when they are subsets of a countable set. But I shifted the scope to include subsets of not just one countable set, but all of them (with the exception that they only contain finitely describable/computable elements such as $\pi$). The point is that having only finitely describable elements in the resulting set is enough to see that it will be countable.

You can have an uncountable set of disjoint countable sets if you include uncomputable numbers, but in that case what I said wouldn't follow.

This might be an unnecessarily convoluted way to say something very trivial.

 

[jbriggs444]

I used the term subset, because it matches the intuition about there being uncountably many of them even when they are subsets of a countable set.

One cannot have an uncountable family of non-empty disjoint subsets of a countable set. There are a number of ways to proceed with a proof.

The fact that the parent set is countable means that we have a bijection with [some subset of] the natural numbers. That means that we have a well ordering of the elements of the parent set. Which means that we can pick out a least element in each non-empty subset. Which, since the subsets are disjoint, immediately gives us a bijection with [some subset of] the natural numbers.

 

[Jarvis323]

One cannot have an uncountable family of non-empty disjoint subsets of a countable set. There are a number of ways to proceed with a proof.

I can't tell if you are objecting to anything I said or if you're just pointing out more observations. I should note I was never objecting to anything you had to say, just trying to further the conversation (in case you interpreted my posts as objections to yours).

Note you could have an uncountable family of disjoint subsets taken from countable sets.

For example $$A= \{S \text{ s.t. } ( \exists T)(|T| \leq |\mathbb{N}| \wedge S \subseteq T) \}$$ includes uncountably many disjoint countable sets and the union of those disjoint sets is not countable.

But,

$$B = \{S \text{ s.t. } ( \exists T \subseteq C)(|T| \leq |\mathbb{N}| \wedge S \subseteq T) \}$$

where $C$ is the computable numbers, includes only countably many disjoint sets and the union of those disjoint sets is countable. I realize that supposing $B$ had uncountably many disjoint sets is nonsense, but what I was trying to get across is that you don't even need to concern yourself with that, the fact that the result is a set of computable numbers is enough to see trivially why the union is countable without it mattering that the union is over a disjoint sets or what the cardinality of the disjoint sets in $B$ is.

In the case of $B$ it's also the case that $$\{S \text{ s.t. } ( \exists T \subseteq C)(|T| \leq |\mathbb{N}| \wedge S \subseteq T) \} \equiv \{S \text{ s.t. } (|S| \leq |\mathbb{N}| \wedge S \subseteq C \} \equiv \{S \text{ s.t. } S \subseteq C \}$$

in other words the subsets of infinite countable sets vs subsets of a countable infinite set issue doesn't matter when the elements are computable. But I added a lot of extra details in case parsing them helps anyone to understand something better.

 

[vortextor]

Can you justify the implicit assertion I have highlighted above? I do not even understand what it is saying.

Best guess: You can chop the decimal representation of an irrational number into an infinite number of pieces, each distinct from one another and each corresponding in some way to a unique rational number. So if there are infinitely many rational numbers for any single irrational number, how can there be more irrational numbers than rational numbers.

So far, so good. This is all correct. For one irrational number there is indeed a deterministic generating procedure we can use to generate an associated countably infinite set of rational numbers.

So what? Will the countably infinite set of rational numbers generated for the next irrational you pick re-use any of the rational numbers you found for the first irrational. If so, the union of all generated rational numbers for all irrational numbers can remain a countable set despite being the union of an uncountable number of countable sets.

Thank you very much, your conclusion is correct, sir. Any so generated rational number belongs to an infinite number of irrational numbers.

 

[sysprog]

Thank you very much, your conclusion is correct, sir. Any so generated rational number belongs to an infinite number of irrational numbers.

That's to me apparently not correct; it's true that 'almost all' numbers are irrational, but (obviously) no rational numbers are irrational.

 

[jbriggs444]

Thank you very much, your conclusion is correct, sir. Any so generated rational number belongs to an infinite number of irrational numbers.

That's to me apparently not correct; it's true that 'almost all' numbers are irrational, but (obviously) no rational numbers are irrational.

I believe the point being made is that the rational number 3.14, for instance, is associated with uncountably many irrational numbers -- all of the ones in the range from 3.14 to 3.15.

The rational number 3.14 "belongs to" the irrational number $\pi$ in the sense that it is a member of the infinite set of truncated decimal approximations to $\pi$: {3, 3.1, 3.14, 3.141, 3.1415, ...}

 

[sysprog]

I believe the point being made is that the rational number 3.14, for instance, is associated with uncountably many irrational numbers -- all of the ones in the range from 3.14 to 3.15.

The rational number 3.14 "belongs to" the irrational number $\pi$ in the sense that it is a member of the infinite set of truncated decimal approximations to $\pi$: {3, 3.1, 3.14, 3.141, 3.1415, ...}

Hmm. It seems to me that I had not appercepted the 'belongs to' ideation in such a way. Thanks.

oh and, let's please not forget our old friend 22/7 . . .

 

[hmmm27]

What chance of having $\mathbb R$ declared a continuous infinite line ; thus - unless an infinite amount of continguous 0 dimensional objects (numbers) along a line have width as well as density - uncountable.

 

[sysprog]

What chance of having $\mathbb R$ declared a continuous infinite line ; thus - unless an infinite amount of continguous 0 dimensional objects (numbers) along a line have width as well as density - uncountable.

Estimation of chance of "having" such a thing "declared" seems to me to be political; however, it's obvious that "0 dimensional objects" are points, and so cannot "have width", and of course a line has only the length dimension . . . also, please, perhaps you can refer to an infinite amount of stuff, and an infinite number of things . . .

 

[hmmm27]

Umm -- estimates of chance of having something declared seems to me to be political; however, "0 dimensional objects" are points, and so cannot "have width", and a line has only the length dimension . . .

My point (pun not particularly intended) is just that : any countable (and possibly uncountable) number of iterations of a 0 width length object (ie: $\mathbb R$) will have no length. Meanwhile Real-ity is, at the very least equivalent to, an infinite line from which any point - whether easily describable or not - can be selected.

 

[sysprog]

For width along with length, you're going from linearity into planarity (welcome to complex numbers ).

 

[mathman]

My point (pun not particularly intended) is just that : any countable (and possibly uncountable) number of iterations of a 0 width length object (ie: $\mathbb R$) will have no length. Meanwhile Real-ity is, at the very least equivalent to, an infinite line from which any point - whether easily describable or not - can be selected.

Sum of countable no. of zeros is zero. Uncountable no. can't be summed!

 

[jbriggs444]

My point (pun not particularly intended) is just that : any countable (and possibly uncountable) number of iterations of a 0 width length object (ie: R) will have no length.

What are you trying to say here?

Any countable set of real numbers has measure zero. Yes.
Some uncountable sets of real numbers have measure zero. Some have positive measure.

Measure is a generalization of length that applies to more sets of reals than just collections of intervals. For sets of reals that are collections of intervals, the measure of the set will (for reasonable measures) match the sum of the lengths of the intervals that make it up. Not all sets of reals are measurable.

Meanwhile Real-ity

Do not make the mistake of thinking that the real numbers have something to do with physical reality. Like all numbers, they are abstractions. They are useful to reason with and about. But it is not certain that they have perfectly matching "real" analogues.

 

[sysprog]

Oh and, despite $\mathbb {C}$ having that second dimension, the number of numbers in $\mathbb{C}$ is exactly the same as the number of numbers in $\mathbb {R}$.

 

[hmmm27]

Measure is a generalization of length that applies to more sets of reals than just collections of intervals. For sets of reals that are collections of intervals, the measure of the set will (for reasonable measures) match the sum of the lengths of the intervals that make it up. Not all sets of reals are measurable.

That would beg the question, not whether the measure of an interval (say 3) is a real number, but whether the continuous interval itself (between 5 and 2, but I don't mean "the set of reals between 5 and 2", which is something else).

Oh and, despite $\mathbb {C}$ having that second dimension, the number of numbers in $\mathbb{C}$ is exactly the same as the number of numbers in $\mathbb {R}$.

That would seem to indicate a 1:1 correspondence between a line and a plane, so I'm guessing you mean something else ?

Unless $a+bi = b+ai$, ie: is commutative, which seems terribly unlikely.

 

[sysprog]

Sum of countable no. of zeros is zero. Uncountable no. can't be summed!

Don't we have to sum uncountably infinite numbers of infinitesimals to get away with doing integral calculus?

 

[sysprog]

That would seem to indicate a 1:1 correspondence between a line and a plane, so I'm guessing you mean something else ?

There is such a bijection, and to cubes and 4D and beyond -- infinite stays infinite . . .

 

[sysprog]

Oh and, despite $\mathbb {C}$ having that second dimension, the number of numbers in $\mathbb{C}$ is exactly the same as the number of numbers in $\mathbb {R}$.

It's perhaps startling to some persons that the number of even-numbered integers, or, for example, of integers evenly divisible by 100, is exactly the same as the number of the entirety of integers.

 

[jbriggs444]

Don't we have to sum uncountably infinite numbers of infinitesimals to get away with doing integral calculus?

It's not a sum. It is (in the Riemann definition, roughly) a countable limit of a finite sum divided by a finite count.

 

[sysprog]

It's not a sum. It is (in the Riemann definition) a countable limit of a finite sum divided by a finite count.

Nice.

 

[jbriggs444]

That would beg the question, not whether the measure of an interval (say 3) is a real number, but whether the continuous interval itself (between 5 and 2, but I don't mean "the set of reals between 5 and 2", which is something else).

If you speak of a continuous interval between 5 and 2 and do not mean the set of reals between 5 and 2 then you should say what it is that you do mean.

That would seem to indicate a 1:1 correspondence between a line and a plane, so I'm guessing you mean something else ?

as @sysprog has pointed out, the cardinality of the real line and that of the complex plane are identical. One approach to showing this is to take a point on the complex plane, represent it with coordinates (e.g. a+bi), express the coordinates a and b as decimal expansions, interleave the digits in the expansions to get a new decimal expansion and interpret that new expansion as a real number on the real number line. And vice versa. There are some minor tweaks needed to deal with the multiple representation problem (i.e. the .100... versus .099... problem), but that only crops up countably many times and can be dealt with easily in a Hilbert Hotel fashion. Understanding the proof in outline is easy. Dotting the i's and crossing the t's can be tedious.

 

[S.G. Janssens]

Given the initial post, it bewilders me that a thread like this can run for four pages. I suppose I will start working on a post asking for my flat Earth hypothesis to be scrutinized.

 

[phyti]

forum;,
By persevering on and off for some years, we can now slay the 'diagonal dragon'.

 

[BWV]

forum;,
By persevering on and off for some years, we can now slay the 'diagonal dragon'.

But you cite Wikipedia as a source but fail to actually deal with the construction of the set in the article:

Next, a sequence s is constructed by choosing the 1st digit as complementary to the 1st digit of s1 (swapping 0s for 1s and vice versa), the 2nd digit as complementary to the 2nd digit of s2, the 3rd digit as complementary to the 3rd digit of s3, and generally for every n, the nth digit as complementary to the nth digit of sn. For the example above, this yields:

s1	=	(0,	0,	0,	0,	0,	0,	0,	...)
s2	=	(1,	1,	1,	1,	1,	1,	1,	...)
s3	=	(0,	1,	0,	1,	0,	1,	0,	...)
s4	=	(1,	0,	1,	0,	1,	0,	1,	...)
s5	=	(1,	1,	0,	1,	0,	1,	1,	...)
s6	=	(0,	0,	1,	1,	0,	1,	1,	...)
s7	=	(1,	0,	0,	0,	1,	0,	0,	...)
...
s	=	(1,	0,	1,	1,	1,	0,	1,	...)

By construction, s differs from each sn, since their nth digits differ (highlighted in the example). Hence, s cannot occur in the enumeration.

Based on this theorem, Cantor then uses a proof by contradiction to show that:

The set T is uncountable.
The proof starts by assuming that T is countable. Then all its elements can be written as an enumeration s1, s2, ... , sn, ... . Applying the previous theorem to this enumeration produces a sequence s not belonging to the enumeration. However, this contradicts s being an element of Tand therefore belonging to the enumeration. This contradiction implies that the original assumption is false. Therefore, T is uncountable.

As to your argument relating to a set of random infinite sequences the probability that the infinite diagonal would be equal to any other number in the set is zero - just as the odds would be of drawing any two equal real numbers from some interval

 

[PeroK]

forum;,
By persevering on and off for some years, we can now slay the 'diagonal dragon'.

https://www.math.cmu.edu/~wgunther/127m12/notes/CSB.pdf

 

[Mark44]

forum;,
By persevering on and off for some years, we can now slay the 'diagonal dragon'.

Nope. You didn't perserere quite long enough...

 

[phyti]

But you cite Wikipedia as a source but fail to actually deal with the construction of the set in the article:

As to your argument relating to a set of random infinite sequences the probability that the infinite diagonal would be equal to any other number in the set is zero - just as the odds would be of drawing any two equal real numbers from some interval

The citation is for people who may not be familiar with the subject. A second source is http://uk.geocities.com/frege@btinternet.com/index.htm Copyright © E.D.Buckner 2005, a translation of Cantor's 1891 paper.

As to your argument relating to a set of random infinite sequences the probability that the infinite diagonal would be equal to any other number in the set is zero - just as the odds would be of drawing any two equal real numbers from some interval

Here is a counter example showing probability doesn't constitute a proof.

11111...
01111...
00111...
00011...
00001...

d=11111...
p=00000...

The diagonal d and sequence S1 are both unlimited 1's, which exist in the binary tree, with the complementary sequence of 0's.
If you don't accept the binary tree as containing all possible sequences of 0 and 1, then show me a counterexample, with just the first 4 positions.

 

[jbriggs444]

Here is a counter example showing probability doesn't constitute a proof.

Cantor's proof does not use probability.

If you don't accept the binary tree as containing all possible sequences of 0 and 1, then show me a counterexample, with just the first 4 positions.

You have asserted that the binary tree is "equivalent" to a particular hypothetical complete sequential list of sequences of zeroes and ones. But you have not identified a sense in which it is equivalent.

One sense in which it is inequivalent is that a completed infinite binary tree has no second row.

 

[BWV]

The citation is for people who may not be familiar with the subject. A second source is http://uk.geocities.com/frege@btinternet.com/index.htm Copyright © E.D.Buckner 2005, a translation of Cantor's 1891 paper.
Here is a counter example showing probability doesn't constitute a proof.

11111...
01111...
00111...
00011...
00001...

d=11111...
p=00000...

The diagonal d and sequence S1 are both unlimited 1's, which exist in the binary tree, with the complementary sequence of 0's.
If you don't accept the binary tree as containing all possible sequences of 0 and 1, then show me a counterexample, with just the first 4 positions.

But you claimed in the the paper:

Assume a complete list L of random infinite sequences. Each sequence S is a unique infinite pattern of symbols from the set {0, 1}.

your example is not a random sequence, nor is it a complete list of possible sequences. And the complement of the diagonal (per Cantor) is not in the set

 

[Mark44]

By persevering on and off for some years, we can now slay the 'diagonal dragon'.

@phyti, your attempt in this thread is no better than your earlier attempt in 2007 in this thread -- https://www.physicsforums.com/threads/cantor-diagonal-argument.170316/

 

[phyti]

But you claimed in the the paper:your example is not a random sequence, nor is it a complete list of possible sequences. And the complement of the diagonal (per Cantor) is not in the set

If the sequences are not ordered by any specified pattern, then they are random.
Cantor, nor anyone else can show you a complete infinite list. It's an abstraction that cannot be made manifest for viewing. The ellipsis (...) is supposed to inform you that the data extends without limit.

 

[phyti]

BWV;

p and d are from the pdf example.
The graphic shows how p, the sequence formed from the diagonal d is actually an element of L, yet goes undetected.
Sequence d is a simple alternating symbol beginning with 0.
The complement p is therefore an alternating symbol beginning with 1.
The arrows show the correspondence forward and backward.
Sr can be anywhere in L.
The position x is 1 for d and 0 for p. Sr is truly different from d at x but would have to be compared in all positions to reveal itself as the complement of d.

Cantor ignores the fact that d, being a linear sequence, is also a member of L, and would have to be compared in all positions to reveal itself as such. Also definition of sequences is independent of spatial orientation.
Using the symmetry properties of the binary tree, if p is an element of L, its complement d must also be an element of L.

Cantor interprets p as he constructs it as an additional S missing from L, based on the one position difference with all the remaining S.
For a set of unique sequences, by definition, each must differ from the others by at least one position.
With p excluded from L per his interpretation, it will differ from all S in L, whereas in a complete L with p included, it will differ from all S except one, itself.

An interesting quote from his paper:
"However, there is a proof of this proposition that is much simpler,"

It seems the simplicity became an obstacle, and his focus on differences obscured his vision.
The binary tree representing L, includes all S, thus nothing is missing.
You can follow Cantor's construction in the binary tree to prove d and p are duplicates.