Logic and Philosophy of Logic, Miscellaneous

It is widely assumed that the identity relation is, among other things, transitive. Some have proposed that the identity relation might hold between objects contingently or occasionally. If, on those proposals, identity is shown to not be transitive, then there is reason to reject such proposals. One such argument attempts to show that the identity relation on such proposals violates transitivity in cases of ‘simultaneous’ fissions and fusion. I argue that, even in those cases, contingent identity and occasional identity are (...) transitive. (shrink)

In Baghdad in the mid twelfth century Abū al-Barakāt proposes a radical new procedure for finding the conclusions of premise-pairs in syllogistic logic, and for identifying those premise-pairs that have no conclusions. The procedure makes no use of features of the standard Aristotelian apparatus, such as conversions or syllogistic figures. In place of these al-Barakāt writes out pages of diagrams consisting of labelled horizontal lines. He gives no instructions and no proof that the procedure will yield correct results. So the (...) reader has to work out what his procedure is and whether it is correct. The procedure turns out to be insightful and entirely correct, but this paper may be the first study to give a full description of the procedure and a rigorous proof of its correctness. (shrink)

I discuss a neglected solution to the skeptical problem introduced by Lewis Carroll’s “What the Tortoise Said to Achilles” (1895) in terms of a self-citational inferential license. I then consider some responses to this solution. The most significant response on behalf of the skeptic utilizes the familiar distinction between two ways of accepting a rule: as action-guiding and as a mere truth. I argue that this is ultimately unsatisfactory and conclude by opting for an alternative conception of rules as representations (...) of behavior deployed for various purposes, some theoretical and others practical. This alternative conception does not allow the skeptical problem to get off the ground. (shrink)

Livro em homenagem ao filósofo brasileiro Luiz Henrique Lopes, um dos maiores expoentes da filosofia analítica. Neste livro grandes nomes da filosofia brasileira discorrem sobre a filosofia analítica e vários assuntos da filosofia contemporânea.

In the first of the Insolubles in Chapter 8 of his Sophismata, Buridan contends that the inference Omnis propositio est affirmativa; ergo, nulla propositio est negativa (PS) is valid, even though it appeals to the self-reference in the conclusion to show that what we (following Read 2001) call the classical conception of validity (CCV) fails. This requires that we accept that there are good inferences in which a false conclusion follows from true premises. Partially following Hughes’ proposal (1982), we argue (...) that the First Sophism (PS) involves three different notions of validity. Two of them correspond to the ones described by Hughes (1982, 80–86), who calls them Theory A and Theory B. The third one—that will we call Theory C—is not mentioned by Hughes; instead, it is suggested by Buridan himself in the first three arguments in favor of the validity of PS. We show that: a) from what Buridan says in his Theory C it follows that PS is a formal and material consequence, and hence, a valid one. Then we show that: b) the rejection of CCV and the acceptance of Nulla propositio est negativa (NPN) as a (formal) consequence of Omnis propositio est affirmativa (OPA) leads to a paradox that bears similarities with the one put forward by Pseudo Scotus—which has been studied by Read (2001) and is related to Curry’s paradox. However, there are enough differences to merit considering this paradox separately, especially in relation to the so-called validity paradoxes. Interestingly, our work suggests that Buridan was aware of these problems, which explains why he introduced a new criterion for validity, one that is not based on truth-preservation but on what Spade (1988) calls firmness, and Klima (2016) correspondence. (shrink)

The Logic of Analogy is a study of the valid logical forms of qualitative and quantitative analogical argument, and the rules pertaining to them. It investigates equally valid conflicting arguments, statistics-based arguments and their utility in science, arguments from precedent used in law-making or law-application, and examines subsumption in analogical terms. Included for purposes of illustration is a large section on Talmudic use of analogical reasoning.

