We argue that C. Darwin and more recently W. Hennig worked at times under the simplifying assumption of an eternal biosphere. So motivated, we explicitly consider the consequences which follow mathematically from this assumption, and the infinite graphs it leads to. This assumption admits certain clusters of organisms which have some ideal theoretical properties of species, shining some light onto the species problem. We prove a dualization of a law of T.A. Knight and C. Darwin, and sketch a decomposition (...) result involving the internodons of D. Kornet, J. Metz and H. Schellinx. A further goal of this paper is to respond to B. Sturmfels’ question, “Can biology lead to new theorems?”. (shrink)

The concept of an infinite game played on a finite graph is perhaps novel in the context of an rather extensive recent literature in which infinite games are generally played on an infinite game tree. We claim two advantages for our model, which is admittedly more restrictive. First, our games have a more apparent resemblance to ordinary parlor games in spite of their infinite duration. Second, by distinguishing those nodes of the graph that determine (...) the winning and losing of the game , we are able to offer a complexity analysis that is useful in computer science applications. (shrink)

We analyze three applications of Ramsey’s Theorem for 4-tuples to infinite traceable graphs and finitely generated infinite lattices using the tools of reverse mathematics. The applications in graph theory are shown to be equivalent to Ramsey’s Theorem while the application in lattice theory is shown to be provable in the weaker system RCA0.

Given a countable graph, we say a set A of its vertices is universal if it contains every countable graph as an induced subgraph, and A is weakly universal if it contains every finite graph as an induced subgraph. We show that, for almost every graph on, (1) every set of positive upper density is universal, and (2) every set with divergent reciprocal sums is weakly universal. We show that the second result is sharp (i.e., a (...) random graph on will almost surely contain non‐universal sets with divergent reciprocal sums) and, more generally, that neither of these two results holds for a large class of partition regular families. (shrink)

The semantic paradoxes are often associated with self-reference or referential circularity. Yablo (Analysis 53(4):251–252, 1993), however, has shown that there are infinitary versions of the paradoxes 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. In this essay, we lay the groundwork for a general investigation into the nature of reference structures that support the semantic paradoxes and the semantic hypodoxes. We develop (...) a functionally complete infinitary propositional language endowed with a denotation assignment and extract the reference structural information in terms of graph-theoretic properties. We introduce the new concepts of dangerous and precarious reference graphs, which allows us to rigorously define the task: classify the dangerous and precarious directed graphs purely in terms of their graph-theoretic properties. Ungroundedness will be shown to fully characterize the precarious reference graphs and fully characterize the dangerous finite graphs. We prove that an undirected graph has a dangerous orientation if and only if it contains a cycle, providing some support for the traditional idea that cyclic structure is required for paradoxicality. This leaves the task of classifying danger for infinite acyclic reference graphs. We provide some compactness results, which give further necessary conditions on danger in infinite graphs, which in conjunction with a notion of self-containment allows us to prove that dangerous acyclic graphs must have infinitely many vertices with infinite out-degree. But a full characterization of danger remains an open question. In the appendices we relate our results to the results given in Cook (J Symb Log 69(3):767–774, 2004) and Yablo (2006) with respect to more restricted sentences systems, which we call $\mathcal{F}$ -systems. (shrink)

This paper deals primarily with countable, simple, connected graphs and the following two conditions which are trivially satisfied if the graphs are finite: (a) there is an edge-recognition algorithm, i.e., an effective procedure which enables us, given two distinct vertices, to decide whether they are adjacent, (b) there is a shortest path algorithm, i.e., an effective procedure which enables us, given two distinct vertices, to find a minimal path joining them. A graph $G = \langle\eta, \eta\rangle$ with η as (...) set of vertices and η as set of edges is an α-graph if it satisfies (a); it is an ω-graph if it satisfies (b). G is called r.e. (isolic) if the sets ν and η are r.e. (isolated). While every ω-graph is an α-graph, the converse is false, even if G is r.e. or isolic. Several basic properties of finite graphs do not generalize to ω-graphs. For example, an ω-tree with more than one vertex need not have two pendant vertices, but may have only one or none, since it may be a 1-way or 2-way infinite path. Nevertheless, some elementary propositions for finite graphs $G = \langle\nu, \eta\rangle$ with $n = \operatorname{card}(\nu), e = \operatorname{card}(\eta)$ , do generalize to isolic ω-graphs, e.g., n - 1 ≤ e ≤ n(n - 1)/2. Let N and E be the recursive equivalence types of ν and η respectively. Then we have for an isolic α-tree $G = \langle\nu, \eta\rangle: N = E + 1$ iff G is an ω-tree. The theorem that every finite graph has a spanning tree has a natural, effective analogue for ω-graphs. The structural difference between isolic α-graphs and isolic ω-graphs will be illustrated by: (i) every infinite graph is isomorphic to some isolic α-graph; (ii) there is an infinite graph which is not isomorphic to any isolic ω-graph. An isolic α-graph is also called a twilight graph. There are c such graphs, c denoting the cardinality of the continuum. (shrink)

When no single universal model for a set of structures exists at a given cardinal, then one may ask in which models of set theory does there exist a small family which embeds the rest. We show that for λ+-graphs (λ regular) omitting cliques of some finite or uncountable cardinality, it is consistent that there are small universal families and 2λ > λ+. In particular, we get such a result for triangle-free graphs.

May the same graph admit two different chromatic numbers in two different universes? How about infinitely many different values? and can this be achieved without changing the cardinals structure? In this paper, it is proved that in Gödel’s constructible universe, for every uncountable cardinal $$\mu $$ below the first fixed-point of the $$\aleph $$ -function, there exists a graph $$\mathcal G_\mu $$ satisfying the following.

