In this paper we relax the assumption that the logical constants of ordinary first-order logic be linearly ordered. As a consequence, we shall have formulas involving not only partially ordered quantifiers, but also partially ordered connectives. The resulting language, called the language of informational independence will be given an interpretation in terms of games of imperfect information. The II-logic will be seen to have some interesting properties: It is very natural to define in this logic two negations, weak negation as (...) failure to verify a sentence, and strong negation as the existence of a falsifying strategy: One can express in this logic complete problems of finite structures, like the non-connectedness and 3-colorability of finite graphs, the satisfiability problem for Boolean circuits built up from NAND-gates, etc. (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)

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)

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 recent years, the research of wavelet frames on the graph has become a hot topic in harmonic analysis. In this paper, we mainly introduce the relevant knowledge of the wavelet frames on the graph, including relevant concepts, construction methods, and related theory. Meanwhile, because the construction of graph tight framelets is closely related to the classical wavelet framelets on ℝ, we give a new construction of tight frames on ℝ. Based on the pseudosplines of type II, (...) we derive an MRA tight wavelet frame with three generators ψ 1, ψ 2, and ψ 3 using the oblique extension principle, which generate a tight wavelet frame in L 2 ℝ. We analyze that three wavelet functions have the highest possible order of vanishing moments, which matches the order of the approximation order of the framelet system provided by the refinable function. Moreover, we introduce the construction of the Haar basis for a chain and analyze the global orthogonal bases on a graph G. Based on the sequence of framelet generators in L 2 ℝ and the Haar basis for a coarse-grained chain, the decimated tight framelets on graphs can be constructed. Finally, we analyze the detailed construction process of the wavelet frame on a graph. (shrink)

We classify countable metrically homogeneous graphs of diameter 3.

The primary objective of this study was to propose a functional discrete mathematical model for analyzing folklore fairy tales. Within this model, characters are denoted as vertices, and explicit instances of communication – both verbal and non-verbal – within the text are depicted as edges. Upon examining a corpus of Eastern Slavic fairy tales in comparison to Chukchi fairy tales, unforeseen outcomes emerged. Notably, the constructed models seem to evade establishing certain connections between characters. Consequently, instances where the interactions among (...) fairy tale characters would result in a non-planar graph structure are notably absent. To put it differently, the models refrain from incorporating sub-graphs delineated by the Kuratowski theorem governing planar graphs, specifically the minimal non-planar graphs Κ5 and Κ3,3. Remarkably, even in more extensive texts featuring a larger cast of characters, connections that would yield a non-planar graph pattern are consistently avoided. This leads to the formulation of a hypothesis positing that traditional folk tales adhere to a “planar narrative” design – an identifiable narrative variant characterized by inherent limitations in complexity. This design, in turn, appears deeply entrenched within the societal framework of the cultures that produced these folk narratives. (shrink)

Several religious traditions of South Asia understand that mental activities produce colors (leśyās) that are associated with the mind or with the soul itself. In Jain texts, there are three theories about how leśyās are produced: that leśyās are a product (parināma) (1) of the passions (kasāyas), (2) of vibrations of the soul (yoga), and (3) of all eight varieties of karmas. The views of various Śvetāmbara and Digambara commentators regarding leśyās are compared.

Lachlan and Woodrow have completly classified the countable ultrahomogeneous graphs. We expand the language of graphs to include a new unary predicate. In this expanded language, ultrahomogeneous vertex 2-colorings of ultrahomogeneous graphs are classified.

Given a graph G, we say that a subset D of the vertex set V is a dominating set if it is near all the vertices, in that every vertex outside of D is adjacent to a vertex in D. A domatic k-partition of G is a partition of V into k dominating sets. In this paper, we will consider issues of computability related to domatic partitions of computable graphs. Our investigation will center on answering two types of questions (...) for the case when k = 3. First, if domatic 3-partitions exist in a computable graph, how complicated can they be? Second, a decision problem: given a graph, how difficult is it to decide whether it has a domatic 3-partition? We will completely classify this decision problem for highly computable graphs, locally finite computable graphs, and computable graphs in general. Specifically, we show the decision problems for these kinds of graphs to be ${\Pi^{0}_{1}}$ -, ${\Pi^{0}_{2}}$ -, and ${\Sigma^{1}_{1}}$ -complete, respectively. (shrink)

