|R| = |NxN|

[Skepdick]

Take any enumeration of the Reals which would be naturally incomplete (by Cantor's own diagonal argument).
Use Cantor's own technique for generating new, unique elements and append it to the initial set.
Apply diagonalization infinitely to produce new elements.

This non-terminating process would eventually enumerate all real numbers.

This is a falsifiable claim: Produce a Real number which would not be enumerated this way.

[Impenitent]

are you are saying all real numbers are the product of real squares?

I'm no mathematician but it would seem that one less than half of all real numbers couldn't be real squares... (if zero is neither positive or negative)

I thought the square root of any negative number was imaginary and not real

-Imp

[Skepdick]

are you are saying all real numbers are the product of real squares?

I'm no mathematician but it would seem that one less than half of all real numbers couldn't be real squares... (if zero is neither positive or negative)

I thought the square root of any negative number was imaginary and not real

-Imp

NxN doesn't mean square. It's not multiplication. It's the Cartesian product - It's combinatorial.

{1,2} x {1,2] => (1, 1), (1,2), (2,1), (2,2)

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

[Impenitent]

are you are saying all real numbers are the product of real squares?

I'm no mathematician but it would seem that one less than half of all real numbers couldn't be real squares... (if zero is neither positive or negative)

I thought the square root of any negative number was imaginary and not real

-Imp

NxN doesn't mean square. It's not multiplication. It's the Cartesian product - It's combinatorial.

{1,2} x {1,2] => (1, 1), (1,2), (2,1), (2,2)

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

thanks for the explanation

-Imp

[wtf]

This is a falsifiable claim: Produce a Real number which would not be enumerated this way.

Possibly of interest to you.

Does intuitionist logic deny diagonal argument?

The answer is that the Cantor diagonal argument is valid in intuitionist logic.

[Skepdick]

This is a falsifiable claim: Produce a Real number which would not be enumerated this way.

Possibly of interest to you.

Does intuitionist logic deny diagonal argument?

The answer is that the Cantor diagonal argument is valid in intuitionist logic.

Yeah, I am familiar - I am not denying Cantor's argument. I am exploiting it.

It's precisely because his argument is constructively valid is why I am using his own method as an analog to "SUCC" in N.
Only don't cal it "SUCC" - call it "ANOTHER". Sprinkle induction.

If Succ + induction generates all elements in N; then which element in R is "ANOTHER + induction" NOT going to generate?

[wtf]

It's precisely because his argument is constructively valid is why I am using his own method as an analog to "SUCC" in N.
Only don't cal it "SUCC" - call it "ANOTHER". Sprinkle induction.

Google did not return any results for Sprinkle induction. Reference please?

If Succ + induction generates all elements in N; then which element in R is "ANOTHER + induction" NOT going to generate?

The antidiagonal of your claimed enumeration is not generated.

The point of the proof is that it shows that an ARBITRARY enumeration of the reals necessarily misses at least one real. So it doesn't matter how many new reals you add. You still have an enumeration, and it's not all the reals.

You do your reputation no favors by putting forth such a specious and content-free argument in support of a manifestly false claim.

[Skepdick]

Google did not return any results for Sprinkle induction. Reference please?

Wut? You don't understand what an inductive definition is?

If the naturals are defined via infinite induction (application?) of the SUCC function;
I am defining the reals via infinite induction (application?) of the ANOTHER function.

Thea"ANOTHER" function being Cantor's own diagonal method. Take an enumeration. Diagonalize -> New Real.

The point of the proof is that it shows that an ARBITRARY enumeration of the reals necessarily misses at least one real.

You can do the exact same thing with arbitrary enumearation of the Naturals. Change the representation to an infinite 0-prefix notation.

...0001
...0002
...0003
....

Or you can assume a Little Endian encoding and represent the naturals like so:

1 = 1000...
2 = 2000...
3 = 3000...
...
10 = 01000...
100 = 001000...
...

So it doesn't matter how many new reals you add. You still have an enumeration, and it's not all the reals.

So it doesn't matter how many new naturals you add. You still have an enumeration, and it's not all the naturals.

But this doesn't prove anything interesting. There exists no "complete" enumeration of an infinite set? Duh!

You do your reputation no favors by putting forth such a specious and content-free argument in support of a manifestly false claim.

Oh no! My reputation! Are you in the horse-trading business, or in the truth-business?

You are doing your reputation no favours by insisting my claim is false without producing a withess to this falsity.

Which real number would NOT be in the enumeration produced by infinite application of Cantor-diagonalization?

[godelian]

Take any enumeration of the Reals which would be naturally incomplete (by Cantor's own diagonal argument).
Use Cantor's own technique for generating new, unique elements and append it to the initial set.
Apply diagonalization infinitely to produce new elements.

This non-terminating process would eventually enumerate all real numbers.

This is a falsifiable claim: Produce a Real number which would not be enumerated this way.

If you produce new real numbers along one diagonal, you would not produce the ones available on the other diagonal.

For example:

1 0
0 1

The diagonalization produces the new number (0 0) from top-left to bottom-right.
It does not produce the new number (1 1) from top-right to bottom-left.

Other example:

0 0 0 | 0 0 0 0 0
0 0 1 | 0 0 0 0 0
0 1 0 | 0 0 0 0 0
0 1 1 | 0 0 0 0 0
1 0 0 | 0 0 0 0 0
1 0 1 | 0 0 0 0 0
1 1 0 | 0 0 0 0 0
1 1 1 | 0 0 0 0 0

New numbers produced by diagonalization:

top-left to bottom-right : ( 1 1 1 1 1 1 1 1 )
top-right to bottom-left : ( 0 0 0 1 1 1 1 1 )

Hence, repeated top-left to bottom-right diagonalization does indeed keep producing new real numbers, but not all of them.

[Skepdick]

Hence, repeated top-left to bottom-right diagonalization does indeed keep producing new real numbers, but not all of them.

This is not interesting and it's moot.

If this statement is a theorem: "There exists no complete enumeration of ANY infinite set"

Then Cantor's result is stupid. Because there exists NO complete enumeration for R.
But there is NO complete enumeration for N either.

[godelian]

Hence, repeated top-left to bottom-right diagonalization does indeed keep producing new real numbers, but not all of them.

This is not interesting and it's moot.

If this statement is a theorem: "There exists no complete enumeration of ANY infinite set"

Then Cantor's result is stupid. Because there exists NO complete enumeration for R.
But there is NO complete enumeration for N either.

Cantor's result is not stupid because -- in terms of constructivism -- it produces an unobjectionable witness for his theorem. This is widely considered to be a requirement for existence theorems.

I don't make the rules. I only follow them.

Repeatedly adding Cantor's result to the table won't produce all real numbers. You only need to find one witness that will not be produced in that fashion. So, since Cantor produces his witness along one diagonal, you can produce another witness along the other diagonal.

[Skepdick]

Cantor's result is not stupid because -- in terms of constructivism -- it produces an unobjectionable witness for his theorem. This is widely considered to be a requirement for existence theorems.

It's not about the witness. It's about which statement is being witnessed.

Repeatedly adding Cantor's result to the table won't produce all real numbers.

Repeatedly invoking the SUCC function won't produce all the natural numbers either.

You only need to find one witness that will not be produced in that fashion.

The final one.

So, since Cantor produces his witness along one diagonal, you can produce another witness along the other diagonal.

Which confirms the theorem...

There exists NO complete enumeration of ANY infinite set

[wtf]

Apply diagonalization infinitely to produce new elements.

I've been meaning to ask you about this.

You say you are some kind of intuitionist or constructivist. There are various flavors of each of those interrelated ways of looking at math and you haven't been too specific; but no matter. I take it that at some level you object to infinitary processes, or at least ones that could not be carried out by, say, a Turing machine.

is this a fair understanding of your position? I'm not up to speed on some of those topics but trying to understand your intent.

Now here, you have a bit of an ill-defined or vaguely defined operation. You "add the new antidiagonal to the list" not once, not twice, but "infinitely," without specifying what that means.

Now in my classical view of mathematics, I can think of a couple of ways to formalize this.

One: You could be doing induction on the natural numbers; or recursion if you prefer to think of it that way. Same difference.

So you define stages s_n as follows:

* Stage_0 is the original list;

* Stage n+1 is the list at Stage_n, augmented with the antidiagonal obtained at Stage_n.

I hope you will agree with my notation for a countably infinite sequence of augmentations.

Now the number of augmentations is countable. The original list was countable -- countability is a definitional property of lists. And you've added countably many new elements to it.

Countable plus countable is countable; so your new augmented list is countable. Therefore it's still a "list," meaning that it's a countably infinite sequence that's order-isomorphic to the natural numbers in their usual order. And therefore it is still subject to Cantor diagonalization, and it can not be a complete list of all the reals.

Cantor diagonalization applies to an ARBITRARY list; so no countably infinite augmentation can ever defeat Cantor's argume.

Two: You define your infinitary augmentation process using transfinite induction, often also called transfinite recursion. Using transfinite recursion, we define:

* Stage-0 is the initial list, from which we can extract the antigiagonal that is not on the list;

* If α+ (lower case Greek alpha) is a successor ordinal, and it's the successor of the ordinal α, then Stage_α+ is the list at Stage_α, augmented by the new antidiagonal generated at stage α; and

* If α is a limit ordinal, Stage_α is the original list augmented by ALL the antidiagonals generated all stages less than α.

Now if you have not seen transfinite ordinals and transfinite recursion before, I don't want to go too far afield into the weeds to explain them, except that I'll try to answer any specific questions anyone may have.

Suffice to say that the basic idea is to count the natural numbers 0, 1, 2, 3, ... and then "keep on going." The first transfinite ordinal after 0, 1, 2, 3, ... is called ω (lower case Greek omega). If you want to think in terms of ordered sets, we now have something that looks like this:

0, 1, 2, 3, ..., ω

You can think of ω as a purely formal symbol with the property that it's greater than every finite natural number. It can also be formalized as a particular set, in the construction of the von Neumann ordinals.

In this sense, having defined stages S_0, S_1, S_2, ... by adding a new antidiagonal every time, we define S_ω as the original list augmented by each of the antidiagonals from stage S_0, S_1, etc.

An ordinal like ω that is not the successor of any other ordinal is called a limit ordinal.

So you see in transfinite recursion, we can take successors, and we can also "roll up countably many successors" and incorporate them into the limit ordinal. So we are doing induction on ordinals rather than induction on natural numbers. And the only difference is that we have to define our process not only at the base and at successors; but also at limit ordinals.

Now, you can keep on going! And if you assume the Axiom of Choice, then every set is cardinally equivalent to some ordinal. Meaning, that with this process of transfinite recursion, we will eventually add in every real. We actually WILL have "ordinal-enumerated" the reals.

The problem is that the ordinal of the reals must be uncountable, again by Cantor's argument.

So even though we can "ordinal-enumerate" all of the reals, we can not do it using a LiST; because an uncountable ordinal is not a list. That is, it is NOT a countably infinite set order-isomorphic to the natural numbers.

So Cantor diagonalization does not aply.

Conclusion 1: Either way, your argument fails. If you use regular induction, you end up with a countable set that must necessarily be missing the anti-diagonal.

And if you use transfinite induction (and assuming Choice), you can indeed eventually enumerate all the reals. But such an enumeration must necessarily use an uncountable ordinal, which is not a list.

Conclusion 2: I'm still puzzled by your willingness to wave your hands and invoke such a radically infinitary operation; either applying induction countably many times; or transfinite induction uncountably many times.

For someone who plays an intuitionist/constructivist/finitist on this forum, it's hard for me to reconcile your use of such infinitary processes.

Hope you can clarify your view of countable and uncountable inductive processes. But either way, your argument fails. A countable enumeration misses its anti-diagonal; and an uncountable enumeration is not a list and is not subject to diagonalization.

I hope this exposition was clear. Feel free to ask questions.

[Skepdick]

Apply diagonalization infinitely to produce new elements.

I've been meaning to ask you about this.

You say you are some kind of intuitionist or constructivist. There are various flavors of each of those interrelated ways of looking at math and you haven't been too specific; but no matter. I take it that at some level you object to infinitary processes, or at least ones that could not be carried out by, say, a Turing machine.

is this a fair understanding of your position? I'm not up to speed on some of those topics but trying to understand your intent.

I object to completed infinities. Potential infinities - have at them. They are just Turing Machines which will never terminate.

They are always approaching - never arriving. Limits...

Now here, you have a bit of an ill-defined or vaguely defined operation. You "add the new antidiagonal to the list" not once, not twice, but "infinitely," without specifying what that means.

I mean the exact same thing you mean when you apply the SUCC operator inductively/recursively to define the Naturals e.g

1. 0 is a Natural number
2. If n is a Natural number, then n + 1 is a Natural number

The number of times you need to call/apply the SUCC operator in order to define all elements of N is identical to the cardinality of N.

The logical implication of this is that the process of defining N will not halt.

This is a recursive/inductive (bottom-up? ) definition:

Code: Select all

data Nat : Set where
  zero : Nat
  succ : Nat → Nat

To be contrasted with a co-inductive/co-recursive (top-down?) definition:

Code: Select all

data CoNat : Set where
  zero : CoNat
  succ : ∞ CoNat → CoNat

That's a different type-signature. I'm sure you don't need me to explain the difference between universal algebras; and universal coalgebras to you?
The curx is that if I define the naturals that way I get to declare some undefined element n

n : CoNat
n = succ (♯ n)

And then I get to play with symbolic AND numeric representations in a single notation e.g "{0, 1, 2, ..., n-2, n-1, n, n+1, n+2, ...}"

Surely you differentiate between numbers with a definite value e.g 1,2,3; and objects with indefinite value e.g n-2, n-1, n, n+1, n+2.

Arbitrarily large objects.

One: You could be doing induction on the natural numbers; or recursion if you prefer to think of it that way. Same difference.

So you define stages s_n as follows:

* Stage_0 is the original list;

* Stage n+1 is the list at Stage_n, augmented with the antidiagonal obtained at Stage_n.

I hope you will agree with my notation for a countably infinite sequence of augmentations.

As a way to communicate informally - sure. Can we agree this is an inductive/recursive but NOT a co-inductive/co-recursive definition?

Can we agree that a co-inductive definition of the above would be something like:

e.g every Real number the anti-diagonal to an incomplete enumeration of R.

Now the number of augmentations is countable.

Yeah, but that's just a vacuous tautology. Countable (by definition) means "1:1 bijection with the set of naturals".
You are already pre-supposing a completed infinity - the set of naturals.

All I am presupposing is a recursive/co-recursive process which defines Nat such as 0, 1,2...; or a CoNat such as inf, inf+1, inf+2...
Sure - such objects can be arbitrarily large. The can be potentially infinite, but they are not completed infinities.

The original list was countable -- countability is a definitional property of lists.

Countable plus countable is countable; so your new augmented list is countable. Therefore it's still a "list," meaning that it's a countably infinite sequence that's order-isomorphic to the natural numbers in their usual order.

It's not impossible for this to be true, but I see no reasont why YOU believe it's true. In your world-view "countable" means "There exists 1:1 bijection with N"

If you claim (by definition!) that L is countable then there is a 1:1 bijection between L and N BY DEFINITION.
ALL elements in L are mapped to ALL elements in N.
Theorem 1: There are NO elements in N which are NOT mapped to elements in L.

If you add another countable set S to L - what are the elements in S being mapped to in N ?!? There are no unmapped elements remaining in N!
And if |L| is order-isomorphic to |N| then it's impossible for |L ∪ S| to be order-isomorphic to |N|, unless S is an empty list.

Sure, there MAY exist some other bijection, between L ∪ S and N. But it's absolutely not the same bijection as the one defined into existence.

And you are merely asserting the existence of such a bijection without constructing it.

And therefore it is still subject to Cantor diagonalization, and it can not be a complete list of all the reals.

Non-sequitur. Using the exact same logic there cannot be a complete list of all the naturals either.

Cantor diagonalization applies to an ARBITRARY list; so no countably infinite augmentation can ever defeat Cantor's argume.

I am not trying to defeat it. I am exploiting Cantor's argument and applying it to the Naturals.
I am constructively proving the statement NO enumeration of the Naturals is countably infinite.

Any recursive/corecursive enumeration of N has necessarily fewer elements than N thus impossible to be a bijection.
Because there are no such things as completed infinities.

Two: You define your infinitary augmentation process using transfinite induction, often also called transfinite recursion. Using transfinite recursion, we define:

* Stage-0 is the initial list, from which we can extract the antigiagonal that is not on the list;

* If α+ (lower case Greek alpha) is a successor ordinal, and it's the successor of the ordinal α, then Stage_α+ is the list at Stage_α, augmented by the new antidiagonal generated at stage α; and

* If α is a limit ordinal, Stage_α is the original list augmented by ALL the antidiagonals generated all stages less than α.

Transfinite induction... you mean the Extended co-recursive naturals?

In the same manner I defined Nat (0 initial, succ: N-> N) and CoNat (infinity, succ: ∞ CoNat -> CoNat)

I can also define CoInfinity

Code: Select all

data CoInfinity : Set where
  infinity : CoInfinity
  succ : ∞ CoInfinity → CoInfinity

-- Base infinity (analogous to ω)
ω : CoInfinity
ω = infinity

-- Successor to infinity (analogous to ω + 1)
ω+1 : CoInfinity
ω+1 = succ (♯ ω)

And I can give you the union of Nat, CoNat, CoInfinity

Code: Select all

data ExtendedNumber : Set where
  finite : ℕ → ExtendedNumber
  conat : ∞ ExtendedNumber → ExtendedNumber
  infinity : ExtendedNumber
  succ-infinity : ∞ ExtendedNumber → ExtendedNumber

Now if you have not seen transfinite ordinals and transfinite recursion before, I don't want to go too far afield into the weeds to explain them, except that I'll try to answer any specific questions anyone may have.

I have a very specific question.

Why do you belive that an object which is countably infinite (1:1 bijection with N) ∪ another object which is countably infinite produces another countably infinite object?

Now, you can keep on going! And if you assume the Axiom of Choice, then every set is cardinally equivalent to some ordinal. Meaning, that with this process of transfinite recursion, we will eventually add in every real. We actually WILL have "ordinal-enumerated" the reals.

Sure. And if we don't assume the Axiom of Choice?

There appears to be a bijection between the Ordinals, Naturals and Transfinite Cardinals because all three are defined in identical manner:
initial element + successor function.

0:Nat <-> Inf:CoNat <-> ω:CoInfinity
succ 0 <-> succ (inf) <-> succ(ω)
...

There is no bijection on a co-recursive definition because Nat is embedded in CoNat, and CoNat is embedded in CoInfinity.

The problem is that the ordinal of the reals must be uncountable, again by Cantor's argument.

Yeah but the ordinal of the naturals is also uncountable. Again - by Cantor's argument.

So even though we can "ordinal-enumerate" all of the reals, we can not do it using a LiST; because an uncountable ordinal is not a list. That is, it is NOT a countably infinite set order-isomorphic to the natural numbers.

This applies equally to the Natural numbers.

Even though we can order-enumerate all the naturals we can not do this using a LIST. Because a transfinite ordinal (such as infinity:CoNat) is NOT a list.

Conclusion 1: Either way, your argument fails. If you use regular induction, you end up with a countable set that must necessarily be missing the anti-diagonal.

This holds for Natural numbers also - on a co-inductive/co-recursive definition. You can generate more and more naturals using anti-diagonals too. GIven the right encoding/representation.

And if you use transfinite induction (and assuming Choice), you can indeed eventually enumerate all the reals. But such an enumeration must necessarily use an uncountable ordinal, which is not a list.

This holds for N also on a co-inductive definition.

Conclusion 2: I'm still puzzled by your willingness to wave your hands and invoke such a radically infinitary operation; either applying induction countably many times; or transfinite induction uncountably many times.

You are continuously equivocating "countably many" and "uncountably many"

I am applying succ to 0 an arbitrarily large number of times. I call this "infinity" in CoNat.
I am applying succ to Infinity an arbitrarily large number of times. I call this ω in CoInfinity
...
...

For someone who plays an intuitionist/constructivist/finitist on this forum, it's hard for me to reconcile your use of such infinitary processes.
[/qute]
Like I said - I have no problem with "infinitary processes". I have a problem with COMPLETED infinitary processes.

An infinitary process which "eventually enumerates all Naturals" is nonsense.
For such a process would need to write down 1, and 2; and 3.... in sequence. On infinite tape wihch has a cardinality equivalent to N.

When will such a process complete?
If it hasn't yet completed - then it's not yet a 1:1 bijection with N.

[Skepdick]

Countable plus countable is countable; so your new augmented list is countable.

On 2nd thought this is impossible to be true in linear logic.

If set A is countable (e.g in 1:1 bijection with N) then mapping A to N fully exhausts N.

There is no "room" left. You can't exhaust N again. |N| + |N| > |N|

Alternatively, if A ∪ B is countable (assuming A and B aren't the empty set) then neither A nor B are countable.

There simply isn't such a thing as "resource exhaustion" in a classical setting.
If I have 1 apple and I give you 2 - how many apples do I have left?

There exists no such operation.