The Controversy over the Existence of the World (henceforth Controversy) is the magnum opus of Polish philosopher Roman Ingarden. Despite the renewed interest for Ingarden’s pioneering ontological work whithin analytic philosophy, little attention has been dedicated to Controversy's main goal, clearly indicated by the very title of the book: finding a solution to the centuries-old philosophical controversy about the ontological status of the external world. -/- There are at least three reasons for this relative indifference. First, even at the time (...) when the book was published, the Controversy was no longer seen as a serious polemical topic, whether it was disqualified as an archaic metaphysical pseudo-problem, or taken to be the last remnant of an antiscientific approach to philosophy culminating in idealism and relativism. Second, Ingarden’s reasoning on the matter is highly complex, at times misleading, and even occasionally faulty. Finally, his analysis is not only incomplete – Controversy being unachieved – but also arguably aporetic. -/- One may wonder, then, why it is still worth excavating this mammoth treatise to study an issue apparently no longer relevant to contemporary philosophy. Aside from historical and exegetical purposes, which are of course very interesting in their own right, Ingarden’s treatment of the Controversy remains one of the most detailed and ambitious ontological undertakings of the twentieth century. Not only does it lay out an incredibly detailed map of possible solutions to the Controversy, but it also tries to show why the latter is a genuine and fundamental problem that owes its hasty disqualification to various oversimplifications over the course of the history of philosophy. -/- In this chapter, I first give an overview of Ingarden’s method, which relies mainly on a combinatorial analysis. Then, I summarize his examination of possible solutions to the Controversy, and determine which ones can be ruled out on ontological grounds. Finally, I explain why this ambitious project ultimately leads to a theoretical impasse, leaving Ingarden unable to come up with a definitive solution to the Controversy – regardless of the fact that the book is unachieved. I argue that his analysis of the problem yields a more modest but nonetheless valuable result. (shrink)

The axioms of projective and affine plane geometry are turned into rules of proof by which formal derivations are constructed. The rules act only on atomic formulas. It is shown that proof search for the derivability of atomic cases from atomic assumptions by these rules terminates . This decision method is based on the central result of the combinatorial analysis of derivations by the geometric rules: The geometric objects that occur in derivations by the rules can be restricted (...) to those known from the assumptions and cases. This “subterm property” is proved by permuting suitably the order of application of the geometric rules. As an example of the decision method, it is shown that there cannot exist a derivation of Euclid’s fifth postulate if the rule that corresponds to the uniqueness of the parallel line construction is taken away from the system of plane affine geometry. (shrink)

Although it is frequently said that logic is a purely formal discipline lacking any content for special philosophical subdisciplines, I argue in this essay that the concepts of predication, and of the properties of objects presupposed by standard first-order logic are sufficient to address many of the traditional problems of ontology. The concept of an object's having a property is extended to provide an intensional definition of the existence of an object as the object's possessing a maximally consistent property combination, (...) consisting, for any property or its complement. Nonexistent objects by the proposed definition are those that either lack both some property and its complement, or have both a property and its complement included in its corresponding property combination. The definition in turn makes it possible to offer solutions based on purely logical concepts of such longstanding metaphysical problems as why there is something rather than nothing, and why there exists exactly one logically contingent actual world, itself a maximally consistent combination of true predication instances or facts. Additionally, the ontology upholds an argument in support of modal actualism and against modal realism, treating all logically possible worlds other than the actual world as predicationally incomplete nonexistent objects or semantic fictions. (shrink)

We study combinatorial principles related to the isomorphism property and the special model axiom in nonstandard analysis.

For every partial combinatory algebra, we define a hierarchy of extensionality relations using ordinals. We investigate the closure ordinals of pca’s, i.e., the smallest ordinals where these relations become equal. We show that the closure ordinal of Kleene’s first model is ${\omega _1^{\textit {CK}}}$ and that the closure ordinal of Kleene’s second model is $\omega _1$. We calculate the exact complexities of the extensionality relations in Kleene’s first model, showing that they exhaust the hyperarithmetical hierarchy. We also discuss embeddings of (...) pca’s. (shrink)

