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)

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)

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)

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)

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)

Monografija obrađuje probleme matematičke logike i kombinatorike. Tematika se odnosi na oblast između kombinatorike, logike i teorije komutacija. Dalje se razrađuju simetrične funkcije, algoritmi i klasifikacija. Rad je baziran na iskustvima Laboratorije za elektrotehniku u Ibaraki (Japan) i sradnji sa kolegama iz Kanade, DDR, USSR-a, Mađarske.

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)

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)

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 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.

Marques (Philosophia, 49(3), 1109–1125 2021) argues that Hom’s Combinatorial Externalism (CE) faces a hitherto unknown problem when coupled with a standard Kratzerian account of deontic modality: CE plus Kratzerian modality would entail the negation of a thesis central to Hom’s analysis of slurs, the null extensionality thesis (i.e., the thesis that slurs have empty extensions). Since modality is an integral part of Hom’s take on slurs, and Kratzer’s account of modality has the status of the standard take on (...) modality, this would be bad news for CE. In this paper, I argue that, pace Marques, CE and a Kratzerian account of deontic modals do not clash with the null extensionality claim. Marques’ discussion, however, helps us expose substantive, non-semantic assumptions concerning practical philosophy that seem to be implicitly built into CE’s semantic analysis of slurs. (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.

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)

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)

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)

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)

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)

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)

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)

§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)

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)

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)

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)

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.

In this thesis, we study the complexity of some mathematical problems: in particular, those arising in computable analysis and algorithmic learning theory for algebraic structures. Our study is not limited to these two areas: indeed, in both cases, the results we obtain are tightly connected to ideas and tools coming from different areas of mathematical logic, including for example descriptive set theory and reverse mathematics.After giving the necessary preliminaries, we first study the uniform computational strength of the Cantor–Bendixson theorem (...) in the Weihrauch lattice. This work falls into the program connecting reverse mathematics and computable analysis via the framework of Weihrauch reducibility. We concentrate on problems related to perfect subsets of Polish spaces, studying the perfect set theorem, the Cantor–Bendixson theorem, and various problems arising from them. As far as we know, this is the first systematic study of problems at the level of $\mathbf {\Pi }^1_1\mathsf {-CA}_0$ in the Weihrauch lattice. We show that the strength of some of the problems we study depends on the topological properties of the Polish space under consideration, while others have the same strength once the space is rich enough.We continue considering problems related to (induced) subgraphs. We provide results on the (effective) Wadge complexity of sets of graphs, that are also used to determine the Weihrauch degree of certain decision problems. The decision problems we consider are defined for a fixed graph G, and they take as input a graph H, answering whether G is an (induced) subgraph of H: we also consider the opposite problem (i.e., answering whether H is an induced subgraph of G). We conclude this part on (induced) subgraphs considering the Weihrauch degree of “search problems.”These problems are defined for a fixed graph G, and they take as input a graph H such that G is an (induced) subgraph H: the output is a copy of G in H. In both cases, we highlight differences and analogies between the subgraph and the induced subgraph relation.We then move our attention to algorithmic learning theory, and we present the framework we use to study the learnability of families of algebraic structures: here, given a countable family of pairwise nonisomorphic structures $\mathfrak {K}$, a learner receives larger and larger pieces of an arbitrary copy of a structure in $\mathfrak {K}$ and, at each stage, is required to output a conjecture about the isomorphism type of such a structure. We say that $\mathfrak {K}$ is learnable if there exists a learner which eventually stabilizes to a correct guess. The framework was lacking a method for comparing the complexity of nonlearnable families, and so we propose a solution to this problem using tools coming from invariant descriptive set theory. To do so, we first prove that a family of structures is learnable if and only if its learning domain is continuously reducible to the relation $E_0$ of eventual agreement on infinite binary sequences and then, replacing $E_0$ with Borel equivalence relations of higher complexity, we obtain a new hierarchy of learning problems. This leads to the notion of E-learnability, where a family of structures $\mathfrak {K}$ is E-learnable, for a Borel equivalence relation E, if there is a continuous reduction from the isomorphism relation associated with $\mathfrak {K}$ to E. It is then natural to ask how the notion of E-learnability interacts with “classical” learning paradigms.Finally, we study the number of mind changes that a learner needs to learn a given family, both from a topological and a combinatorial point of view, and we consider how the complexity of a learner (in terms of Turing reducibility) affects the number of mind changes for learning a given family.Abstract prepared by Vittorio Cipriani.E-mail: [email protected]: https://air.uniud.it/handle/11390/1252226. (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)

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)

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)

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.

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)

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)

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 objective of this paper is to present the truth tables method of the propositional calculus of Tractatus Logico-Philosophicus as a result of computational procedures involving recursive operations in mathematics, since the secondary literature that is involved with such a problem fails to demonstrate such aspect of the work. The proposal is to demonstrate the base calculation of the truth operations as a consequence of the application of mathematical resources that involve the notion of recursivity, inspired both in the natural (...) numbers as well as in the factorial calculus, as well as in the procedures recommended by the combinatorial analysis and the calculation of probability. It is hoped, therefore, to present the truth operations of the propositional calculus as coming from the application of arithmetic to the logical resources. (shrink)

Neuroethological investigations of mammalian and avian auditory systems have documented species-specific specializations for processing complex acoustic signals that could, if viewed in abstract terms, have an intriguing and striking relevance for human speech sound categorization and representation. Each species forms biologically relevant categories based on combinatorial analysis of information-bearing parameters within the complex input signal. This target article uses known neural models from the mustached bat and barn owl to develop, by analogy, a conceptualization of human processing of (...) consonant plus vowel sequences that offers a partial solution to the noninvariance dilemma the locus equations orderly output constraint”) is hypothesized based on the notion of an evolutionarily conserved auditory-processing strategy. High correlation and linearity between critical parameters in the speech signal that help to cue place of articulation categories might have evolved to satisfy a preadaptation by mammalian auditory systems for representing tightly correlated, linearly related components of acoustic signals. (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.

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.

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)

This commentary focuses on the nature of combinatorial properties for speech and the locus equation. The presence of some overlap in locus equation space suggests that this higher order property may not be strictly invariant and may require other cues or properties for the perception of place of articulation. Moreover, combinatorial analysis in two-dimensional space and the resultant linearity appear to have a “special” status in the development of this theoretical framework. However, place of articulation is only (...) one of many phonetic dimensions in language. It is suggested that a multidimensional space including patterns derived in the frequency, amplitude, and time domains will be needed to characterize the phonetic categories of speech, and that although the derived properties ultimately may not meet the conditions of linearity, they will reflect a higher order acoustic invariance. (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)

Girotto and Legrenzi's 1993 facilitation effect for their SARS version of Wason s THOG problem a disjunctive reasoning task was examined. The effect was not replicated when the standard THOG problem instructions were used in Experiments 1 and 2. However, in Experiment 3 when Girotto and Legrenzi's precise instructions were used, facilitation was observed. Experiment 4 further investigated the role of the type of instructions in the observed facilitation. The results suggest that such facilitation may result from attentional factors rather (...) than the use of a combinatorial analysis in the problem. (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)

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 argued that epistemically strongly emergent properties may develop in a physical system. A comparison with the significantly more complex neural network of the brain shows that also consciousness is epistemically emergent in a strong sense. 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 system limits set by quantum mechanics, implying that consciousness is fundamentally irreducible to low-level phenomena. In the perspective of a modified definition of free will, the character of the physical interactions of the brain's neural system is subsequently studied. As an ontologically open system, it is asserted that its future states are undeterminable in principle. We argue that this leads to freedom of the will. (shrink)