Search

We show that arithmetical transfinite recursion is equivalent to a suitable formalization of the following: For every ordinal $\alpha$ there exists an ordinal $\beta$ such that $1+\beta\cdot(\beta+\alpha)$ (ordinal arithmetic) admits an almost order preserving collapse into $\beta$. Arithmetical comprehension is equivalent to a statement of the same form, with $\beta\cdot\alpha$ at the place of $\beta\cdot(\beta+\alpha)$. We will also characterize the principles that any set is contained in a countable coded $\omega$-model of arithmetical transfinite recursion resp. arithmetical comprehension., Comment: This is the accepted version of a paper published in The Journal of Symbolic Logic

We present three ordinal notation systems representing ordinals below $\varepsilon_0$ in type theory, using recent type-theoretical innovations such as mutual inductive-inductive definitions and higher inductive types. We show how ordinal arithmetic can be developed for these systems, and how they admit a transfinite induction principle. We prove that all three notation systems are equivalent, so that we can transport results between them using the univalence principle. All our constructions have been implemented in cubical Agda., 14 pages, to appear at CPP 2020

We display the entire structure ${\cal R}_2$ coding $\Sigma_1$- and $\Sigma_2$-elementarity on the ordinals. This will enable the analysis of pure $\Sigma_3$-elementary substructures., Comment: Extensive rewrite of the previous version of the paper according to reviewers' recommendations. The paper was corrected, improved, and extended considerably to become readable as stand-alone text. Numerous instructive examples were added. The introduction was extended and a figure added. The preprint is in final form and the corresponding article in press

We study influence of ordinal transformations on results of queries in rank-aware databases which derive their operations with ranked relations from totally ordered structures of scores with infima acting as aggregation functions. We introduce notions of ordinal containment and equivalence of ranked relations and prove that infima-based algebraic operations with ranked relations are invariant to ordinal transformations: Queries applied to original and transformed data yield results which are equivalent in terms of the order given by scores, meaning that top-k results of queries remain the same. We show this important property is preserved in alternative query systems based of relational calculi developed in context of G\"odel logic. We comment on relationship to monotone query evaluation and show that the results can be attained in alternative rank-aware approaches.

How do we compare the complexities of various classes of structures? The Turing ordinal of a class of structures, introduced by Jockusch and Soare, is defined in terms of the number of jumps required for coding to be possible. The back-and-forth ordinal, introduced by Montalban, is defined in terms of Σ α -types. The back-and-forth ordinal is (roughly) bounded by the Turing ordinal. In this paper, we show that, if we do not restrict the allowable classes, the reverse inequality need not hold. Indeed, for any computable ordinals α ≤ β we present a class of structures with back-and-forth ordinal α and Turing ordinal β . We also present an example of a class of structures with back-and-forth ordinal 1 but no Turing ordinal.

Each hereditarily finite set is associated with a unique extensional acyclic digraph. Three parameters, indicating the size or richness of a set, are associated with its digraph: the cardinality of the set, and the numbers of nodes and of edges in the digraph. We study the effects on these parameters of the operations of the ordinal arithmetic of sets.

Pohlers's ordinal analysis in his monograph [12] contains some flaws and thereby ends up with incorrect proof-theoretic ordinals of several systems. The present paper determines their correct proof-theoretic ordinals and also supplements [12] with the ordinal analysis of some other relevant impredicative systems.

The ordinal sum of triangular norms on the unit interval has been proposed to construct new triangular norms. However, considering general bounded lattices, the ordinal sum of triangular norms and conorms may not generate triangular norms and conorms. In this paper, we study and propose some new construction methods yielding triangular norms and conorms on general bounded lattices. Moreover, we generalize these construction methods by induction to a ordinal sum construction for triangular norms and conorms, applicable on any bounded lattice. And some illustrative examples are added for clarity.

In this contribution new ways of constructing of ordinal sum of fuzzy implications are proposed. These methods are based on a construction of ordinal sums of overlap functions. Moreover, preservation of some properties of these ordinal sums of fuzzy implications are examined. Among others neutrality property, identity property, and ordering property are considered.