Western contemporary logic has been used to advance the field of Islamic philosophical theology, which historically utilised Aristotelian-Avicennian logic, on grounds of there being an inherent normativity in logic. This is in spite of the surrounding controversy on the status of logic in the Islamic theological tradition. The normative authority of logic means that it influences the content of what we ought to believe and how we ought to revise those beliefs. This paper seeks to demonstrate that, notwithstanding the incompatible (...) differences between the two systems, the underlying feature of both Western contemporary logic and Aristotelian- Avicennian logic is logical normativity. It then argues that an inherent normativity of logic in the Islamic theological/philosophical tradition is unmotivated. Instead, it proposes to reinstate logic as anti-exceptional within the Islamic theological/philosophical tradition as a viable alternative. (shrink)

We solve two problems from a work of Haskel and Pillay concerning maximal stable quotients of groups ∧-definable in NIP theories. The first result says that if G is a ∧-definable group in a distal theory, then Gst=G00 (where Gst is the smallest ∧-definable subgroup with G∕Gst stable, and G00 is the smallest ∧-definable subgroup of bounded index). In order to get it, we prove that distality is preserved under passing from T to the hyperimaginary expansion Theq. The second result (...) is an example of a group G definable in a nondistal NIP theory for which G=G00, but Gst is not an intersection of definable groups. Our example is a saturated extension of (R,+,[0,1]). Moreover, we make some observations on the question whether there is such an example which is a group of finite exponent. We also take the opportunity and give several characterizations of stability of hyperdefinable sets involving continuous logic. (shrink)

This paper summarises the contributions to our Topical Collection on indeterminacy and underdetermination. The collection includes papers in ethics, metaethics, logic, metaphysics, epistemology, philosophy of science, philosophy of language and philosophy of computation.

After introducing the debate between substance philosophy and process philosophy, and clarifying the relevance of the category of ‘substance’ in Peirce’s thought, the present paper reconstructs the role of ‘substance’ and ‘being’ from Peirce’s early works to his theory of the proposition, provided after his studies on the logic of relatives. If those two categories apparently disappear in Peirce’s writings from the mid-1890s onwards, the account of ‘subject’ and ‘copula’ in Peirce’s analysis of the proposition allows one to grasp the (...) reasons why Peirce omits ‘substance’ and ‘being’ in favor of his three categories (Firstness, Secondness, Thirdness), and to understand why his philosophy cannot be considered as a substance philosophy. (shrink)

El Anti-Excepcionalismo Lógico afirma que la Lógica es como cualquier otra ciencia. Si esta afirmación es cierta, entonces ella no sólo es revisable, sino que además todo lo que se puede decir sobre las ciencias aplica, mutatis mutandis, para la misma. El propósito de este artículo es explorar esta consecuencia del Anti-Excepcionalismo Lógico, acercando a la Filosofía de la Lógica el marco teórico de las Máquinas Nomológicas de Nancy Cartwright. De acuerdo con esta visión, lo que hay de verdadero en (...) las teorías científicas no está en el mundo sino en sus modelos: sistemas altamente controlados, estables, artificiales y específicos, dentro de los cuales se manifiestan regularidades sistematizables y enseñables. Mi afirmación es que lo mismo puede decirse de la Lógica: ella no captura las Leyes del Pensamiento o de la Razón, porque el pensamiento y la razón no están gobernados necesariamente por leyes. Sobre lo que sí puede decirse que versan las Leyes de la Lógica son metafísicas posibles: historias acerca de qué son las proposiciones, el pensamiento, la verdad y la validez. A fin de ilustrar y defender esta tesis, presento un ejemplo de Máquina Nomológica de la Lógica Clásica, basada en una lectura original del Tractatus de Wittgenstein, e investigo algunas de sus consecuencias. Mi conclusión es que esta imagen de la Lógica impacta en el problema de la revisión de la Lógica Clásica, en la medida en que muestra que dicha revisión no necesariamente responde a un proceso racional de adecuación de la teoría a los hechos porque los “hechos” relevantes no son anteriores a la teoría misma, sino que están moldeados y conducidos por ella. Palabras clave: Anti-Excepcionalismo Lógico, Abductivismo, Máquinas Nomológicas, Revisión Lógica, Filosofía de la Lógica. (shrink)