Several results about the game of cops and robbers on infinite graphs are analyzed from the perspective of computability theory. Computable robber-win graphs are constructed with the property that no computable robber strategy is a winning strategy, and such that for an arbitrary computable ordinal \, any winning strategy has complexity at least \}\). Symmetrically, computable cop-win graphs are constructed with the property that no computable cop strategy is a winning strategy. Locally finite infinite trees and graphs are (...) explored. The Turing computability of a binary relation used to classify cop-win graphs is studied, and the computational difficulty of determining the winner for locally finite computable graphs is discussed. (shrink)

We explore a general method based on trees of elementary submodels in order to present highly simplified proofs to numerous results in infinite combinatorics. While countable elementary submodels have been employed in such settings already, we significantly broaden this framework by developing the corresponding technique for countably closed models of size continuum. The applications range from various theorems on paradoxical decompositions of the plane, to coloring sparse set systems, results on graph chromatic number and constructions from point-set topology. (...) Our main purpose is to demonstrate the ease and wide applicability of this method in a form accessible to anyone with a basic background in set theory and logic. (shrink)

If [Formula: see text] is a closed Noetherian graph on a [Formula: see text]-compact Polish space with no infinite cliques, it is consistent with the choiceless set theory ZF[Formula: see text][Formula: see text][Formula: see text]DC that [Formula: see text] is countably chromatic and there is no Vitali set.

We examine a number of results of infinite combinatorics using the techniques of reverse mathematics. Our results are inspired by similar results in recursive combinatorics. Theorems included concern colorings of graphs and bounded graphs, Euler paths, and Hamilton paths.

A cardinal characteristic can often be described as the smallest size of a family of sequences which has a given property. Instead of this traditional concern for a smallest realization of the given property, a basically new approach, taken in [4] and [5], asks for a realization whose members are sequences of labels that correspond to 1-way infinite paths in a labelled graph. We study this approach as such, establishing tools that are applicable to all these cardinal characteristics. (...) As an application, we demonstrate the power of the tools developed by presenting a short proof of the bounded graph conjecture [4]. (shrink)

We define an evolving Shelah‐Spencer process as one by which a random graph grows, with at each time a new node incorporated and attached to each previous node with probability, where is fixed. We analyse the graphs that result from this process, including the infinite limit, in comparison to Shelah‐Spencer sparse random graphs discussed in [21] and throughout the model‐theoretic literature. The first order axiomatisation for classical Shelah‐Spencer graphs comprises a Generic Extension axiom scheme and a No Dense (...) Subgraphs axiom scheme. We show that in our context Generic Extension continues to hold. While No Dense Subgraphs fails, a weaker Few Rigid Subgraphs property holds. (shrink)

Let CKDT be the assertion that for every countably infinite bipartite graph G, there exist a vertex covering C of G and a matching M in G such that C consists of exactly one vertex from each edge in M. (This is a theorem of Podewski and Steffens [12].) Let ATR0 be the subsystem of second-order arithmetic with arithmetical transfinite recursion and restricted induction. Let RCA0 be the subsystem of second-order arithmetic with recursive comprehension and restricted induction. We (...) show that CKDT is provable in ART0. Combining this with a result of Aharoni, Magidor, and Shore [2], we see that CKDT is logically equivalent to the axioms of ATR0, the equivalence being provable in RCA0. (shrink)

Halin in 1965 proved that if a graph has [Formula: see text] many pairwise disjoint rays for each [Formula: see text] then it has infinitely many pairwise disjoint rays. We analyze the complexity of this and other similar results in terms of computable and proof theoretic complexity. The statement of Halin’s theorem and the construction proving it seem very much like standard versions of compactness arguments such as König’s Lemma. Those results, while not computable, are relatively simple. They only (...) use arithmetic procedures or, equivalently, finitely many iterations of the Turing jump. We show that several Halin-type theorems are much more complicated. They are among the theorems of hyperarithmetic analysis. Such theorems imply the ability to iterate the Turing jump along any computable well ordering. Several important logical principles in this class have been extensively studied beginning with work of Kreisel, H. Friedman, Steel and others in the 1960s and 1970s. Until now, only one purely mathematical example was known. Our work provides many more and so answers Question 30 of Montalbán’s Open Questions in Reverse Mathematics in 2011. Some of these theorems including ones in Halin in 1965 are also shown to have unusual proof theoretic strength as well. (shrink)

Analogues of Ramsey’s Theorem for infinite structures such as the rationals or the Rado graph have been known for some time. In this context, one looks for optimal bounds, called degrees, for the number of colors in an isomorphic substructure rather than one color, as that is often impossible. Such theorems for Henson graphs however remained elusive, due to lack of techniques for handling forbidden cliques. Building on the author’s recent result for the triangle-free Henson graph, we (...) prove that for each [Formula: see text], the k-clique-free Henson graph has finite big Ramsey degrees, the appropriate analogue of Ramsey’s Theorem. We develop a method for coding copies of Henson graphs into a new class of trees, called strong coding trees, and prove Ramsey theorems for these trees which are applied to deduce finite big Ramsey degrees. The approach here provides a general methodology opening further study of big Ramsey degrees for ultrahomogeneous structures. The results have bearing on topological dynamics via work of Kechris, Pestov, and Todorcevic and of Zucker. (shrink)

In this paper we study the Kolmogorov complexity for non-effective computations, that is, either halting or non-halting computations on Turing machines. This complexity function is defined as the length of the shortest input that produce a desired output via a possibly non-halting computation. Clearly this function gives a lower bound of the classical Kolmogorov complexity. In particular, if the machine is allowed to overwrite its output, this complexity coincides with the classical Kolmogorov complexity for halting computations relative to the first (...) jump of the halting problem. However, on machines that cannot erase their output –called monotone machines–, we prove that our complexity for non effective computations and the classical Kolmogorov complexity separate as much as we want. We also consider the prefix-free complexity for possibly infinite computations. We study several properties of the graph of these complexity functions and specially their oscillations with respect to the complexities for effective computations. (shrink)