The problem of when a recursive graph has a recursive k-coloring has been extensively studied by Bean, Schmerl, Kierstead, Remmel, and others. In this paper, we study the polynomial time analogue of that problem. We develop a number of negative and positive results about colorings of polynomial time graphs. For example, we show that for any recursive graph G and for any k, there is a polynomial time graph G′ whose vertex set is {0,1}* such that there (...) is an effective degree preserving correspondence between the set of k-colorings of G and the set of k-colorings of G′ and hence there are many examples of k-colorable polynomial time graphs with no recursive k-colorings. Moreover, even though every connected 2-colorable recursive graph is recursively 2-colorable, there are connected 2-colorable polynomial time graphs which have no primitive recursive 2-coloring. We also give some sufficient conditions which will guarantee that a polynomial time graph has a polynomial time or exponential time coloring. (shrink)

The purpose is to study the strength of Ramsey’s Theorem for pairs restricted to recursive assignments ofk-many colors, with respect to Intuitionistic Heyting Arithmetic. We prove that for every natural number$k \ge 2$, Ramsey’s Theorem for pairs and recursive assignments ofkcolors is equivalent to the Limited Lesser Principle of Omniscience for${\rm{\Sigma }}_3^0$formulas over Heyting Arithmetic. Alternatively, the same theorem over intuitionistic arithmetic is equivalent to: for every recursively enumerable infinitek-ary tree there is some$i < k$and some branch with infinitely many (...) children of indexi. (shrink)

We classify countable metrically homogeneous graphs of diameter 3.

We make comments on some problems Erdős and Hajnal posed in their famous problem list. Let X be a graph on $\omega _1$ with the property that every uncountable set A of vertices contains a finite set s such that each element of $A-s$ is joined to one of the elements of s. Does then X contain an uncountable clique? We prove that both the statement and its negation are consistent. Do there exist circuitfree graphs $\{X_n:n<\omega \}$ on $\omega (...) _1$ such that if $A\in [\omega _1]^{\aleph _1}$, then $\{n<\omega :X_n\cap [A]^2=\emptyset \}$ is finite? We show that the answer is yes under CH, and no under Martin’s axiom. Does there exist $F:[\omega _1]^2\to 3$ with all three colors appearing in every uncountable set, and with no triangle of three colors. We give a different proof of Todorcevic’ theorem that the existence of a $\kappa $ -Suslin tree gives $F:[\kappa ]^2\to \kappa $ establishing $\kappa \not \to [\kappa ]^2_{\kappa }$ with no three-colored triangles. This statement in turn implies the existence of a $\kappa $ -Aronszajn tree. (shrink)

