On Wainer's notation for a minimal subrecursive inaccessible ordinal

We show the following results on Wainer's notation for a minimal subrecursive inaccessible ordinal τ: First, we give a constructive proof of the collapsing theorem. Secondly, we prove that the slow-growing hierarchy and the fast-growing hierarchy up to τ have elementary properties on increase and domination, which completes Wainer's proof that τ is a minimal subrecursive inaccessible. Our results are obtained by showing a strong normalization theorem for the term structure of the notation. MSC: 03D20, 03F15.     

Aggregation on Finite Ordinal Scales by Scale Independent Functions

We define and investigate the scale independent aggregation functions that are meaningful to aggregate finite ordinal numerical scales. Here scale independence means that the functions always have discrete representatives when the ordinal scales are considered as totally ordered finite sets. We also show that those scale independent functions identify with the so-called order invariant functions, which have been described recently. In particular, this identification allows us to justify the continuity property for certain order invariant functions in a natural way. Mathematics Subject Classifications (2000) Primary: 91C05, 91E45; Secondary: 06A99, 39A12.Jean-Luc Marichal: Partially supported by a grant from the David M. Kennedy Center for International Studies, Brigham Young University.Radko Mesiar: Partially supported by grants VEGA 1/0273/03 and APVT-20-023402.     

From Fibring to Cryptofibring. A Solution to the Collapsing Problem

The semantic collapse problem is perhaps the main difficulty associated to the very powerful mechanism for combining logics known as fibring. In this paper we propose cryptofibred semantics as a generalization of fibred semantics, and show that it provides a solution to the collapsing problem. In particular, given that the collapsing problem is a special case of failure of conservativeness, we formulate and prove a sufficient condition for cryptofibring to yield a conservative extension of the logics being combined. For illustration, we revisit the example of combining intuitionistic and classical propositional logics. Mathematics Subject Classification (2000): 03B22 (03B35, 03G25, 03G30)     

Cut-Elimination Theorem for the Logic of Constant Domains

The logic CD is an intermediate logic (stronger than intuitionistic logic and weaker than classical logic) which exactly corresponds to the Kripke models with constant domains. It is known that the logic CD has a Gentzen-type formulation called LD (which is same as LK except that (→) and (?–) rules are replaced by the corresponding intuitionistic rules) and that the cut-elimination theorem does not hold for LD . In this paper we present a modification of LD and prove the cut-elimination theorem for it. Moreover we prove a “weak” version of cut-elimination theorem for LD , saying that all “cuts” except some special forms can be eliminated from a proof in LD . From these cut-elimination theorems we obtain some corollaries on syntactical properties of CD : fragments collapsing into intuitionistic logic. Harrop disjunction and existence properties, and a fact on the number of logical symbols in the axiom of CD . Mathematics Subject Classification : 03B55. 03F05.     

Dynamic ordinal analysis

 Dynamic ordinal analysis is ordinal analysis for weak arithmetics like fragments of bounded arithmetic. In this paper we will define dynamic ordinals – they will be sets of number theoretic functions measuring the amount of sΠ ^b ₁(X) order induction available in a theory. We will compare order induction to successor induction over weak theories. We will compute dynamic ordinals of the bounded arithmetic theories sΣ ^b _n (X)−L ^m IND for m=n and m=n+1, n≥0. Different dynamic ordinals lead to separation. In this way we will obtain several separation results between these relativized theories. We will generalize our results to further languages extending the language of bounded arithmetic. Received: 27 April 2001 / Published online: 19 December 2002 The results for sΣ ^b _n (X)−L ^m IND are part of the authors dissertation [3]; the results for sΣ ^b _m (X)−L ^m+1 IND base on results of ARAI [1]. Mathematics Subject Classification (2000): Primary 03F30; Secondary 03F05, 03F50 Key words or phrases: Dynamic ordinal – Bounded arithmetic – Proof-theoretic ordinal – Order induction – Semi-formal system – Cut-elimination     

Finding the optimal metric in classification problems with ordinal features

A method for finding the optimal distance function for the classification problem with two classes in which the objects are specified by vectors of their ordinal features is proposed. An optimal distance function is sought by the minimization of the weighted difference of the average intraclass and interclass distances. It is assumed that a specific distance function is given for each feature, which is defined on the Cartesian product of the set of integer numbers in the range from 0 to N − 1 and takes values from 0 to M. Distance functions satisfy modified metric properties. The number of admissible distance functions is calculated, which enables one to significantly reduce the complexity of the problem. To verify the appropriateness of metric optimization and to perform experiments, the nearest neighbor algorithm is used.     

A simplified functorial construction of the veblen hierarchy

We give a simple and elementary proof of the following result of Girard and Vauzeilles which is proved in [5]: “The binary Veblen function ψ: On × On — On is a dilator.” Our proof indicates the intimate connection between the traditional theory of ordinal notation systems and Girard's theory of denotation systems. MSC: 03F15.     

Systems of iterated projective ordinal notations and combinatorial statements about binary labeled trees