Every set can been thought of as a directed graph whose edge relation is ∈. We show that many natural examples of directed graphs of this kind are indivisible: for every infinite κ, for every indecomposable λ, and every countable model of set theory. All of the countable digraphs we consider are orientations of the countable random graph. In this way we find indivisible well‐founded orientations of the random graph that are distinct up to isomorphism, and (...) ℵ1 that are distinct up to siblinghood. (shrink)

The universal homogeneous triangle-free graph, constructed by Henson [A family of countable homogeneous graphs, Pacific J. Math.38(1) (1971) 69–83] and denoted H3, is the triangle-free analogue of the Rado graph. While the Ramsey theory of the Rado graph has been completely established, beginning with Erdős–Hajnal–Posá [Strong embeddings of graphs into coloured graphs, in Infinite and Finite Sets. Vol.I, eds. A. Hajnal, R. Rado and V. Sós, Colloquia Mathematica Societatis János Bolyai, Vol. 10 (North-Holland, 1973), pp. 585–595] (...) and culminating in work of Sauer [Coloring subgraphs of the Rado graph, Combinatorica26(2) (2006) 231–253] and Laflamme–Sauer–Vuksanovic [Canonical partitions of universal structures, Combinatorica26(2) (2006) 183–205], the Ramsey theory of H3 had only progressed to bounds for vertex colorings [P. Komjáth and V. Rödl, Coloring of universal graphs, Graphs Combin.2(1) (1986) 55–60] and edge colorings [N. Sauer, Edge partitions of the countable triangle free homogenous graph, Discrete Math.185(1–3) (1998) 137–181]. This was due to a lack of broadscale techniques. We solve this problem in general: For each finite triangle-free graph G, there is a finite number T(G) such that for any coloring of all copies of G in H3 into finitely many colors, there is a subgraph of H3 which is again universal homogeneous triangle-free in which the coloring takes no more than T(G) colors. This is the first such result for a homogeneous structure omitting copies of some nontrivial finite structure. The proof entails developments of new broadscale techniques, including a flexible method for constructing trees which code H3 and the development of their Ramsey theory. (shrink)

Let $\Gamma$ be the random bipartite graph, a countable graph with two infinite sides, edges randomly distributed between the sides, but no edges within a side. In this paper, we investigate the reducts of $\Gamma$ that preserve sides. We classify the closed permutation subgroups containing the group $\operatorname {Aut}(\Gamma)^{\ast}$ , where $\operatorname {Aut}(\Gamma)^{\ast}$ is the group of all isomorphisms and anti-isomorphisms of $\Gamma$ preserving the two sides. Our results rely on a combinatorial theorem of Nešetřil and Rödl (...) and a strong finite submodel property for $\Gamma$. (shrink)

We generalize the Unstable Formula Theorem characterization of stable theories from Shelah [11], that a theory T is stable just in case any infinite indiscernible sequence in a model of T is an indiscernible set. We use a generalized form of indiscernibles from [11], in our notation, a sequence of parameters from an L-structure M, , indexed by an L′-structure I is L′-generalized indiscernible inM if qftpL′=qftpL′ implies tpL=tpL for all same-length, finite ¯,j from I. Let Tg be the (...) theory of linearly ordered graphs in the language with signature Lg={<,R}. Let Kg be the class of all finite models of Tg. We show that a theory T has NIP if and only if any Lg-generalized indiscernible in a model of T indexed by an Lg-structure with age equal to Kg is an indiscernible sequence. (shrink)

For automatic and recursive graphs, we investigate the following problems: (A) existence of a Hamiltonian path and existence of an infinite path in a tree (B) existence of an Euler path, bounding the number of ends, and bounding the number of infinite branches in a tree (C) existence of an infinite clique and an infinite version of set cover The complexity of these problems is determined for automatic graphs and, supplementing results from the literature, for recursive (...) graphs. Our results show that these problems (A) are equally complex for automatic and for recursive graphs ( $\Sigma _{1}^{1}\text{-complete}$ ), (B) are moderately less complex for automatic than for recursive graphs (complete for different levels of the arithmetic hierarchy), (C) are much simpler for automatic than for recursive graphs (decidable and $\Sigma _{1}^{1}\text{-complete}$ , resp.). (shrink)

When seeking to coordinate in a game with imperfect information, it is often relevant for a player to know what other players know. Keeping track of the information acquired in a play of infinite duration may, however, lead to infinite hierarchies of higher-order knowledge. We present a construction that makes explicit which higher-order knowledge is relevant in a game and allows us to describe a class of games that admit coordinated winning strategies with finite memory.

Let ΩΩ be the semigroup of all mappings of a countably infinite set Ω. If U and V are subsemigroups of ΩΩ, then we write U≈V if there exists a finite subset F of ΩΩ such that the subsemigroup generated by U and F equals that generated by V and F. The relative rank of U in ΩΩ is the least cardinality of a subset A of ΩΩ such that the union of U and A generates ΩΩ. In this (...) paper we study the notions of relative rank and the equivalence ≈ for semigroups of endomorphisms of binary relations on Ω.The semigroups of endomorphisms of preorders, bipartite graphs, and tolerances on Ω are shown to lie in two equivalence classes under ≈. Moreover such semigroups have relative rank 0, 1, 2, or in ΩΩ where is the minimum cardinality of a dominating family for . We give examples of preorders, bipartite graphs, and tolerances on Ω where the relative ranks of their endomorphism semigroups in ΩΩ are 0, 1, 2, and .We show that the endomorphism semigroups of graphs, in general, fall into at least four classes under ≈ and that there exist graphs where the relative rank of the endomorphism semigroup is 20. (shrink)