We study the proof-theoretic strength and effective content of the infinite form of Ramsey's theorem for pairs. Let RT n k denote Ramsey's theorem for k-colorings of n-element sets, and let RT $^n_{ denote (∀ k)RT n k . Our main result on computability is: For any n ≥ 2 and any computable (recursive) k-coloring of the n-element sets of natural numbers, there is an infinite homogeneous set X with X'' ≤ T 0 (n) . Let IΣ n and BΣ (...) n denote the Σ n induction and bounding schemes, respectively. Adapting the case n = 2 of the above result (where X is low 2 ) to models of arithmetic enables us to show that RCA 0 + IΣ 2 + RT 2 2 is conservative over RCA 0 + IΣ 2 for Π 1 1 statements and that $RCA_0 + I\Sigma_3 + RT^2_{ , is Π 1 1 -conservative over RCA 0 + IΣ 3 . It follows that RCA 0 + RT 2 2 does not imply BΣ 3 . In contrast, J. Hirst showed that $RCA_0 + RT^2_{ does imply BΣ 3 , and we include a proof of a slightly strengthened version of this result. It follows that $RT^2_{ is strictly stronger than RT 2 2 over RCA 0. (shrink)

Fix an integer $r \ge 3$. We consider metric spaces on n points such that the distance between any two points lies in $\left\{ {1, \ldots,r} \right\}$. Our main result describes their approximate structure for large n. As a consequence, we show that the number of these metric spaces is $\left\lceil {{{r + 1} \over 2}} \right\rceil ^{\left + o\left}.$Related results in the continuous setting have recently been proved by Kozma, Meyerovitch, Peled, and Samotij [34]. When r is even, our (...) structural characterization is more precise and implies that almost all such metric spaces have all distances at least $r/2$. As an easy consequence, when r is even, we improve the error term above from $o\left$ to $o\left$, and also show a labeled first-order 0-1 law in the language ${\cal L}_r $, consisting of r binary relations, one for each element of $[r]$. In particular, we show the almost sure theory T is the theory of the Fraïssé limit of the class of all finite simple complete edge-colored graphs with edge colors in $\left\{ {r/2, \ldots,r} \right\}$.Our work can be viewed as an extension of a long line of research in extremal combinatorics to the colored setting, as well as an addition to the collection of known structures that admit logical 0-1 laws. (shrink)

LetT be a universal theory of graphs such that Mod(T) is closed under disjoint unions. Letℳ T be a disjoint union ℳ i such that eachℳ i is a finite model ofT and every finite isomorphism type in Mod(T) is represented in{ℳ i ∶i<Ω3}. We investigate under what conditions onT, Th(ℳ T ) is a coinductive theory, where a theory is called coinductive if it can be axiomatizated by ∃∀-sentences. We also characterize coinductive graphs which have quantifier-free rank 1.

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)

We investigate the definability in monadic ∑11 and monadic Π11 of the problems REGk, of whether there is a regular subgraph of degree k in some given graph, and XREGk, of whether, for a given rooted graph, there is a regular subgraph of degree k in which the root has degree k, and their restrictions to graphs in which every vertex has degree at most k, namely REGkk and XREGkk, respectively, for k ≥ 2 . Our motivation partly (...) stems from the fact that REGkk and XREGkk are logspace equivalent to CONN and REACH, respectively, for k ≥ 3, where CONN is the problem of whether a given graph is connected and REACH is the problem of whether a given graph has a path joining two given vertices. We use monadic first - order reductions, monadic ∑11 games and a recent technique due to Fagin, Stockmeyer and Vardi to almost completely classify whether these problems are definable in monadic ∑11 and monadic Π11, and we compare the definability of these problems. (shrink)

In lieu of an abstract, here is a brief excerpt of the content:424 CAN HUME'S USE OF A SIMPLE/COMPLEX DISTINCTION BE MADE CONSISTENT? There is little doubt that Hume equivocates on the distinction between simple and complex impressions and ideas. Sometimes he identifies properties such as colors and shapes as simples. This is what he does, in fact, when he first introduces the distinction: Simple perceptions or impressions and ideas are such as admit of no distinction nor separation. The complex (...) are the contrary to these, and may be distinguished into parts. Tho' a particular colour, taste, and smell are qualities all united together in this apple, 'tis easy to perceive they are not the same, but are at least distinguishable from each other. Later, however, Hume speaks of simples not as qualities (or, of course, as substances) but as objects, i.e., things with properties: it is not red and round that are the simples but the red, round spot. He says, for example: Before I leave this subject I shall employ the same principles to explain that distinction of reason, which is so much talk'd of, and is so little understood, in the schools. Of this kind is the distinction betwixt figure and the body figur'd; motion and the body mov'd. The difficulty of explaining this distinction arises from the principle above explain'd, that all ideas, which are different, are separable. For it follows from thence, that if the figure be different from the body, their ideas must be separable as well as distinguishable; if they be not different, their ideas can neither be separable nor distinguishable (T 2425 ). 425 A genuine inconsistency with regard to the simple/complex distinction would have far reaching implications for Hume's system. Even the question concerning his understanding of necessity may be affected. It has been argued, for example, that what Hume believes separates the philosophical relations that are necessary from those that are not is that the former are internal relations. The suggestion is that the doctrine of internal relations, which is inextricably tied to a specific characterization of a simple/complex distinction, provides the essential contrast Hume needs for his ultimate denial that the causal relation is necessary. The consequences are compounded if we also take Robinson to be right in his attempt to reconcile Hume's 'conflicting' statements about causation in terms of the distinction between the natural and philosophical relations. While it is pointless to deny the ambiguity just set out (and, of course, one must remain constantly watchful to determine how Hume is employing the simple/complex distinction in a particular case), I believe a reconciliation of the two positions is still possible and that there is no genuine contradiction in Hume's system over this issue. The principle shift occurs between the distinction presented in logical terms and its presentation in psychological terms. In the latter instance what Hume seems to be worried about is Platonism: a metaphysics that countenances the existence of unexemplif ied qualities. This is most evident in the passage above where Hume, in effect, makes the following argument: if it were the case that (1) what is distinguishable in thought is separable in reality; and (2) figure and body are 426 distinguishable in thought; then it would follow that (3) figure and body are separable in reality. However, (3), i.e., Platonism, is false. But then so must be (2). Hume never deviates from this conclusion and its implications for his model of thought throughout the Treatise. It is this argument, for example, which became the basis for Hume's accusation against Locke's theory of abstraction and the foundation of his own view. So far Hume has it that neither thought nor experience present us with colors and shapes in isolation. This is his psychological point. Yet that need not be seen as conclusive with regard to what is to count as a logical simple. Building on his notion of a distinction of reason, Hume says: Thus when a globe of white marble is presented, we receive only the impression of a white colour dispos 'd in a certain form, nor are we able to separate and distinguish the colour from the form. But observing afterwards... (shrink)

: According to a consensus of psycho-physiological and philosophical theories, color sensations (or qualia) are generated in a cerebral "space" fed from photon-photoreceptor interaction (producing "metamers") in the retina of the eye. The resulting "space" has three dimensions: hue (or chroma), saturation (or "purity"), and brightness (lightness, value or intensity) and (in some versions) is further structured by primitive or landmark "colors"—usually four, or six (when white and black are added to red, yellow, green and blue). It has also been (...) proposed that there are eleven semantic universals—labeling the previous six plus the "intermediaries" of orange, pink, brown, purple, and gray. There are many versions of this consensus, but they all aim to provide ontological, epistemological and semantic blueprints for the brute fact of the reality of color ordained by Nature (evolution). In contrast to this consensus, we have argued that "seeing color" is not a matter of light waves impacting on our eyes, producing sensations to be categorized and labeled in the "color space" in the brain. While electrochemical events may unproblematically be regarded as the causal precondition for seeing color, the reception of sensations in "the color space" as semantically labeled natural categories, kinds, or information, is a "just so" story: it is Wittgenstein's beetle in a box. In contrast we consider that the authority of this consensus might better be regarded not as the result of the truth-tracking of nature, but as the sociohistorical outcome of philosophical presuppositions, scientific theories, experimental practices, technological apparatus, and their feed forward into the lifeworld. The question we shall therefore explore is whether, or to what extent, we ourselves are changed, as the conditions of production of color science change. Thus we are doing a kind of anthropology at two levels: of color science itself (and its effect on our own lifeworld), and of those studied by the "anthropology of color". As befits this stance we are agnostic about the theoretical entities of color science (cf. van Fraassen 2001), and within this new context, we propose to cross-cut object-and-subject, organism-and-environment (the bedrock of color science) in socio-historical ways. Our approach is in part inspired by, but not the same as, that of Gibson, in that we wish to pursue the notion of "social affordances" (Burmudez 1995). We suggest that color has become a naturalization through science-based technologies, which, through praxes and materializations, have become the perceptual and cultural entities that structure experience and understanding in the lifeworld. It is this naturalization that we shall refer to and characterize as "the historically inflected exosomatic organ". Consequently we shall explore the historical ontology of "color" without assuming an underlying biological constant (Dupré 2001). In part 1 we show the flimsiness of the evidence for the three dimensions of color, borrowed from physics, and fine-tuned to a "standard observer" (a "spectral creature" with a phenomenal "color space"). In part 2 we address the structuring of hue through the development of color circles and color spaces. This is followed by a review of the evidence for unique hues. Again the evidence is shown to be flimsy. We then show that an isolated domain of color is a particular kind of model, not a "natural given". In part 3, after reviewing what is referred to as "the isomorphy thesis," we discuss the exemplary case study of Berlin and Kay (1969). This illustrates the pull of stadial models presupposed by their evolutionary theory of color language. The Berlin and Kay paradigm proposes that American English color terms are incorrigible and can provide the universal metalanguage. We conclude by presenting an alternative account, namely that we ourselves are changed as the conditions of production of color science change. We argue that it is better to regard "seeing-color" as a historically inflected exosomatic organ that provides social affordances for those trained to grasp them. (shrink)

We provide here irrefutable facts that prove the falsehood of the claims published in [1] by Dehmer and Mowshowitz (DM) against our paper published in [2]. We first prove that Dehmer’s definition of node probability [3] is flawed. In addition, we show that it was not Dehmer in [3] who proposed this definition for the first time. We continue by proving how the use of Dehmer’s definition does not reveal all the physico-mathematical richness of the walk entropy of graphs. Finally, (...) we show a few facts about the failure of DM themselves to cite properly the relevant literature in their field. We also show here how the Editors of Complexity have failed to manage the publication of [1] in an appropriate way according to the accepted guidelines given in the Code of Conduct and Best Practice Guidelines for Journal Editors, published by the Committee on Publication Ethics (COPE). (shrink)

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.

Classic voltaic batteries of the silver/zinc and copper/zinc types are the ancestors of today's primary cells, and facilitated the development of many aspects of electrical technology. Nevertheless, they appear never to have been studied and evaluated in a quantitative manner, with results recorded in terms of volts, amps, ohms, and watts. Research of this nature is reported here, and has been conducted for the most part with copper/zinc cells. Log–log graphs of voltage versus load and current, and power versus load, (...) are presented for many electrolyte systems. It has been shown that, although the textbook electrolyte of dilute sulphuric acid does work, it is an order of magnitude inferior to a solution containing some additional nitric acid. The latter diminishes the current‐limiting phenomenon of polarization, and was in fact used by Davy, Faraday, and other early investigators. A quantitative consideration of Nicholson and Carlisle's discovery of the electrolysis of water with a silver/zinc voltaic pile is followed by examination of the electrolysis of pure water, trough batteries, and Davy's isolation of potassium and sodium. Every battery gives maximum power when its resistance is adjusted to match the resistance of the load: the maximum output of the ‘Great Battery’ of the Royal Institution is assessed at no more than 3 kW. The paper concludes with a note on the recognized hazard of long‐term exposure to mercury vapour and its possible relevance to the health of Michael Faraday. (shrink)

Improving a theorem of Gasarch and Hirst, we prove that if 2 ≤ k ≤ m < ω, then the following is equivalent to WKL0 over RCA0 Every locally k-colorable graph is m-colorable.

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)

A graph-theoretic account of logics is explored based on the general notion of m-graph (that is, a graph where each edge can have a finite sequence of nodes as source). Signatures, interpretation structures and deduction systems are seen as m-graphs. After defining a category freely generated by a m-graph, formulas and expressions in general can be seen as morphisms. Moreover, derivations involving rule instantiation are also morphisms. Soundness and completeness theorems are proved. As a consequence of (...) the generality of the approach our results apply to very different logics encompassing, among others, substructural logics as well as logics with nondeterministic semantics, and subsume all logics endowed with an algebraic semantics. (shrink)

The sensory colors that figure in visual perceptual experience are either properties of the object of consciousness (naïve realism, sense-data theory), or properties of the subject of consciousness (adverbialism) (Section 1). I consider an argument suggested by the work of A. D. Smith that the existence of certain kinds of perceptual constancies shows that adverbialism is correct, for only adverbialism can account for such constancies (Section 3). I respond on behalf of the naïve realist that naïve realism is compatible with (...) the existence of such constancies, so long as naïve realism adopts the view that sensory colors are relational properties of physical objects, not intrinsic properties (Section 4). In other words, the naïve realist should adopt the theory of appearing (Section 5). (shrink)

The classical Halpern–Läuchli theorem states that for any finite coloring of a finite product of finitely branching perfect trees of height ω, there exist strong subtrees sharing the same level set such that tuples in the product of the strong subtrees consisting of elements lying on the same level get the same color. Relative to large cardinals, we establish the consistency of a tail cone version of the Halpern–Läuchli theorem at a large cardinal (see Theorem 3.1), which, roughly speaking, deals (...) with many colorings simultaneously and diagonally. Among other applications, we generalize a polarized partition relation on rational numbers due to Laver and Galvin to one on linear orders of larger saturation. (shrink)

We consider a class of graphs embedded in $R^2$ as noncommutative proof-nets with an explicit exchange rule. We give two characterization of such proof-nets, one representing proof-nets as CW-complexes in a two-dimensional disc, the other extending a characterization by Asperti. As a corollary, we obtain that the test of correctness in the case of planar graphs is linear in the size of the data. Braided proof-nets are proof-nets for multiplicative linear logic with Mix embedded in $R^3$ . In order to (...) prove the cut-elimination theorem, we consider proof-nets in $R^2$ as projections of braided proof-nets under regular isotopy. (shrink)

Some colors are compound colors, in the sense that they look complex: orange, violet, green..., by contrast to elemental colors like yellow or blue. In the chapter 3 of his Unterschungen zur Sinnespsychologie, Brentano purports to reconcile the claim that some colors are indeed intrinsically composed of others, with the claim that colors are impenetrable with respect to each other. His solution: phenomenal green is like a chessboard of blue and yellow squares. Only, such squares are so small that we (...) cannot discriminate between their location in perception. Consequently we get the impression of an homogeneous green extent. After having presented Brentano's solution, we argued that it is hardly compatible with Brentano's own conception of descriptive psychology, to the extent that it introduces in-existent objects (small yellow and blue squares), which cannot be perceived. We propose another solution to Brentano's puzzle, more in tune with his own assumptions, or so we argue. According to it, the yellow and the blue are in the green without being spatially in the green. A green extent has yellow and blue components, but these are not spatial components. This solution reconciles impenetrability (since the component colors are not localized) with the reality of compounds color. Besides, it has the advantage of taking the phenomenology of compounds colors, as Brentano's describes it, to the letter. Compound colors are what they seem: complex but not spatially complex. (shrink)

Let’s say that a philosophical theory is white just in case it treats the perspective of the white (perhaps Western male) as objective.1 The potential dangers of proposing or defending white theories are two-fold. First, if not all of reality is objective, a fact which I take to be established beyond doubt,2 then white theories could well turn out to be false.3 A white theory is unwarranted (and indeed false) when it treats nonobjective reality as objective. Second, by proposing or (...) defending unwarranted white theories one thereby treats the perspective of the non-white as faulty, and this in turn serves to perpetuate the distorted representation of whites as superior to non-whites. As David Owen puts it, [whiteness] serves to underwrite perceptions, understandings, justifications and explanations of the social order that perpetuate distortions in the social system that are a legacy of our nation’s history …what is associated with whiteness becomes defined as natural, normal or mainstream.4 In this chapter I will focus on a particular class of philosophical theories, viz. philosophical theories of color. I argue that realist theories of the objectivist variety.. (shrink)

What we observe, through our usually limited lens, is that differential growing of space determines forms -characterized by their shape, size and coloration. As non-Euclidean geometrical mathematics have proclaimed: forms are manifestations of the curvature of space. Physics and other natural laws impose mathematical structural restrictions to biological forms. The molecules comprising any living form become arranged in specific ways in response to physical forces as well as chemical and biochemical conditions. Over time, such forms inherit additional historical restrictions that (...) make up their meaning, their semiotics. Color does not escape from this orthogenic reality. In this study, we present the colored pattern of the connexivum of Triatoma maculata, an insect vector of the etiologic agent of Chagas disease. This model is used as an example to appreciate mimicry under a heterodox and provocative approach. We unveil that beyond 1) mathematical and 2) historical semiotic restrictions of T. maculata mimesis of a yellowish-black alternating pattern, there are also 3) artistic interpretations; where metaphysics of life, beyond human perspective, is included. (shrink)

