Examination of Cantor’s proofs for uncountability and axiom for counting infinite sets

[PengKuan Em]

I do a detailed analysis of Cantor’s theory of uncountable sets. The logic of his proofs has some weaknesses. I propose an axiom and a solution to continuum hypothesis.

The main idea is:
Assumption of Cantor’s proofs: All real numbers (set R) are in a list (list L).

This assumption means R=L, considering L as a set. This makes the claim “a real number is created but is not in the list L” wrong. Indeed, if a number is outside L, it is outside R too. So, the statement “the created real number is not in the list L” means it is not in R and is not a real number, which is equivalent to claim that a real number is not real number. This is absurd but Cantor’s diagonal argument and nested intervals proof both claim that a real number is not in the list L and thus, is not a real number, which make them wrong.

On the other hand, Cantor's both proofs search for contradiction. Can “this real number is not a real number” be the contradiction? No. The contradiction of the proofs is in the third step: sout “is not in the list”. By failing to create sout the second step collapses before the third step declares the contradiction.

See the paper
https://www.academia.edu/86410224/Examination_of_Cantors_proofs_for_uncountability_and_axiom_for_counting_infinite_sets

Kuan Peng

[Ross A. Finlayson]

Hi Kuan Peng, have you heard of Ross Finlayson?

[Ben Bacarisse]

PengKuan Em <tita...@gmail.com> writes:

> I do a detailed analysis of Cantor’s theory of uncountable sets. The
> logic of his proofs has some weaknesses.

I think you should revire the proof because it is not at all the proof
you think it is.

> I propose an axiom and a
> solution to continuum hypothesis.
>
> The main idea is:
> Assumption of Cantor’s proofs: All real numbers (set R) are in a list
> (list L).
>
> This assumption means R=L, considering L as a set.

A list of reals is a function (indeed a bijection) between N and R.
It's a set of pairs {(1, r_1), (2, r_2), ...}, so R=L is a bit sloppy.
You mean R=image(L) (sometimes written L(N) since the image is set of
values of L over N).

> This makes the claim “a real number is created but is not in the list
> L” wrong.

How? The proof is that no list (no bijection from N to R) has R as it's
image. From any list, a real can be constructed that is not in the
list.

> Indeed, if a number is outside L, it is outside R too.

Some authors (rather pointlessly) assume that R=image(L) for some L for
the purpose of showing that assumption to be false. But the
construction is always of a real number. Just not one in the list it
was constructed from.

--
Ben.

[PengKuan Em]

I know you here. But, do you have the same idea than me? Please explain.

PK

[PengKuan Em]

Le dimanche 11 septembre 2022 à 22:34:47 UTC+2, Ben Bacarisse a écrit :
> PengKuan Em <tita...@gmail.com> writes:
>
> > I do a detailed analysis of Cantor’s theory of uncountable sets. The
> > logic of his proofs has some weaknesses.
> I think you should revire the proof because it is not at all the proof
> you think it is.

I have explained in the paper where maybe you will find it more correct.

> > I propose an axiom and a
> > solution to continuum hypothesis.
> >
> > The main idea is:
> > Assumption of Cantor’s proofs: All real numbers (set R) are in a list
> > (list L).
> >
> > This assumption means R=L, considering L as a set.
> A list of reals is a function (indeed a bijection) between N and R.
> It's a set of pairs {(1, r_1), (2, r_2), ...}, so R=L is a bit sloppy.
> You mean R=image(L) (sometimes written L(N) since the image is set of
> values of L over N).

I mean that when seeing L as only the set of it members, L have the same members than R.

> > This makes the claim “a real number is created but is not in the list
> > L” wrong.
> How? The proof is that no list (no bijection from N to R) has R as it's
> image. From any list, a real can be constructed that is not in the
> list.

This is what Cantor said. But if L=R, then if r (real number) is not in L it is not in R. I have constructed a list L in my paper

> > Indeed, if a number is outside L, it is outside R too.
> Some authors (rather pointlessly) assume that R=image(L) for some L for
> the purpose of showing that assumption to be false. But the
> construction is always of a real number. Just not one in the list it
> was constructed from.
>
> --
> Ben.

I have cited this example in my paper:
Let us explain this logical hole with a simple example. Let N3 = {2, 3, 1} be the set of all integers smaller than 4. Let L3 = {1, 2, 3} be a list of all the members of N3. We propose to create an integer in N3 which is not in L3. Suppose that we have created 5, but 5 is not in N3. The hole in this reasoning is that the created integer can only be 1 or 2 or 3 and then, it must be in L3. In conclusion, a member of N3 cannot be out of the list L3.

Also, a list of all the n-bits contains 2^n members, but they have only n bit. The constructed number is created with n numbers only, because of the diagonal. So, the constructed number is not in the first n number, but is in the remaining 2^n-n members of the list. when n goes to infinity, this is always true.

I have explained this in detail in the paper.

PK

[Ben Bacarisse]

PengKuan Em <tita...@gmail.com> writes:

> Le dimanche 11 septembre 2022 à 22:34:47 UTC+2, Ben Bacarisse a écrit :
>> PengKuan Em <tita...@gmail.com> writes:
>>
>> > I do a detailed analysis of Cantor’s theory of uncountable sets. The
>> > logic of his proofs has some weaknesses.
>> I think you should revire the proof because it is not at all the proof
>> you think it is.
>
> I have explained in the paper where maybe you will find it more
> correct.

I read sci.logic. If you can't explain here, that's fine. I wish you
luck and I'll read you published paper (you know, properly published)
when it comes out.

>> > I propose an axiom and a
>> > solution to continuum hypothesis.
>> >
>> > The main idea is:
>> > Assumption of Cantor’s proofs: All real numbers (set R) are in a list
>> > (list L).
>> >
>> > This assumption means R=L, considering L as a set.
>> A list of reals is a function (indeed a bijection) between N and R.
>> It's a set of pairs {(1, r_1), (2, r_2), ...}, so R=L is a bit sloppy.
>> You mean R=image(L) (sometimes written L(N) since the image is set of
>> values of L over N).
>
> I mean that when seeing L as only the set of it members, L have the
> same members than R.

