Initial algebras without iteration
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F21%3A00363397" target="_blank" >RIV/68407700:21230/21:00363397 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.4230/LIPIcs.CALCO.2021.5" target="_blank" >https://doi.org/10.4230/LIPIcs.CALCO.2021.5</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.CALCO.2021.5" target="_blank" >10.4230/LIPIcs.CALCO.2021.5</a>
Alternative languages
Result language
angličtina
Original language name
Initial algebras without iteration
Original language description
The Initial Algebra Theorem by Trnková et al. states, under mild assumptions, that an endofunctor has an initial algebra provided it has a pre-fixed point. The proof crucially depends on transfinitely iterating the functor and in fact shows that, equivalently, the (transfinite) initial-algebra chain stops. We give a constructive proof of the Initial Algebra Theorem that avoids transfinite iteration of the functor. For a given pre-fixed point A of the functor, it uses Pataraia’s theorem to obtain the least fixed point of a monotone function on the partial order formed by all subobjects of A. Thanks to properties of recursive coalgebras, this least fixed point yields an initial algebra. We obtain new results on fixed points and initial algebras in categories enriched over directed-complete partial orders, again without iteration. Using transfinite iteration we equivalently obtain convergence of the initial-algebra chain as an equivalent condition, overall yielding a streamlined version of the original proof.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10101 - Pure mathematics
Result continuities
Project
<a href="/en/project/GA19-00902S" target="_blank" >GA19-00902S: Injectivity and Monads in Algebra and Topology</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2021
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)
ISBN
978-3-95977-212-9
ISSN
1868-8969
e-ISSN
—
Number of pages
20
Pages from-to
1-20
Publisher name
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Place of publication
Dagstuhl
Event location
Salzburg
Event date
Aug 31, 2021
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—