Standard |N is not recursive

[Julio Di Egidio]

The standard (as in "standard mathematics") set of natural numbers is
not recursive. Let's start with Halmos:

On 23/11/2021 01:10, Julio Di Egidio wrote:
[Re: The non-existence of the set of all things that are NOT purple]
> On Monday, 22 November 2021 at 22:51:52 UTC+1, Julio Di Egidio wrote:
>> On Monday, 22 November 2021 at 21:04:13 UTC+1, Fritz Feldhase wrote:
>>> On Monday, November 22, 2021 at 6:44:16 PM UTC+1, Julio Di Egidio
wrote:
>>
>>>> Maybe it's trivial, but I'd expect some proof of existence of a
>>>> least element or something...
>> <snipped>
>>
>>> Note that we are working in the context of ZFC without the Axiom of
>>> Foundation.
>>> Indeed! We may restate the AoI the following way now: EA succSet(A).
>>> Finally, [Halmos] defines w [omega], the set of (all) natural
>>> numbers:
>>> | Since the intersection of every (non-empty) family of successor
>>> sets is a successor set itself (proof?),
>>> the intersection of all the successor sets included in A is a
>>> successor set w.
>>
>> I'm with you/him that far.
>>
>>> The set w is a subset of every successor set. If, indeed, B is an
>>> arbitrary successor set,
>>> then so is A n B. Since A n B c A, the set A n B is one of the sets
>>> that entered into the definition of w;
>>> it follows that w c A n B, and, consequently, that w c B.
>>
>> OK if by 'c' you did *not* mean proper subset, otherwise I don't see
>> why that should be (generally) true.

I was being polite: to be clear, the point was that's simply false.

>>> The minimality property so established uniquely characterizes w
>>
>> Does it? Nor, on the other hand, I can see how we would prove that
>> there is not just one successor set in that entire universe.
>
> OK, it cannot be unique, we can add "non-standard zeros" (with their
> successors), i.e. elements that are not 0 or a successor thereof, to
> any successor set and it is still a successor set, QED. Then we might
> say the minimal successor set is the one that only contains "standard"
> elements, those than can be reached from 0 by a finite number of
> successor applications. -- I am still not convinced though, all that
> talk of standard/non-standard: can we actually prove that an arbitrary
> set X is *not* a "standard" element of successor sets?

Enough thought: unless I am missing something, the answer is simply no.
QED.

For those who have missed the steps (kudos to FF for giving me the "basis"):

1. define successor of a set; // succ(x) = x union {x}
2. define generic successor set ("successor sets", SSs);
// s is an SS iff 0 in s and, for all n, if n in s then succ(n) in s;
3. define standard vs non-standard elements of (any of) SSs;
// 0 is standard and, for all x, if x is standard so is succ(x);
// x is non-standard iff not x is standard;
4. see that that distinction is *not* decidable (recursive);
// if x is standard, checking is-standard(x) will always terminate;
// if x is not standard, checking is-standard(x) will not terminate.
5. give up on a minimal SS, since a fortiori it is *not* recursive; or,
5'. subvert logic by authority, and go chase uber-cardinals and
blowing-up singularities ever after.

(Right? This is an open project: just you'll excuse me if I won't be
holding my breath.)

Now let us rather reconsider PM...

Julio

[Jim Burns]

On 11/25/2021 3:10 AM, Julio Di Egidio wrote:
> On 23/11/2021 01:10, Julio Di Egidio wrote:
> [Re: The non-existence of the set of all things that are NOT purple]
> > On Monday, 22 November 2021 at 22:51:52 UTC+1, Julio Di Egidio wrote:
> >> On Monday, 22 November 2021 at 21:04:13 UTC+1, Fritz Feldhase wrote:
> >>> On Monday, November 22, 2021 at 6:44:16 PM UTC+1, Julio Di Egidio
> wrote:
> >>
> >>>> Maybe it's trivial, but I'd expect some proof of
> >>>> existence of a least element or something...
> >> <snipped>
> >>
> >>> Note that we are working in the context of ZFC without
> >>> the Axiom of Foundation.
> >>> Indeed! We may restate the AoI the following way now:
> >>> EA succSet(A).
> >>> Finally, [Halmos] defines w [omega], the set of
> >>> (all) natural numbers:
> >>> | Since the intersection of every (non-empty) family of
> >>> successor sets is a successor set itself (proof?),
> >>> the intersection of all the successor sets included in A
> >>> is a successor set w.
> >>
> >> I'm with you/him that far.