I knew what you meant. I was hoping you'd start to used terms
correctly. But no L can't "have the same members" as R. If anyone
assumes it does, it is simply to show that assumption leads to a
contradiction.

>> > This makes the claim “a real number is created but is not in the list
>> > L” wrong.
>> How? The proof is that no list (no bijection from N to R) has R as it's
>> image. From any list, a real can be constructed that is not in the
>> list.
>
> This is what Cantor said. But if L=R, then if r (real number) is not
> in L it is not in R.

Yes, but L =/= R for all L. Assuming something does not make it so.

> I have constructed a list L in my paper

This is called burying the lede! You should start with this and explain
how you think it is not possible to construct, from your L, an r in R
such that r not in image(L). (But from what you say below, you don't
know enough about R to understand the proof you claim to be
undermining.)

> I have cited this example in my paper:
> Let us explain this logical hole with a simple example. Let N3 = {2,
> 3, 1} be the set of all integers smaller than 4. Let L3 = {1, 2, 3} be
> a list of all the members of N3. We propose to create an integer in N3
> which is not in L3. Suppose that we have created 5, but 5 is not in
> N3. The hole in this reasoning is that the created integer can only be
> 1 or 2 or 3 and then, it must be in L3. In conclusion, a member of N3
> cannot be out of the list L3.

This is a pointless analogy because N (and specifically the subset of N
less that 4) does not have the key property. R is closed under taking
the least upper bound, that means that any countable list of reals can
be used to construct a real not in the list.

I find it extraordinary that people who don't know much about a subject
feel empowered to claim that others have got it all wrong. You don't
know the key property that distinguishes R from, say, Q but you don't
let that hold you back. And I am 100% sure that someone telling you
that you are missing a key fact won't make you go and read about how R
is defined. You'll just keep posting the same stuff.

> Also, a list of all the n-bits contains 2^n members, but they have
> only n bit. The constructed number is created with n numbers only,
> because of the diagonal. So, the constructed number is not in the
> first n number, but is in the remaining 2^n-n members of the
> list. when n goes to infinity, this is always true.

Same problem.

> I have explained this in detail in the paper.

More detail about a fundamental understanding is not going to help.

--
Ben.

[Ross A. Finlayson]

Can you provide two counterexamples?

Define a function with domain natural integers and range [0,1],
i.e. that is 1-1, and onto, from N to R[0,1].

I describe a reductio where an example is defined,
then what are its mathematical properties.



Then also there's apologetics to explain why Cantor's otherwise
theorem(s) don't apply, i.e. why it's a "counterexample",
that otherwise Cantor provides any number of "examples",
of an element not on his list.

Here my usual examples are f(n) = n/d, d->oo, n->d,
then a in the space of the signal domain, point out
what is the usual abstract source of reconstruction,
with a doubling space and an infinite domain.

Simply though it's particularly that one counterexample
there, or, "sweep", these days about writing same in
generalized functions and modeling functions as
limts of standard functions. (Much simpler geometrically.)

This is the most sort of glaring example, but it's apologetics
that all functions in Cantor's theory are Cartesian, this is not.

So, Ross Finlayson wrote it.

[Jeff Barnett]

Should that be, instead "More detail about a fundamental
MISunderstanding is not going to help."?
--
Jeff Barnett

[Ben Bacarisse]

Yup. Thanks for spotting that. I make lots of typos, but the ones that
reverse the meaning are bad!

--
Ben.

[Fritz Feldhase]

On Sunday, September 11, 2022 at 8:48:42 PM UTC+2, tita...@gmail.com wrote:

> The main idea is:
> Assumption of Cantor’s proofs: All real numbers (set R) are in a list (list L).

Actually, there is no need to assume that. Moreover Cantor never proved anything in this way.

It suffices to consider an arbitrary subset L c IR. If we assume that L is countable, we can prove that there is a number r e IR which is not in L. Case closed.

It seems to me that you do not understand indirect proofs (proofs by contradiction). Hence the approach mentioned above should be less problematic for you.

Note the differences marked with "[...]":

> This assumption means R = L,

We don't start with that assumption. (See comment above.) Hence our approach