This paper distinguishes between causal isolation robustness analysis and independent determination robustness analysis and suggests that the triangulation of the results of different epistemic means or activities serves different functions in them. Circadian clock research is presented as a case of causal isolation robustness analysis: in this field researchers made use of the notion of robustness to isolate the assumed mechanism behind the circadian rhythm. However, in contrast to the earlier philosophical case studies on causal isolation robustness (...) analysis (Weisberg and Reisman in Philos Sci 75:106–131, 2008 ; Kuorikoski et al. in Br J Philos Sci 61:541–567, 2010 ), robustness analysis in the circadian clock research did not remain in the level of mathematical modeling, but it combined it with experimentation on model organisms and a new type of model, a synthetic model. (shrink)

The authors aim to reinstate a spirit of philosophical enquiry in physics. They abandon the intuitive continuum concepts and build up constructively a combinatorial mathematics of process. This radical change alone makes it possible to calculate the coupling constants of the fundamental fields which? via high energy scattering? are the bridge from the combinatorial world into dynamics. The untenable distinction between what is?observed?, or measured, and what is not, upon which current quantum theory is based, is not needed. (...) If we are to speak of mind, this has to be present? albeit in primitive form? at the most basic level, and not to be dragged in at one arbitrary point to avoid the difficulties about quantum observation. There is a growing literature on information-theoretic models for physics, but hitherto the two disciplines have gone in parallel. In this book they interact vitally. (shrink)

We investigate the complexity of various combinatorial theorems about linear and partial orders, from the points of view of computability theory and reverse mathematics. We focus in particular on the principles ADS (Ascending or Descending Sequence), which states that every infinite linear order has either an infinite descending sequence or an infinite ascending sequence, and CAC (Chain-AntiChain), which states that every infinite partial order has either an infinite chain or an infinite antichain. It is well-known that Ramsey's Theorem for (...) pairs (RT₂²) splits into a stable version (SRT₂²) and a cohesive principle (COH). We show that the same is true of ADS and CAC, and that in their cases the stable versions are strictly weaker than the full ones (which is not known to be the case for RT₂² and SRT₂²). We also analyze the relationships between these principles and other systems and principles previously studied by reverse mathematics, such as WKL₀, DNR, and BΣ₂. We show, for instance, that WKL₀ is incomparable with all of the systems we study. We also prove computability-theoretic and conservation results for them. Among these results are a strengthening of the fact, proved by Cholak, Jockusch, and Slaman, that COH is Π₁¹-conservative over the base system RCA₀. We also prove that CAC does not imply DNR which, combined with a recent result of Hirschfeldt, Jockusch, Kjos-Hanssen, Lempp, and Slaman, shows that CAC does not imply SRT₂² (and so does not imply RT₂²). This answers a question of Cholak, Jockusch, and Slaman. Our proofs suggest that the essential distinction between ADS and CAC on the one hand and RT₂² on the other is that the colorings needed for our analysis are in some way transitive. We formalize this intuition as the notions of transitive and semitransitive colorings and show that the existence of homogeneous sets for such colorings is equivalent to ADS and CAC, respectively. We finish with several open questions. (shrink)

This article aims to present Christology not as an add-on to monotheism, but as its specific Christian form. What Christ means can only be explained with reference to God and vice versa; what God stands for in a Christian sense has to be explained with reference to Jesus Christ and not with reference to generic religious terms. Christology thus informs and forms the Christian understanding of how to relate God and reality. Therefore, Christology has to be developed as combinatory Christology (...) bringing different dimensions of reality including scientific and evolutionary perspectives into creative interplay. Theology is an ‘art of combination’, which in ever new ways relates traditions of faith with theoretical and historical knowledge in order to find relevant ways of understanding God’s presence in the world, to articulate the Christian faith in a meaningful way and to form our ways of living in such a way as to conform to God’s passion for the life of God’s creatures. This article wants to lay grounds for such an endeavour by re-evaluating the history of Christology and combining this analysis with present day challenges. (shrink)

Most studies of motifs of biological regulatory networks focus on the analysis of asymptotical behaviours, but transient properties are rarely addressed. In the line of our previous study devoted to isolated circuits 19:172–178, 2003), we consider chorded circuits, that are motifs made of an elementary positive or negative circuit with a chord, possibly a self-loop. We provide detailed descriptions of the boolean dynamics of chorded circuits versus isolated circuits, under the synchronous and asynchronous updating schemes within the logical formalism. (...) To this end, we address the description of the trajectories in the dynamics of isolated circuits with coding techniques and adapt them for chorded circuits. The use of the logical modeling gives access to mathematical tools allowing complete analytical analysis of basic yet important motifs. In particular, we show that whatever the chosen updating rule, the dynamics depends on a small number of parameters. (shrink)

