In this paper, we develop primitive recursive analogues of regular cardinals by using ordinal representation systems for KPi and KPM. We also define primitive recursive analogues of inaccessible and hyperinaccessible cardinals. Moreover, we characterize the primitive recursive analogue of the least (uncountable) regular cardinal.

§1. Introduction. The purpose of this paper is, in general, to report the state of the art of ordinal analysis and, in particular, the recent success in obtaining an ordinal analysis for the system of-analysis, which is the subsystem of formal second order arithmetic, Z2, with comprehension confined to-formulae. The same techniques can be used to provide ordinal analyses for theories that are reducible to iterated-comprehension, e.g.,-comprehension. The details will be laid out in [28].Ordinal-theoretic proof (...) theory came into existence in 1936, springing forth from Gentzen's head in the course of his consistency proof of arithmetic. Gentzen fostered hopes that with sufficiently large constructive ordinals one could establish the consistency of analysis, i.e., Z2. Considerable progress has been made in proof theory since Gentzen's tragic death on August 4th, 1945, but an ordinal analysis of Z2is still something to be sought. However, for reasons that cannot be explained here,-comprehension appears to be the main stumbling block on the road to understanding full comprehension, giving hope for an ordinal analysis of Z2in the foreseeable future.Roughly speaking,ordinally informativeproof theory attaches ordinals in a recursive representation system to proofs in a given formal system; transformations on proofs to certain canonical forms are then partially mirrored by operations on the associated ordinals. Among other things, ordinal analysis of a formal system serves to characterize its provably recursive ordinals, functions and functionals and can yield both conservation and combinatorial independence results. (shrink)

§1. Introduction. The purpose of this paper is, in general, to report the state of the art of ordinal analysis and, in particular, the recent success in obtaining an ordinal analysis for the system of -analysis, which is the subsystem of formal second order arithmetic, Z2, with comprehension confined to -formulae. The same techniques can be used to provide ordinal analyses for theories that are reducible to iterated -comprehension, e.g., -comprehension. The details will be laid out (...) in [28].Ordinal-theoretic proof theory came into existence in 1936, springing forth from Gentzen's head in the course of his consistency proof of arithmetic. Gentzen fostered hopes that with sufficiently large constructive ordinals one could establish the consistency of analysis, i.e., Z2. Considerable progress has been made in proof theory since Gentzen's tragic death on August 4th, 1945, but an ordinal analysis of Z2 is still something to be sought. However, for reasons that cannot be explained here, -comprehension appears to be the main stumbling block on the road to understanding full comprehension, giving hope for an ordinal analysis of Z2 in the foreseeable future.Roughly speaking, ordinally informative proof theory attaches ordinals in a recursive representation system to proofs in a given formal system; transformations on proofs to certain canonical forms are then partially mirrored by operations on the associated ordinals. Among other things, ordinal analysis of a formal system serves to characterize its provably recursive ordinals, functions and functionals and can yield both conservation and combinatorial independence results. (shrink)

Abstract.This paper is the first in a series of three which culminates in an ordinal analysis of Π12-comprehension. On the set-theoretic side Π12-comprehension corresponds to Kripke-Platek set theory, KP, plus Σ1-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 Σ1-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 Π12-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. (shrink)

§1. Introduction. The purpose of this paper is, in general, to report the state of the art of ordinal analysis and, in particular, the recent success in obtaining an ordinal analysis for the system of-analysis, which is the subsystem of formal second order arithmetic, Z2, with comprehension confined to-formulae. The same techniques can be used to provide ordinal analyses for theories that are reducible to iterated-comprehension, e.g.,-comprehension. The details will be laid out in [28].Ordinal-theoretic proof (...) theory came into existence in 1936, springing forth from Gentzen's head in the course of his consistency proof of arithmetic. Gentzen fostered hopes that with sufficiently large constructive ordinals one could establish the consistency of analysis, i.e., Z2. Considerable progress has been made in proof theory since Gentzen's tragic death on August 4th, 1945, but an ordinal analysis of Z2is still something to be sought. However, for reasons that cannot be explained here,-comprehension appears to be the main stumbling block on the road to understanding full comprehension, giving hope for an ordinal analysis of Z2in the foreseeable future.Roughly speaking,ordinally informativeproof theory attaches ordinals in a recursive representation system to proofs in a given formal system; transformations on proofs to certain canonical forms are then partially mirrored by operations on the associated ordinals. Among other things, ordinal analysis of a formal system serves to characterize its provably recursive ordinals, functions and functionals and can yield both conservation and combinatorial independence results. (shrink)