A teaching document I've used in my courses on truth and on incompleteness. Aimed at students who have a good grasp of basic logic, and decent math skills, it attempts to give them the background they need to understand a proper statement of the classic results due to Gödel and Tarski, and sketches their proofs. Topics covered include the notions of language and theory, the basics of formal syntax and arithmetization, formal arithmetic (Q and PA), representability, diagonalization, and the incompleteness (...) and undefinability theorems. (shrink)

In this paper, we present the history of and the research directions in relating logic. For this purpose we will describe Epstein's Programme, which postulates accounting for the content of sentences in logical research. We will focus on analysing the content relationship and Epstein's logics that are based on it, which are special cases of relating logic. Moreover, the set-assignment semantics will be discussed. Next, the Torunian Programme of Relating Semantics will be presented; this programme explores the various non-logical relationships (...) in logical research, including those which are content-related. We will present a general description of relating logic and semantics as well as the most prominent issues regarding the Torunian Programme, including some of its special cases and the results achieved to date. -/- . (shrink)

Answering a question of Cifú Lopes, we give a syntactic characterization of those continuous sentences that are preserved under reduced products of metric structures. In fact, we settle this question in the wider context of general structures as introduced by the second author.

Skolem studied the germs at infinity of the smallest class of real valued functions on the positive real line containing the constant $1$, the identity function ${\mathbf {x}}$, and such that whenever f and g are in the set, $f+g,fg$ and $f^g$ are in the set. This set of germs is well ordered and Skolem conjectured that its order type is epsilon-zero. Van den Dries and Levitz computed the order type of the fragment below $2^{2^{\mathbf {x}}}$. Here we prove that (...) the set of asymptotic classes within any Archimedean class of Skolem functions has order type $\omega $. As a consequence we obtain, for each positive integer n, an upper bound for the fragment below $2^{n^{\mathbf {x}}}$. We deduce an epsilon-zero upper bound for the fragment below $2^{{\mathbf {x}}^{\mathbf {x}}}$, improving the previous epsilon-omega bound by Levitz. A novel feature of our approach is the use of Conway’s surreal number for asymptotic calculations. (shrink)

Our main result is that there exist structures which cannot be computably recovered from their tree of tuples. This implies that there are structures with no computable copies which nevertheless cannot code any information in a natural/functorial way.

A mass problem is a set of functions $\omega \to \omega $. For mass problems ${\mathcal {C}}, {\mathcal {D}}$, one says that ${\mathcal {C}}$ is Muchnik reducible to ${\mathcal {D}}$ if each function in ${\mathcal {C}}$ is computed by a function in ${\mathcal {D}}$. In this paper we study some highness properties of Turing oracles, which we view as mass problems. We compare them with respect to Muchnik reducibility and its uniform strengthening, Medvedev reducibility.For $p \in [0,1]$ let ${\mathcal {D}}$ (...) be the mass problem of infinite bit sequences y such that for each computable bit sequence x, the bit sequence $ x {\,\leftrightarrow\,} y$ has asymptotic lower density at most p = y$ ). We show that all members of this family of mass problems parameterized by a real p with $0 p$ for each computable set x. We prove that the Medvedev complexity of the mass problems ${\mathcal {B}}$ is the same for all $p \in $, by showing that they are Medvedev equivalent to the mass problem of functions bounded by ${2^{2}}^{n}$ that are almost everywhere different from each computable function.Next, together with Joseph Miller, we obtain a proper hierarchy of the mass problems of type $\text {IOE}$ : we show that for any order function g there exists a faster growing order function $h $ such that $\text {IOE}$ is strictly above $\text {IOE}$ in the sense of Muchnik reducibility.We study cardinal characteristics in the sense of set theory that are analogous to the highness properties above. For instance, ${\mathfrak {d}} $ is the least size of a set G of bit sequences such that for each bit sequence x there is a bit sequence y in G so that $\underline \rho >p$. We prove within ZFC all the coincidences of cardinal characteristics that are the analogs of the results above. (shrink)