For n≥3, define Tn to be the theory of the generic Kn-free graph, where Kn is the complete graph on n vertices. We prove a graph-theoretic characterization of dividing in Tn and use it to show that forking and dividing are the same for complete types. We then give an example of a forking and nondividing formula. Altogether, Tn provides a counterexample to a question of Chernikov and Kaplan.

A function is diagonally non-computable if it diagonalizes against the universal partial computable function. D.n.c. functions play a central role in algorithmic randomness and reverse mathematics. Flood and Towsner asked for which functions h, the principle stating the existence of an h-bounded d.n.c. function implies Ramsey-type weak König’s lemma. In this paper, we prove that for every computable order h, there exists an ω\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\omega}$$\end{document} -model of h-DNR which is not a not (...) model of the Ramsey-type graph coloring principle for two colors and therefore not a model of RWKL. The proof combines bushy tree forcing and a technique introduced by Lerman, Solomon and Towsner to transform a computable non-reducibility into a separation over ω\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\omega}$$\end{document} -models. (shrink)

We propose a couple of general ways of constructing authentication schemes from actions of a semigroup on a set, without exploiting any specific algebraic properties of the set acted upon. Then we give several concrete realizations of this general idea, and in particular, we describe several authentication schemes with long-term private keys where forgery is NP-hard. Computationally hard problems that can be employed in these realizations include the Graph Colorability problem, the Diophantine problem, and many others.