§1. Introduction. The purpose of this paper is, in general, to report the state of the art of ordinal analysis and, in particular, the recent success in obtaining an ordinal analysis for the system of-analysis, which is the subsystem of formal second order arithmetic, Z2, with comprehension confined to-formulae. The same techniques can be used to provide ordinal analyses for theories that are reducible to iterated-comprehension, e.g.,-comprehension. The details will be laid out in [28].Ordinal-theoretic proof (...) theory came into existence in 1936, springing forth from Gentzen's head in the course of his consistency proof of arithmetic. Gentzen fostered hopes that with sufficiently large constructive ordinals one could establish the consistency of analysis, i.e., Z2. Considerable progress has been made in proof theory since Gentzen's tragic death on August 4th, 1945, but an ordinal analysis of Z2is still something to be sought. However, for reasons that cannot be explained here,-comprehension appears to be the main stumbling block on the road to understanding full comprehension, giving hope for an ordinal analysis of Z2in the foreseeable future.Roughly speaking,ordinally informativeproof theory attaches ordinals in a recursive representation system to proofs in a given formal system; transformations on proofs to certain canonical forms are then partially mirrored by operations on the associated ordinals. Among other things, ordinal analysis of a formal system serves to characterize its provably recursive ordinals, functions and functionals and can yield both conservation and combinatorial independence results. (shrink)

In ordinal analysis of impredicative theories so-called collapsing functions are of central importance. Unfortunately, the definition procedure of these functions makes essential use of uncountable cardinals whereas the notation system that they call into being corresponds to a recursive ordinal. It has long been claimed that, instead, one should manage to develop such functions directly on the basis of admissible ordinals. This paper is meant to show how this can be done. Interpreting the collapsing functions as operating (...) directly on admissible sets also renders a new and perspicuous approach to well-ordering proofs possible. MSC: 03F15, 03F35. (shrink)

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.

In this paper we provide a formal analysis of the idea of normative co-ordination. We argue that this idea is based on the assumption that agents can achieve flexible co-ordination by conferring normative positions to other agents. These positions include duties, permissions, and powers. In particular, we explain the idea of declarative power, which consists in the capacity of the power-holder of creating normative positions, involving other agents, simply by proclaiming such positions. In addition, we account also for the concepts (...) of representation, namely the representatives capacity of acting in the name of his principal, and of mandate, which is the mandatees duty to act as the mandator has requested. Finally, we show how the framework can be applied to represent the contract-net protocol. Some brief remarks on future research and applications conclude this contribution. (shrink)

In this paper, representational structures of arithmetical thinking, encoded in human minds, are described. On the basis of empirical research, it is possible to distinguish four types of mental number lines: the shortest mental number line, summation mental number lines, point-place mental number lines and mental lines of exact numbers. These structures may be treated as generative mechanisms of forming arithmetical representations underlying our numerical acts of reference towards cardinalities, ordinals and magnitudes. In the paper, the theoretical framework for a (...) formal model of mental arithmetical representations is constructed. Many competitive conceptions of the mental system responsible for our arithmetical thinking may be unified within the presented framework. The paradigm underlying our research may be interpreted philosophically as a neo-Kantian approach to modeling the mind’s representational structures. (shrink)