> [doesn't make] the claim “a real number is [defined which] is not in the [set] L” wrong.

> if a [real] number is outside [of] L, it is [just] outside [of L].

> So, the statement “the [defined] real number is not in the [set] L” [just] means it is not in [the set L]

> [Now the] claim that a [real] number [that's not in L] is not [in L] is [not] absurd [but a tautology].

> Cantor’s diagonal argument [...] [shows/proves] that [there is] a real number [which] is not in [the set] L

Right.

Actually, the argument is quite simple.

[Mike Terry]

On 11/09/2022 19:48, PengKuan Em wrote:
> I do a detailed analysis of Cantor’s theory of uncountable sets. The logic of his proofs has some weaknesses. I propose an axiom and a solution to continuum hypothesis.
>
> The main idea is:
> Assumption of Cantor’s proofs: All real numbers (set R) are in a list (list L).
>
> This assumption means R=L, considering L as a set.

I think you're not really familiar with everyday set theory, where "lists", "functions",
"countability" etc. are formally defined.

A better (for mathematicians) way of saying what you try to say in your PDF is:

Set R is the set of all real numbers.
List L is [by definition of "list"] a function N: --> R, and its range is (precisely) the whole of
R. In this post I use N for set of natural numbers {1,2,3,...}

It's also ok to summarise L as something like "assume L is an enumeration of R" or "L is a list
containing all members of R", but you have to understand that they are all saying the same thing - L
is actually a function mapping N to R! (And hence L =/= R )

Sets are not a priori ordered, and L is not simply the same set as R - it has a "function"
structure. Mostly mathematicians define functions (using set theory) as sets of ordered pairs, so
function f is the set { (x, f(x)) : x in domain of f}

I understand what you mean, however. I would say R = Range(L). This is not the biggest problem
with your paper, but your paper very early on (before L is introduced) says:

R = {r_1, r_2, r_3, ...}, i in N, r_i in R, [1]

so you are already pre-assuming that R is countable! R cannot be written in this form, as shown by
Cantor's argument. (If nothing else, this alerts readers to the lack of maths background of the
author, and primes them to expect a flurry of similar basic level mistakes... i.e. although they
don't say it out loud, they're already thinking "duffer"? You only get 3 strikes and you're out! :) )

Your paper should just say R = set of real numbers, define L by one of the wordings I used, and
conclude R = Range(L).

> This makes the claim “a real number is created but is not in the list L” wrong. Indeed, if a number is outside L, it is outside R too. So, the statement “the created real number is not in the list L” means it is not in R and is not a real number, which is equivalent to claim that a real number is not real number. This is absurd but Cantor’s diagonal argument and nested intervals proof both claim that a real number is not in the list L and thus, is not a real number, which make them wrong.

This is the key problem with your paper. I think the cause is that you don't understand proof by
contradiction, but maybe it's more subtle.

Quote from paper:
1. Assumption A: All real numbers are in a list.
2. sflip is created with the diagonal construction and is a real number.
3. sflip is not in the list, contradicting thus the Assumption A.
4. Conclusion: the set of all real numbers cannot be put into a list.

So Assumption A is where we ASSUME the existence of the list L above. L is not "constructed", just
assumed to exist, i.e. we ASSUME there is a function L: N --> R with Range(L) = R.

The point is that HAVING ASSUMED assumption A, IT FOLLOWS by solid logic, that what you call sflip
IS NOT in Range(L), AND ALSO that s_flip IS in R.

Above (and in your paper) you're saying the claim is "wrong", and "absurd" - but the claim is
logically valid GIVEN THE ASSUMPTION A. There is nothing "wrong" with the /argument/ in the proof!
It has just derived a contradiction from assumption A. Therefore we conclude assumption A is false.

That is the pattern for all proof by contradiction, and it's clear in your paper you are horribly
confused by this - but it's one of the most common proof patterns. Nobody claims that it is TRUE
that sflip is both in R and not in R. The only claim is that IF ASSUMPTION A WERE TRUE, then it
would follow that sflip is both in R and not in R. But assumption A is in fact not true, so no
problem. (Unless you just don't accept proof by contradiction...)

Hmm, also you use the word "created" for sflip. sflip is /constructed/ from L, and was always in
the set R (which contains ALL real numbers), so "created" is a bad choice of words - hopefully
that's just a language issue, not a real misunderstanding.

> On the other hand, Cantor's both proofs search for contradiction. Can “this real number is not a real number” be the contradiction? No.

Yes, that's one way of realising a concrete contradiction. When we have made an inconsistent
assumption, there will be MANY possible contradiction statements that we could derive - deriving any
one of them is sufficient to reject the original assumption.

> The contradiction of the proofs is in the third step: sout “is not in the list”.

Well, it comes out the same. "sflip is not in the list" means sflip is not in Range(L) = R, i.e.
it's not a real number. And yet step 2 ensures it is in R: contradiction! Any contradiction we
can deduce from the starting assumption suffices equally well.

> By failing to create sout the second step collapses before the third step declares the contradiction.

But the second step DOESN'T FAIL. It validly CONSTRUCTS sflip from the assumed list L, and the
construction by its nature guarantees sflip is a real number. [...under the assumption A, of course...]

You just don't understand how proof by contradiction works.


Mike.

[Ross A. Finlayson]

-0 = 0

[Ross A. Finlayson]

In Cartesian functions there are everywhere-non-diagonals,
here there is only antidiagonal then that the function is only
defined while the antidiagonal is at the end, where it goes.

It's always so contrived that, ....

Assume you have an antidiagonal algorithm,
but the equivalency function already has exactly one,
an antidiagonal algorithm, and its end isn't missing.

Apply to nested intervals, no worries there,
it's a counterexample to the existence.

All, proofs by contradiction, where "the diagonal argument",
is, ..., not constructive in the manner of not being the usual
deliberative constructible, the proof by contradiction.

Funny that in a formalist's world such an intuitionist notion
is what for formalists should be all "profound".

"Hodges' hopeless" is the usual collection of unsound arguments
against uncountability, or rather for the countable.

[Mike Terry]

In the paper, there is an attempt at list construction, but it totally fails in a common mistake.

Basically, PKE constructs finite length lists of all n bit binary numbers. PKE correctly observes
that the sflip construction (on just the first n entries) constructs a number beyond the first n
entries. So far so good!

Then the "magic": [note: m=2^n, where n is the number of bits]

----- quote:
When m increases indefinitely to reach infinity, we write m=∞ and the number of bits equals
log_2(∞), see (9). In this case, the numbers f_i in Table 3 will have infinitely many bits because
log_1(∞) is the numbers of bits. Then f_i become the real numbers ri, which equal 0.b1b2b3 …, see
(10). Equation (10) is in fact (6) with n=∞.
----- endquote

so, no list is actually constructed! It's just a series of examples of finite lists - and even
these are presented in what looks like random order - followed by a "now let n=∞" suggestion.
The conclusion is also just trying to state the conclusion above for n (correct for finite n)
changing n or m to ∞ :

----- quote:
The flipped number for ri is named rflip and equals fflip with m=∞. rflip is a real number but does
not equal any number of the first list Llog2(∞), which respects Cantor’s diagonal argument. But the
list L∞ being longer than Llog2(∞), we would find rflip at the position log2(∞)+p, rflip =
rlog2(∞)+p. So, rflip belongs to the list L∞, see Table 4.
----- endquote

sort of like saying sflip IS a real number, and its not entry 1 in the list, nor entry 2,3,4,5,6,...
but it IS still there in the list at some entry beyond all the entries indexed by all those finite
numbers in N. (IIUC)

Umm, obviously there are no entries in the list beyond those indexed by one of 1,2,3,4,5.... I
don't think PKE is going to be convinced by anything anyone says here.


Mike.

[Ben Bacarisse]

Mike Terry <news.dead.p...@darjeeling.plus.com> writes:

> Above (and in your paper) you're saying the claim is "wrong", and
> "absurd" - but the claim is logically valid GIVEN THE ASSUMPTION A.
> There is nothing "wrong" with the /argument/ in the proof! It has
> just derived a contradiction from assumption A. Therefore we conclude
> assumption A is false.

Proof by contradiction seems to trip lots of people up, and it's
annoying that it's so often used for this theorem because it's absolutely
not needed. It is simple to prove that for any L: N -> R, there is an r
in R not in range(L).

Proof by contradiction goes

Exists X such that X is what we want
-> bad things happen -> ~Exists X such that X is what we want

where the direct version is just a proof that

For all X, X is not what we want

(from which "~Exists X such that X is what want" follows, but it often
unsaid.)

--
Ben.

[Mike Terry]

On 12/09/2022 14:44, Ben Bacarisse wrote:
> Mike Terry <news.dead.p...@darjeeling.plus.com> writes:
>
>> Above (and in your paper) you're saying the claim is "wrong", and
>> "absurd" - but the claim is logically valid GIVEN THE ASSUMPTION A.
>> There is nothing "wrong" with the /argument/ in the proof! It has
>> just derived a contradiction from assumption A. Therefore we conclude
>> assumption A is false.
>
> Proof by contradiction seems to trip lots of people up, and it's
> annoying that it's so often used for this theorem because it's absolutely
> not needed. It is simple to prove that for any L: N -> R, there is an r
> in R not in range(L).
>
> Proof by contradiction goes
>
> Exists X such that X is what we want
> -> bad things happen -> ~Exists X such that X is what we want
>

Just to be devil's advocate, I like this, because what we actually want to prove is

Not (exists X such that...)

and to prove a "not anything..." it is natural to assume the negative and reach a contradiction.

I know from many of your posts that you (mildly?) dislike this for some reason, or at least believe
your alternative is better, but I don't /really/ get it. (I get that you can do argue a different
way, but not why so many seem to consider that to be preferable, as though there's an unspoken
/flaw/ in proof by contradiction. TBC I've no objection to the other way of arguing.)

> where the direct version is just a proof that
>
> For all X, X is not what we want
>
> (from which "~Exists X such that X is what want" follows, but it often
> unsaid.)
>

Sure, no problem. How might we justify the unspoken final step "~Exists X such that X is what want"
from "For all X, X is not what we want"? Probably something like:

Assume Exists x such that x is what we want.
Then some individual m has the properties we want. [existential um whatnot]
Then from the hypothesis, m does not have the properties we want. [universal instantiation]
Contradiction, hence not (Exists X which is what we want)

Of course we can just say "it's a basic law of logic", but that's just a way of side-stepping the
natural semantic justification which is a proof by contradiction. Or so it seems to me (but what do
I know!?). Bottom line for me I suppose is that I consider it a total non-issue. :) [Same with HP
proof starting by assuming there exists a halt decider...] And surely proof by contradiction is
something every student HAS to get to grips with at some point? So if there's a problem, best to
confront it head on and sort it.


Mike.

[Fritz Feldhase]

On Monday, September 12, 2022 at 6:40:59 PM UTC+2, Mike Terry wrote:

> I know from many of your posts that you (mildly?) dislike this for some reason, or at least believe
> your alternative is better, but I don't /really/ get it. (I get that you can do argue a different
> way, but not why so many seem to consider that to be preferable, as though there's an unspoken
> /flaw/ in proof by contradiction.

I'd say the idea is that the direct proof is "constructive". Given any countable subset S of IR we can "construct" a real number d which is not in S. Concerning your comment above, especially see (*) below.

"A proof is nonconstructive if it asserts the existence of some object without actually constructing or finding that object. Such proofs are used freely in mainstream ("classical") mathematics. Constructivism is the practice of avoiding such proofs or at least pointing them out explicitly. Different philosophical views lead to different kinds of constructivism:

- A mathematician who accepts nonconstructive proofs may nevertheless prefer constructive ones when available, because they are more informative. Indeed, most mathematicians are part-time constructivists, at least in this respect: When we are teaching, we try to illustrate abstract concepts with concrete examples. (*)

- On the other hand, some mathematicians consider all nonconstructive proofs unacceptable, for philosophical reasons. At issue are the meaning of "existence" of an object and the meaning of "proof" of a statement."

Source: https://math.vanderbilt.edu/schectex/papers/difficult.pdf

[PengKuan Em]

Le lundi 12 septembre 2022 à 01:16:43 UTC+2, Ben Bacarisse a écrit :
> PengKuan Em <tita...@gmail.com> writes:
> > I mean that when seeing L as only the set of it members, L have the
> > same members than R.

> But no L can't "have the same members" as R. If anyone
> assumes it does, it is simply to show that assumption leads to a
> contradiction.

You think that you have the right to say “But no L can't have the same members as R”. However, you don’t because “L can't have the same members as R” is the result of Cantor's nested intervals proof and diagonal argument. In our case, we are discussing whether Cantor is right or wrong. So, we have to discuss on the ground where Cantor’s nested intervals proof and diagonal argument do not exist.

If you use “L can't have the same members as R”, then you are saying:
Because “Cantor is right”, then “L can't have the same members as R”, so “Cantor is right”. This is cycling argument which is a logical fallacy.

So, starting from the ground where Cantor does not exist, I can assume “L has the same members as R”, then derive what its consequence is. So, the derivation below is correct in logic :
Assumption: “L has the same members as R”.
r being not in L, then r is not in R because of the assumption.

> > This is what Cantor said. But if L=R, then if r (real number) is not
> > in L it is not in R.
> Yes, but L =/= R for all L. Assuming something does not make it so.

Again, “L =/= R for all L” cannot be used on the ground where we discuss.

“Assuming something does not make it so”. Yes, Assumption is only the first step of the proof by contradiction.

> > I have constructed a list L in my paper
> This is called burying the lede! You should start with this and explain
> how you think it is not possible to construct, from your L, an r in R
> such that r not in image(L). (But from what you say below, you don't
> know enough about R to understand the proof you claim to be
> undermining.)

On the ground where Cantor does not exist, on have the right to construct the list L because the set R is not proven uncountable.

> > I have cited this example in my paper:

> This is a pointless analogy because N (and specifically the subset of N
> less that 4) does not have the key property. R is closed under taking
> the least upper bound, that means that any countable list of reals can
> be used to construct a real not in the list.

Why does “R is closed under taking the least upper bound” implies “any countable list of reals can be used to construct a real not in the list”?

I put the link to my paper just in case where someone need it.
https://www.academia.edu/86410224/Examination_of_Cantors_proofs_for_uncountability_and_axiom_for_counting_infinite_sets

[PengKuan Em]

Le lundi 12 septembre 2022 à 01:16:43 UTC+2, Ben Bacarisse a écrit :
> This is a pointless analogy because N (and specifically the subset of N
> less that 4) does not have the key property. R is closed under taking
> the least upper bound, that means that any countable list of reals can
> be used to construct a real not in the list.

> --
> Ben.

Cantor’s diagonal argument is a proof by contradiction which we summarize as the 4 steps deduction below:

1. Assumption A: All real numbers are in a list.
2. sflip is created with the diagonal construction and is a real number.
3. sflip is not in the list, contradicting thus the Assumption A.
4. Conclusion: the set of all real numbers cannot be put into a list.

Under the assumption “all real numbers are in L”, L includes R
Every real number is necessarily member of L.
So, real number that is out of the list L does not exist under the assumption.
Under the assumption, real number that is out of the list L cannot be constructed.

Cantor constructs 0.(flipped bits) from a list Ld
0.(flipped bits) is a real number.
Because the bits are flipped, 0.(flipped bits) is not in the list from which 0.(flipped bits) is constructed, Ld
Is Ld the list L mentioned by the Assumption?

0.(flipped bits) is not in Ld. On the other hand, 0.(flipped bits) is a real number and thus, under the assumption, is in the list L.
Because 0.(flipped bits) is in L, 0.(flipped bits) is not in Ld:
Ld is not L.

The assumption about L is not contradicted by the result about Ld. That is, “0.(flipped bits) is not in Ld” is not against “0.(flipped bits) is in L”. As 0.(flipped bits) can be in L, Cantor’s proofs fail.

I put the link to my paper just in case where someone want to read it.
https://www.academia.edu/86410224/Examination_of_Cantors_proofs_for_uncountability_and_axiom_for_counting_infinite_sets

[PengKuan Em]

Le lundi 12 septembre 2022 à 01:45:04 UTC+2, Ross A. Finlayson a écrit :
> Can you provide two counterexamples?
>
> Define a function with domain natural integers and range [0,1],
> i.e. that is 1-1, and onto, from N to R[0,1].
>

I gave this example:
(all natural numbers with n bits from 0 up to 2^n,) /2^n, n>oo.

Which is a function N to R[0,1] , in my paper section 4.b
https://www.academia.edu/86410224/Examination_of_Cantors_proofs_for_uncountability_and_axiom_for_counting_infinite_sets

I have also given (all n-digits natural numbers) /10^n, n>oo in
https://www.academia.edu/23155464/Cardinality_of_the_set_of_decimal_numbers

>
> Then also there's apologetics to explain why Cantor's otherwise
> theorem(s) don't apply, i.e. why it's a "counterexample",
> that otherwise Cantor provides any number of "examples",
> of an element not on his list.
>

> So, Ross Finlayson wrote it.

I have just given this in this thread.

Cantor’s diagonal argument is a proof by contradiction which we summarize as the 4 steps deduction below:
1. Assumption A: All real numbers are in a list.
2. sflip is created with the diagonal construction and is a real number.
3. sflip is not in the list, contradicting thus the Assumption A.
4. Conclusion: the set of all real numbers cannot be put into a list.

Under the assumption “all real numbers are in L”, L includes R
Every real number is necessarily member of L.
So, real number that is out of the list L does not exist under the assumption.
Under the assumption, real number that is out of the list L cannot be constructed.

Cantor constructs 0.(flipped bits) from a list Ld
0.(flipped bits) is a real number.
Because the bits are flipped, 0.(flipped bits) is not in the list from which 0.(flipped bits) is constructed, Ld
Is Ld the list L mentioned by the Assumption?

0.(flipped bits) is not in Ld. On the other hand, 0.(flipped bits) is a real number and thus, under the assumption, is in the list L.
Because 0.(flipped bits) is in L, 0.(flipped bits) is not in Ld:
Ld is not L.

The assumption about L is not contradicted by the result about Ld. That is, “0.(flipped bits) is not in Ld” is not against the assumption “0.(flipped bits) is in L”. As 0.(flipped bits) can be in L, Cantor’s proofs fail.

PK

[PengKuan Em]

Le lundi 12 septembre 2022 à 02:20:31 UTC+2, Fritz Feldhase a écrit :

> On Sunday, September 11, 2022 at 8:48:42 PM UTC+2, wrote:
>
> > The main idea is:
> > Assumption of Cantor’s proofs: All real numbers (set R) are in a list (list L).
> Actually, there is no need to assume that. Moreover Cantor never proved anything in this way.
>
> It suffices to consider an arbitrary subset L c IR. If we assume that L is countable, we can prove that there is a number r e IR which is not in L. Case closed.

I have just given this in this thread

[Fritz Feldhase]

On Monday, September 12, 2022 at 7:04:28 PM UTC+2, tita...@gmail.com wrote:

> So, starting from the ground [...] I can assume “L has the same members as R”, then derive [a contradiction].

Right - almost. If L is a "list" (in mathematical terms a /sequence/) then the assumption would be that there exists a sequence (L_n)_(n e IN) of real numbers such that for all r e IR there is (exactly) an n e IN such that r = L_n.

> So, the derivation below is correct in logic :
> Assumption: “L has the same members as R”.

If you can find (construct/define) an r0 e IR such that there is no n e IN with r0 = L_n then this implies a contradiction, since from our ASSUMPTION we get that for all r e IR there is (exactly) an n e IN such that r = L_n.

> Yes, [the] assumption is only the first step of the proof by contradiction.

Indeed! Now we can derive a contradiction! See comment above.

Go figure!

[Mike Terry]

On 12/09/2022 17:52, Fritz Feldhase wrote:
> On Monday, September 12, 2022 at 6:40:59 PM UTC+2, Mike Terry wrote:
>
>> I know from many of your posts that you (mildly?) dislike this for some reason, or at least believe
>> your alternative is better, but I don't /really/ get it. (I get that you can do argue a different
>> way, but not why so many seem to consider that to be preferable, as though there's an unspoken
>> /flaw/ in proof by contradiction.
>
> I'd say the idea is that the direct proof is "constructive". Given any countable subset S of IR we can "construct" a real number d which is not in S. Concerning your comment above, especially see (*) below.
>
> "A proof is nonconstructive if it asserts the existence of some object without actually constructing or finding that object. Such proofs are used freely in mainstream ("classical") mathematics. Constructivism is the practice of avoiding such proofs or at least pointing them out explicitly. Different philosophical views lead to different kinds of constructivism:
>

So... in our case we're looking to prove that there is no X meeting our requirements; a statement of
the form ¬∃x P(x). So how would a constructive proof of this go?

I'll suggest it would be along the lines of demonstrating that a proof of P(a) leads to a
contradiction. I.e. that ASSUMING P(a) [..has been proved..] we can make further [constructively
acceptable] proof steps to reach a contradiction.

That's exactly what happens when we assume L is a list covering all of R, then use it to CONSTRUCT
the sflip number which is proved missing from L. Of course, we haven't "constructed" L which is
effectively given, but we can argue constructively from its existence to reach the required
contradiction.

Well, I may have got all the above wrong as I'm not a constructivist. I think it would be the
position taken by an intuitionist at least, but I may well have got wrong too, as it's just the
result of background reading from many years ago. [I would genuinely be interested in how such
proofs are handled by constructivists, from some reasonably definitive source rather than people
just saying what they imagine.]

Bottom line is I'm not a constructivist, and I don't think the people frowning at "proof by
contradiction" proofs, instead prefering e.g. "given any list of elements of R we can find an
element not in the list" are constructivists! So I'm doubting whether that's really what's going on
here...

> - A mathematician who accepts nonconstructive proofs may nevertheless prefer constructive ones when available, because they are more informative. Indeed, most mathematicians are part-time constructivists, at least in this respect: When we are teaching, we try to illustrate abstract concepts with concrete examples. (*)

Yes, I 100% agree with at least the sentiment behind that. Proofs can sometimes be quick, but
leaving you feeling uninformed, where a longer constructive (or more "direct") proof seems to give a
better understanding.

An example would be where we come to proofs of Halting Problem (no TM decides Halting). Books like
Linz often give the "usual" proof where H is assumed to be a halt decider, and the proof constructs
from H a new TM H_Hat and proves that H incorrectly decides the input (<H_Hat>, <H_Hat>). Of
course, we have the same issue here as to whether this kind of proof is "constructive" given that
existence of H is merely assumed within the proof as a working hypothesis, but the construction of
H_Hat from H is a concrete set of steps that can be applied to any decider H, and the proof is
constructive in that sense. So for students I'd say the proof is informative, and "convinving" in
the sense you were referring to.

In contrast, Linz also gives a quicker proof, based on a proof that there exists a recursively
enumerable language which is not decideable (its complement is not recursively enumerable). Well
this is fine, I agree, and having done the pre-req work it is shorter. But I imagine to many it
seems to lack the convincing "constructive" demonstration provided by the "usual" H/H_Hat proof. I
actually don't know whether this second proof is constructive!! (I suspect not, but if it is, there
would need to be a fair bit of careful unwinding of proofs and definitions to properly convince me.
And as I'm not a constructivist there's not much motivation for me to investigate this...)

So which HP proof is "better"? I accept both and can see different merits in each. I would expect
students get more from the "constructive" style H/H_Hat proof at least on first meeting them, but
I'm really just guessing there.

>
> - On the other hand, some mathematicians consider all nonconstructive proofs unacceptable, for philosophical reasons. At issue are the meaning of "existence" of an object and the meaning of "proof" of a statement."
>
> Source: https://math.vanderbilt.edu/schectex/papers/difficult.pdf
>

Yes, all these concerns can be quite tricky. Another one I struggle with is whether proofs are
considered "finitary" and exactly why that is. All seems slightly wooly to me! :) Perhaps it's
better to just get on with doing maths rather than talking about doing it, hehe.