Generalizedn-gons are certain geometric structures (incidence geometries) that generalize the concept of projective planes (the nontrivial generalized 3-gons are exactly the projective planes).In a simplified world, every generalizedn-gon of finite Morley rank would be an algebraic one, i.e., one of the three families described in [9] for example. To our horror, John Baldwin [2], using methods discovered by Hrushovski [7], constructed ℵ1-categorical projective planes which are not algebraic. The projective planes that Baldwin constructed fail to be algebraic in a dramatic (...) way.Indeed, every algebraic projective plane over an algebraically closed field is Desarguesian [12]. In particular, an algebraically closed field (isomorphic to the base field) can be interpreted in every one of them. However, in the projective planes that Baldwin constructed, one cannot even interpret an infinite group.In this article we show that the same phenomenon occurs for the generalizedn-gons ifn≥ 3 is an odd integer. For each suchnwe constructmany nonisomorphic generalizedn-gons of finite Morley rank that do not interpret an infinite group. As one may expect, our method is inspired by Hrushovski and Baldwin, and we follow Baldwin's line of approach. Quite often our proofs are a verification of the fact that the proofs of Baldwin [2] forn= 3 carry over to an arbitrary positive odd integern(which is sometimes far from being obvious). As in [2], we begin by defining a certain collection of finite graphsK* and a binary relation ≤ on these graphs. We show that (K*, ≤) satisfies the amalgamation property. (shrink)

Given a graph G whose set of vertices is a Polish space X, the weak Borel chromatic number of G is the least size of a family of pairwise disjoint G -independent Borel sets that covers all of X. Here a set of vertices of a graph G is independent if no two vertices in the set are connected by an edge.We show that it is consistent with an arbitrarily large size of the continuum that every closed (...) class='Hi'>graph on a Polish space either has a perfect clique or has a weak Borel chromatic number of at most ℵ1. We observe that some weak version of Todorcevic's Open Coloring Axiom for closed colorings follows from MA.Slightly weaker results hold for Fσ-graphs. In particular, it is consistent with an arbitrarily large size of the continuum that every locally countable Fσ-graph has a Borel chromatic number of at most ℵ1.We refute various reasonable generalizations of these results to hypergraphs. (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)