The generality of a derivation is an equivalence relation on the set of occurrences of variables in its premises and conclusion such that two occurrences of the same variable are in this relation if and only if they must remain occurrences of the same variable in every generalization of the derivation. The variables in question are propositional or of another type. A generalization of the derivation consists in diversifying variables without changing the rules of inference. This paper examines in the (...) setting of categorial proof theory the conjecture that two derivations with the same premises and conclusions stand for the same proof if and only if they have the same generality. For that purpose generality is defined within a category whose arrows are equivalence relations on finite ordinals, where composition is rather complicated. Several examples are given of deductive systems of derivations covering fragments of logic, with the associated map into the category of equivalence relations of generality. This category is isomorphically represented in the category whose arrows are binary relations between finite ordinals, where composition is the usual simple composition of relations. This representation is related to a classical representation result of Richard Brauer. (shrink)

The generality of a derivation is an equivalence relation on the set of occurrences of variables in its premises and conclusion such that two occurrences of the same variable are in this relation if and only if they must remain occurrences of the same variable in every generalization of the derivation. The variables in question are propositional or of another type. A generalization of the derivation consists in diversifying variables without changing the rules of inference.This paper examines in the setting (...) of categorial proof theory the conjecture that two derivations with the same premises and conclusions stand for the same proof if and only if they have the same generality. For that purpose generality is defined within a category whose arrows are equivalence relations on finite ordinals, where composition is rather complicated. Several examples are given of deductive systems of derivations covering fragments of logic, with the associated map into the category of equivalence relations of generality.This category is isomorphically represented in the category whose arrows are binary relations between finite ordinals, where composition is the usual simple composition of relations. This representation is related to a classical representation result of Richard Brauer. (shrink)

In this article we investigate whether the following conjecture is true or not: does the addition-free theta functions form a canonical notation system for the linear versions of Friedman’s well-partial-orders with the so-called gap-condition over a finite set of n labels. Rather surprisingly, we can show this is the case for two labels, but not for more than two labels. To this end, we determine the order type of the notation systems for addition-free theta functions in terms of ordinals (...) less than ε0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varepsilon _0$$\end{document}. We further show that the maximal order type of the Friedman ordering can be obtained by a certain ordinal notation system which is based on specific binary theta functions. (shrink)

The concept of representation has been a key element in the scientific study of mental processes, ever since such studies commenced. However, usage of the term has been all but too liberal—if one were to adhere to common use it remains unclear if there are examples of physical systems which cannot be construed in terms of representation. The problem is considered afresh, taking as the starting point the notion of activity spaces—spaces of spatiotemporal events produced by dynamical systems. (...) It is argued that representation can be analyzed in terms of the geometrical and topological properties of such spaces. Several attributes and processes associated with conceptual domains, such as logical structure, generalization and learning are considered, and given analogues in structural facets of activity spaces, as are misrepresentation and states of arousal. Based on this analysis, representational systems are defined, as is a key concept associated with such systems, the notion of representational capacity. According to the proposed theory, rather than being an all or none phenomenon, representation is in fact a matter of degree—that is can be associated with measurable quantities, as is behooving of a putative naturalistic construct. (shrink)

The introduction of connectionist or parallel distributed processing (PDP) systems to model cognitive functions has raised the question of the possible relations between these models and traditional information processing models which employ rules to manipulate representations. After presenting a brief account of PDP models and two ways in which they are commonly interpreted by those seeking to use them to explain cognitive functions, I present two ways one might relate these models to traditional information processing models and so not totally (...) repudiate the tradition of modelling cognition through systems of rules and representations. The proposal that seems most promising is that PDP-type structures might provide the underlying framework in which a rule and representation model might be implemented. To show how one might pursue such a strategy, I discuss recent research by Barsalou on the instability of concepts and show how that might be accounted for in a system whose microstructure had a PDP architecture. I also outline how adopting a multi-leveled view of the mind, where on one level the mind employed a PDP-type system and at another level constituted a rule processing system, would allow researchers to relocate some problems which seemed difficult to explain at one level, such as the capacity for concept learning, to another level where it could be handled in a straightforward manner. (shrink)

