Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Mild Shock <janburse@fastmail.fm> |
|---|---|
| Newsgroups | sci.math |
| Subject | Re: Ordinals |
| Date | 2024-03-01 21:08 +0100 |
| Message-ID | <urtckj$qfmv$1@solani.org> (permalink) |
| References | (10 earlier) <2NRiNAMtOqLljuoKQ0Z4UbqiHbE@jntp> <urrh33$cbpp$7@i2pn2.org> <thicnWRrTbih0Hz4nZ2dnZfqn_udnZ2d@giganews.com> <urtarb$qese$1@solani.org> <urtblr$qfb8$1@solani.org> |
I think the key are these terminological definitions:
"In order theory, a partial order is called well-founded if the
corresponding strict order is a well-founded relation. If the order is a
total order then it is called a well-order."
https://en.wikipedia.org/wiki/Well-founded_relation
So my tree "?" in question might have no infinite descend,
but it might not belong to the same total order, as the
other sets. But how exclude "?" ? The criteria of
transitive set is not violated:
trans(A) :<=> ∀ x , y : x ∈ A ∧ y ∈ x ⇒ y ∈ A
https://de.wikipedia.org/wiki/Transitive_Menge
One can easily verify that the above is satisfied by
the set "?". So what is violated? Well this
here is violate, namely each elememt should be
transitive as well, and so on:
"hereditarily transitive sets"
h-trans(A) :<=> trans(A) & ∀x(x ∈ A => h-trans(A))
Because the third branch is not transitive:
> ? = o
> / | \
> * o o
> | |
> * o
> |
> *
>
> Or as a set:
>
> ? = {{},{{}},{{{}}}}.
So I remember Jim Burns when he posited a more
general approach, he said transfinite induction
must be satisfied.
Otherwise we can take this Quine atom x = {x},
https://math.stackexchange.com/a/2874533
And by a suitable interpretation of the circular
h-trans definition, a definition that is not well-defined
since it has no unique interpretation,
we might judge this Quine atom an ordinal.
LoL
Mild Shock schrieb:
>
> Know that one is the secret and source of all the cardinals.
> -- Abraham ibn Ezra (1153)
>
> But have mercy to me. So far I thought in ordinal
> anlysis of programs, we would simply take the
> tree of execution, and this is somehow an ordinal
>
> for a terminating program? But whats the tree
> repectively ordinal for for example 3! = 6 ?
> Are all finite ordinals the same or not?
>
> For example the ordinals 0, 1, 2, 3, with von
> Neumann succeessor are:
>
> 0 = {}
> 1 = {{}}
> 2 = {{},{{}}}
> 3 = {{},{{}},{{{},{{}}}}}.
>
> Or as trees, * = empty set, o = non-empty set:
>
> 0 = *
>
> 1 = o
> |
> *
>
> 2 = o
> / \
> * o
> |
> *
>
>
> 3 = o
> / | \
> * o o
> | / \
> * * o
> |
> *
>
>
> But what about this tree, it has also no infinite decend,
> but what property is missing to make it an ordinal?
>
> ? = o
> / | \
> * o o
> | |
> * o
> |
> *
>
> Or as a set:
>
> ? = {{},{{}},{{{}}}}.
>
> Why is it not an ordinal?
>
> P.S.: I tried to find an answer here, but I guess
> I am too lazy to read it. Its starts with the funny
> quote and has funny pictures in it:
>
> Trees, ordinals and termination
> N Dershowitz · 1993
> https://link.springer.com/content/pdf/10.1007/3-540-56610-4_68.pdf
>
> Mild Shock schrieb:
>> Somehow I am quite new to the ordinal analysis
>> that Alan Turing started. Nice find Gödel introduces
>> a nice notion in his incompletness paper,
>>
>> namely he says a function is primitive recursive,
>> to degree N, if the primitive recursion schema is
>> applied N times. So I guess this definition of
>>
>> factorial would then have degree 3, since 'R' is used 3 times:
>>
>> /* The R combinator */
>> natrec(_, 0, X, X) :- !. % attention, not steadfast
>> natrec(F, N, X, Z) :- M is N-1, natrec(F, M, X, Y), call(F, Y, Z).
>>
>> plus(X, Y, Z) :- natrec(succ, X, Y, Z).
>>
>> mult(X, Y, Z) :- natrec(plus(X), Y, 0, Z).
>>
>> step((X,Y),(Z,T)) :- succ(X,Z), mult(Z,Y,T).
>>
>> factorial(X,Y) :- natrec(step,X,(0,1),(_,Y)).
>>
>> Works fine, although eats quite some computing resources,
>> i.e. 9_303_219 inferences, since it must form
>> 3268800 successors:
>>
>> ?- factorial(10,X).
>> X = 3628800.
>>
>> ?- time(factorial(10,X)).
>> % 9,303,219 inferences, 0.578 CPU in 0.617 seconds
>> (94% CPU, 16092054 Lips)
>> X = 3628800.
>>
>> Ross Finlayson schrieb:
>>> ... fourier my ass, what has it to do with ordinals ...
>>>
>>
>
Back to sci.math | Previous | Next — Previous in thread | Next in thread | Find similar
Re: Ordinals "markus...@gmail.com" <markusklyver@gmail.com> - 2024-02-20 11:35 -0800
Re: Ordinals Mild Shock <janburse@fastmail.fm> - 2024-02-20 20:54 +0100
Re: Ordinals "mitchr...@gmail.com" <mitchrae3323@gmail.com> - 2024-02-20 11:59 -0800
Re: Ordinals Ross Finlayson <ross.a.finlayson@gmail.com> - 2024-02-20 12:15 -0800
Re: Ordinals Ross Finlayson <ross.a.finlayson@gmail.com> - 2024-02-20 12:27 -0800
Re: Ordinals Jim Burns <james.g.burns@att.net> - 2024-02-20 17:02 -0500
Re: Ordinals Ross Finlayson <ross.a.finlayson@gmail.com> - 2024-02-20 19:36 -0800
Re: Ordinals Mild Shock <bursejan@gmail.com> - 2024-02-21 05:47 -0800
Re: Ordinals Mild Shock <bursejan@gmail.com> - 2024-02-21 05:50 -0800
Re: Ordinals Mild Shock <bursejan@gmail.com> - 2024-02-21 06:16 -0800
Re: Ordinals Ross Finlayson <ross.a.finlayson@gmail.com> - 2024-02-21 10:24 -0800
Re: Ordinals Mild Shock <janburse@fastmail.fm> - 2024-02-22 09:03 +0100
Re: Ordinals Mild Shock <janburse@fastmail.fm> - 2024-02-22 09:11 +0100
Re: Ordinals Ross Finlayson <ross.a.finlayson@gmail.com> - 2024-02-22 10:16 -0800
Re: Ordinals Mild Shock <janburse@fastmail.fm> - 2024-02-22 19:20 +0100
Re: Ordinals Mild Shock <janburse@fastmail.fm> - 2024-02-22 19:22 +0100
Re: Ordinals Mild Shock <janburse@fastmail.fm> - 2024-02-22 19:40 +0100
Re: Ordinals Mild Shock <janburse@fastmail.fm> - 2024-02-22 20:00 +0100
Re: Ordinals Ross Finlayson <ross.a.finlayson@gmail.com> - 2024-02-22 10:55 -0800
Re: Ordinals Mild Shock <janburse@fastmail.fm> - 2024-02-22 20:08 +0100
Re: Ordinals Mild Shock <janburse@fastmail.fm> - 2024-02-22 20:13 +0100
Re: Ordinals Ross Finlayson <ross.a.finlayson@gmail.com> - 2024-02-22 11:01 -0800
Re: Ordinals Mild Shock <janburse@fastmail.fm> - 2024-02-22 20:11 +0100
Re: Ordinals Mild Shock <janburse@fastmail.fm> - 2024-02-22 20:13 +0100
Re: Ordinals Jim Burns <james.g.burns@att.net> - 2024-02-22 14:34 -0500
Re: Ordinals Ross Finlayson <ross.a.finlayson@gmail.com> - 2024-02-22 11:39 -0800
Re: Ordinals Mild Shock <janburse@fastmail.fm> - 2024-02-23 00:41 +0100
Re: Ordinals WM <wolfgang.mueckenheim@tha.de> - 2024-02-21 08:33 +0000
Re: Ordinals Jim Burns <james.g.burns@att.net> - 2024-02-21 12:59 -0500
Re: Ordinals WM <wolfgang.mueckenheim@tha.de> - 2024-02-22 13:00 +0000
Re: Ordinals Jim Burns <james.g.burns@att.net> - 2024-02-22 11:13 -0500
Re: Ordinals WM <wolfgang.mueckenheim@tha.de> - 2024-02-23 08:47 +0000
Semanticists candy (Was: Ordinals) Mild Shock <janburse@fastmail.fm> - 2024-02-26 12:58 +0100
Re: Ordinals Jim Burns <james.g.burns@att.net> - 2024-02-27 14:25 -0500
Re: Ordinals Ross Finlayson <ross.a.finlayson@gmail.com> - 2024-02-27 11:59 -0800
Re: Ordinals WM <wolfgang.mueckenheim@tha.de> - 2024-02-27 20:05 +0000
Re: Ordinals Jim Burns <james.g.burns@att.net> - 2024-02-27 17:24 -0500
Re: Ordinals WM <wolfgang.mueckenheim@tha.de> - 2024-02-28 09:48 +0000
Re: Ordinals Jim Burns <james.g.burns@att.net> - 2024-02-28 06:52 -0500
Re: Ordinals WM <wolfgang.mueckenheim@tha.de> - 2024-02-28 17:24 +0000
Re: Ordinals Richard Damon <richard@damon-family.org> - 2024-02-28 17:07 -0500
Re: Ordinals WM <wolfgang.mueckenheim@tha.de> - 2024-02-29 08:23 +0000
Re: Ordinals Richard Damon <richard@damon-family.org> - 2024-02-29 07:35 -0500
Re: Ordinals WM <wolfgang.mueckenheim@tha.de> - 2024-02-29 19:25 +0000
Re: Ordinals "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-02-29 13:48 -0800
Re: Ordinals Richard Damon <richard@damon-family.org> - 2024-02-29 22:12 -0500
Re: Ordinals Ross Finlayson <ross.a.finlayson@gmail.com> - 2024-02-29 19:36 -0800
Re: Ordinals Mild Shock <janburse@fastmail.fm> - 2024-03-01 20:38 +0100
Re: Ordinals Mild Shock <janburse@fastmail.fm> - 2024-03-01 20:52 +0100
Re: Ordinals Mild Shock <janburse@fastmail.fm> - 2024-03-01 21:08 +0100
Re: Ordinals Jim Burns <james.g.burns@att.net> - 2024-03-01 15:56 -0500
Re: Ordinals Mild Shock <janburse@fastmail.fm> - 2024-03-01 22:53 +0100
Re: Ordinals Mild Shock <janburse@fastmail.fm> - 2024-03-01 23:11 +0100
Re: Ordinals Mild Shock <janburse@fastmail.fm> - 2024-03-01 23:33 +0100
Re: Ordinals Jim Burns <james.g.burns@att.net> - 2024-03-01 19:41 -0500
Re: Ordinals Ross Finlayson <ross.a.finlayson@gmail.com> - 2024-03-01 20:15 -0800
Re: Ordinals Ross Finlayson <ross.a.finlayson@gmail.com> - 2024-03-02 10:49 -0800
Re: Ordinals Mild Shock <janburse@fastmail.fm> - 2024-03-02 20:40 +0100
Re: Ordinals Ross Finlayson <ross.a.finlayson@gmail.com> - 2024-03-01 14:45 -0800
Re: Ordinals WM <wolfgang.mueckenheim@tha.de> - 2024-03-01 08:47 +0000
Re: Ordinals Richard Damon <richard@damon-family.org> - 2024-03-01 09:44 -0500
Re: Ordinals WM <wolfgang.mueckenheim@tha.de> - 2024-03-01 18:29 +0000
Re: Ordinals Richard Damon <richard@damon-family.org> - 2024-03-01 14:00 -0500
Re: Ordinals WM <wolfgang.mueckenheim@tha.de> - 2024-03-02 12:36 +0000
Re: Ordinals Richard Damon <richard@damon-family.org> - 2024-03-02 09:22 -0500
Re: Ordinals WM <wolfgang.mueckenheim@tha.de> - 2024-03-02 15:25 +0000
Re: Ordinals "mitchr...@gmail.com" <mitchrae3323@gmail.com> - 2024-02-20 17:21 -0800
RSemanticists candy (Re: Ordinals) [Addendum] Mild Shock <janburse@fastmail.fm> - 2024-02-26 13:01 +0100
csiph-web