We analyze the precise modal commitments of several natural varieties of set-theoretic potentialism, using tools we develop for a general model-theoretic account of potentialism, building on those of Hamkins, Leibman and Löwe [14], including the use of buttons, switches, dials and ratchets. Among the potentialist conceptions we consider are: rank potentialism, Grothendieck–Zermelo potentialism, transitive-set potentialism, forcing potentialism, countable-transitive-model potentialism, countable-model potentialism, and others. In each case, we identify lower bounds for the modal validities, which are generally either S4.2 or S4.3, (...) and an upper bound of S5, proving in each case that these bounds are optimal. The validity of S5 in a world is a potentialist maximality principle, an interesting set-theoretic principle of its own. The results can be viewed as providing an analysis of the modal commitments of the various set-theoretic multiverse conceptions corresponding to each potentialist account. (shrink)

A theory of magnitudes involves criteria for their equivalence, comparison and addition. In this article we examine these aspects from an abstract viewpoint, by focusing on the so-called De Zolt’s postulate in the theory of equivalence of plane polygons (“If a polygon is divided into polygonal parts in any given way, then the union of all but one of these parts is not equivalent to the given polygon”). We formulate an abstract version of this postulate and derive it from some (...) selected principles for magnitudes. We also formulate and derive an abstract version of Euclid’s Common Notion 5 (“The whole is greater than the part”), and analyze its logical relation to the former proposition. These results prove to be relevant for the clarification of some key conceptual aspects of Hilbert’s proof of De Zolt’s postulate, in his classicalFoundations of Geometry(1899). Furthermore, our abstract treatment of this central proposition provides interesting insights for the development of a well-behaved theory ofcompatiblemagnitudes. (shrink)

The Unified Foundational Ontology (UFO) was developed over the last two decades by consistently putting together theories from areas such as formal ontology in philosophy, cognitive science, linguistics, and philosophical logics. It comprises a number of micro-theories addressing fundamental conceptual modeling notions, including entity types and relationship types. The aim of this paper is to summarize the current state of UFO, presenting a formalization of the ontology, along with the analysis of a number of cases to illustrate the application of (...) UFO and facilitate its comparison with other foundational ontologies in this special issue. (The cases originate from the First FOUST Workshop – the Foundational Stance, an international forum dedicated to Foundational Ontology research.). (shrink)

This volume of the Logica Yearbook series brings together articles presented at the annual international symposium Logica 2012, Hejnice, the Czech Republic. The articles range over mathematical and philosophical logic, history and philosophy of logic, and the analysis of natural language.

The first aim of this paper is to prove a topological completeness theorem for a weak version of Stalnaker’s logic KB of knowledge and belief. The weak version of KB is characterized by the assumption that the axioms and rules of KB have to be satisfied with the exception of the axiom (NI) of negative introspection. The proof of a topological completeness theorem for weak KB is based on the fact that nuclei (as defined in the framework of point-free topology) (...) give rise to a profusion of topological belief operators that are compatible with the familiar topological knowledge operator. Thereby a canonical topological model for weak KB can be constructed. For this canonical model a truth lemma for the K and B holds such that a completeness theorem for KB can be proved in the familiar way. The second aim of this paper is to show that the topological interpretation of knowledge K comes along with a complete Heyting algebra of belief operators B that all fit the knowledge operator K in the sense that the pairs (K, B) satisfy all axioms of weak KB. This amounts to a pluralistic relation between knowledge and belief: Knowledge does not fully determine belief, rather it designs a conceptual space for belief operators where different (competing) belief operators coexist. (shrink)