In this paper, we give an axiomatization of the ordinal number system, in the style of Dedekind’s axiomatization of the natural number system. The latter is based on a structure $(N,0,s)$ consisting of a set N, a distinguished element $0\in N$ and a function $s\colon N\to N$. The structure in our axiomatization is a triple $(O,L,s)$, where O is a class, L is a class function defined on all s-closed ‘subsets’ of O, and s is a class (...) function $s\colon O\to O$. In fact, we develop the theory relative to a Grothendieck-style universe (minus the power set axiom), as a way of bringing the natural and the ordinal cases under one framework. We also establish a universal property for the ordinal number system, analogous to the well-known universal property for the natural number system. (shrink)

While it is known that intuitionistic ZF set theory formulated with Replacement, IZFR, does not prove Collection, it is a longstanding open problem whether IZFR and intuitionistic set theory ZF formulated with Collection, IZF, have the same proof-theoretic strength. It has been conjectured that IZF proves the consistency of IZFR. This paper addresses similar questions but in respect of constructive Zermelo–Fraenkel set theory, CZF. It is shown that in the latter context the proof-theoretic strength of Replacement is the same as (...) that of Strong Collection and also that the functional version of the Regular Extension Axiom is as strong as its relational version.Moreover, it is proved that, contrary to IZF, the strength of CZF increases if one adds an axiom asserting that the trichotomous ordinals form a set.Unlike IZF, constructive Zermelo–Fraenkel set theory is amenable to ordinal analysis and the proofs in this paper make pivotal use thereof in the guise of well-ordering proofs for ordinal representation systems. (shrink)

We consider five ordinal notation systems of ε0 which are all well-known and of interest in proof-theoretic analysis of Peano arithmetic: Cantor’s system, systems based on binary trees and on countable tree-ordinals, and the systems due to Schütte and Simpson, and to Beklemishev. The main point of this paper is to demonstrate that the systems except the system based on binary trees are equivalent as structured systems, in spite of the fact that they have their origins in (...) different views and trials in proof theory. This is true while Weiermann’s results based on Friedman-style miniaturization indicate that the system based on binary trees is of different character than the others. (shrink)

In this paper, it will be argued that each time a procedure in a representational system is functioning adequately and automatically, the child steps up to a metaprocedural level and considers the procedure as a unit in its own right. Data will be drawn from microdevelopment in children's creation of external memory devices (i.e., changes in representation of a spatial task during a one hour's session) as well as from macrodevelopment in language acquisition (i.e., changes occurring over age (...) in a study of nominal determiners, pronouns and gender markers). These two aspects of development of representational systems are examined with respect to the spontaneous passage from concrete reference to abstract systems, from idiosyncratic to conventional notations, from redundant to economic marking, from unifunctional to plurifunctional meaningful units. These micro‐ and manodevelopmental changes take place in a spontaneous fashion despite the fact that the child's earlier system is adequate for successfully conveying the information required. A discussion will be made of the way in which children tend to indicate externally, by unifunctional markers, information which was implicit in their earlier use of an adult‐like system. They appear to be striving for the delicate balance between encoding and decoding efforts, ultimately leading to a felicitous representational system. Metaprocedural behavior is hypothesized to act as a control mechanism in the striving for this delicate balance of information content and information processing effort. It also appears to act as a control mechanism for the interprocedural organizotion of what was previously a plethora of juxtaposed, unconnected procedures yielding superficially analogous behavior. The stepping‐up to a metaprocedural level seems to occur each time the child has a handle on his currently functioning, goal‐oriented system. This enables the child to treat the system, or procedures which are part thereof, as units functioning in their own right. Thus there appears to be a deep‐rooted psychological tendency for a representational tool which functions well procedurally to become subsequently a problem‐space per se. (shrink)

Positing the importance of sensorimotor contingencies for perception is by no means denying the presence and importance of representations. Using the evidence of mirror neurons we will show the intrinsic relationship between action control and representation within the logic of forward models.