Call this Lemma 1.
| If ∀s ∈ A, Succ(s) and A ≠ {} then Succ(∩A)

> >>> The set w is a subset of every successor set. If, indeed, B is an
> >>> arbitrary successor set,
> >>> then so is A n B. Since A n B c A, the set A n B is one of the sets
> >>> that entered into the definition of w;
> >>> it follows that w c A n B, and, consequently, that w c B.
> >>
> >> OK if by 'c' you did *not* mean proper subset, otherwise
> >> I don't see why that should be (generally) true.
>
> I was being polite:
> to be clear, the point was that's simply false.

You're wrong.

I suspect that the reason that disagreement is
typically expressed more tentatively in math and logic
circles is less a matter being polite and more
a matter of having been wrong in the past -- or,
more significantly, a matter of _having realized_
they were wrong in the past.

----
Define the set of successor subsets of A
sccsbs(A) = { s ⊆ A | Succ(s) }

Let A be a successor set.
Define
ω[A] = Intrsct(sccsbs(A))

Because intersection, ∀s ∈ sccsbs(A), ω[A] ⊆ s


Let B be any successor set.
By Lemma 1, Succ(A∩B)
A∩B ⊆ A
A∩B ∈ sccsbs(A)
ω[A] ⊆ A∩B

Also, A∩B ⊆ B, so
ω[A] ⊆ A∩B ⊆ B
ω[A] ⊆ B

Lemma 2.
∀B, Succ(B) -> ω[A] ⊆ B

> >>> The minimality property so established uniquely characterizes w
> >>
> >> Does it? Nor, on the other hand, I can see how we would prove that
> >> there is not just one successor set in that entire universe.

Let B be a successor set.
By Lemma 1, Succ(ω[B])
By Lemma 2, ω[A] ⊆ ω[B]

By a similar argument, ω[B] ⊆ ω[A]

( ω[A] ⊆ ω[B] ∧ ω[B] ⊆ ω[A] ) -> ω[A] = ω[B]

Lemma 3.
∀A,B, Succ(A) & Succ(B) -> ω[A] = ω[B]

Dropping '[A]', ω is the unique intersection
of all the successor subsets of any successor set.
Changing the successor set doesn't change ω

> > OK, it cannot be unique, we can add "non-standard zeros" (with their
> > successors), i.e. elements that are not 0 or a successor thereof, to
> > any successor set and it is still a successor set, QED. Then we might

Let A be a successor set.
Add non-standard zero {b} and its successors.
B = A ∪ { {b}, {b,{b}}, {b,{b},{b,{b}}}, ... }
Yes, B is a successor set.
No, that doesn't affect ω

Nonstandard {b}, {b,{b}}, ... are not in any
successor subset of A.
The intersection of successor subsets of B must
subset each successor subset of A.
No nonstandard {b}, {b,{b}}, ... is in any subset of A.
No nonstandard {b}, {b,{b}}, ... is in ω

> > any successor set and it is still a successor set, QED. Then we might
> > say the minimal successor set is the one that only contains "standard"
> > elements, those than can be reached from 0 by a finite number of
> > successor applications.  --  I am still not convinced though, all that
> > talk of standard/non-standard: can we actually prove that an arbitrary
> > set X is *not* a "standard" element of successor sets?
>
> Enough thought: unless I am missing something, the answer is simply no.
> QED.