Mike.

[Fritz Feldhase]

On Monday, September 12, 2022 at 8:54:20 PM UTC+2, tita...@gmail.com wrote:
> Le lundi 12 septembre 2022 à 02:20:31 UTC+2, Fritz Feldhase a écrit :
> > On Sunday, September 11, 2022 at 8:48:42 PM UTC+2, wrote:
> >
> > > The main idea is:
> > > Assumption of Cantor’s proofs: All real numbers (set R) are in a list (list L).

I SAID:

> > Actually, there is no need to assume that. Moreover Cantor never proved anything in this way.
> >
> > It suffices to consider an arbitrary subset L c IR. If we assume that L is countable, we can prove that there is a number r e IR which is not in L. Case closed.

NO PROOF BY CONTRADICTION NEEDED!

> Cantor’s diagonal argument is a proof by contradiction which we summarize as the 4 steps deduction below:

1. Assumption A: All real numbers are in a list. <bla bla bla>"

CAN'T YOU READ?!

I SAID:

(a) Actually, there is no need to assume that.

(b) Moreover Cantor never proved anything in this way

...especially NOT the uncountability of "the real numbers".

[Ben Bacarisse]

Mike Terry <news.dead.p...@darjeeling.plus.com> writes:

> On 12/09/2022 14:44, Ben Bacarisse wrote:
>> Mike Terry <news.dead.p...@darjeeling.plus.com> writes:
>>
>>> Above (and in your paper) you're saying the claim is "wrong", and
>>> "absurd" - but the claim is logically valid GIVEN THE ASSUMPTION A.
>>> There is nothing "wrong" with the /argument/ in the proof! It has
>>> just derived a contradiction from assumption A. Therefore we conclude
>>> assumption A is false.
>>
>> Proof by contradiction seems to trip lots of people up, and it's
>> annoying that it's so often used for this theorem because it's absolutely
>> not needed. It is simple to prove that for any L: N -> R, there is an r
>> in R not in range(L).
>>
>> Proof by contradiction goes
>>
>> Exists X such that X is what we want
>> -> bad things happen -> ~Exists X such that X is what we want
>
> Just to be devil's advocate, I like this, because what we actually
> want to prove is
>
> Not (exists X such that...)
>
> and to prove a "not anything..." it is natural to assume the negative
> and reach a contradiction.
>
> I know from many of your posts that you (mildly?) dislike this for
> some reason, or at least believe your alternative is better, but I
> don't /really/ get it.

