wtf wrote: ↑Wed Oct 16, 2024 3:57 am
Skepdick wrote: ↑Wed Oct 09, 2024 2:04 pm
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...
wtf wrote: ↑Wed Oct 16, 2024 3:57 am
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.
wtf wrote: ↑Wed Oct 16, 2024 3:57 am
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.
wtf wrote: ↑Wed Oct 16, 2024 3:57 am
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.
wtf wrote: ↑Wed Oct 16, 2024 3:57 am
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.
wtf wrote: ↑Wed Oct 16, 2024 3:57 am
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.
wtf wrote: ↑Wed Oct 16, 2024 3:57 am
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.
wtf wrote: ↑Wed Oct 16, 2024 3:57 am
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
wtf wrote: ↑Wed Oct 16, 2024 3:57 am
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?
wtf wrote: ↑Wed Oct 16, 2024 3:57 am
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.
wtf wrote: ↑Wed Oct 16, 2024 3:57 am
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.
wtf wrote: ↑Wed Oct 16, 2024 3:57 am
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.
wtf wrote: ↑Wed Oct 16, 2024 3:57 am
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.
wtf wrote: ↑Wed Oct 16, 2024 3:57 am
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.
wtf wrote: ↑Wed Oct 16, 2024 3:57 am
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
...
...
wtf wrote: ↑Wed Oct 16, 2024 3:57 am
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.