You are apparently missing the distinction between A
and Intrsct(sccsbs(A))

> For those who have missed the steps (kudos to FF for giving me the
> "basis"):
>
> 1. define successor of a set;  // succ(x) = x union {x}
> 2. define generic successor set ("successor sets", SSs);
>   // s is an SS iff 0 in s and, for all n, if n in s then succ(n) in s;
> 3. define standard vs non-standard elements of (any of) SSs;
>   // 0 is standard and, for all x, if x is standard so is succ(x);
>   // x is non-standard iff not x is standard;

There is conventionally an implicit minimality condition
in a definition like that. With a minimality condition,
standard and non-standard elements are exactly what
one would expect them tobe.

Without that convention, I could assert {b} is standard,
and you could not prove me wrong.

You could prove {b} was not in ω[B] = Intrsct(sccsbs(B))
but this does not contradict {b} being your "standard"

It seems to me that a minimality condition is called for,
implicit or otherwise. If you disagree, why do you disagree?

[Julio Di Egidio]

On Thursday, 25 November 2021 at 17:10:19 UTC+1, Jim Burns wrote:
> On 11/25/2021 3:10 AM, Julio Di Egidio wrote:
> > On 23/11/2021 01:10, Julio Di Egidio wrote:

> > I was being polite:
> > to be clear, the point was that's simply false.
> You're wrong.
>
> I suspect that the reason that disagreement is
> typically expressed more tentatively in math and logic
> circles is less a matter being polite and more
> a matter of having been wrong in the past -- or,
> more significantly, a matter of _having realized_
> they were wrong in the past.