Six characteristics of effective representational systems for conceptual learning in complex domains have been identified. Such representations should: (1) integrate levels of abstraction; (2) combine globally homogeneous with locally heterogeneous representation of concepts; (3) integrate alternative perspectives of the domain; (4) support malleable manipulation of expressions; (5) possess compact procedures; and (6) have uniform procedures. The characteristics were discovered by analysing and evaluating a novel diagrammatic representation that has been invented to support students' comprehension of electricity—AVOW diagrams (Amps, (...) Volts, Ohms, Watts). A task analysis is presented that demonstrates that problem solving using a conventional algebraic approach demands more effort than AVOW diagrams. In an experiment comparing two groups of learners using the alternative approaches, the group using AVOW diagrams learned more than the group using equations and were better able to solve complex transfer problems and questions involving multiple constraints. Analysis of verbal protocols and work scratchings showed that the AVOW diagram group, in contrast to the equations group, acquired a coherently organised network of concepts, learnt effective problem solving procedures, and experienced more positive learning events. The six principles of effective representations were proposed on the basis of these findings. AVOW diagrams are Law Encoding Diagrams, a general class of representations that have been shown to support learning in other scientific domains. (shrink)

In this paper, it will be argued that each time a procedure in a representational system is functioning adequately and automatically, the child steps up to a metaprocedural level and considers the procedure as a unit in its own right. Data will be drawn from microdevelopment in children's creation of external memory devices (i.e., changes in representation of a spatial task during a one hour's session) as well as from macrodevelopment in language acquisition (i.e., changes occurring over age (...) in a study of nominal determiners, pronouns and gender markers). These two aspects of development of representational systems are examined with respect to the spontaneous passage from concrete reference to abstract systems, from idiosyncratic to conventional notations, from redundant to economic marking, from unifunctional to plurifunctional meaningful units. These micro‐ and manodevelopmental changes take place in a spontaneous fashion despite the fact that the child's earlier system is adequate for successfully conveying the information required. A discussion will be made of the way in which children tend to indicate externally, by unifunctional markers, information which was implicit in their earlier use of an adult‐like system. They appear to be striving for the delicate balance between encoding and decoding efforts, ultimately leading to a felicitous representational system. Metaprocedural behavior is hypothesized to act as a control mechanism in the striving for this delicate balance of information content and information processing effort. It also appears to act as a control mechanism for the interprocedural organizotion of what was previously a plethora of juxtaposed, unconnected procedures yielding superficially analogous behavior. The stepping‐up to a metaprocedural level seems to occur each time the child has a handle on his currently functioning, goal‐oriented system. This enables the child to treat the system, or procedures which are part thereof, as units functioning in their own right. Thus there appears to be a deep‐rooted psychological tendency for a representational tool which functions well procedurally to become subsequently a problem‐space per se. (shrink)

Six characteristics of effective representational systems for conceptual learning in complex domains have been identified. Such representations should: (1) integrate levels of abstraction; (2) combine globally homogeneous with locally heterogeneous representation of concepts; (3) integrate alternative perspectives of the domain; (4) support malleable manipulation of expressions; (5) possess compact procedures; and (6) have uniform procedures. The characteristics were discovered by analysing and evaluating a novel diagrammatic representation that has been invented to support students' comprehension of electricity—AVOW diagrams (Amps, (...) Volts, Ohms, Watts). A task analysis is presented that demonstrates that problem solving using a conventional algebraic approach demands more effort than AVOW diagrams. In an experiment comparing two groups of learners using the alternative approaches, the group using AVOW diagrams learned more than the group using equations and were better able to solve complex transfer problems and questions involving multiple constraints. Analysis of verbal protocols and work scratchings showed that the AVOW diagram group, in contrast to the equations group, acquired a coherently organised network of concepts, learnt effective problem solving procedures, and experienced more positive learning events. The six principles of effective representations were proposed on the basis of these findings. AVOW diagrams are Law Encoding Diagrams, a general class of representations that have been shown to support learning in other scientific domains. (shrink)

There are various approaches to ontology metamodelling, and the notion of biologically inspired modular knowledge representation systems can provide insight in the workings of such phenomena as emergent properties of network structures. What is more relevant from knowledge engineering standpoint, such approach could provide innovation and enhancement of the level of expression as well as overall functionality of modular ontologies. To do so, one needs to find biological structures that would be the basis for modularity on different levels of (...) hierarchy within the artificial system. Network analysis tools as well as systems biology and biocomputing provide a framework for research in this field. (shrink)