It's absolutely fine for mathematicians. But a few non-mathematicians
can get into a state about it, and I used to teach non-mathematicians.

I think the notion of /assuming/ as opposed to /asserting/ might be part
of what trips some students up. Another is that the assumption itself
can play into a deep unspoken belief. If you come to CS as a
programmer, the idea of a program that can't exist is very odd. Surely,
the student imagines, every reasonable sounding specification can be
met?

Specification: determine if a context free grammar (give in, say, BNF)
is ambiguous or not. The result is 100% pinned down. No ambiguity.
How could there /not/ be an algorithm to do this?

I'm not saying it's a major problem, but when you spend a few years
re-writing a lecture course, you end up making changes based on all sort
of seemingly minor hiccups from the past.

--
Ben.

[Ben Bacarisse]

Indeed. Both of the famous proofs are of the form "for any list L, L
fails because...".

--
Ben.

[Ben Bacarisse]

PengKuan Em <tita...@gmail.com> writes:

> Le lundi 12 septembre 2022 à 01:16:43 UTC+2, Ben Bacarisse a écrit :
>> PengKuan Em <tita...@gmail.com> writes:
>> > I mean that when seeing L as only the set of it members, L have the
>> > same members than R.
>> But no L can't "have the same members" as R. If anyone
>> assumes it does, it is simply to show that assumption leads to a
>> contradiction.
>
> You think that you have the right to say “But no L can't have the same
> members as R”. However, you don’t because “L can't have the same
> members as R” is the result of Cantor's nested intervals proof and
> diagonal argument. In our case, we are discussing whether Cantor is
> right or wrong. So, we have to discuss on the ground where Cantor’s
> nested intervals proof and diagonal argument do not exist.