Three objections have recently been levelled at the analysis of intrinsicness offered by Rae Langton and David Lewis. While these objections do seem telling against the particular theory Langton and Lewis offer, they do not threaten the broader strategy Langton and Lewis adopt: defining intrinsicness in terms of combinatorial features of properties. I show how to amend their theory to overcome the objections without abandoning the strategy.

1. Setting off: An introduction. 1.1. A measure of motivation. 1.2. Computable mathematics. 1.3. Reverse mathematics. 1.4. An overview. 1.5. Further reading -- 2. Gathering our tools: Basic concepts and notation. 2.1. Computability theory. 2.2. Computability theoretic reductions. 2.3. Forcing -- 3. Finding our path: Konig's lemma and computability. 3.1. II[symbol] classes, basis theorems, and PA degrees. 3.2. Versions of Konig's lemma -- 4. Gauging our strength: Reverse mathematics. 4.1. RCA[symbol]. 4.2. Working in RCA[symbol]. 4.3. ACA[symbol]. 4.4. WKL[symbol]. 4.5. [symbol]-models. (...) 4.6. First order axioms. 4.7. Further remarks -- 5. In defense of disarray -- 6. Achieving consensus: Ramsey's theorem. 6.1. Three proofs of Ramsey's theorem. 6.2. Ramsey's theorem and the arithmetic hierarchy. 6.3. RT, ACA[symbol], and the Paris-Harrington theorem. 6.4. Stability and cohesiveness. 6.5. Mathias forcing and cohesive sets. 6.6. Mathias forcing and stable colorings. 6.7. Seetapun's theorem and its extensions. 6.8. Ramsey's theorem and first order axioms. 6.9. Uniformity -- 7. Preserving our power: Conservativity. 7.1. Conservativity over first order systems. 7.2. WKL[symbol] and II[symbol]-conservativity. 7.3. COH and r-II[symbol]-conservativity -- 8. Drawing a map: Five diagrams -- 9. Exploring our surroundings: The world below RT[symbol]. 9.1. Ascending and descending sequences. 9.2. Other combinatorial principles provable from RT[symbol]. 9.3. Atomic models and omitting types -- 10. Charging ahead: Further topics. 10.1. The Dushnik-Miller theorem. 10.2. Linearizing well-founded partial orders. 10.3. The world above ACA[symbol]. 10.4. Still further topics, and a final exercise. (shrink)

The present volume is an introduction to the use of tools from computability theory and reverse mathematics to study combinatorial principles, in particular Ramsey's theorem and special cases such as Ramsey's theorem for pairs. It would serve as an excellent textbook for graduate students who have completed a course on computability theory.

A considerable number of areas of bioscience, including gene and drug discovery, metabolic engineering for the biotechnological improvement of organisms, and the processes of natural and directed evolution, are best viewed in terms of a ‘landscape’ representing a large search space of possible solutions or experiments populated by a considerably smaller number of actual solutions that then emerge. This is what makes these problems ‘hard’, but as such these are to be seen as combinatorial optimisation problems that are best (...) attacked by heuristic methods known from that field. Such landscapes, which may also represent or include multiple objectives, are effectively modelled in silico, with modern active learning algorithms such as those based on Darwinian evolution providing guidance, using existing knowledge, as to what is the ‘best’ experiment to do next. An awareness, and the application, of these methods can thereby enhance the scientific discovery process considerably. This analysis fits comfortably with an emerging epistemology that sees scientific reasoning, the search for solutions, and scientific discovery as Bayesian processes. (shrink)

The system of combinatory logic presented in this essay differs from usual systems of combinatory logic by its addition of Boolean operators and a theory of quantification. It differs from Fitch's previous systems in containing a strong extensionality principle. The system is claimed to provide adequate foundations for a major part of mathematical analysis. In this Report the elementary theory of natural numbers is developed in detail. An excellent introduction to Fitch's work; the exposition is clear and well developed.--J. (...) R. W. (shrink)