Logicians disagree about how validity—the very heart of logic—should be understood. Many different formal systems have been born due to this disagreement. This thesis examines how teachers explain the subject matter of logic to students in introductory logic textbooks, and demonstrates the different explanations teachers use. These differences help explain why logicians have different intuitions about validity.

This book is dedicated to the work of Alasdair Urquhart. The book starts out with an introduction to and an overview of Urquhart’s work, and an autobiographical essay by Urquhart. This introductory section is followed by papers on algebraic logic and lattice theory, papers on the complexity of proofs, and papers on philosophical logic and history of logic. The final section of the book contains a response to the papers by Urquhart. Alasdair Urquhart has made extremely important contributions to a (...) variety of fields in logic. He produced some of the earliest work on the semantics of relevant logic. He provided the undecidability of the logics R and E, as well as some of their close neighbors. He proved that interpolation fails in some of those systems. Urquhart has done very important work in complexity theory, both about the complexity of proofs in classical and some nonclassical logics. In pure algebra, he has produced a representation theorem for lattices and some rather beautiful duality theorems. In addition, he has done important work in the history of logic, especially on Bertrand Russell, including editing Volume four of Russell’s Collected Papers. (shrink)

Gert H. Muller The growth of the number of publications in almost all scientific areas, as in the area of logic, is taken as a sign of our scientifically minded culture, but it also has a terrifying aspect. In addition, given the rapidly growing sophistica tion, specialization and hence subdivision of logic, researchers, students and teachers may have a hard time getting an overview of the existing literature, partic ularly if they do not have an extensive library available in their (...) neighbourhood: they simply do not even know what to ask for! More specifically, if someone vaguely knows that something vaguely connected with his interests exists some where in the literature, he may not be able to find it even by searching through the publications scattered in the review journals. Answering this challenge was and is the central motivation for compiling this Bibliography. The Bibliography comprises the following six volumes : I. Classical Logic W. Rautenberg II. Non-classical Logics W. Rautenberg III. Model Theory H. -D. Ebbinghaus IV. Recursion Theory P. G. Hinman V. Set Theory A. R. Blass VI. Proof Theory; Constructive Mathematics J. E. Kister; D. van Dalen & A. S. Troelstra. (shrink)

No further information has been provided for this title.

When asked in 1962 on what he was working Kazimierz Ajdukiewicz replied: Several years ago Polish Scientific Publishers suggested that I pre pare a new edition of The Logical Foundations of Teaching, which I wrote 1 before 1939 as a contribution to The Encyclopaedia of Education. It was a small booklet covering elementary information about logical semantics and scientific methodology, information which in my opinion was necessary as a foundation of teaching and as an element of the education of any (...) teacher. When I recently set to preparing the new edition, I rewrote practically everything, and a booklet of some 100 pages swelled into a bulky volume almost five times bigger. The issues have remained practically the same, but they are now analysed much more thoroughly and the threshold of difficulty is much higher now. The main stress has been laid on the methods used in the empirical sciences, and within that field, on the theory of measurement and the methods of statistical inference. I am now working on the last chapter of the book, concerned with explanation procedures and theory construction in the empirical sciences. When that book, which I intend to entitle Pragmatic Logic, is com pleted I intend to prepare for the press Vol. 2 of my minor writings, 2 Language and Cognition, which will cover some of my post-war pa pers. (shrink)

There is a profound, but frequently ignored relationship between logical consequence (formal implication) and material implication. The first repeats the patterns of the latter, but with a wider modal reach. It is argued that this kinship between formal and material implication simply means that they express the same kind of implication, but differ in scope. Formal implication is unrestricted material implication. This apparently innocuous observation has some significant corollaries: (1) conditionals are not connectives, but arguments; (2) the traditional examples of (...) valid argumentative forms are metalogical principles that express the properties of logical consequence; (3) formal logic is not a useful guide to detect valid arguments in the real world; (4) it is incoherent to propose alternatives to the material implication while accepting the classical properties of formal implication; (5) some of the counter-examples to classical argumentative forms and known conditional puzzles are unsound. (shrink)