No we don't. You'd like to, but I don't have to. You have shown you
know very little about the real numbers and what Cantors proofs actually
are (neither uses proof by contradiction, at least no explicitly).
There is very little reason for me to do more than read the outline you
gave, note that you don't know what you are talking about, and post a
correction.

In fact I went further, but that may yet prove to be a mistake.

> If you use “L can't have the same members as R”, then you are saying:
> Because “Cantor is right”, then “L can't have the same members as R”,
> so “Cantor is right”. This is cycling argument which is a logical
> fallacy.

No it's not. If the proof is sound, I may assert it. To be explicit: I
am /not/ saying "let's assume Cantor is right, therefore you are wrong"
-- that would be circular. I am saying "Cantor is right. I and 7,815
others have checked the proof and it is sound. You are wrong". Note
that there is no "therefore". I am not making /any/ kind of logical
argument as to why you are wrong.

> So, starting from the ground where Cantor does not exist, I can assume
> “L has the same members as R”, then derive what its consequence is.

Indeed you can (barring the "detail" that L and R don't even have the
same sort if members).

> So, the derivation below is correct in logic :
> Assumption: “L has the same members as R”.
> r being not in L, then r is not in R because of the assumption.

Yes. But if, (as is the case), r is also provably in R (by the
definition or R and the construction of r), we have a contradiction.
Something has to go: r not in R by the assumption; r in R by the
construction. The only candidate is the assumption.

