The Experts below are selected from a list of 198 Experts worldwide ranked by ideXlab platform
Thomas Strahm - One of the best experts on this subject based on the ideXlab platform.
-
autonomous fixed point progressions and fixed point Transfinite Recursion
1999Co-Authors: Thomas StrahmAbstract:This paper is a contribution to the area of metapredicative proof theory. It continues recent investigations on the Transfinitely iterated fixed point theories IDα (cf. [10]) and addresses the question of autonomity in iterated fixed point theories. An external and an internal form of autonomous generation of Transfinite hierarchies of fixed points of positive arithmetic operators are introduced and proof-theoretically analyzed. This includes the discussion of the principle of so-called fixed point Transfinite Recursion. Connections to theories for iterated inaccessibility in the context of Kripke Platek set theory without foundation are revealed.
-
Autonomous Fixed Point Progressions and Fixed Point Transfinite Recursion
2026Co-Authors: Thomas StrahmAbstract:. This paper is a contribution to the area of metapredicative proof theory. It continues recent investigations on the Transfinitely iterated fixed point theories # ID# (cf. [10]) and addresses the question of autonomity in iterated fixed point theories. An external and an internal form of autonomous generation of Transfinite hierarchies of fixed points of positive arithmetic operators are introduced and proof-theoretically analyzed. This includes the discussion of the principle of so-called fixed point Transfinite Recursion. Connections to theories for iterated inaccessibility in the context of Kripke Platek set theory without foundation are revealed. 1 Introduction The foundational program to study the principles and ordinals which are implicit in a predicative conception of the universe of sets of natural numbers led to the progression of systems of ramified analysis up to the famous Feferman-Schutte ordinal # 0 in the early sixties. Since then numerous theories have been found w..
Heikkilä Seppo - One of the best experts on this subject based on the ideXlab platform.
-
A mathematically derived definitional/semantical theory of truth
2018Co-Authors: Heikkilä SeppoAbstract:Ordinary and Transfinite Recursion and induction and ZF set theory are used to construct from a fully interpreted object language and from an extra formula a new language. It is fully interpreted under a suitably defined interpretation. This interpretation is equivalent to the interpretation by meanings of sentences if the object language is so interpreted. The added formula provides a truth predicate for the constructed language. The so obtained theory of truth satisfies the norms presented in Hannes Leitgeb's paper 'What Theories of Truth Should be Like (but Cannot be)'
-
A mathematically derived definitional/semantical theory of truth
2017Co-Authors: Heikkilä SeppoAbstract:Ordinary and Transfinite Recursion and induction and ZF set theory are used to construct from a fully interpreted object language and from an extra formula a new language. It is fully interpreted under a suitably defined interpretation. This interpretation is equivalent to the interpretation by meanings of sentences if the object language is so interpreted. The added formula provides a truth predicate for the constructed language. The so obtained theory of truth satisfies the norms presented in Hannes Leitgeb's paper 'What Theories of Truth Should be Like (but Cannot be)'.Comment: Some proofs are simplified (see, eg. the proof of Lemma 3.2
-
On the construction of fully interpreted formal languages which posses their truth predicates
2015Co-Authors: Heikkilä SeppoAbstract:We shall construct by ordinary Recursion method subsets to the set $D$ of G\"odel numbers of the sentences of a language $\mathcal L$. That language is formed by sentences of a fully interpreted formal language $L$, called an MA language, and sentences containing a monadic predicate letter $T$. From the class of the constructed subsets of $D$ we extract one set $U$ by Transfinite Recursion method. Interpret those sentences whose G\"odel numbers are in $U$ as true, and their negations as false. These sentences together form an MA language. It is a sublanguage of $\mathcal L$ having $L$ as its sublanguage, and $T$ is its truth predicate.Comment: 10 page
Lawrence C. Paulson - One of the best experts on this subject based on the ideXlab platform.
-
set theory for verification ii induction and Recursion
arXiv: Logic in Computer Science, 2000Co-Authors: Lawrence C. PaulsonAbstract:A theory of recursive definitions has been mechanized in Isabelle's Zermelo-Fraenkel (ZF) set theory. The objective is to support the formalization of particular recursive definitions for use in verification, semantics proofs and other computational reasoning. Inductively defined sets are expressed as least fixedpoints, applying the Knaster-Tarski Theorem over a suitable set. Recursive functions are defined by well-founded Recursion and its derivatives, such as Transfinite Recursion. Recursive data structures are expressed by applying the Knaster-Tarski Theorem to a set, such as V[omega], that is closed under Cartesian product and disjoint sum. Worked examples include the transitive closure of a relation, lists, variable-branching trees and mutually recursive trees and forests. The Schr\"oder-Bernstein Theorem and the soundness of propositional logic are proved in Isabelle sessions.
-
Set theory for verification. II: Induction and Recursion
Journal of Automated Reasoning, 1995Co-Authors: Lawrence C. PaulsonAbstract:A theory of recursive definitions has been mechanized in Isabelle's Zermelo-Fraenkel (ZF) set theory. The objective is to support the formalization of particular recursive definitions for use in verification, semantics proofs, and other computational reasoning. Inductively defined sets are expressed as least fixedpoints, applying the Knaster-Tarski theorem over a suitable set. Recursive functions are defined by well-founded Recursion and its derivatives, such as Transfinite Recursion. Recursive data structures are expressed by applying the Knaster-Tarski theorem to a set, such as V _ω, that is closed under Cartesian product and disjoint sum. Worked examples include the transitive closure of a relation, lists, variable-branching trees, and mutually recursive trees and forests. The Schröder-Bernstein theorem and the soundness of propositional logic are proved in Isabelle sessions.
-
Set theory for verification: II. induction and Recursion
1995Co-Authors: Lawrence C. PaulsonAbstract:Abstract. A theory of recursive definitions has been mechanized in Isabelle’s Zermelo-Fraenkel (ZF) set theory. The objective is to support the formalization of particular recursive definitions for use in verification, semantics proofs and other computational reasoning. Inductively defined sets are expressed as least fixedpoints, applying the Knaster-Tarski Theorem over a suitable set. Recursive functions are defined by well-founded Recursion and its derivatives, such as Transfinite Recursion. Recursive data structures are expressed by applying the Knaster-Tarski Theorem to a set, such as Vω, that is closed under Cartesian product and disjoint sum. Worked examples include the transitive closure of a relation, lists, variable-branching trees and mutually recursive trees and forests. The Schröder-Bernstein Theorem and the soundness of propositional logic are proved in Isabelle sessions. Key words: Isabelle, set theory, recursive definitions, the Schröder-Bernstein Theore
-
Set Theory for Verification: II - Induction and Recursion
1995Co-Authors: Lawrence C. PaulsonAbstract:. A theory of recursive definitions has been mechanized in Isabelle's Zermelo-Fraenkel (ZF) set theory. The objective is to support the formalization of particular recursive definitions for use in verification, semantics proofs and other computational reasoning. Inductively defined sets are expressed as least fixedpoints, applying the Knaster-Tarski Theorem over a suitable set. Recursive functions are defined by well-founded Recursion and its derivatives, such as Transfinite Recursion. Recursive data structures are expressed by applying the Knaster-Tarski Theorem to a set, such as V# , that is closed under Cartesian product and disjoint sum. Worked examples include the transitive closure of a relation, lists, variable-branching trees and mutually recursive trees and forests. The Schroder-Bernstein Theorem and the soundness of propositional logic are proved in Isabelle sessions. Key words: Isabelle, set theory, recursive definitions, the Schroder-Bernstein Theorem Contents 1 Introd..
Stephen G Simpson - One of the best experts on this subject based on the ideXlab platform.
-
subsystems of second order arithmetic
1999Co-Authors: Stephen G SimpsonAbstract:List of tables Preface Acknowledgements 1. Introduction Part I. Development of Mathematics within Subsystems of Z2: 2. Recursive comprehension 3. Arithmetical comprehension 4. Weak Konig's lemma 5. Arithmetical Transfinite Recursion 6. pi11 comprehension Part II. Models of Subsystems of Z2: 7. ss-models 8. omega-models 9. Non-omega-models Part III. Appendix: 10. Additional results Bibliography Index.
-
On the strength of König’s duality theorem of countable bipartite graphs
1994Co-Authors: Stephen G SimpsonAbstract:Abstract. Let CKDT be the assertion that, for every countably infinite bipartite graph G, there exist a vertex covering C of G and a matching M in G such that C consists of exactly one vertex from each edge in M. (This is a theorem of Podewski and Steffens [12].) Let ATR0 be the subsystem of second order arithmetic with arithmetical Transfinite Recursion and restricted induction. Let RCA0 be the subsystem of second order arithmetic with recursive comprehension and restricted induction. We show that CKDT is provable in ATR0. Combining this with a result of Aharoni, Magidor and Shore [2], we see that CKDT is logically equivalent to the axioms of ATR0, the equivalence being provable in RCA0. 1
-
On The Strength Of König's Duality Theorem For Countable Bipartite Graphs
1994Co-Authors: Stephen G SimpsonAbstract:Let CKDT be the assertion that, for every countably infinite bipartite graph G, there exist a vertex covering C of G and a matching M in G such that C consists of exactly one vertex from each edge in M . (This is a theorem of Podewski and Steffens [12].) Let ATR 0 be the subsystem of second order arithmetic with arithmetical Transfinite Recursion and restricted induction. Let RCA 0 be the subsystem of second order arithmetic with recursive comprehension and restricted induction. We show that CKDT is provable in ATR 0 . Combining this with a result of Aharoni, Magidor and Shore [2], we see that CKDT is logically equivalent to the axioms of ATR 0 , the equivalence being provable in RCA 0
Sam Sanders - One of the best experts on this subject based on the ideXlab platform.
-
the strength of compactness in computability theory and nonstandard analysis
Annals of Pure and Applied Logic, 2019Co-Authors: Dag Normann, Sam SandersAbstract:Abstract Compactness is one of the core notions of analysis: it connects local properties to global ones and makes limits well-behaved. We study the computational properties of the compactness of Cantor space 2 N for uncountable covers. The most basic question is: how hard is it to compute a finite sub-cover from such a cover of 2 N ? Another natural question is: how hard is it to compute a sequence that covers 2 N minus a measure zero set from such a cover? The special and weak fan functionals respectively compute such finite sub-covers and sequences. In this paper, we establish the connection between these new fan functionals on one hand, and various well-known comprehension axioms on the other hand, including arithmetical comprehension, Transfinite Recursion, and the Suslin functional. In the spirit of Reverse Mathematics, we also analyse the logical strength of compactness in Nonstandard Analysis. Perhaps surprisingly, the results in the latter mirror (often perfectly) the computational properties of the special and weak fan functionals. In particular, we show that compactness (nonstandard or otherwise) readily brings us to the outer edges of Reverse Mathematics (namely Π 2 1 - CA 0 ), and even into Schweber's higher-order framework (namely Σ 1 2 -separation).
-
the strength of compactness in computability theory and nonstandard analysis
arXiv: Logic, 2018Co-Authors: Dag Normann, Sam SandersAbstract:The authors recently pioneered a connection between Nonstandard Analysis and Computability Theory, resulting in a number of surprising results and even more open questions. We answer some of the latter in this paper, all of which pertain to the two following intimately related topics. (T.1) A basic property of Cantor space $2^{\mathbb{N}}$ is Heine-Borel compactness: Any open cover of $2^{\mathbb{N}}$, has a finite sub-cover. A natural question is: How hard is it to compute such a finite sub-cover? We make this precise by analysing functionals that given $g:2^{\mathbb{N}}\rightarrow \mathbb{N}$, output $\langle f_0 , \dots, f_n\rangle $ in $2^{\mathbb{N}}$ such that the neighbourhoods defined from $\overline{f_i}g(f_i)$ for $i\leq n$ cover $2^{\mathbb{N}}$. The special and weak fan functionals are central objects in this study. (T.2) A basic property of $2^{\mathbb{N}}$ in Nonstandard Analysis is Abraham Robinson's nonstandard compactness, i.e. that every binary sequence is `infinitely close' to a standard binary sequence. We analyse the strength of this nonstandard compactness property in the spirit of Reverse Mathematics, which turns out to be intimately related to the computational properties of the special and weak fan functionals. We establish the connection between these new fan functionals on one hand, and arithmetical comprehension, Transfinite Recursion, and the Suslin functional on the other hand. We show that compactness (nonstandard or otherwise) readily brings us to the outer edges of Reverse Mathematics (namely $\Pi_2^1$-CA$_0$), and even into Schweber's higher-order framework (namely $\Sigma_{1}^{2}$-separation).