The structure ${\cal C}_2:=(1^\infty,\le,\le_1,\le_2)$, introduced and first analyzed in Carlson and Wilken 2012 (APAL), is shown to be elementary recursive. Here, $1^\infty$ denotes the proof-theoretic ordinal of the fragment $\Pi^1_1$-$\mathrm{CA}_0$ of second order number theory, or equivalently the set theory $\mathrm{KPl}_0$, which axiomatizes limits of models of Kripke-Platek set theory with infinity. The partial orderings $\le_1$ and $\le_2$ denote the relations of $\Sigma_1$- and $\Sigma_2$-elementary substructure, respectively. In a subsequent article we will show that the structure ${\cal C}_2$ comprises the core of the structure ${\cal R}_2$ of pure elementary patterns of resemblance of order $2$. In Carlson and Wilken 2012 (APAL) the stage has been set by showing that the least ordinal containing a cover of each pure pattern of order $2$ is $1^\infty$. However, it is not obvious from Carlson and Wilken 2012 (APAL) that ${\cal C}_2$ is an elementary recursive structure. This is shown here through a considerable disentanglement in the description of connectivity components of $\le_1$ and $\le_2$. The key to and starting point of our analysis is the apparatus of ordinal arithmetic developed in Wilken 2007 (APAL) and in Section 5 of Carlson and Wilken 2012 (JSL), which was enhanced in Carlson and Wilken 2012 (APAL) specifically for the analysis of ${\cal C}_2$.

Elementary patterns of resemblance notate ordinals up to the ordinal of $${\Pi^1_1 - CA_0}$$ ? 1 1 - C A 0 . We provide ordinal multiplication and exponentiation algorithms using these notations.

We describe the countable ordinals in terms of iterations of Mostowski collapsings. This gives a proof-theoretic bound on definable countable ordinals in Zermelo-Fraenkel set theory ZF.

It was recently proved that each subspace of an ordinal space is also orderable. The present note aims to give a simple proof of this fact., peer-reviewed

The paper relativizes the method of ordinal analysis developed for Kripke-Platek set theory to theories which have the power set axiom. We show that it is possible to use this technique to extract information about Power Kripke-Platek set theory, KP (P). As an application it is shown that whenever KP (P) + AC proves a Π statement then it holds true in the segment V of the von Neumann hierarchy, where τ stands for the Bachmann-Howard ordinal.

We provide mutual elementary recursive order isomorphisms between classical ordinal notations, based on Skolem hulling, and notations from pure elementary patterns of resemblance of order $2$, showing that the latter characterize the proof-theoretic ordinal of the fragment $\Pi^1_1$-$\mathrm{CA}_0$ of second order number theory, or equivalently the set theory $\mathrm{KPl}_0$. As a corollary, we prove that Carlson's result on the well-quasi orderedness of respecting forests of order $2$ implies transfinite induction up to the ordinal of $\mathrm{KPl}_0$. We expect that our approach will facilitate analysis of more powerful systems of patterns., Comment: corrected Theorem 4.2 with according changes in section 3 (mainly Definition 3.3), results unchanged. The manuscript was edited, aligned with reference [14] (moving former Lemma 3.5 there), and argumentation was revised, with minor corrections in (the proof of) Theorem 4.2; results unchanged. Updated revised preprint; to appear in the APAL (2017)

A behavioural pseudometric is often defined as the least fixed point of a monotone function F on a complete lattice of 1-bounded pseudometrics. According to Tarski@?s fixed point theorem, this least fixed point can be obtained by (possibly transfinite) iteration of F, starting from the least element @? of the lattice. The smallest ordinal @a such that F^@a(@?)=F^@a^+^1(@?) is known as the closure ordinal of F. We prove that if F is also continuous with respect to the sup-norm, then its closure ordinal is @w. We also show that our result gives rise to simpler and modular proofs that the closure ordinal is @w.

One of the most important operators in soft computing are the triangular norms (t-norms), as well as the combination among them. The ordinal sum of triangular norms on [0, 1] has been used to construct other triangular norms. However, on a bounded lattice, an ordinal sum of t-norms may not be a t-norm. Several necessary and sufficient conditions are presented in this paper for ensuring whether an ordinal sum on a bounded lattice of arbitrary t-norms is, in fact, a t-norm. Moreover, we show that a large set of ordinal sums verify these conditions. Hence, they are very interesting in order to verify whether an ordinal sum on a bounded lattice is a t-norm for a particular family of t-norms.

It is known that an ordinal is the order type of the lexicographic ordering of a regular language if and only if it is less than ωω. We design a polynomial time algorithm that constructs, for each well-ordered regular language L with respect to the lexicographic ordering, given by a deterministic finite automaton, the Cantor Normal Form of its order type. It follows that there is a polynomial time algorithm to decide whether two deterministic finite automata accepting well-ordered regular languages accept isomorphic languages. We also give estimates on the state complexity of the smallest "ordinal automaton" representing an ordinal less than ωω, together with an algorithm that translates each such ordinal to an automaton.

