An ordinal analysis of stability

This paper is the first in a series of three which culminates in an ordinal analysis of ¹₂-comprehension. On the set-theoretic side ¹₂-comprehension corresponds to Kripke-Platek set theory, KP, plus ₁-separation. The strength of the latter theory is encapsulated in the fact that it proves the existence of ordinals such that, for all >, is -stable, i.e. L is a ₁-elementary substructure of L. The objective of this paper is to give an ordinal analysis of a scenario of not too complicated stability relations as experience has shown that the understanding of the ordinal analysis of ¹₂-comprehension is greatly facilitated by explicating certain simpler cases first.This paper introduces an ordinal representation system based on -indescribable cardinals which is then employed for determining an upper bound for the proof–theoretic strength of the theory KPi+ is +-stable, where KPi is KP augmented by the axiom saying that every set is contained in an admissible set.The results in this paper were obtained in 1995 when the author was a Heisenberg Fellow of the German Science Foundation, Deutsche Forschungsgemeinschaft.     

S-PLUS code for ordinal correspondence analysis

Summary  Correspondence analysis is a popular graphical tool used to analyse contingency tables. In the past, it has commonly been performed by applying a singular value decomposition to a transformation of the data in the contingency table. A recent advance in its theory is to perform a bivariate moment decomposition instead. This approach is especially useful for the detection of linear and non-linear associations between ordinal variables; a feature not readily available using singular value decomposition. This paper outlines S-PLUS code that will perform correspondence analysis using bivariate moment decomposition. It also includes a simple plotting function that will enable the graphical interpretation of the different levels of association.     

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     

An ordinal well-posedness property for Nash equilibria

The aim of this article is to give, for Nash equilibria, a well-posedness criterion in the form of an ordinal property. This property is important for games because it captures the case when players' decisions depend on preferences and not on a special choice of a utility function. The ordinal characteristics of this well-posedness criterion comes from considering value-bounded approximate equilibria.     

An ordinal sorting method for group decision-making

Several group decision-making methods were proposed with the aim to establish, from individual opinions, a collective one. However, the literature review of such methods show that, until now, few of them accept individual preferences expressed in partial pre-orders or, more generally, in preferences relational systems (p.r.s.). In addition, the majority of these methods produce a ranking on the alternative set, i.e. they concern the ranking decision-making problematic. In fact, the efforts provided to develop methods which treat, for example, the sorting problematic, remain insufficient. For these reasons, we propose in this paper an ordinal sorting method which determines, from individual p.r.s., at least one collective assignment which takes into account the relative importance of the members. If there is more than one collective assignment, an interactive procedure to reach a consensus assignment is proposed.     

Proof theory and ordinal analysis

In the first part we show why ordinals and ordinal notations are naturally connected with proof theoretical research. We introduce the program of ordinal analysis. The second part gives examples of applications of ordinal analysis.Dedicated to K. Schütte on the occasion of his 80th birthdayWork partly supported by a grant of the Volkswagenstiftung     

列联资料的有向聚类分析及其应用

本文针对单向有序列联资料 ,提出了有序因素的秩效应概念。在秩效应排序的基础上 ,构造了平均秩效应原则 ,并对因素各水平进行有向聚类分析。利用该方法对大学生隐性教育调查资料进行了剖析     

A statistical model for the analysis of ordinal level dependent variables

This paper develops a model, with assumptions similar to those of the linear model, for use when the observed dependent variable is ordinal. This model is an extension of the dichotomous probit model, and assumes that the ordinal nature of the observed dependent variable is due to methodological limitations in collecting the data, which force the researcher to lump together and identify various portions of an (otherwise) interval level variable. The model assumes a linear eflect of each independent variable as well as a series of break points between categories for the dependent variable. Maximum likelihood estimators are found for these parameters, along with their asymptotic sampling distributions, and an analogue of R ² (the coefficient of determination in regression analysis) is defined to measure goodness of fit. The use of the model is illustrated with an analysis of Congressional voting on the 1965 Medicare Bill.     

Classification trees for ordinal variables

We introduce new criteria to obtain classification trees for ordinal response variables. At this aim, Breiman et al. (Classification and regression trees. Wadsworth, Belmont, 1984), extended their twoing criterion to the ordinal case. Following CART procedure, we extend the well known Gini–Simpson criterion to the ordinal case. Referring to the exclusivity preference property (introduced by Taylor and Silverman in Stat Comput 3:147–161, 1993, for the nominal case), suitably modified for the ordinal case, a second criterion is introduced. The hereby proposed methods are compared with the ordered twoing criterion via simulations.     

An ordinal indexing on the space of strictly singular operators

Using the notion of S _ξ -strictly singular operators introduced by Androulakis, Dodos, Sirotkin and Troitsky, we define an ordinal index on the subspace of strictly singular operators between two separable Banach spaces. In our main result, we provide a sufficient condition implying that this index is bounded by ω ₁. In particular, we apply this result to study operators on totally incomparable spaces, hereditarily indecomposable spaces and spaces with few operators.     

An algorithm for ordinal sorting based on ELECTRE with categories defined by examples

This work proposes a Progressive Assisted Sorting Algorithm (PASA) based on a multicriteria evaluation ELECTRE-type method. The purpose of the PASA is to aid a decision maker to progressively sort a set of alternatives into a set of categories, which we considered are ordered (ordinal sorting), following a consistency principle. We consider the principle that if an alternative outranks (is as good as) a second one, then it must belong to the same category or to a better category. The set of alternatives already sorted by the decision maker will implicitly define the categories, and will constrain the range of categories where other alternatives may be sorted. We show how the same idea may be used in an aggregation/disaggregation approach, considering some parameters of ELECTRE are not fixed a priori, but are constrained only by the examples provided. In this context, we establish a “convex-shape property” stating that the range of possible categories for an alternative is always an interval of categories. A discussion contrasting this approach with ELECTRE TRI is included in the conclusions.     

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.     

Optimal bounds for ordinal comparison maps

In this note, we answer the following question: Given two recursively presented well orderingsR, S of subsets of the natural numbers, what is the complexity of an ordinal comparison mapκ takingR isomorphically onto an initial segment ofS (or vice versa)?     

A potential approach for ordinal games

We introduce the class of ordinal games with a potential, which are characterized by the absence of weak improvement cycles, the same condition used by Voorneveld and Norde (1997) for ordinal potential games.     

Adequateness and interpretability of objective functions in ordinal data analysis

Objective functions that are applied in ordinal data analysis must be adequate, i.e. carefully adapted to the structure of the observed data. In addition, any analysis of data that is based upon objective functions must lead to interpretable results. After a general characterization of adequate objective functions in ordinal data analysis, therefore, the particular problems of constructing adequate and interpretable dissimilarity coefficients and correlation coefficients in ordinal data analysis, stress measures (stress functions) in non-metric scaling and generalized stress measures or correlation coefficients in any theory of rank estimation will be discussed.