A biologically unavoidable sequence is an infinite gender sequence which occurs in every gendered, infinite genealogical network satisfying certain tame conditions. We show that every eventually periodic sequence is biologically unavoidable (this generalizes König's Lemma), and we exhibit some biologically avoidable sequences. Finally we give an application of unavoidable sequences to cellular automata.

Let $\mathscr {C}$ be a class of finite and infinite graphs that is closed under induced subgraphs. The well-known Łoś–Tarski Theorem from classical model theory implies that $\mathscr {C}$ is definable in first-order logic by a sentence $\varphi $ if and only if $\mathscr {C}$ has a finite set of forbidden induced finite subgraphs. This result provides a powerful tool to show nontrivial characterizations of graphs of small vertex cover, of bounded tree-depth, of bounded shrub-depth, etc. in terms of (...) forbidden induced finite subgraphs. Furthermore, by the Completeness Theorem, we can compute from $\varphi $ the corresponding forbidden induced subgraphs. This machinery fails on finite graphs as shown by our results: –There is a class $\mathscr {C}$ of finite graphs that is definable in first-order logic and closed under induced subgraphs but has no finite set of forbidden induced subgraphs.–Even if we only consider classes $\mathscr {C}$ of finite graphs that can be characterized by a finite set of forbidden induced subgraphs, such a characterization cannot be computed from a first-order sentence $\varphi $ that defines $\mathscr {C}$ and the size of the characterization cannot be bounded by $f(|\varphi |)$ for any computable function f.Besides their importance in graph theory, the above results also significantly strengthen similar known theorems for arbitrary structures. (shrink)

Philosophers and social scientists have recently turned to Lewis sender–receiver games to provide an account of how lexical terms can acquire meaning through an evolutionary process. However, the evolution of meaning is contingent on both the particular sender–receiver game played and the choice of evolutionary dynamic. In this paper I explore some differences between models that presume an infinitely large and randomly mixed population and models in which a finite number of agents communicate with their neighbors in a social network. (...) My results show that communication with neighbors is more conducive to the evolution of meaning than communication with strangers. Additionally, I show that the behavior of the system is highly dependent on the topological structure of the social network. I argue that a specific class of networks—small world graphs—is especially conducive to the evolution of meaning. This is because small world graphs have a short characteristic path length while still maintaining a high degree of correlation between neighbors. Since many actual social networks, such as friendship networks and nervous systems, are conjectured to be small world structures, these results indicate that these networks are quite hospitable to the efficient evolution of meaning. (shrink)

A connected graph is called Hamilton-connected if there exists a Hamiltonian path between any pair of its vertices. Determining whether a graph is Hamilton-connected is an NP-complete problem. Hamiltonian and Hamilton-connected graphs have diverse applications in computer science and electrical engineering. The detour index of a graph is defined to be the sum of lengths of detours between all the unordered pairs of vertices. The detour index has diverse applications in chemistry. Computing the detour index for a (...) graph is also an NP-complete problem. In this paper, we study the Hamilton-connectivity of convex polytopes. We construct three infinite families of convex polytopes and show that they are Hamilton-connected. An infinite family of non-Hamilton-connected convex polytopes is also constructed, which, in turn, shows that not all convex polytopes are Hamilton-connected. By using Hamilton connectivity of these families of graphs, we compute exact analytical formulas of their detour index. (shrink)

Viewing the language of modal logic as a language for describing directed graphs, a natural type of directed graph to study modally is one where the nodes are sets and the edge relation is the subset or superset relation. A well-known example from the literature on intuitionistic logic is the class of Medvedev frames $\langle W,R\rangle$ where $W$ is the set of nonempty subsets of some nonempty finite set $S$, and $xRy$ iff $x\supseteq y$, or more liberally, where $\langle (...) W,R\rangle$ is isomorphic as a directed graph to $\langle \wp(S)\setminus\{\emptyset\},\supseteq\rangle$. Prucnal [32] proved that the modal logic of Medvedev frames is not finitely axiomatizable. Here we continue the study of Medvedev frames with extended modal languages. Our results concern definability. We show that the class of Medvedev frames is definable by a formula in the language of tense logic, i.e., with a converse modality for quantifying over supersets in Medvedev frames, extended with any one of the following standard devices: nominals (for naming nodes), a difference modality (for quantifying over those $y$ such that $x\not= y$), or a complement modality (for quantifying over those $y$ such that $x\not\supseteq y$). It follows that either the logic of Medvedev frames in one of these tense languages is finitely axiomatizable---which would answer the open question of whether Medvedev's [31] "logic of finite problems'' is decidable---or else the minimal logics in these languages extended with our defining formulas are the beginnings of infinite sequences of frame-incomplete logics. (shrink)

We prove, by a probabilistic argument, that a class of ω-categorical structures, on which algebraic closure defines a pregeometry, has the finite submodel property. This class includes any expansion of a pure set or of a vector space, projective space or affine space over a finite field such that the new relations are sufficiently independent of each other and over the original structure. In particular, the random graph belongs to this class, since it is a sufficiently independent expansion of (...) an infinite set, with no structure. The class also contains structures for which the pregeometry given by algebraic closure is non-trivial. (shrink)

A cylindric algebra atom structure is said to be strongly representable if all atomic cylindric algebras with that atom structure are representable. This is equivalent to saying that the full complex algebra of the atom structure is a representable cylindric algebra. We show that for any finite n >3, the class of all strongly representable n-dimensional cylindric algebra atom structures is not closed under ultraproducts and is therefore not elementary. Our proof is based on the following construction. From an arbitrary (...) undirected, loop-free graph Γ, we construct an n-dimensional atom structure E(Γ), and prove, for infinite Γ, that E(Γ) is a strongly representable cylindric algebra atom structure if and only if the chromatic number of Γ is infinite. A construction of Erdős shows that there are graphs (k < ω)with infinite chromatic number, but having a non-principal ultraproduct $\prod _D\Gamma _k $ whose chromatic number is just two. It follows that $E(\Gamma _k )$ is strongly representable (each k < ω) but $\Pi _D E(\Gamma _k)$ is not. (shrink)

Roy T Cook examines the Yablo paradox--a paradoxical, infinite sequence of sentences, each of which entails the falsity of all others that follow it. He focuses on questions of characterization, circularity, and generalizability, and pays special attention to the idea that it provides us with a semantic paradox that involves no circularity.

Let AC and AI denote the collections of graphs with vertex set ω and which have, respectively, no infinite independent subgraph, and no infinite complete subgraph. Both AC and AI are coanalytic sets of reals that are not analytic, and they are disjoint by Ramsey’s theorem. We prove that there exists a Borel set separating AC and AI, and we discuss the sense in which this is an infinite analogue of a weak version of.

We discuss conceptual change and progress within mathematics, in particular how tools, structural concepts and representations are transferred between fields that appear to be unconnected or remote from each other. The theoretical background is provided by the frame concept, which is used in linguistics, cognitive science and artificial intelligence to model how explicitly given information is combined with expectations deriving from background knowledge. In mathematical proofs, we distinguish two kinds of frames, namely structural frames and ontological frames. The interaction between (...) both kinds of frames can drive mathematical interpretation. We first discuss two examples where structural frames (formulaic notation) drive ontological development (the discovery or exploration of mathematical objects). The development of Boole’s Boolean algebra may at first appear as a metaphorical treatment of the (then) new area of logic. In the analysis, we discuss how different (aspects of) certain algebraic frames change in the transfer, how arising difficulties are solved and overall argue that Boole uses the numerical algebra frame as a research template for the discovery of a system for calculations in logic. Following Ifrah, we analyse the discovery of zero as an extension to the number ontology as driven by the development of notation. Both structural and ontological frames are extended and simplified as notation progresses. Finally, we discuss two examples from infinite combinatorics, viz. topological graph theory, and one foundational issue. In both examples, the two simultaneous frames about one object are maintained independently. They motivate different research questions, but may also fruitfully interact: shifting between multiple synchronously maintained perspectives acts as a motor of innovation. The analysis shows how a frame-based approach allows to model how different perspectives drive mathematical innovation because they highlight different aspects, questions and heuristics. (shrink)

Each relational structure X has an associated Gaifman graph, which endows X with the properties of a graph. If x is an element of X, let $B_n (x)$ be the ball of radius n around x. Suppose that X is infinite, connected and of bounded degree. A first-order sentence ϕ in the language of X is almost surely true (resp. a. s. false) for finite substructures of X if for every x ∈ X, the fraction of substructures (...) of $B_n (x)$ satisfying ϕ approaches 1 (resp. 0) as n approaches infinity. Suppose further that, for every finite substructure, X has a disjoint isomorphic substructure. Then every ϕ is a. s. true or a. s. false for finite substructures of X. This is one form of the geometric zero-one law. We formulate it also in a form that does not mention the ambient infinite structure. In addition, we investigate various questions related to the geometric zero-one law. (shrink)

Assuming certain conditions on a class equation image of finitely generated first-order structures admitting the model-theoretical construction of a Fraïssé limit, we characterize retracts of such limits as algebraically closed structures in a class naturally related to equation image. In this way we generalize an earlier description of retracts of the countably infinite random graph.

Ecological economics is an interdisciplinary science that is primarily concerned with developing interventions to achieve sustainable ecological and economic systems. While ecological economists have, over the last few decades, made various empirical, theoretical, and conceptual advancements, there is one concept in particular that remains subject to confusion: critical natural capital. While critical natural capital denotes parts of the environment that are essential for the continued existence of our species, the meaning of terms commonly associated with this concept, such as ‘non-substitutable’ (...) and ‘impossible to substitute,’ require a clearer formulation then they tend to receive. With the help of equations and graphs, this article develops new definite account of critical natural capital that makes explicit what it means for objective environmental conditions to be essential for continued existence. The second main part of this article turns to the question of formally modeling the priority of conserving critical natural capital. While some ecological economists have maintained that, beyond a certain threshold, critical natural capital possesses absolute infinite value, absolute infinite utility models encounter significant problems. This article shows that a relative infinite utility model provides a better way to model the priority of conserving critical natural capital. (shrink)

We consider modal logics whose intermediate fragments lie between the logic of infinite problems [20] and the Medvedev logic of finite problems [15]. There is continuum of such logics [19]. We prove that none of them is finitely axiomatizable. The proof is based on methods from [12] and makes use of some graph-theoretic constructions (operations on coverings, and colourings).

continent. 1.2 (2011): 70-75. cartography of ghosts . . . And as a way to talk . . . of temporality the topography of imagination, this body whose dirty entry into the articulation of history as rapturous becoming & unbecoming, greeted with violence, i take permission to extend this grace —Akilah Oliver from “An Arriving Guard of Angels Thusly Coming To Greet” Our disappearance is already here. —Jacques Derrida, 117 I wrestled with death as a threshold, an aporia, a bandit, (...) a part of life. —Akilah Oliver Moraine in geological lingo is that which is left behind. Moraine- a euphemism for the de-stabilizing referent of the writer-ly body as a “troubled and troubling landscape marked by cultural and historical signifiers, the body as flesh memory [...] the body as transitory” (Oliver, Author Statement). Moraine— a geological metaphor of the poet as a holder of memory, as an accumulation of rocks and debris carried along the edge, terminal, dropped at the foot of language (in language). “Flesh Memory” according to Akilah Oliver is "that which my body recalls [...] everything has to do with the task of remembrance and its narrative reinvention [...] I was always translating an idea of the world as it presented itself at any given time. To write was a choice about how to be seen, how to enter the world as translator, actor, participant, in the dialogues that apparently made the real 'real'" (Levitsky). Flesh. Memory. The stuff some poems are made from. The stuff that gets abandoned, gleaned, and picked up by more flesh and memory. "My body, my life has always felt like a kaleidoscopic rip in the dominant fabric [...] has always been a dialogue with the impossible and the apparent” (Levitsky). The impossible-body or poet's body anticipates and performs (through language) an irretrievable death. IN APORIA I realized everything I must have been doing must have been Death. It was Christmas or Labor Day—a holiday—and every time you turned on the radio they said something like ‘four million’ or ‘going to die’.” — Andy Warhol I’m trying on egos, [a justification for the planet’s continuance]. Oh hello transgressor, you’ve come to collect utilitarian debts, humbling narrative space. Give me condition and wheatgrass, I his body disintegrating. I his body is ossification. Death my habit radius, yeah yeah. I his body can’t refuse this summons. I can’t get out this fucking room. Tell me something different about torture dear Trickster. Tell me about the lightness my mother told me to pick the one i love the best how it signals everything I ever wish to believe true just holy on my ship. I jump all over this house. this is it [what I thought is thought only, nothing more deceptive than]: I his body keeps thinking someone will come along, touch me. As like human or lima bean. I’m cradling you to my breast, you are looking out. A little wooden lion you & Peter carve on Bluff Street is quieting across your cheekbone. Not at all like the kind of terror found in sleep, on trembling grounds. It is yesterday now. I have not had a chance to dance in this century. Tonight I shall kill someone, a condition to remember Sunday morning. To think of lives as repetitions [rather than singular serial incarnations]. To understand your death is as exacerbating as trying to figure out why as schoolchildren in mid-nineteen-sixties Southern California we performed reflexive motions: cutting out lace snowflakes, reading Dick and Jane search for their missing mittens, imagining snow. Disintegrat ing . The -ing gerund catapults from the non-finite verb into past, present, future. The -ing as a tail pinned to death, a dog spinning to bite and never fully reaching itself, always shy of the end, circumreferential; a double copulative: deathing. Possessively AO calls it “habit radius” (a virtual fetish attribute) or an inescapable death presence that “confronts us with the paradox of an unattainable object [...] through it’s being unattainable” (Agamben, 27). A flirtation or dialogue with an unknowable thing and aporia utilized as investigative instrument to engage (death) while (in Southern California) we “perform reflexive motions,” cut lace snowflakes, imagine snow, and pay rent like “yeah, yeah” what else is new. And this too, fiction. The book I wish to right. The restored fallen, heroic. Did you expect a different grace from the world? Or upon exit? I’m working on “tough.” They think I am already. All ready. Who is the dead person? Is "I'm sorry" real to a dead person? Browning grass. My hands on this table. A contentious century. A place to pay rent. Redemptive moments. Am I now the dead person? Dead person, dead person, will you partake in my persimmon feast? The body inside the body astounds, confesses sins of the funhouse. I too have admired the people of this planet. Their frilly, orderly intellects. The use they’ve made of cardamom, radiation as well. How they’ve pasteurized milk, loaned surnames to stars, captured tribes, diseases, streets, and ideas too. The living-body as archive: is it possible to experience the living-body as archive without a (kind of) death? Sifting the rubble, rummaging through hoarded debris, skin sheds, memory-napping, and re-awoken (in flesh and) on terrain. “An investigative poetics seeks to unravel staid communities of thought and grasp at what might always be just beyond reach; a poetics of inquiry that lies between language as meaning, and language as rapturous entry into the world of posited ideas and idealism”( Levitsky). Something snaps. Lights blow out prior to embarking upon an investigative poetics. It begins with a question (often a sexy aporia) that leads to openings. "Every politics of memory [...] implies an intervention of the state. It's a state that legislates and acts with regard to the nonfinite mass of materials to be stored, materials which must be collected, preserved” (Derrida & Stiegler, 62). It seems poetic investigation already contains the potentiality of an (invisible) archive if the writer is “always writing” especially when not. Here’s my stupid digital romantic inclination: the living-body (of a poet) is a self-sustaining archive of non-finite memories. But not even I really believe that. AO innovated and sculpted an investigative poetic praxis. In a conversation with poet Rachel Levitsky, poetic-voice is viewed not as a precious identifier, but as a means to think through/about form, concluding that form is linked to framing. While poetic-voice may have tendency to precede form, it also erupts as a result of framing techniques. “They are frames that hold the shape of thinking (which is also to say of imagining) [...].”7 This reminds me of my rabbit who symmetrically chewed the corners of his hutch, which makes me wonder if it’s an expression of the shape of some animal anxiety tick I won’t ever have access to. Beyond the form/frame, death is an unoriginal yet unique limit; death is a damn deathless thing. It functions as a source of poetic investigation; that thing always “just beyond reach.” And how is death not a fetish (in this case an obsessive reverence for something non-material)? “Insofar as it [death] is a presence, a fetish [...] it is in fact something concrete and tangible; but insofar as it is the presence of an absence, it is, at the same time, immaterial and intangible, because it alludes continuously beyond itself to something that can never really be possessed [...] The fetish is [...] a sign of an absence, it is not an unrepeatable unique object; on the contrary, it is something infinitely capable of substitution, without any successive incarnations ever succeeding in exhausting the nullity of which it is the symbol” (Agamben, 33). AO utilized absence (the absent body [catapulted by the death of a beloved]) as an apparatus to investigate. In the process of conversing with absence or that which is absent, the absent body is affectionately objectified, incessantly summonsed back to a place of recognition, of objects, a desire for the absent body to remain intact while exiting the structural limits of grammar and syntax by moving into chant forms “to say what cannot be said” (Levitsky). from AN ARRIVING GUARD OF ANGELS THUSLY COMING TO GREET dear oluchi- the light is blinking rapidly on the black boxy machine. your room seems bigger than before and i am still planning to read some of those robert jordan books of yours. yesterday at the used bookstore where i was browsing the mysteries to “stall reality” (they are really not mysteries at all, they just employ death as the plot mistress but are unable to grasp its mystery at all)—well the point is, things were calm down here for a while and the world was little. i want to be big like you. or i want you not vast, not dead, not gone, but human small and here. i am so selfish. that is what i really want. to see you again. to oil your scalp. to hear you walk in the door, say ma i’m home . give me a chance to say welcome home son. or when leaving, don’t forget your hat . what do you wear out there? i wish you could have taken your new shoes with you. i’m so proud of you. i’m sorry for the way you died. i miss you all the time. even before, i missed you. out there, one time, some different men said: “shake for me girl, i wanna be your backdoor man.” who dat you love. 5/18/03 A letter-poem in sixteen lines “dear oluchi-” is safe-housed in epistolary form. Poetic voice is rendered as internal thought meanderings, a not-so-much confession, private/(pillow?) talk in the desire to be heard/witnessed by the referent and reader with an intent to absolve. The diminutive “i” bears a relation to poet Fanny Howe’s “little g God” in that “One of the (many) things I like about little g God is that you can have a vodka tonic while you talk to little g God, sing along to Bowie’s “I’m Afraid Of Americans,” and hum Coltrane’s “A Love Supreme,” though maybe not all at the same time” (Oliver, 2009). Towards the middle of the poem AO is at a used bookstore and remarks on the funny employment of death as a ‘plot mistress’ that ‘they’ (the dubious employed mystery authors) are ‘unable to grasp’, thereby giving death a mouthpiece, a modeling job, something to do to pass the time. from THE VISIBLE UNSEEN When I first saw graffiti, I recognized in it an ugly aesthetic, a dialectics of violence, a distortion of limbs, a hieroglyph. It was only later when I read the names of the dead that I then saw the path of ghosts charted there; its narrative of loss for the visible unseen whose place in history has been fictionalized and rendered unseen under the totalizing glare of history. Inscriptions, traces, specters. Graffiti begs a public face just as ghosts require non-ghosts (humans) to sense them. The “visible unseen” is a game of hide-and-seek between public viewer and graffiti-inscriber, an ephemeral-violent aesthetic on an ephemeral-policed canvas. Graffiti-inscribers already submit to being forgotten, expect to be washed away; perhaps it’s a holy urban mandala created by gangster-type monks without Buddhism. [...] in its refusal to disappear it forces a discourse in the public imagination we are forced to see what we would rather not, to make sense of an encoded language that we cannot read on the level of meaning. it irritates, forces its agency on us, speaks outside and beyond semiotic reach. An epic font-size pervading the public’s imagination, illegible, I could just close my eyes, remain passive, drive past, abandon it beyond reach, push it further away beyond death walls. In Barcelona I watched a clean up crew wash walls with an awesome water hose but I was more intrigued by their bodies; not a distortion of limbs, not hieroglyph but also not entirely legible; the laboring body permanently erasing specters of the city, and of course they knew it was also an invitation for the ghosts to return. Graffiti is death’s little sister, is also an aporia. [...] Graffiti (fr GK -graph(os), something drawn or written, to diagram or chart) attempts to stage the impossible: to erase the essence of its own subjectivity. Graffiti is a cartography of ghosts, a mapping of elegiac rapture (the transporting of a person from one place to another, as in heaven) and rupture (the state of being broken open.) Dwelling is a fiction stasis. [...] The notion of the past as being something done with, a look-back event, inhibits the possibility of reading graffiti as rapture, as rupture. If graffiti posits history as always in the process of becoming undone. [...] Because what is the body, if not also a complex temple, an unstable site through which to negotiate subjects, materiality, economies, gods, and modes of representations? The site where we are all already belated. Graphein meaning “to write.” “Derrida says every archive makes a law, and the law of genre is its own rupture” (Bloch, 39). However, graffiti is an (non/anti)-archive of erasure due to (the politics of) washing out its subjectivity, which only adds onto (or is symptomatic of) its character. The inhibition of “reading graffiti as rapture, as rupture” is partly due to it being a “look-back” event in that it’s process involves scratching through layers to reveal previous specters underneath. Graffiti (as an ancient genre) has always been a thing of ‘becoming undone’, and therefore ‘belated and always in arrival’ (Levitsky). It’s a Dionysian activity done at night with it’s back turned toward us. "The specter [...] is of the visible, but of the invisible visible, it is the visibility of a body which is not present in flesh and blood [...] appearing for vision, to the brightness of day [...] something becomes almost visible which is visible only insofar as it is not visible in flesh and blood. It is a night visibility. As soon as there is a technology of the image, visibility brings night. It incarnates in a night body, it radiates in a night light" (Derrida & Stiegler, 115). (shrink)

We are concerned here with recursive function theory analogs of certain problems in chromatic graph theory. The motivating question for our work is: Does there exist a recursive (countably infinite) planar graph with no recursive 4-coloring? We obtain the following results: There is a 3-colorable, recursive planar graph which, for all k, has no recursive k-coloring; every decidable graph of genus p ≥ 0 has a recursive 2(χ(p) - 1)-coloring, where χ(p) is the least number (...) of colors which will suffice to color any graph of genus p; for every k ≥ 3 there is a k-colorable, decidable graph with no recursive k-coloring, and if k = 3 or if k = 4 and the 4-color conjecture fails the graph is planar; there are degree preserving correspondences between k-colorings of graphs and paths through special types of trees which yield information about the degrees of unsolvability of k-colorings of graphs. (shrink)

The connections between forms of code and coding and the many crises that currently afflict the contemporary world run deep. Code and crisis in our time mutually define, and seemingly prolong, each other in ‘infinite branching graphs’ of decision problems. There is a growing academic literature that investigates digital code and software from a wide range of perspectives –power, subjectivity, governmentality, urban life, surveillance and control, biopolitics or neoliberal capitalism. The various strands in this literature are reflected in the (...) papers that comprise this special issue. They address topics ranging from social networks, mass media, financial markets and academic plagiarism to highway engineering in relation to the dynamics and diversity of crises. Against this backdrop, the purpose of this essay is to highlight and explore some of the underlying themes connecting codes and codings and the production and apprehension of ‘crisis’. We analyse how the ever-increasing intermediation of contemporary life by codes of various kinds has been closely shadowed by a proliferation of crises. We discuss three related aspects of the coupling of code and crisis (signification, performativity and excess) running across these seemingly diverse topics. We and the other contributors in this special issue seek to go beyond the restricted (and often restricting) understanding of code as the language of machines. Rather, we view code qua programs and algorithms as epitomizing a much broader phenomenon. The codes that we live, and that we live by, also tell us about the ways in which the ‘will to power’ and the 'will to knowledge' tend to be enacted in the contemporary world. (shrink)

Limiting identification of r.e. indexes for r.e. languages and limiting identification of programs for computable functions have served as models for investigating the boundaries of learnability. Recently, a new approach to the study of "intrinsic" complexity of identification in the limit has been proposed. This approach, instead of dealing with the resource requirements of the learning algorithm, uses the notion of reducibility from recursion theory to compare and to capture the intuitive difficulty of learning various classes of concepts. Freivalds, Kinber, (...) and Smith have studied this approach for function identification and Jain and Sharma have studied it for language identification. The present paper explores the structure of these reducibilities in the context of language identification. It is shown that there is an infinite hierarchy of language classes that represent learning problems of increasing difficulty. It is also shown that the language classes in this hierarchy are incomparable, under the reductions introduced, to the collection of pattern languages. Richness of the structure of intrinsic complexity is demonstrated by proving that any finite, acyclic, directed graph can be embedded in the reducibility structure. However, it is also established that this structure is not dense. The question of embedding any infinite, acyclic, directed graph is open. (shrink)

König, D. [1926. ‘Sur les correspondances multivoques des ensembles’, Fundamenta Mathematica, 8, 114–34] includes a result subsequently called König's Infinity Lemma. Konig, D. [1927. ‘Über eine Schlussweise aus dem Endlichen ins Unendliche’, Acta Litterarum ac Scientiarum, Szeged, 3, 121–30] includes a graph theoretic formulation: an infinite, locally finite and connected graph includes an infinite path. Contemporary applications of the infinity lemma in logic frequently refer to a consequence of the infinity lemma: an infinite, locally finite (...) tree with a root has a infinite branch. This tree lemma can be traced to [Beth, E. W. 1955. ‘Semantic entailment and formal derivability’, Mededelingen der Kon. Ned. Akad. v. Wet., new series 18, 13, 309–42]. It is argued that Beth independently discovered the tree lemma in the early 1950s and that it was later recognized among logicians that Beth's result was a consequence of the infinity lemma. The equivalence of these lemmas is an easy consequence of a well known result in graph theory: every connected, locally finite graph has among its partial subgraphs a spanning tree. (shrink)