>> > I have cited this example in my paper:
>>
>> This is a pointless analogy because N (and specifically the subset of N
>> less that 4) does not have the key property. R is closed under taking
>> the least upper bound, that means that any countable list of reals can
>> be used to construct a real not in the list.
>
> Why does “R is closed under taking the least upper bound” implies “any
> countable list of reals can be used to construct a real not in the
> list”?

I'm sorry but this is the sort of thing you should know before wading
into a topic like this. You should be able to explain exactly how the
proof /claims/ to work, even if you think it has a flaw.

This property of R (which is equivalent to the definition using Dedekind
cuts and the definition using Cauchy sequences) is available all over
the web and in every textbook on the subject. I don't want to write ip
up for you here. But if you want to one-minute summary I'd give to a
student who stops me in the corridor it would be:

In the proof using decimal digits (one that Cantor never gave) the value
of the anti-diagonal is given by a Cauchy sequence -- a bounded
monotonic sequence of rationals. The limit so denoted is therefore a
real number, but it is also, by construction, not in range(L).

The other proofs all use a version of this property, but the details
vary.

--
Ben.

[Ben Bacarisse]

PengKuan Em <tita...@gmail.com> writes:

> Le lundi 12 septembre 2022 à 01:16:43 UTC+2, Ben Bacarisse a écrit :
>> This is a pointless analogy because N (and specifically the subset of N
>> less that 4) does not have the key property. R is closed under taking
>> the least upper bound, that means that any countable list of reals can
>> be used to construct a real not in the list.
>

> Cantor’s diagonal argument is a proof by contradiction which we
> summarize as the 4 steps deduction below:
> 1. Assumption A: All real numbers are in a list.
> 2. sflip is created with the diagonal construction and is a real number.
> 3. sflip is not in the list, contradicting thus the Assumption A.
> 4. Conclusion: the set of all real numbers cannot be put into a list.

Well, it's not Cantor's proof (either of them) but it is how the theorem
is often presented these days. Cantor's proof are not by contradiction.
(This is an over-simplification. Detail available in anyone cares.)

> Under the assumption “all real numbers are in L”, L includes R

Yes. (I hate the imprecision, but I don't want to come over as fussing
over "details" like L and R and not the same kind of thing at all.)

> Every real number is necessarily member of L.

Since that was assumed, yes.

> So, real number that is out of the list L does not exist under the
> assumption.

Yes.

> Under the assumption, real number that is out of the list L cannot be
> constructed.

Yes.

> Cantor constructs 0.(flipped bits) from a list Ld
> 0.(flipped bits) is a real number. Because the bits are flipped,
> 0.(flipped bits) is not in the list from which 0.(flipped bits) is
> constructed, Ld Is Ld the list L mentioned by the Assumption?
>
> 0.(flipped bits) is not in Ld. On the other hand, 0.(flipped bits) is
> a real number and thus, under the assumption, is in the list L.
> Because 0.(flipped bits) is in L, 0.(flipped bits) is not in Ld: Ld is
> not L.
>
> The assumption about L is not contradicted by the result about
> Ld. That is, “0.(flipped bits) is not in Ld” is not against
> “0.(flipped bits) is in L”. As 0.(flipped bits) can be in L, Cantor’s
> proofs fail.