We prove that the ordinal sum of n-copulas is always an n-copula and show that every copula may be represented as an ordinal sum, once the set of its idempotents is known. In particular, it will be shown that every copula can be expressed as the ordinal sum of copulas having only trivial idempotents. As a by-product, we also characterize all associative copulas whose n-ary forms are n-copulas for all n.

We provide a positive solution for Post’s Problem for ordinal register machines, and also prove that these machines and ordinal Turing machines compute precisely the same partial functions on ordinals. To do so, we construct ordinal register machine programs which compute the necessary functions. In addition, we show that any set of ordinals solving Post’s Problem must be unbounded in the writable ordinals.

The technique of using infinitary rules in an ordinal analysis has been one of the most productive developments in ordinal analysis. Unfortunately, one of the most advanced variants, the Buchholz Ωμ rule, does not apply to systems much stronger than Π11-comprehension. In this paper, we propose a new extension of the Ω rule using game-theoretic quantifiers. We apply this to a system of inductive definitions with at least the strength of a recursively inaccessible ordinal.

Exploiting the fact that Π 1 0 -definable non-monotone inductive definitions have the same closure ordinal as arbitrary arithmetically definable monotone inductive definitions, we show that the proof theoretic ordinal of an axiomatization ( Π 1 0 - FXP ) 0 of Π 1 0 -definable non-monotone inductive definitions coincides with the proof theoretic ordinal of the theory ID 1 of arithmetically definable monotone inductive definitions.

In Simmons (Arch Math Logic 43:65–83, 2004), I described a method of producing ordinal notations ‘from below’ (for countable ordinals up to the Howard ordinal) and compared that method with the current popular ‘from above’ method which uses a collapsing function from uncountable ordinals. This ‘from below’ method employs a slight generalization of the normal function—the fruitful functions—and what seems to be a new class of functions—the helpful functions—which exist at all levels of the function space hierarchy over ordinals. Unfortunately, I was rather sparing in my description of these classes of functions. In this paper I am much more generous. I describe the properties of the helpful functions on all finite levels and, in the final section, indicate how they can be used to simplify the generation of ordinal notations. The main aim of this paper is to fill in the details missing from [7]. The secondary aim is to indicate what can be done with helpful functions. Fuller details of this development will appear elsewhere.

We generalize ordinary register machines on natural numbers to machines whose registers contain arbitrary ordinals. Ordinal register machines are able to compute a recursive bounded truth predicate on the ordinals. The class of sets of ordinals which can be read off the truth predicate satisfies a natural theory SO. SO is the theory of the sets of ordinals in a model of the Zermelo-Fraenkel axioms ZFC. This allows the following characterization of computable sets: a set of ordinals is ordinal register computable if and only if it is an element of Godel’s constructible universe L.

We consider belief revision involving conditional statements where the antecedent is almost certainly false. In order to represent such statements, we use Ordinal Conditional Functions that may take infinite values. In this manner, we are able to capture the intuition that the antecedent can not be verified by a finite number of observations. We define belief revision in this context through basic ordinal arithmetic, and we propose an approach to conditional revision in which only the right hypothetical levels are revised by conditional information. We compare our approach to existing work on conditional revision and belief improvement.

The concept of weighted ordinal arithmetic means and other related weighted ordinal means is studied. Based on the relevant results on the scale [0,1], new types of weighted ordinal means are proposed. In some cases these ordinal means coincide with those proposed by Godo and Torra, but not in the case when ordinal means introduced by them are not idempotent. Based on divisible ordinal t-conorms and modifying the approach of Godo and Torra, we show how the previously introduced weighted ordinal means can be obtained without exploiting the formal similarity of the structure of continuous t-conorms on [0,1] and divisible ordinal t-conorms.

In [2] T. J. Carlson introduces an approach to ordinal notation systems which is based on the notion of Σ1-elementary substructure. We gave a detailed ordinal arithmetical analysis (see [7]) of the ordinal structure based on Σ1-elementarily as defined in [2]. This involved the development of an appropriate ordinal arithmetic that is based on a system of classical ordinal notations derived from Skolem hull operators, see [6]. In the present paper we establish an effective order isomorphism between the classical and the new system of ordinal notations using the results from [6] and [7]. Moreover, on the basis of a concept of relativization we develop mutual (relatively) elementary recursive assignments which are uniform with respect to the underlying relativization.