We establish natural criteria under which normally iterable premice are iterable for stacks of normal trees. Let Ω be a regular uncountable cardinal. Let m < ω and M be an m-sound premouse and Σ be...

A wide Aronszajn tree is a tree of size and height $\omega _{1}$ with no uncountable branches. We prove that under $MA$ there is no wide Aronszajn tree which is universal under weak embeddings. This solves an open question of Mekler and Väänänen from 1994. We also prove that under $MA$, every wide Aronszajn tree weakly embeds in an Aronszajn tree, which combined with a result of Todorčević from 2007, gives that under $MA$ every wide Aronszajn tree embeds into a (...) Lipschitz tree or a coherent tree. We also prove that under $MA$ there is no wide Aronszajn tree which weakly embeds all Aronszajn trees, improving the result in the first paragraph as well as a result of Todorčević from 2007 who proved that under $MA$ there are no universal Aronszajn trees. (shrink)

This paper aims to argue for, else illustrate the epistemological significance of the use of non transitive similarity relations, mapping only to "types", as methodologically being on a par with the use of transitive similarity relations (equivalence relations), mapping as well to "predicates". -/- In this paper the sketch of an exact but simple geometrical model of the above construct is followed by mentioning respective use cases for non transitive similarity relations from science and humanities. A well known metaphysics example (...) is elaborated along these lines to some extent. (shrink)

El estudio actual de la argumentación se encuentra distanciado de la lógica. En este artículo sostengo que restaurar el vínculo del estudio de la argumentación con esta disciplina podría resultar benéfico para la metas descriptivas y normativas de este campo de investigación. Tras destacar algunos aspectos del surgimiento la teoría de la argumentación contemporánea, enfatizando la idea de "perspectivas", explico cómo el reconocimiento de sus objetivos y tareas volvió problemática la coexistencia de varios enfoques o aproximaciones para el estudio de (...) la realidad argumentativa. Sugiero algunas hipótesis explicativas sobre el abandono del enfoque lógico en favor de otras alternativas y, a continuación, ofrezco razones para encauzar el estudio sistemático de la argumentación desde este enfoque. Además de las consideraciones normativas y las herramientas descriptivas que pueden aducirse en su favor, sostengo que el enfoque lógico puede proporcionar una clase de integración a este campo investigación de maneras que no están disponibles para otras aproximaciones. (shrink)

Logical analysis of the applicability of nominals (which are introduced by hybrid logic) in the formal descriptions of the world (within modern knowledge representation and semantics-based systems) is very important because nominals, as second sorts of propositional symbols, can support logical identification of the described world at specific [temporal and/or spacial] states. This paper will focus on answering the philosophical-logical question of ‘how a fundamental world description in description logic (DL) and a nominal can be related to each other?’. Based (...) on my assumption that nominals can support more adequate identification of the world in DL, this paper will deal with the concept of ‘world identification’. Accordingly, based on a logical-terminological analysis of nominals, the paper will analyse hybridised fundamental world descriptions. The research will finally reach the idea that we can have a hybrid description logic based on the analysed concepts. (shrink)

In ordinary language, in the medical sciences, and in the overlap between them, we frequently make claims which imply that we might have had different gametic origins from the ones we actually have. Such statements seem intuitively true and coherent. But they counterfactually ascribe different DNA to their referents and therefore contradict material-origin essentialism, which Kripke and his followers argue is intuitively obvious. In this paper I argue, using examples from ordinary language and from philosophy of medicine and bioethics, that (...) statements which attribute alternative material origins to their referents are useful, common in political and medical reasoning, and in many cases best interpreted literally. So we must replace the doctrine of material-origin essentialism with one that can make sense of ordinary discourse and the language of the medical sciences. I propose an anti-essentialist account of such counterfactuals according to which individuals’ modal properties are relative to a given inquiry. (shrink)