The Löwenheim-Skolem theorem was published in Skolem's long paper of 1920, with the first section dedicated to the theorem. The second section of the paper contains a proof-theoretical analysis of derivations in lattice theory. The main result, otherwise believed to have been established in the late 1980s, was a polynomial-time decision algorithm for these derivations. Skolem did not develop any notation for the representation of derivations, which makes the proofs of his results hard to follow. Such a formal notation (...) is given here by which these proofs become transparent. A third section of Skolem's paper gives an analysis for derivations in plane projective geometry. To clear a gap in Skolem's result, a new conservativity property is shown for projective geometry, to the effect that a proper use of the axiom that gives the uniqueness of connecting lines and intersection points requires a conclusion with proper cases (logically, a disjunction in a positive part) to be proved. The forgotten parts of Skolem's first paper on the Löwenheim-Skolem theorem are the perhaps earliest combinatorial analyses of formal mathematical proofs, and at least the earliest analyses with profound results. (shrink)

This book continues from where the authors' previous book, Structural Proof Theory, ended. It presents an extension of the methods of analysis of proofs in pure logic to elementary axiomatic systems and to what is known as philosophical logic. A self-contained brief introduction to the proof theory of pure logic is included that serves both the mathematically and philosophically oriented reader. The method is built up gradually, with examples drawn from theories of order, lattice theory and elementary geometry. The (...) aim is, in each of the examples, to help the reader grasp the combinatorial behaviour of an axiom system, which typically leads to decidability results. The last part presents, as an application and extension of all that precedes it, a proof-theoretical approach to the Kripke semantics of modal and related logics, with a great number of new results, providing essential reading for mathematical and philosophical logicians. (shrink)

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]). (shrink)

In the thesis some combinatorial statements are analysed from the reverse mathematics point of view. Reverse mathematics is a research program, which dates back to the Seventies, interested in finding the exact strength, measured in terms of set-existence axioms, of theorems from ordinary non set-theoretic mathematics. After a brief introduction to the subject, an on-line (incremental) algorithm to transitively reorient infinite pseudo-transitive oriented graphs is defined. This implies that a theorem of Ghouila-Houri is provable in RCA_0 and hence is (...) computably true. Interval graphs and interval orders are the common theme of the second part of the thesis. A chapter is devoted to analyse the relative strength of different characterisations of countable interval graphs and to study the interplay between countable interval graphs and countable interval orders. In this context the theme of unique orderability of interval graphs arises, which is studied in the following chapter. The last chapter about interval orders inspects the strength of some statements involving the dimension of countable interval orders. The third part is devoted to the analysis of two theorems proved by Rival and Sands in 1980. The first principle states that each infinite graph contains an infinite subgraph such that each vertex of the graph is adjacent either to none, or to one or to infinitely many vertices of the subgraph. This statement, restricted to countable graphs, is proved to be equivalent to ACA_0 and hence to be stronger than Ramsey's theorem for pairs, despite the similarity of partial order with finite width contains an infinite chain such that each point of the poset is comparable either to none or to infinitely many points of the chain. For each k less than or equal to 3, the latter principle restricted to countable poset of width k is proved to be equivalent to ADS. Some complementary results are presented in the thesis. (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)

This manuscript contributes to a future definition of objectivity by bringing together recent statements in epistemology and methodology. It outlines how improved objectivity can be achieved by systematically incorporating multiple perspectives, thereby improving the validity of science. The more result-biasing perspectives are known, the more a phenomenon of interest can be disentangled from these perspectives. Approaches that call for the integration of perspective into objectivity at the epistemological level or that systematically incorporate different perspectives at the statistical level already exist (...) and are brought together in the manuscript. Recent developments in research methodology, such as transparency, reproducibility of research processes, pre-registration of studies, or free access to raw data, analysis strategies, and syntax, promote the explication of perspectives because they make the entire research process visible. How the explication of perspectives can be done practically is outlined in the manuscript. As a result, future research programs can be organized in such a way that meta-analyses and meta-meta-analyses can be conducted not only backward but forward and prospectively as a regular and thus well-prepared part of objectification and validation processes. (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)

This article discusses the role of diagrams in mathematical reasoning in the light of a case study in analysis. In the example presented certain combinatorial expressions were first found by using diagrams. In the published proofs the pictures were replaced by reasoning about permutation groups. This article argues that, even though the diagrams are not present in the published papers, they still play a role in the formulation of the proofs. It is shown that they play a role (...) in concept formation as well as representations of proofs. In addition we note that 'visualization' is used in two different ways. In the first sense 'visualization' denotes our inner mental pictures, which enable us to see that a certain fact holds, whereas in the other sense 'visualization' denotes a diagram or representation of something. (shrink)