None of this is in Cantor[1]. But other proofs do use bits, often
incorrectly. You can't just flip bits because many reals in [0,1] have
two binary representations. If you see a proof flipping bits, it's
probably wrong. There are lots of fixes, so let's not get hung up more
of those details mathematicians are so obsessed by.

Unfortunately I can't make out what your construction is. Suffice it to
say that the usual construction makes are real, r, not in range(L) for
any function L: N -> R.

By assumption, since r is a real, r is in range(L) for the assumed L,
and by construction r is /not/ in range(L). We have to ditch the
assumption.

[1] I think some people think Cantor's m/w proof is about bits, but it's
not.

--
Ben.

[Fritz Feldhase]

On Monday, September 12, 2022 at 11:26:23 PM UTC+2, Ben Bacarisse wrote:

> [1] I think some people think Cantor's m/w proof is about bits, but it's not.

Yeah.

But since you mentioned his m/w proof: Isn't his proof a real beauty? I'd tend to say _yes_.

Funny thing, that *Cantor* never proved the uncountability of the reals "this way" (i. e. by that diagonal argument). ("Funny" because the proof is "practically" credited to him.)

(I'm quite sure you know that there are some subtle points when using the diagonal argument for proving the uncountability of the reals and that these points do not arise when just considering w/m sequences.)

[Ben Bacarisse]

Fritz Feldhase <franz.fri...@gmail.com> writes:

> On Monday, September 12, 2022 at 11:26:23 PM UTC+2, Ben Bacarisse wrote:
>
>> [1] I think some people think Cantor's m/w proof is about bits, but it's not.
>
> Yeah.
>
> But since you mentioned his m/w proof: Isn't his proof a real beauty?
> I'd tend to say _yes_.

Oh, yes. It's extraordinary. Truly simple and elegant.

> Funny thing, that *Cantor* never proved the uncountability of the
> reals "this way" (i. e. by that diagonal argument). ("Funny" because
> the proof is "practically" credited to him.)

Yes, just as Turing never proved the halting theorem! (He proved
something similar that fitted his purpose -- addressing the
Entscheidungsproblem.)

--
Ben.

[Khong Dong]

On Monday, 12 September 2022 at 17:16:35 UTC-6, Ben Bacarisse wrote:
> Fritz Feldhase <franz.fri...@gmail.com> writes:
>
> > On Monday, September 12, 2022 at 11:26:23 PM UTC+2, Ben Bacarisse wrote:
> >
> >> [1] I think some people think Cantor's m/w proof is about bits, but it's not.

> > Yeah.
> >
> > But since you mentioned his m/w proof: Isn't his proof a real beauty?
> > I'd tend to say _yes_.

> Oh, yes. It's extraordinary. Truly simple and elegant.

Except it's logically _invalid_ -- just as Euclid's "proof" of the infinitude of primes!

> > Funny thing,

> Yes,

That's why there's this caveat from a SME mathematician that there is a:

"need for researchers to deactivate the thought patterns that they have installed in their brains and taken for granted for so many years".

(https://www.scientificamerican.com/article/math-mystery-shinichi-mochizuki-and-the-impenetrable-proof).

[Khong Dong]

On Monday, 12 September 2022 at 20:22:43 UTC-6, Khong Dong wrote:
> On Monday, 12 September 2022 at 17:16:35 UTC-6, Ben Bacarisse wrote:
> > Fritz Feldhase <franz.fri...@gmail.com> writes:
> >
> > > On Monday, September 12, 2022 at 11:26:23 PM UTC+2, Ben Bacarisse wrote:
> > >
> > >> [1] I think some people think Cantor's m/w proof is about bits, but it's not.
>
> > > Yeah.
> > >
> > > But since you mentioned his m/w proof: Isn't his proof a real beauty?
> > > I'd tend to say _yes_.
>
> > Oh, yes. It's extraordinary. Truly simple and elegant.

> Except it's logically _invalid_ -- just as Euclid's "proof" of the infinitude of primes!

In Euclid's case, he assumed -- one way or the other -- there are infinitely many primes to prove there can't be just a finitude of.

In Cantor's "proof", he (and we) assumed -- one way or the other [via the definition of "countable" infinity] -- that there can't be an 1-1 mapping from R to N.

Did Cantor know anything about _UPPER_ Löwenheim–Skolem theorem (https://en.wikipedia.org/wiki/L%C3%B6wenheim%E2%80%93Skolem_theorem)?

What did Cantor know about the _transcendency_ of the well-ordering of prime-numerals? About the _invalidity_ of Henkin's theory-*assumption*?

[Ben Bacarisse]

Khong Dong <khongdo...@gmail.com> writes:

> On Monday, 12 September 2022 at 20:22:43 UTC-6, Khong Dong wrote:
>> On Monday, 12 September 2022 at 17:16:35 UTC-6, Ben Bacarisse wrote:
>> > Fritz Feldhase <franz.fri...@gmail.com> writes:
>> >
>> > > On Monday, September 12, 2022 at 11:26:23 PM UTC+2, Ben Bacarisse wrote:
>> > >
>> > >> [1] I think some people think Cantor's m/w proof is about bits, but it's not.
>>
>> > > Yeah.
>> > >
>> > > But since you mentioned his m/w proof: Isn't his proof a real beauty?
>> > > I'd tend to say _yes_.
>>
>> > Oh, yes. It's extraordinary. Truly simple and elegant.
>
>> Except it's logically _invalid_ -- just as Euclid's "proof" of the
>> infinitude of primes!
>
> In Euclid's case, he assumed -- one way or the other -- there are
> infinitely many primes to prove there can't be just a finitude of.

No, he did not.

> In Cantor's "proof", he (and we) assumed -- one way or the other [via
> the definition of "countable" infinity] -- that there can't be an 1-1
> mapping from R to N.

No, he did not.

--
Ben.

[PengKuan Em]

<