This note is part of the implementation of a programme in foundations of mathematics to find exact threshold versions of all mathematical unprovability results known so far, a programme initiated by Weiermann. Here we find the exact versions of unprovability of the finite graph minor theorem with growth rate condition restricted to planar graphs, connected planar graphs and graphs embeddable into a given surface, assuming an unproved conjecture : ‘there is a number a>0 such that for all k≥3, and (...) all n≥1, the proportion of connected graphs among unlabelled planar graphs of size n omitting the k-element circle as minor is greater than a’. Let γ be the unlabelled planar growth constant . Let P be the following first-order arithmetical statement with real parameter c: “for every K there is N such that whenever G1,G2,…,GN are unlabelled planar graphs with Gigraph minor theorem. (shrink)

The ventricular pressure profile is characteristic of the cardiac contraction progress and is useful to evaluate the cardiac performance. In this contribution, a tissue-level electromechanical model of the left ventricle is proposed, to assist the interpretation of left ventricular pressure waveforms. The left ventricle has been modeled as an ellipsoid composed of twelve mechano-hydraulic sub-systems. The asynchronous contraction of these twelve myocardial segments has been represented in order to reproduce a realistic pressure profiles. To take into account the different energy (...) domains involved, the tissue-level scale and to facilitate the building of a modular model, multiple formalisms have been used: Bond Graph formalism for the mechano-hydraulic aspects and cellular automata for the electrical activation. An experimental protocol has been defined to acquire ventricular pressure signals from three pigs, with different afterload conditions. Evolutionary Algorithms have been used to identify the model parameters in order to minimize the error between experimental and simulated ventricular pressure signals. Simulation results show that the model is able to reproduce experimental ventricular pressure. In addition, electro-mechanical activation times have been determined in the identification process. For example, the maximum electrical activation time is reached, respectively, 96.5, 139.3 and 131.5 ms for the first, second, and third pigs. These preliminary results are encouraging for the application of the model on non-invasive data like ECG, arterial pressure or myocardial strain. (shrink)