Anselm of Cantorbery wrote Proslogion, where is formulated the famous ‘Unum argumentum’ about the existence of God. This argument was been disputed and criticized by numerous logicians from an extensional view point. The classical predicate logic is not able to give a formal frame to develop an adequate analysis of this argument. According to us, this argument is not an ontological proof; it analyses the meaning of the “quo nihil maius cogitari posit”, a characterization of God, and establish, by (...) absurd, that “quod non posit cogitare non esse” by using the hypothesis: “to think in re” is taller than “to think in solo intelectu”. We discuss this relation and the difference between the meanings of the elementary predicates ‘to be in re’, ‘to be in intellectu’ and ‘to be in solo intellectu’. We propose a new logical approach of this ‘Unum argumentum’ of Anselm by using Curry’s Combinatory Logic. Indeed, Combinatory Logic is an abstract applicative formalism of operators applied to operands; in this formalism, the predicates, viewed as specific operators, can be composed and can be transformed, by an intrinsic way, into more complex predicates, by means of abstract operators, called “combinators”, studied by Combinatory Logic. We show that this formalism is a logical frame where it becomes possible to discuss and to formulate cognitive representations of the meanings of predicates used inside of the ‘Unum argumentum’ and to explain how the argument runs. (shrink)

We describe a model-theoretic approach to ordinal analysis via the finite combinatorial notion of an α-large set of natural numbers. In contrast to syntactic approaches that use cut elimination, this approach involves constructing finite sets of numbers with combinatorial properties that, in nonstandard instances, give rise to models of the theory being analyzed. This method is applied to obtain ordinal analyses of a number of interesting subsystems of first- and second-order arithmetic.

This paper explores the difference between Connectionist proposals for cognitive a r c h i t e c t u r e a n d t h e s o r t s o f m o d e l s t hat have traditionally been assum e d i n c o g n i t i v e s c i e n c e . W e c l a i m t h a t t h (...) e m a j o r d i s t i n c t i o n i s t h a t , w h i l e b o t h Connectionist and Classical architectures postulate representational mental states, the latter but not the former are committed to a symbol-level of representation, or to a ‘language of thought’: i.e., to representational states that have combinatorial syntactic and semantic structure. Several arguments for combinatorial structure in mental representations are then reviewed. These include arguments based on the ‘systematicity’ of mental representation: i.e., on the fact that cognitive capacities always exhibit certain symmetries, so that the ability to entertain a given thought implies the ability to entertain thoughts with semantically related contents. We claim that such arguments make a powerful case that mind/brain architecture is not Connectionist at the cognitive level. We then consider the possibility that Connectionism may provide an account of the neural (or ‘abstract neurological’) structures in which Classical cognitive architecture is implemented. We survey a n u m b e r o f t h e s t a n d a r d a r g u m e n t s t h a t h a v e b e e n o f f e r e d i n f a v o r o f Connectionism, and conclude that they are coherent only on this interpretation. (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 this paper two new combinatorial principles in nonstandard analysis are isolated and applications are given. The second principle provides an equivalent formulation of Henson's isomorphism property.

The problem of combinatorial optimization is considered in relation to the choice of the location of the location of power supplies when solving the problem of the development of urban distribution networks of power supply. Two methods have been developed for placing power supplies and assigning consumers to them to solve this problem. The first developed method consists in placing power supplies of the same standard sizes, and the second - of different standard sizes. The fundamental difference between the (...) created methods and the existing ones is that the proposed methods take into account all the material of the problem and have specialized methods for coding possible solutions, modified operators of crossing and selection. The proposed methods effectively solve the problem of low inheritance, topological unfeasibility of the found solutions, as a result of which the execution time is significantly reduced and the accuracy of calculations is increased. In the developed methods, the lack of taking into account the restrictions on the placement of new power supplies is realized, which made it possible to solve the problem of applying the methods for a narrow range of problems. A comparative analysis of the results obtained by placing power supplies of the same standard sizes and known methods was carried out, and it was found that the developed method works faster than the known methods. It is shown that the proposed approach ensures stable convergence of the search process by an acceptable number of steps without artificial limitation of the search space and the use of additional expert information on the feasibility of possible solutions. The results obtained allow us to propose effective methods to improve the quality of decisions made on the choice of the location of power supply facilities in the design of urban electrical. (shrink)

According to Thagard and Stewart :1–33, 2011), creativity results from the combination of neural representations, and combination results from convolution, an operation on vectors defined in the holographic reduced representation framework. They use these ideas to understand creativity as it occurs in many domains, and in particular in science. We argue that, because of its algebraic properties, convolution alone is ill-suited to the role proposed by Thagard and Stewart. The semantic pointer concept allows us to see how we can apply (...) the full range of HRR operations while keeping the modal representations so central to Thagard and Stewart’s theory. By adding another combination operation and using semantic pointers as the combinatorial basis, this modified version overcomes the limitations of the original theory and perhaps helps us explain aspects of creativity not covered by the original theory. While a priori reasons cast doubts on the use of HRR operations with modal representations :5039–5054, 1987) such as semantic pointers, recent models point in the other direction, allowing us to be optimistic about the success of the revised version. (shrink)

