Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userConstructing Initial Algebras Using Inflationary Iteration
76
0
0.0
(
0
)
Added by
Andrew Pitts
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
An old theorem of Adamek constructs initial algebras for sufficiently cocontinuous endofunctors via transfinite iteration over ordinals in classical set theory. We prove a new version that works in constructive logic, using inflationary iteration over a notion of size that abstracts from limit ordinals just their transitive, directed and well-founded properties. Borrowing from Taylors constructive treatment of ordinals, we show that sizes exist with upper bounds for any given signature of indexes. From this it follows that there is a rich class of endofunctors to which the new theorem applies, provided one admits a weak form of choice (WISC) due to Streicher, Moerdijk, van den Berg and Palmgren, and which is known to hold in the internal constructive logic of many kinds of elementary topos.
rate research
Read More
For every partial combinatory algebra (pca), we define a hierarchy of extensionality relations using ordinals. We investigate the closure ordinals of pcas, i.e. the smallest ordinals where these relations become equal. We show that the closure ordinal of Kleenes first model is $omega_1^textit{CK}$ and that the closure ordinal of Kleenes second model is $omega_1$. We calculate the exact complexities of the extensionality relations in Kleenes first model, showing that they exhaust the hyperarithmetical hierarchy. We also discuss embeddings of pcas.
This article extends the idea of solving parity games by strategy iteration to non-deterministic strategies: In a non-deterministic strategy a player restricts himself to some non-empty subset of possible actions at a given node, instead of limiting himself to exactly one action. We show that a strategy-improvement algorithm by by Bjoerklund, Sandberg, and Vorobyov can easily be adapted to the more general setting of non-deterministic strategies. Further, we show that applying the heuristic of all profitable switches leads to choosing a locally optimal successor strategy in the setting of non-deterministic strategies, thereby obtaining an easy proof of an algorithm by Schewe. In contrast to the algorithm by Bjoerklund et al., we present our algorithm directly for parity games which allows us to compare it to the algorithm by Jurdzinski and Voege: We show that the valuations used in both algorithm coincide on parity game arenas in which one player can surrender. Thus, our algorithm can also be seen as a generalization of the one by Jurdzinski and Voege to non-deterministic strategies. Finally, using non-deterministic strategies allows us to show that the number of improvement steps is bound from above by O(1.724^n). For strategy-improvement algorithms, this bound was previously only known to be attainable by using randomization.
Formulae of the Lambek calculus are constructed using three binary connectives, multiplication and two divisions. We extend it using a unary connective, positive Kleene iteration. For this new operation, following its natural interpretation, we present two lines of calculi. The first one is a fragment of infinitary action logic and includes an omega-rule for introducing iteration to the antecedent. We also consider a version with infinite (but finitely branching) derivations and prove equivalence of these t
In [1] a new cosmological model is proposed with no big bang singularity in the past, though past geodesically incomplete. This model starts with an inflationary era, follows with a stiff matter dominated period and evolves to accelerated expansion in an asymptotically de Sitter regime in a realistic fashion. The big bang singularity is replaced by a directional singularity. This singularity cannot be reached by comoving observers, since it would take them an infinite proper time lapse to go back to it. On the contrary, observers with nonzero linear momentum have the singularity at finite proper time in their past, though arbitrarily large. Hence, the time lapse from the initial singularity can be as long as desired, even infinity, depending on the linear momentum of the observer. This conclusion applies to similar inflationary models. Due to the interest of these models, we address here the properties of such singularities.
For simple theories with a strong version of amalgamation we obtain the canonical hyperdefinable group from the group configuration. This provides a generalization to simple theories of the group configuration theorem for stable theories.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