The exact correspondence between ordinal notations derived from Skolem hull operators, which are classical in ordinal analysis, and descriptions of ordinals in terms of Σ 1 -elementarity, an approach developed by T.J. Carlson, is analyzed in full detail. The ordinal arithmetical tools needed for this purpose were developed in [G. Wilken, Ordinal arithmetic based on Skolem hulling, Annals of Pure and Applied Logic 145 (2) (2007) 130–161]. We show that the least ordinal κ such that κ 1 ∞ (as defined in [T.J. Carlson, Elementary patterns of resemblance, Annals of Pure and Applied Logic 108 (2001) 19–77] and described below) is the proof theoretic ordinal of the set-theoretic system KP l 0 , confirming a claim of Carlson. Moreover, we characterize the class of all ordinals κ such that κ 1 ∞ and provide an ordinal arithmetical analysis of Carlson’s entire structure R 1 in the style of [T.J. Carlson, Ordinal arithmetic and Σ 1 -elementarity, Archive for Mathematical Logic 38 (1999) 449–460].

The notions of finite and infinite second-order characterizability of cardinal and ordinal numbers are developed. Several known results for the case of finite characterizability are extended to infinite characterizability, and investigations of the second-order theory of ordinals lead to some observations about the Fraenkel-Carnap question for well-orders and about the relationship between ordinal characterizability and ordinal arithmetic. The broader significance of cardinal characterizability and the relationships between different notions of characterizability are also discussed.

The Bachmann-Howard structure, that is the segment of ordinal numbers below the proof theoretic ordinal of Kripke-Platek set theory with infinity, is fully characterized in terms of CARLSON’s approach to ordinal notation systems based on the notion of Σ1-elementarity.

Ordinal sums have been introduced in many different contexts, e.g., for posets, semigroups, t-norms, copulas, aggregation operators, or quite recently for hoops. In this contribution, we focus on ordinal sums of t-norms acting on some bounded lattice which is not necessarily a chain or an ordinal sum of posets. Necessary and sufficient conditions are provided for an ordinal sum operation yielding again a t-norm on some bounded lattice whereas the operation is determined by an arbitrary selection of subintervals as carriers for arbitrary summand t-norms. By such also the structure of the underlying bounded lattice is investigated. Further, it is shown that up to trivial cases there are no ordinal sum t-norms on product lattices in general.

It is shown that, according to NF, many of the assertions of ordinal arithmetic involving the T-function which is peculiar to NF turn out to be equivalent to the truth-in-certain-permutation-models of assertions which have perfectly sensible ZF-style meanings, such as: the existence of wellfounded sets of great size or rank, or the nonexistence of small counterexamples to the wellfoundedness of ∈. Everything here holds also for NFU if the permutations are taken to fix all urelemente.

How do ordinals measure the strength and computational power of formal theories? This paper is concerned with the connection between ordinal representation systems and theories established in ordinal analyses. It focusses on results which explain the nature of this connection in terms of semantical and computational notions from model theory, set theory, and generalized recursion theory.

This paper is intended to give for a general mathematical audience (including non-logicians) a survey of intriguing connections between analytic combinatorics and logic. We define the ordinals below e 0 in non-logical terms and we survey a selection of recent results about the analytic combinatorics of these ordinals. Using a versatile and flexible (logarithmic) compression technique we give applications to phase transitions for independence results, Hilbert’s basis theorem, local number theory, Ramsey theory, Hydra games, and Goodstein sequences. We discuss briefly universality and renormalization issues in this context. Finally, we indicate how regularity properties of ordinal count functions can be used to prove logical limit laws.

Termination proofs are of critical importance for establishing the correct behavior of both transformational and reactive computing systems. A general setting for establishing termination proofs involves the use of the ordinal numbers, an extension of the natural numbers into the transfinite that were introduced by Cantor in the nineteenth century and are at the core of modern set theory. We present the first comprehensive treatment of ordinal arithmetic on compact ordinal notations and give efficient algorithms for various operations, including addition, subtraction, multiplication, and exponentiation. Using the ACL2 theorem proving system, we implemented our ordinal arithmetic algorithms, mechanically verified their correctness, and developed a library of theorems that can be used to significantly automate reasoning involving the ordinals. To enable users of the ACL2 system to fully utilize our work required that we modify ACL2, e.g., we replaced the underlying representation of the ordinals and added a large library of definitions and theorems. Our modifications are available starting with ACL2 version 2.8.

This paper deals with a proof theory for a theory T N of \(\Pi _{N}\)-reflecting ordinals using a system \(\mathit{Od}(\Pi _{N})\) of ordinal diagrams. This is a sequel to the previous one (Arai, Ann Pure Appl Log 129:39–92, 2004) in which a theory for \(\Pi _{3}\)-reflecting ordinals is analysed proof-theoretically.