In 1932, von Neumann proposed classifying the statistical behavior of differentiable systems. Joint work of B. Weiss and the author proved that the classification problem is complete analytic. Based on techniques in that proof, one is able to show that the collection of recursive diffeomorphisms of the 2-torus that are isomorphic to their inverses is $\Pi ^0_1$-hard via a computable 1-1 reduction. As a corollary there is a diffeomorphism that is isomorphic to its inverse if and only if the Riemann (...) Hypothesis holds, a different one that is isomorphic to its inverse if and only if Goldbach’s conjecture holds and so forth. Applying the reduction to the $\Pi ^0_1$-sentence expressing “ZFC is consistent” gives a diffeomorphism T of the 2-torus such that the question of whether $T\cong T^{-1}$ is independent of ZFC. (shrink)

The semantic paradoxes are associated with self-reference or referential circularity. However, there are infinitary versions of the paradoxes, such as Yablo's paradox, that do not involve this form of circularity. It remains an open question what relations of reference between collections of sentences afford the structure necessary for paradoxicality -- these are the so-called "dangerous" directed graphs. Building on Rabern, et. al (2013) we reformulate this problem in terms of fixed points of certain functions, thereby boiling it down to get (...) a purely mathematical problem. (shrink)

We give a short proof of the fundamental theorem of central element theory. The original proof is constructive and very involved and relies strongly on the fact that the class be a variety. Here we give a more direct nonconstructive proof which applies for the more general case of a first-order class which is both closed under the formation of direct products and direct factors.

If ${\mathfrak {F}}$ is a type-definable family of commensurable subsets, subgroups or subvector spaces in a metric structure, then there is an invariant subset, subgroup or subvector space commensurable with ${\mathfrak {F}}$. This in particular applies to type-definable or hyper-definable objects in a classical first-order structure.

Consider a definably complete uniformly locally o-minimal expansion of the second kind of a densely linearly ordered abelian group. Let $f:X \rightarrow R^n$ be a definable map, where X is a definable set and R is the universe of the structure. We demonstrate the inequality $\dim ) \leq \dim $ in this paper. As a corollary, we get that the set of the points at which f is discontinuous is of dimension smaller than $\dim $. We also show that the (...) structure is definably Baire in the course of the proof of the inequality. (shrink)

In connection with the work of Anscombe, Macpherson, Steinhorn and the present author in [1] we investigate the notion of a multidimensional exact class, a special kind of multidimensional asymptotic class with measuring functions that yield the exact sizes of definable sets, not just approximations. We use results about smooth approximation [24] and Lie coordinatization [13] to prove the following result, as conjectured by Macpherson: For any countable language $\mathcal {L}$ and any positive integer d the class $\mathcal {C}$ of (...) all finite $\mathcal {L}$-structures with at most d 4-types is a polynomial exact class in $\mathcal {L}$, where a polynomial exact class is a multidimensional exact class with polynomial measuring functions. (shrink)

Предложен е семантичен подход към логиката, в рамките на какъвто е вид дискурс, отличим със своята тавтологичност. На тази основа е даден пример и сравнение с психоаналитичен (Фройдистки) дискурс.

We present three examples of countable homogeneous structures whose automorphism groups are not universal, namely, fail to contain isomorphic copies of all automorphism groups of their substructures.Our first example is a particular case of a rather general construction on Fraïssé classes, which we call diversification, leading to automorphism groups containing copies of all finite groups. Our second example is a special case of another general construction on Fraïssé classes, the mixed sums, leading to a Fraïssé class with all finite symmetric (...) groups appearing as automorphism groups and at the same time with a torsion-free automorphism group of its Fraïssé limit. Our last example is a Fraïssé class of finite models with arbitrarily large finite abelian automorphism groups, such that the automorphism group of its Fraïssé limit is again torsion-free. (shrink)