You forget I am not an English native speaker, plus I am even sarcastic at times, go figure... You instead just echo, suspect and inject the worst nazi bullshit around, as usual indeed. That said, I suggest you simply reconsider what you wrote (don't count on me wasting any time on your trolls) and try again if you are serious: you go second order, which is completely out of place here, and of course (possibly) at second order we can do it...

Have fun,

Julio

[Julio Di Egidio]

But, to be clear since *you* won't get it otherwise, that I had been trying to be polite is plain true. You are simply full oh shit...

*Troll Alert*

Julio

[Jim Burns]

On 11/26/2021 2:38 AM, Julio Di Egidio wrote:

> and try again if you are serious:
> you go second order, which is completely out of place here,
> and of course (possibly) at second order we can do it...

ZFC-Regularity is first order.
Not possibly, certainly, we can do it.
I just showed you.

If you have trouble understanding, try asking questions.

----

> >>> | Since the intersection of every (non-empty) family of
> >>> successor sets is a successor set itself (proof?),
> >>> the intersection of all the successor sets included in A
> >>> is a successor set w.
> >>
> >> I'm with you/him that far.

Call this Lemma 1.
| If ∀s ∈ A, Succ(s) and A ≠ {} then Succ(∩A)

> to be clear, the point was that's simply false.

You're wrong.

> Have fun,
>
> Julio
>

[Jim Burns]

On 11/26/2021 2:41 AM, Julio Di Egidio wrote:
> On Friday, 26 November 2021 at 08:38:03 UTC+1,
> Julio Di Egidio wrote:
>> On Thursday, 25 November 2021 at 17:10:19 UTC+1,
>> Jim Burns wrote:
>>> On 11/25/2021 3:10 AM, Julio Di Egidio wrote:
>>>> On 23/11/2021 01:10, Julio Di Egidio wrote:

>>>> I was being polite:
>>>> to be clear, the point was that's simply false.
>>>
>>> You're wrong.
>>>
>>> I suspect that the reason that disagreement is
>>> typically expressed more tentatively in math and logic
>>> circles is less a matter being polite and more
>>> a matter of having been wrong in the past -- or,
>>> more significantly, a matter of _having realized_
>>> they were wrong in the past.
>>
>> You forget I am not an English native speaker,

I have kept that in mind. I don't think English is
the problem here.
What you write is pretty clear at the language level.
And this is mostly Mathematics-English.

I think that you react defensively to challenges to
your mathematical knowledge. In you, what "defensively"
looks like is what, in my neighborhood, the Midwest US,
would be thought to be some kind of mental breakdown.

I haven't forgotten you're not a local. I have given you
enormous leeway because of it.

I wonder if there is some part of Italy where people
live their lives saturated in outrageous insults. Rome?

On the positive side, it's possible you are actually trying
to learn, in between bouts of -- just guessing -- Being Roman.

If you want to learn, you need to get over being defensive
over not knowing or not understanding things. If you
think you've hidden that, you're wrong. You're just
making it harder to help you.

>> plus I am even sarcastic at times, go figure...
>> You instead just echo, suspect and inject the worst
>> nazi bullshit around, as usual indeed.
>> That said, I suggest you simply reconsider
>> what you wrote (don't count on me wasting any time on
>> your trolls)

[Python]

I won't bet on that... Julio once tried to understand Special
Relativity (on - go figure! - sci.physics.relativity). It didn't
end well. He end up forging his own version of SR, completely idiotic
and self-contradictory.

[Ross A. Finlayson]

"SR is local", is a rather modern way of solving some problems with
some interpretations of SR.

It's been quite shaking the recent news about that "inflationary theories
don't hold up", making for a re-think that is necessarily retro as much
as piling on adjustments.


About recursivity and the infinite, the supertasl and asymptotics and
asymptotic freedom is a pretty interesting thing, here what happens
to point to mathematical infinities for physics, for singularity theory
and string theory and so on.

[Python]

Finlayson, what you just wrote make very little sense. Moreover it
is completely unrelated with the post you were answering to.

[Ross A. Finlayson]

Of course you might know that string theory is basically a theory of
mathematical infinitesimals, that the "atomic scale" is the regime
that is finitely small to the Democritan or structure in chemsitry,
that the superstrings are finitely small again, why the orders of
magnitude -25 and -50 basically are there to represent a finite value
of the "infinite limit" for a contiguous continuous substrate of a
continuous space-time for a continuum mechanics.


Then with respect to the transfer principle and bridge results,
about what follows after recursivity also completeness, about
N and omega and N+ and ubiquitous ordinals and an infinite
ordinals and whether it's extra-ordinary and that it's compact,
it's speaking to the matter.

So, I hope you'll enjoy that physics' need for real mathematical
infinities for its theories, makes for that eventually the various
applied features are basically for a holist monism.

[Ross A. Finlayson]

I don't know if you're aware of theories where there isn't actually
any standard model of the integers, rather fragments and extensions.

Instead it's directly axiomatized in ZF that there's a complete inductive
set that is axiomatized well-founded that otherwise would as neatly
as anything else be Russell's Frege's antinomy.

[Python]

Ross A. Finlayson wrote:
...

> Of course you might know that string theory is basically a theory

> of [ blah ]

could you please go fuck yourself?

[Julio Di Egidio]

On Friday, 26 November 2021 at 17:50:15 UTC+1, Ross A. Finlayson wrote:
> On Friday, November 26, 2021 at 6:20:30 AM UTC-8, Python wrote:
> > Jim Burns wrote:

<snip>

> > > If you want to learn, you need to get over being defensive
> > > over not knowing or not understanding things. If you
> > > think you've hidden that, you're wrong. You're just
> > > making it harder to help you.
> >
> > I won't bet on that... Julio once tried to understand Special
> > Relativity (on - go figure! - sci.physics.relativity). It didn't
> > end well. He end up forging his own version of SR, completely idiotic
> > and self-contradictory.
>
> "SR is local", is a rather modern way of solving some problems with
> some interpretations of SR.

Ross, please don't bother, these are patently pathological cases:
rather ignore them, as that's what they do, pollute ponds...

Julio

[Julio Di Egidio]

Rather, stop feeding the trolls and you too please be more careful: SR is
much more than just a local theory if you actually ask me. Look up so
called Geometric Algebra as a starter...

EODigression.

Julio

[Ross A. Finlayson]

Ah, but one of its central tenets that light is always fastest in the geodesy,
is that light instead or the image is outrun, as what under acceleration,
is that light, is flux and conserved for its energy, also is the central tenet
defining that on the chip, there is Rayleigh Dalton.

So, it's local in both respects.

Also for other usual matters where special relativity is applied in
computing what are values that result after constants, what
are expected propagations, in phase transitions, is that the usual
computer chip is where special relativity in the optonic and thermionic,
also besides insulator or where gates make charge for those being
usual classical junctions, special relativity in light and electricity
of course is a usual general controller, of what under its invariance
when there are not gauge theories after the "kinetic" there is
what's left of relativity, or where they are gauge theories,
what it means when, "SR, is, ..., "only" local and not necessarily
global or total in field effect the theory", here then is for whether
and how it is point under the invariance, SR and for often the
constructive and so on propagated in theories with parallel transport.

Standard N or the thread subject is "integers, positive, infinite".

I.e. "standard" N is "standardly" infinite.

Standardizability is great for standardizing the term, here
it means much the same in effect for what as a value,
as such terms of unbounded in the linear, it means
"one square infinite", and for example that there is
or isn't, an infinite square, or only an infinite table.

Usually it makes for the operators or arithmetic, what
is called standardization for normalization in usually
probability's terms, here also in terms what reflect
effort in words, here the point is that there is some
refular set-theoretic infinity called omega as an ordinal
or some recursive set that's infinite what is called
an "inductive" set (infinite).

Here having one doesn't necessarily mean having more than one,
that "there is an unbounded inductive resource, let's call it time",
makes usually for bounds in all the things, with mathematics
and geometry, that any two infinities that happen to be square
simply make a 1 X 1 space.

[Mostowski Collapse]

In theoretical computer science "recursive" means
partial recursive and terminating. Partial recursive
has different definitions, which are all the same

by Church thesis:

It states that a function on the natural numbers can be calculated
by an effective method if and only if it is computable by a Turing machine.
https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis

In as far natural number arithmetic is not recursive.
You can easily define functions which are
not recursive.

[Mostowski Collapse]

Somehow sci.logic is proof that Ultracrepidarianism doesn't
work, not like bitrot stackexchange seems to suggest. A little
upvote here and a little downvote here,

and we have expert knowledge?

LoL

On the other hand I am all in with Karl Marx: “ 'Ne sutor ultra crepidam' –
this nec plus ultra of handicraft wisdom became sheer nonsense,
from the moment the watchmaker Watt invented the steam-engine,
the barber Arkwright the throstle,

and the working-jeweller Fulton the steamship."
https://en.wikipedia.org/wiki/Sutor,_ne_ultra_crepidam

[Mostowski Collapse]

There was a proposal:
https://area51.stackexchange.com/proposals/29144/beginner-theoretical-computer-science
But it now says:
This proposal has been deleted

Now if you want to join cstheory.stackexchange.com it
says Anybody can ask a question Anybody can answer
The best answers are voted up and rise to the top

But if you do that, they slap their policy into your face:
It allows only questions that "can be discussed between
two professors or between two graduate students working
on Ph.D.'s, but not usually between a professor and a
typical undergraduate student".
https://meta.stackexchange.com/questions/79351/should-research-level-only-sites-be-allowed

I am not lying when I say even Andrej Bauer did
that. But how do you want to launch a proof assistants
site, I assume for everybody? if you cannot divert
cs theory questions to another stackexchange?

proof assistants are full of cs theory stuff.

[Mostowski Collapse]

Anyway, these bitrot exchanges are mushrooming,
what about this one, would it be helpful?

https://cs.stackexchange.com/