According to Thagard and Stewart :1–33, 2011), creativity results from the combination of neural representations, and combination results from convolution, an operation on vectors defined in the holographic reduced representation framework. They use these ideas to understand creativity as it occurs in many domains, and in particular in science. We argue that, because of its algebraic properties, convolution alone is ill-suited to the role proposed by Thagard and Stewart. The semantic pointer concept allows us to see how we can apply (...) the full range of HRR operations while keeping the modal representations so central to Thagard and Stewart’s theory. By adding another combination operation and using semantic pointers as the combinatorial basis, this modified version overcomes the limitations of the original theory and perhaps helps us explain aspects of creativity not covered by the original theory. While a priori reasons cast doubts on the use of HRR operations with modal representations :5039–5054, 1987) such as semantic pointers, recent models point in the other direction, allowing us to be optimistic about the success of the revised version. (shrink)

A fixed-parameter is an algorithm that provides an optimal solution to a combinatorial problem. This research-level text is an application-oriented introduction to the growing and highly topical area of the development and analysis of efficient fixed-parameter algorithms for hard problems. The book is divided into three parts: a broad introduction that provides the general philosophy and motivation; followed by coverage of algorithmic methods developed over the years in fixed-parameter algorithmics forming the core of the book; and a discussion (...) of the essential from parameterized hardness theory with a focus on W [1]-hardness, which parallels NP-hardness, then stating some relations to polynomial-time approximation algorithms, and finishing up with a list of selected case studies to show the wide range of applicability of the presented methodology. Aimed at graduate and research mathematicians, programmers, algorithm designers and computer scientists, the book introduces the basic techniques and results and provides a fresh view on this highly innovative field of algorithmic research. (shrink)

In recent years, several remarkable results have shown that certain theorems of finite combinatorics are unprovable in certain logical systems. These developments have been instrumental in stimulating research in both areas, with the interface between logic and combinatorics being especially important because of its relation to crucial issues in the foundations of mathematics which were raised by the work of Kurt Godel. Because of the diversity of the lines of research that have begun to shed light on these issues, there (...) was a need for a comprehensive overview which would tie the lines together. This volume fills that need by presenting a balanced mixture of high quality expository and research articles that were presented at the August 1985 AMS-IMS-SIAM Joint Summer Research Conference, held at Humboldt State University in Arcata, California.With an introductory survey to put the works into an appropriate context, the collection consists of papers dealing with various aspects of 'unprovable theorems and fast-growing functions'. Among the topics addressed are: ordinal notations, the dynamical systems approach to Ramsey theory, Hindman's finite sums theorem and related ultrafilters, well quasiordering theory, uncountable combinatorics, nonstandard models of set theory, and a length-of-proof analysis of Godel's incompleteness theorem. Many of the articles bring the reader to the frontiers of research in this area, and most assume familiarity with combinatorics and/or mathematical logic only at the senior undergraduate or first-year graduate level. (shrink)