We study a partial order on countably complete ultrafilters introduced by Ketonen [2] as a generalization of the Mitchell order. The following are our main results: the order is wellfounded; its linearity is equivalent to the Ultrapower Axiom, a principle introduced in the author’s dissertation [1]; finally, assuming the Ultrapower Axiom, the Ketonen order coincides with Lipschitz reducibility in the sense of generalized descriptive set theory.

There is a Turing computable embedding $\Phi $ of directed graphs $\mathcal {A}$ in undirected graphs. Moreover, there is a fixed tuple of formulas that give a uniform effective interpretation; i.e., for all directed graphs $\mathcal {A}$, these formulas interpret $\mathcal {A}$ in $\Phi $. It follows that $\mathcal {A}$ is Medvedev reducible to $\Phi $ uniformly; i.e., $\mathcal {A}\leq _s\Phi $ with a fixed Turing operator that serves for all $\mathcal {A}$. We observe that there is a graph G (...) that is not Medvedev reducible to any linear ordering. Hence, G is not effectively interpreted in any linear ordering. Similarly, there is a graph that is not interpreted in any linear ordering using computable $\Sigma _2$ formulas. Any graph can be interpreted in a linear ordering using computable $\Sigma _3$ formulas. Friedman and Stanley [4] gave a Turing computable embedding L of directed graphs in linear orderings. We show that there is no fixed tuple of $L_{\omega _1\omega }$ -formulas that, for all G, interpret the input graph G in the output linear ordering $L$. Harrison-Trainor and Montalbán [7] have also shown this, by a quite different proof. (shrink)

In this paper we investigate the computational complexity of deciding if the variety generated by a given finite idempotent algebra satisfies a special type of Maltsev condition that can be specified using a certain kind of finite labelled path. This class of Maltsev conditions includes several well known conditions, such as congruence permutability and having a sequence of n Jónsson terms, for some given n. We show that for such “path defined” Maltsev conditions, the decision problem is polynomial-time solvable.

We prove that the homeomorphism relation between compact spaces can be continuously reduced to the homeomorphism equivalence relation between absolute retracts, which strengthens and simplifies recent results of Chang and Gao, and Cieśla. It follows then that the homeomorphism relation of absolute retracts is Borel bireducible with the universal orbit equivalence relation. We also prove that the homeomorphism relation between regular continua is classifiable by countable structures and hence it is Borel bireducible with the universal orbit equivalence relation of the (...) permutation group on a countable set. On the other hand we prove that the homeomorphism relation between rim-finite metrizable compacta is not classifiable by countable structures. (shrink)

Answering one of the main questions of [S.-D. Friedman, T. Hyttinen and V. Kulikov, Generalized descriptive set theory and classification theory, Mem. Amer. Math. Soc. 230 80, Chap. 7], we show that there is a tight connection between the depth of a classifiable shallow theory [Formula: see text] and the Borel rank of the isomorphism relation [Formula: see text] on its models of size [Formula: see text], for [Formula: see text] any cardinal satisfying [Formula: see text]. This is achieved by (...) establishing a link between said rank and the [Formula: see text]-Scott height of the [Formula: see text]-sized models of [Formula: see text], and yields to the following descriptive set-theoretical analog of Shelah’s Main Gap Theorem: Given a countable complete first-order theory [Formula: see text], either [Formula: see text] is Borel with a countable Borel rank, or it is not Borel at all. The dividing line between the two situations is the same as in Shelah’s theorem, namely that of classifiable shallow theories. We also provide a Borel reducibility version of the above theorem, discuss some limitations to the possible complexities of [Formula: see text], and provide a characterization of categoricity of [Formula: see text] in terms of the descriptive set-theoretical complexity of [Formula: see text]. (shrink)

We study a family of ultraproducts of finite fields with the Frobenius automorphism in this paper. Their theories have the strict order property and TP2. But the coarse pseudofinite dimension of the definable sets is definable and integer-valued. Moreover, we also discuss the possible connection between coarse dimension and transformal transcendence degree in these difference fields.