The ventricular pressure profile is characteristic of the cardiac contraction progress and is useful to evaluate the cardiac performance. In this contribution, a tissue-level electromechanical model of the left ventricle is proposed, to assist the interpretation of left ventricular pressure waveforms. The left ventricle has been modeled as an ellipsoid composed of twelve mechano-hydraulic sub-systems. The asynchronous contraction of these twelve myocardial segments has been represented in order to reproduce a realistic pressure profiles. To take into account the different energy (...) domains involved, the tissue-level scale and to facilitate the building of a modular model, multiple formalisms have been used: Bond Graph formalism for the mechano-hydraulic aspects and cellular automata for the electrical activation. An experimental protocol has been defined to acquire ventricular pressure signals from three pigs, with different afterload conditions. Evolutionary Algorithms have been used to identify the model parameters in order to minimize the error between experimental and simulated ventricular pressure signals. Simulation results show that the model is able to reproduce experimental ventricular pressure. In addition, electro-mechanical activation times have been determined in the identification process. For example, the maximum electrical activation time is reached, respectively, 96.5, 139.3 and 131.5 ms for the first, second, and third pigs. These preliminary results are encouraging for the application of the model on non-invasive data like ECG, arterial pressure or myocardial strain. (shrink)

The relationship of Grundy and chromatic numbers of graphs in the context of Reverse Mathematics is investi-gated.

