History
Year:
-
Type:
Journal
Book
Article
Please fill in your query. A complete syntax description you will find on the General Help page.
Monotone relations, fixed points and recursive definitions. (English)
Makinson, David (ed.) et al., Towards mathematical philosophy. Papers from the Studia Logica conference Trends in Logic IV, Toruń, Poland, September 1‒4, 2006. Berlin: Springer (ISBN 978-1-4020-9083-7/hbk; 978-1-4020-9084-4/e-book). Trends in Logic‒Studia Logica Library 28, 125-164 (2009).
This paper mainly concerns in the theory of fixed points in posets, with focus on existence of objects described by various fixed-point procedures rather than on their definability. Moreover, the outlined method concerns fixed points of relations, not just functions. Therefore, the significance of fixed points in the context of indeterminate recursion principles is shown. The structures studied are posets which are at least chain-$σ$-complete. Many of the results presented in the paper are formulated in the language of such posets, but there are also theorems establishing the relationship between fixed-point theorems and results belonging to other disciplines, especially to set theory (in particular, AC and its weaker counterparts) as well as to definability by arithmetic recursion. In Section 1 of the paper, the necessary concepts and results from the theory of order are collected, and some fixed-point theorems for relations are presented. Further, the author introduces a version of a notion of a monotone relation and discusses its differences from those of {\it J. Desharnais} and {\it B. Möller} [High.-Order Symb. Comput. 18, No. 1‒2, 51‒77 (2005; Zbl 1081.06001)]. The main theorem states that, under the axiom of dependent choices, every chain-$σ$-continuous (hence, monotone) relation $R$ on a chain-$σ$-complete poset has a fixed point provided the set of $R$-images of $0$ is non-empty. An alternative proof of the downward Löwenheim-Skolem-Tarski theorem is outlined for illustration of the scope of the main theorem.
Jānis Cīrulis (Riga)