o formalization of intensional functions was made for the purpose of many-valued interpretation of the belief-operators within the scope of the classical logic system. The first aim of the paper is to present and discuss this rather unknown many-valued construction and its properties. The fact that the manyvaluedness of o systems is purely formal - their characteristic matrices are Boolean - calls for further consideration. Departing from intristic similarities of the tables for the epistemic operators to the information functions (...) we show that o structures may be rewritten as special knowledge representation systems. These systems use 0 and 1 as the only values and are called “epistemic”. Their role for the theory of knowledge information systems may be compared to that of the functionally complete matrices in the class of all logical matrices for a given propositional language. (shrink)

A duality between Pawlak's knowledge representation systems and certain information systems of logical type, called bi-consequence systems is established. As an application a first-order characterization of some informational relations is given and a completeness theorem for the corresponding modal logic INF is proved. It is shown that INF possesses finite model property and hence is decidable.

The possibility of ideography is an empirical question. Prior examples of graphic codes do not provide compelling evidence for the infeasibility of ideography, because they fail to satisfy essential cognitive requirements that have only recently been revealed by studies of representational systems in cognitive science. Design criteria derived from cognitive principles suggest how effective graphic codes may be engineered.

We define ordinal representations in the simply typed lambda calculus, and consider the ordinal functions representable with respect to these notations. The results of this paper have the same flavor as those of Schwichtenberg and Statman on numeric functions representable in the simply typed lambda calculus. We define four families of ordinal notations; in order of increasing generality of the type of notation, the representable functions consist of the closure under composition of successor and α ωα, addition (...) and α ωα, addition and multiplication, and addition, multiplication, and a “weak” discriminator. (shrink)

Though capturing powerful analytical principles, this excellent article misses ways in which psychology and neuroscience bear on reciprocity and decision-making. I suggest more explicit consideration of scale. We may go further beyond gene-culture dualism by articulating how varieties of living systems, while ultimately drawing from both genetic and cultural streams, evolve sufficiently as unitary targets of selection to mediate higher-level complex systems. (Published Online April 27 2007).

Any set x is uniquely specified by the graph of the membership relation on the set obtained by adjoining x to the transitive closure of x. Thus any operation on sets can be looked at as an operation on these graphs. We look at the operations of ordinal arithmetic of sets in this light. This turns out to be simplest for a modified ordinal arithmetic based on the Zermelo ordinals, instead of the usual von Neumann ordinals. In this (...) arithmetic, addition of sets corresponds to concatenating graphs, and multiplication corresponds to replacing each edge of a graph by a copy of another graph. Characterizations for the von Neumann case are also given. (shrink)

En este trabajo se define formamente el concepto de representacion en química utilizando homomorfismos desde estructuras algebraicas, que llamamos sistemas de tipo C, en otras estructuras especiales de símbolos muy relacionados con los que son habituales en la qímica experimental. Para la definicion de los sistemas de tipo C se ha seleccionado un conjunto minimo de relaciones y funciones, que son necesarias para expresar proposiciones significativas en química. Tambien se define un lenguaje formal de primer orden adecuado a los sistemas (...) de tipo C, que llamamos L(C). EI resultado principal que se demuestra es que toda representación que verifica las mismas sentencias de L(C) que un sistema de tipo C, es necesariamente isomorfo a él. Se concluye por lo tanto que puede existir un problema linguístico subyacente en la aplicacion que de la mecaníca cuántica se hace en la química teórica.The concept of representation in chemistry bas been formallv defined by means of homomorphisms from algebraical structures, which we call type-C systems, to some special sets of symbols which can be related to the symbols ordinarily used in experimental chemistry. A minimum number of relations and functions, which would suffice to express significant propositions in chemistry, have been chosen to define type-C systems. A first order formal language L(C) adequate to type-C systems has been defined. It has been shown that each representation that verifies the same sentences of L(C) as a type-C system is necessarily isomorphic to it. It is concluded that a systematic study of the representation problem in chemistry is in order because a deep language problem underlies the application of quantum mechanies to chemical problems. (shrink)