Countable homogeneous relational structures have been studied by many people. One area of focus is the Ramsey theory of such structures. After a review of background material, a partition theorem of Laflamme, Sauer, and Vuksanovic for countable homogeneous binary relational structures is discussed with a focus on the size of the set of unavoidable colors.

The authors consider reflexive games that describe the interaction of subjects making decisions based on an awareness structure, i.e., a hierarchy of beliefs about essential parameters, beliefs about beliefs, and so on. It was shown that the language of graphs of reflexive games represents a convenient uniform description method for reflexion effects in bélles-léttres.

Three studies were conducted to examine the relation of spatial visualization to solving kinematics problems that involved either predicting the two‐dimensional motion of an object, translating from one frame of reference to another, or interpreting kinematics graphs. In Study 1, 60 physics‐naíve students were administered kinematics problems and spatial visualization ability tests. In Study 2, 17 (8 high‐ and 9 low‐spatial ability) additional students completed think‐aloud protocols while they solved the kinematics problems. In Study 3, the eye movements of fifteen (...) (9 high‐ and 6 low‐spatial ability) students were recorded while the students solved kinematics problems. In contrast to high‐spatial students, most low‐spatial students did not combine two motion vectors, were unable to switch frames of reference, and tended to interpret graphs literally. The results of the study suggest an important relationship between spatial visualization ability and solving kinematics problems with multiple spatial parameters. (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)