We introduce the appropriate iterated version of the system of ordinal notations from [G1] whose order type is the familiar Howard ordinal. As in [G1], our ordinal notations are partly inspired by the ideas from [P] where certain crucial properties of the traditional Munich' ordinal notations are isolated and used in the cut-elimination proofs. As compared to the corresponding impredicative Munich' ordinal notations (see e.g. [B1, B2, J, Sch1, Sch2, BSch]), our ordinal notations arearbitrary terms in the appropriate simple term algebra based on the notion of collapsing functions (which we would rather identify as projective functions). In Sect. 1 below we define the systems of ordinal notationsPRJ(), for any primitive recursive limit wellordering. In Sect. 2 we prove the crucial well-foundness property by using the appropriate well-quasi-ordering property of the corresponding binary labeled trees [G3]. In Sect. 3 we interprete inPRJ() the familiar Veblen-Bachmann hierarchy of ordinal functions, and in Sect. 4 we show that the corresponding Buchholz's system of ordinal notationsOT() is a proper subsystem ofPRJ(), although it has the same order type according to [G3] together with the interpretation from Sect. 2 in the terms of labeled trees. In Sect. 5 we use Friedman's approach in order to obtain an appropriate purely combinatorial statement which is not provable in the theory of iterated inductive definitions ID_< , for arbitrarily large limit ordinal. Formal theories, axioms, etc. used below are familiar in the proof theory of subsystems of analysis (see [BFPS, T, BSch]).     

Ordinal utility and economic price indices

Summary In economic price index theory, a reference level of utility is needed for measuring the change in the cost of living oetween a base period and a comparison period. A reference level function can be used to derive this reference utility level from the utilities attained at the base and at the comparison prices. Depending on the scale type of the underlying utility function, the reference level function has to satisfy certain invariance conditions. In this paper, these conditions are formulated as functional equations for interval scales and for ordinal utility scales. By solving these equations, we characterize the class of admissible reference level functions for the respective scale type.We thank J. Aczél and an anonymous referee for their comments on an earlier version of the paper.     

A Uniform Approach to Fundamental Sequences and Hierarchies

In this article we give a unifying approach to the theory of fundamental sequences and their related Hardy hierarchies of number-theoretic functions and we show the equivalence of the new approach with the classical one. Mathematics Subject Classification: 03D20, 03F15, 03E10.     

Non-circular,non-well-founded set universes

We show that there are universes of sets which contain descending ?-sequences of length α for every ordinal α, though they do not contain any ?-cycle. It is also shown that there is no set universe containing a descending ?-sequence of length On. MSC: 03E30; 03E65.     

A Note on Contact Shape Optimization with Semicoercive State Problems

This note deals with contact shape optimization for problems involving floating structures. The boundedness of solutions to state problems with respect to admissible domains, which is the basic step in the existence analysis, is a consequence of Korn's inequality in coercive cases. In semicoercive cases (meaning that floating bodies are admitted), the Korn inequality cannot be directly applied and one has to proceed in another way: to use a decomposition of kinematically admissible functions and a Korn type inequality on appropriate subspaces. In addition, one has to show that the constant appearing in this inequality is independent with respect to a family of admissible domains.     

Concordant outranking with multiple criteria of ordinal significance

In this paper we address the problem of aggregating outranking statements from multiple preference criteria of ordinal significance. The concept of ordinal concordance of a global outranking situation is defined and an operational test for its presence is developed. Finally, we propose a new kind of robustness analysis for global outranking statements integrating classical dominance, ordinal and classical majority concordance in a same ordinal valued logical framework.Received: March 2004, Revised: October 2004, MSC classification: 90B50, 06A06, 03C80     

On the existence and uniqueness of pairwise stable networks

In this paper we show how externalities between links affect the existence and uniqueness of pairwise stable (PS) networks. For this we introduce the properties ordinal convexity (concavity) and ordinal strategic complements (substitutes) of utility functions on networks. It is shown that there exists at least one PS network if the profile of utility functions is ordinal convex and satisfies the ordinal strategic complements property. On the other hand, ordinal concavity and ordinal strategic substitutes are sufficient for some uniqueness properties of PS networks. Additionally, we elaborate on the relation of the link externality properties to definitions in the literature.     

On Robinsonian dissimilarities, the consecutive ones property and latent variable models

A dissimilarity measure on a set of objects is Robinsonian if its matrix can be symmetrically permuted so that its elements do not decrease when moving away from the main diagonal along any row or column. The Robinson property of a dissimilarity reflects an order of the objects. If a dissimilarity is not observed directly, it must be obtained from the data. Given that an ordinal structure is assumed to underlie the data, the dissimilarity function of choice may or may not recover the order correctly. For four dissimilarity measures for binary data it is investigated what ordinal data structure of 0s and 1s is correctly recovered. We derive sufficient conditions for the dissimilarity functions to be Robinsonian. The sufficient conditions differ with the dissimilarity measures. The paper concludes with some limitations of the study.     

Delays, Recurrence and Ordinals

We apply set-theoretical ideas to an iteration problem of dynamicalsystems. Among other results, we prove that these iterationsnever stabilise later than the first uncountable ordinal; forevery countable ordinal we give examples in Baire space andin Cantor space of an iteration that stabilises exactly at thatordinal; we give an example of an iteration with recursive datawhich stabilises exactly at the first non-recursive ordinal;and we find new examples of complete analytic sets simply definablefrom concepts of recurrence. 2000 Mathematics Subject Classification:primary 03E15, 37B20, 54H05; secondary 37B10, 37E15.     

Reflection of Long Game Formulas

We study game formulas the truth of which is determined by a semantical game of uncountable length. The main theme is the study of principles stating reflection of these formulas in various admissible sets. This investigation leads to two weak forms of strict-II¹₁ reflection (or ∑₁-compactness). We show that admissible sets such as H(ω₂) and L_ω2 which fail to have strict-II¹₁ reflection, may or may not, depending on set-theoretic hypotheses satisfy one or both of these weaker forms. Mathematics Subject Classification : 03C70, 03C75.     

Post’s Problem for ordinal register machines: An explicit approach

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.