One of the traditional ways mathematical ideas and even new areas of mathematics are created is from experiments. One of the best-known examples is that of the Fermat hypothesis, which was conjectured by Fermat in his attempts to find integer solutions for the famous Fermat equation. This hypothesis led to the creation of a whole field of knowledge, but it was proved only after several hundred years. This book, based on the author's lectures, presents several new directions of mathematical research. (...) All of these directions are based on numerical experiments conducted by the author, which led to new hypotheses that currently remain open, i.e., are neither proved nor disproved. The hypotheses range from geometry and topology (statistics of plane curves and smooth functions) to combinatorics (combinatorial complexity and random permutations) to algebra and number theory (continuous fractions and Galois groups). For each subject, the author describes the problem and presents numerical results that led him to a particular conjecture. In the majority of cases there is an indication of how the readers can approach the formulated conjectures (at least by conducting more numerical experiments). Written in Arnold's unique style, the book is intended for a wide range of mathematicians, from high school students interested in exploring unusual areas of mathematics on their own, to college and graduate students, to researchers interested in gaining a new, somewhat nontraditional perspective on doing mathematics. In the interest of fostering a greater awareness and appreciation of mathematics and its connections to other disciplines and everyday life, MSRI and the AMS are publishing books in the Mathematical Circles Library series as a service to young people, their parents and teachers, and the mathematics profession. Titles in this series are co-published with the Mathematical Sciences Research Institute (MSRI). (shrink)

Topics covered in Discrete Mathematics have become essential tools in many areas of studies in recent years. This is primarily due to the revolution in technology, communications, and cyber security. The book treats major themes in a typical introductory modern Discrete Mathematics course: Propositional and predicate logic, proof techniques, set theory (including Boolean algebra, functions and relations), introduction to number theory, combinatorics and graph theory. An accessible, precise, and comprehensive approach is adopted in the treatment of each topic. The ability (...) of abstract thinking and the art of writing valid arguments are emphasized through detailed proof of (almost) every result. Developing the ability to think abstractly and roguishly is key in any areas of science, information technology and engineering. Every result presented in the book is followed by examples and applications to consolidate its comprehension. The hope is that the reader ends up developing both the abstract reasoning as well as acquiring practical skills. All efforts are made to write the book at a level accessible to first-year students and to present each topic in a way that facilitates self-directed learning. Each chapter starts with basic concepts of the subject at hand and progresses gradually to cover more ground on the subject. Chapters are divided into sections and subsections to facilitate readings. Each section ends with its own carefully chosen set of practice exercises to reenforce comprehension and to challenge and stimulate readers. As an introduction to Discrete Mathematics, the book is written with the smallest set of prerequisites possible. Familiarity with basic mathematical concepts (usually acquired in high school) is sufficient for most chapters. However, some mathematical maturity comes in handy to grasp some harder concepts presented in the book. (shrink)

We give a combinatorial analysis (using edge expansion) of a variant of the iterative expander construction due to Reingold, Vadhan, and Wigderson [44], and show that this analysis can be formalized in the bounded arithmetic system VNC^1 (corresponding to the “NC^1 reasoning”). As a corollary, we prove the assumption made by Jeřábek [28] that a construction of certain bipartite expander graphs can be formalized in VNC^1 . This in turn implies that every proof in Gentzen's sequent calculus (...) LK of a monotone sequent can be simulated in the monotone version of LK (MLK) with only polynomial blowup in proof size, strengthening the quasipolynomial simulation result of Atserias, Galesi, and Pudlák [9]. (shrink)

This book discusses in dialogue form the basic principles of mathematics and its applications including the question: What is mathematics? What does its specific method consist of? What is its relation to the sciences and humanities? What can it offer to specialists in different fields? How can it be applied in practice and in discovering the laws of nature? Dramatized by the dialogue form and shown in the historical movements in which they originated, these questions are discussed in their full (...) complexity, yet are easily comprehended. The first dialogue, whose chief actor is Socrates, leads the reader to the source of modern mathematics in Athens in the 5th Century BC. The second dialogue, featuring Archimedes, takes place during the siege of Syracuse in 212 BC and shows the birth of applied mathematics. The third dialogue occurs in the year 1633 in Rome, its chief character being Galileo Galilei who fully realized the central importance of the mathematical method in discovering the laws of nature. Intended as supplemental reading for philosophy of mathematics courses at the high school or college level it will be of interest to both specialists and non-specialists in mathematics. Alfréd Rényi was born in Budapest Hungary in 1921. He studied mathematics and physics at the University of Budapest and received his Ph. D. from the University of Szaged in 1945. Since 1950 he has been Director of the Mathematical Research Institute of the Hungarian Academy of Sciences and since 1952 a professor at the University of Budapest. Dr. Renyi was a visiting professor at Michigan State University in 1961, at the University of Michigan in 1964 and at Stanford University in 1966. His main fields of research are probability theory, mathematical statistics and information theory, and he has also worked in analytic number theory as well as in various branches of analysis, combinatorial analysis and geometry. (shrink)

A question dating to Mardešić and Prasolov’s 1988 work [S. Mardešić and A. V. Prasolov, Strong homology is not additive, Trans. Amer. Math. Soc. 307(2) (1988) 725–744], and motivating a considerable amount of set theoretic work in the years since, is that of whether it is consistent with the ZFC axioms for the higher derived limits [Formula: see text] [Formula: see text] of a certain inverse system [Formula: see text] indexed by [Formula: see text] to simultaneously vanish. An equivalent formulation (...) of this question is that of whether it is consistent for all [Formula: see text]-coherent families of functions indexed by [Formula: see text] to be trivial. In this paper, we prove that, in any forcing extension given by adjoining [Formula: see text]-many Cohen reals, [Formula: see text] vanishes for all [Formula: see text]. Our proof involves a detailed combinatorial analysis of the forcing extension and repeated applications of higher-dimensional [Formula: see text]-system lemmas. This work removes all large cardinal hypotheses from the main result of [J. Bergfalk and C. Lambie-Hanson, Simultaneously vanishing higher derived limits, Forum Math. Pi 9 (2021) e4] and substantially reduces the least value of the continuum known to be compatible with the simultaneous vanishing of [Formula: see text] for all [Formula: see text]. (shrink)

The mind–body problem is analyzed in a physicalist perspective. By combining the concepts of emergence and algorithmic information theory in a thought experiment, employing a basic nonlinear process, it is shown that epistemologically emergent properties may develop in a physical system. Turning to the significantly more complex neural network of the brain it is subsequently argued that consciousness is epistemologically emergent. Thus reductionist understanding of consciousness appears not possible; the mind–body problem does not have a reductionist solution. The ontologically emergent (...) character of consciousness is then identified from a combinatorial analysis relating to universal limits set by quantum mechanics, implying that consciousness is fundamentally irreducible to low-level phenomena. (shrink)

It is widely assumed that there exist certain objects which can in no way be distinguished from each other, unless by their location in space or other reference-system. Some of these are, in a broad sense, 'empirical objects', such as electrons. Their case would seem to be similar to that of certain mathematical 'objects', such as the minimum set of manifolds defining the dimensionality of an R -space. It is therefore at first sight surprising that there exists no branch of (...) mathematics, in which a third parity-relation, besides equality and inequality, is admitted; for this would seem to furnish an appropriate model for application to such instances as these. I hope, in this work, to show that such a mathematics in feasible, and could have useful applications if only in a limited field. The concept of what I here call 'indistinguishability' is not unknown in logic, albeit much neglected. It is mentioned, for example, by F. P. Ramsey [1] who criticizes Whitehead and Russell [2] for defining 'identity' in such a way as to make indistinguishables identical. But, so far as I can discover, no one has made any systematic attempt to open up the territory which lies behind these ideas. What we find, on doing so, is a body of mathematics, offering only a limited prospect of practical usefulness, but which on the theoretical side presents a strong challenge to conventional ideas. (shrink)

The mind-body problem is analyzed in a physicalist perspective. By combining the concepts of emergence and algorithmic information theory in a thought experiment employing a basic nonlinear process, it is shown that epistemically strongly emergent properties may develop in a physical system. Turning to the significantly more complex neural network of the brain it is subsequently argued that consciousness is epistemically emergent. Thus reductionist understanding of consciousness appears not possible; the mind-body problem does not have a reductionist solution. The ontologically (...) emergent character of consciousness is then identified from a combinatorial analysis relating to universal limits set by quantum mechanics, implying that consciousness is fundamentally irreducible to low-level phenomena. (shrink)

In this paper I argue that warrant for Lewis’ principle of recombination presupposes warrant for a combinatorial analysis of intrinsicality, which in turn presupposes warrant for the principle of recombination. This, I claim, leads to a vicious circularity: warrant for neither doctrine can get off the ground.