Digraph games are cooperative TU-games associated to domination structures which can be modeled by directed graphs. Examples come from sports competitions or from simple majority win digraphs corresponding to preference profiles in social choice theory. The Shapley value, core, marginal vectors and selectope vectors of digraph games are characterized in terms of so-called simple score vectors. A general characterization of the class of (almost positive) TU-games where each selectope vector is a marginal vector is provided in terms of game (...) semi-circuits. Finally, applications to the ranking of teams in sports competitions and of alternatives in social choice theory are discussed. (shrink)

Digraph games are cooperative TU-games associated to domination structures which can be modeled by directed graphs. Examples come from sports competitions or from simple majority win digraphs corresponding to preference profiles in social choice theory. The Shapley value, core, marginal vectors and selectope vectors of digraph games are characterized in terms of so-called simple score vectors. A general characterization of the class of (almost positive) TU-games where each selectope vector is a marginal vector is provided in terms of game (...) semi-circuits. Finally, applications to the ranking of teams in sports competitions and of alternatives in social choice theory are discussed. (shrink)

The unwinding that Cook, 767–774 2004) proposed is a simple but powerful method of generating new paradoxes from known ones. This paper extends Cook’s unwinding to a larger class of paradoxes and studies further the basic properties of the unwinding. The unwinding we study is a procedure, by which when inputting a Boolean modal net together with a definable digraph, we get a set of sentences in which we have a ‘counterpart’ for each sentence of the Boolean modal net and (...) each point of the digraph. What is more, whenever a sentence of the Boolean modal net says another sentence is necessary, then the counterpart of the first sentence at a point correspondingly says the counterparts of the second one at all accessible points of that point are all true. The output of the procedure is called ‘the unwinding of a Boolean modal net on a definable digraph’. We prove that the unwinding procedure preserves paradoxicality: a Boolean modal net is paradoxical on a definable digraph, iff the unwinding of it on this digraph is also paradoxical. Besides, the dependence digraph for the unwinding of a Boolean modal net on a definable digraph is proved to be isomorphic to the unwinding of the dependence digraph for the Boolean modal net on the previous definable digraph. So the unwinding of a Boolean modal net on a digraph is self-referential, iff the Boolean modal net is self-referential and the digraph is cyclic. Thus, on the one hand, the unwinding of any Boolean modal net on an acyclic digraph is non-self-referential. In particular, the unwinding of any Boolean modal net on \ is non-self-referential. On the other hand, if a Boolean modal net is paradoxical on a locally finite digraph, the unwinding of it on that digraph must be self-referential. Hence, starting from a Boolean modal paradox, the unwinding can output a non-self-referential paradox only if the digraph is not locally finite. (shrink)

We introduce values for rooted-tree and sink-tree digraph games axiomatically and provide their explicit formula representation. These values may be considered as natural extensions of the lower equivalent and upper equivalent solutions for line-graph games studied in van den Brink et al. (Econ Theory 33:349–349, 2007). We study the distribution of Harsanyi dividends. We show that the problem of sharing a river with a delta or with multiple sources among different agents located at different levels along the riverbed can be (...) embedded into the framework of a rooted-tree or sink-tree digraph game correspondingly. (shrink)

Given two structures${\cal M}$and${\cal N}$on the same domain, we say that${\cal N}$is a reduct of${\cal M}$if all$\emptyset$-definable relations of${\cal N}$are$\emptyset$-definable in${\cal M}$. In this article the reducts of the Henson digraphs are classified. Henson digraphs are homogeneous countable digraphs that omit some set of finite tournaments. As the Henson digraphs are${\aleph _0}$-categorical, determining their reducts is equivalent to determining the closed supergroupsG≤ Sym of their automorphism groups.A consequence of the classification is that there are${2^{{\aleph _0}}}$pairwise noninterdefinable (...) Henson digraphs which have no proper nontrivial reducts. Taking their automorphisms groups gives a positive answer to a question of Macpherson that asked if there are${2^{{\aleph _0}}}$pairwise nonconjugate maximal-closed subgroups of Sym. By the reconstruction results of Rubin, these groups are also nonisomorphic as abstract groups. (shrink)

Classical logic, of first or higher order, is extended with sentential operators and quantifiers, interpreted substitutionally over unrestricted substitution class. Operators mark a single layered, consistent metalanguage. Self-reference, arising from substitutional quantification over sentences, allows to express paradoxes which, unlike contradictions, do not lead to explosion. Semantics of the resulting language, using semi-kernels of digraphs, is non-explosive yet two-valued and has classical semantics as a special case for clasically consistent theories. A complete reasoning is obtained by extending LK with (...) two rules for sentential quantifiers. Adding (cut) yields a complete system for the explosive semantics. (shrink)

Different characterizations of classes of shift dynamical systems via labeled digraphs, languages, and sets of forbidden words are investigated. The corresponding naming systems are analyzed according to reducibility and particularly with regard to the computability of the topological entropy relative to the presented naming systems. It turns out that all examined natural representations separate into two equivalence classes and that the topological entropy is not computable in general with respect to the defined natural representations. However, if a specific labeled (...) digraph representation - namely primitive, right-resolving labeled digraphs - of some class of shifts is considered, namely the shifts having the specification property, then the topological entropy gets computable. (shrink)

It is known that peer group games are a special class of games with a permission structure. However, peer group games are also a special class of digraph games. To be specific, they are digraph games in which the digraph is the transitive closure of a rooted tree. In this paper we first argue that some known results on solutions for peer group games hold more general for digraph games. Second, we generalize both digraph games as well as games with (...) a permission structure into a model called games with a local permission structure, where every player needs permission from its predecessors only to generate worth, but does not need its predecessors to give permission to its own successors. We introduce and axiomatize a Shapley value-type solution for these games, generalizing the conjunctive permission value for games with a permission structure and the β\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta $$\end{document}-measure for weighted digraphs. (shrink)

For digraphs G, we write V(G) for the set of all vertices of G, and E(G) for the set of all edges of G. A digraph on a set E is a digraph G where V(G) = E.

Digraphs provide an alternative syntax for propositional logic, with digraph kernels corresponding to classical models. Semikernels generalize kernels and we identify a subset of well-behaved semikernels that provides nontrivial models for inconsistent theories, specializing to the classical semantics for the consistent ones. Direct reasoning with classical resolution is sound and complete for this semantics, when augmented with a specific weakening which, in particular, excludes Ex Falso. Dropping all forms of weakening yields reasoning which also avoids typical fallacies of relevance.

Digraphs provide an alternative syntax for propositional logic, with digraph kernels corresponding to classical models. Semikernels generalize kernels and we identify a subset of well-behaved semikernels that provides nontrivial models for inconsistent theories, specializing to the classical semantics for the consistent ones. Direct (instead of refutational) reasoning with classical resolution is sound and complete for this semantics, when augmented with a specific weakening which, in particular, excludes Ex Falso. Dropping all forms of weakening yields reasoning which also avoids typical (...) fallacies of relevance. (shrink)

We deal with the ranking problem of the nodes in a directed graph. The bilateral relationships specified by a directed graph may reflect the outcomes of a sport competition, the mutual reference structure between websites, or a group preference structure over alternatives. We introduce a class of scoring methods for directed graphs, indexed by a single nonnegative parameter α. This parameter reflects the internal slackening of a node within an underlying iterative process. The class of so-called internal slackening scoring methods, (...) denoted by λα, consists of the limits of these processes. It is seen that λ0 extends the invariant scoring method, while λ∞ extends the fair bets scoring method. Method λ1 corresponds with the existing λ-scoring method of Borm et al. (Ann Oper Res 109(1):61–75, 2002) and can be seen as a compromise between λ0 and λ∞. In particular, an explicit proportionality relation between λα and λ1 is derived. Moreover, the internal slackening scoring methods are applied to the setting of social choice situations where they give rise to a class of social choice correspondences that refine both the Top cycle correspondence and the Uncovered set correspondence. (shrink)

Une nouvelle inscription digraphe a été découverte dans le sanctuaire d'Aphrodite à Amathonte de Chypre : c'est la consécration par le roi Androklès, dans les années 330-310 av. J.-C, des statues de ses deux fils, Orestheus et Andragoras, à « l'Aphrodite chypriote ». La partie écrite en syllabaire chypriote malheureusement très mutilée, paraît transcrire la langue indigène, dite « étéochypriote ».

The geometric system of deduction called N-Graphs was introduced by de Oliveira in 2001. The proofs in this system are represented by means of digraphs and, while its derivations are mostly based on Gentzen's sequent calculus, the system gets its inspiration from geometrically based systems, such as the Kneales' tables of development, Statman's proofs-as-graphs, Buss' logical flow graphs, and Girard's proof-nets. Given that all these geometric systems appeal to the classical symmetry between premises and conclusions, providing an intuitionistic version (...) of any of these is an interesting exercise in extending the range of applicability of the geometric system in question. In this article we produce an intuitionistic version of N-Graphs, based on Maehara's LJ' system, as described by Takeuti. Recall that LJ' has multiple conclusions in all but the essential intuitionistic rules, e.g., implication right and negation right. We show soundness and completeness of our intuitionistic N-Graphs with respect to LJ'. We also discuss how we expect to extend this work to a version of N-Graphs corresponding to the intuitionistic logic system FIL (Full Intuitionistic Logic) of de Paiva and Pereira and sketch future developments. (shrink)

We consider the classification problem for several classes of countable structures which are “vertex-transitive”, meaning that the automorphism group acts transitively on the elements. We show that the classification of countable vertex-transitive digraphs and partial orders are Borel complete. We identify the complexity of the classification of countable vertex-transitive linear orders. Finally we show that the classification of vertex-transitive countable tournaments is properly above \ in complexity.

This paper gives a definition of self-reference on the basis of the dependence relation given by Leitgeb (2005), and the dependence digraph by Beringer & Schindler (2015). Unlike the usual discussion about self-reference of paradoxes centering around Yablo's paradox and its variants, I focus on the paradoxes of finitary characteristic, which are given again by use of Leitgeb's dependence relation. They are called 'locally finite paradoxes', satisfying that any sentence in these paradoxes can depend on finitely many sentences. I prove (...) that all locally finite paradoxes are self-referential in the sense that there is a directed cycle in their dependence digraphs. This paper also studies the 'circularity dependence' of paradoxes, which was introduced by Hsiung (2014). I prove that the locally finite paradoxes have circularity dependence in the sense that they are paradoxical only in the digraph containing a proper cycle. The proofs of the two results are based directly on König's infinity lemma. In contrast, this paper also shows that Yablo's paradox and its nested variant are non-self-referential, and neither McGee's paradox nor the omega-cycle liar paradox has circularity dependence. (shrink)

According to the revision theory of truth, the paradoxical sentences have certain revision periods in their valuations with respect to the stages of revision sequences. We find that the revision periods play a key role in characterizing the degrees of paradoxicality for Boolean paradoxes. We prove that a Boolean paradox is paradoxical in a digraph, iff this digraph contains a closed walk whose height is not any revision period of this paradox. And for any finitely many numbers greater than 1, (...) if any of them is not divisible by any other, we can construct a Boolean paradox whose primary revision periods are just these numbers. Consequently, the degrees of Boolean paradoxes form an unbounded dense lattice. The area of Boolean paradoxes is proved to be rich in mathematical structures and properties. (shrink)

$${{{\mathcal {F}}}}$$ -systems are useful digraphs to model sentences that predicate the falsity of other sentences. Paradoxes like the Liar and the one of Yablo can be analyzed with that tool to find graph-theoretic patterns. In this paper we studied this general model consisting of a set of sentences and the binary relation ‘ $$\ldots $$ affirms the falsity of $$\ldots $$ ’ among them. The possible existence of non-referential sentences was also considered. To model the sets of all (...) the sentences that can jointly be valued as true we introduced the notion of conglomerate, the existence of which guarantees the absence of paradox. Conglomerates also enabled us to characterize referential contradictions, i.e., sentences that can only be false under a classical valuation due to the interactions with other sentences in the model. A Kripke-style fixed-point characterization of groundedness was offered, and complete (meaning that every sentence is deemed either true or false) and consistent (meaning that no sentence is deemed true and false) fixed points were put in correspondence with conglomerates. Furthermore, argumentation frameworks are special cases of $$\mathcal{F}$$ -systems. We showed the relation between local conglomerates and admissible sets of arguments and argued about the usefulness of the concept for the argumentation theory. (shrink)

This paper gives a definition of self-reference on the basis of the dependence relation given by Leitgeb (J Philos Logic 34(2):155–192, 2005), and the dependence digraph by Beringer and Schindler (Reference graphs and semantic paradox, 2015. https://www.academia.edu/19234872/reference_graphs_and_semantic_paradox). Unlike the usual discussion about self-reference of paradoxes centering around Yablo’s paradox and its variants, I focus on the paradoxes of finitary characteristic, which are given again by use of Leitgeb’s dependence relation. They are called ‘locally finite paradoxes’, satisfying that any sentence in (...) these paradoxes can depend on finitely many sentences. I prove that all locally finite paradoxes are self-referential in the sense that there is a directed cycle in their dependence digraphs. This paper also studies the ‘circularity dependence’ of paradoxes, which was introduced by Hsiung (Logic J IGPL 22(1):24–38, 2014). I prove that the locally finite paradoxes have circularity dependence in the sense that they are paradoxical only in the digraph containing a proper cycle. The proofs of the two results are based directly on König’s infinity lemma. In contrast, this paper also shows that Yablo’s paradox and its ∀∃\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\forall \exists $$\end{document}-unwinding variant are non-self-referential, and neither McGee’s paradox nor the ω\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}-cycle liar has circularity dependence. (shrink)

We generalize the [Formula: see text] dichotomy to doubly-indexed sequences of analytic digraphs. Under a mild definability assumption, we use this generalization to characterize the family of Borel actions of tsi Polish groups on Polish spaces that can be decomposed into countably-many Borel actions admitting complete Borel sets that are lacunary with respect to an open neighborhood of the identity. We also show that if the group in question is non-archimedean, then the inexistence of such a decomposition yields a (...) special kind of continuous embedding of [Formula: see text] into the corresponding orbit equivalence relation. (shrink)

We consider three problems concerning alpha conversion of closed terms (combinators). (1) Given a combinator M find the an alpha convert of M with a smallest number of distinct variables. (2) Given two alpha convertible combinators M and N find a shortest alpha conversion of M to N. (3) Given two alpha convertible combinators M and N find an alpha conversion of M to N which uses the smallest number of variables possible along the way. We obtain the following results. (...) (1) There is a polynomial time algorithm for solving problem (1). It is reducible to vertex coloring of chordal graphs. (2) Problem (2) is co-NP complete (in recognition form). The general feedback vertex set problem for digraphs is reducible to problem (2). (3) At most one variable besides those occurring in both M and N is necessary. This appears to be the folklore but the proof is not familiar. A polynomial time algorithm for the alpha conversion of M to N using at most one extra variable is given. There is a tradeoff between solutions to problem (2) and problem (3) which we do not fully understand. (shrink)

We study the partial orderings of the form ⟨P,⊂⟩\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\langle \mathbb{P}, \subset\rangle}$$\end{document}, where X\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb{X}}$$\end{document} is a binary relational structure with the connectivity components isomorphic to a strongly connected structure Y\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb{Y}}$$\end{document} and P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb{P} }$$\end{document} is the set of substructures of X\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} (...) \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb {X}}$$\end{document} isomorphic to X\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb{X}}$$\end{document}. We show that, for example, for a countable X\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb{X}}$$\end{document}, the poset ⟨P,⊂⟩\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\langle \mathbb {P}, \subset\rangle}$$\end{document} is either isomorphic to a finite power of P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb{P} }$$\end{document} or forcing equivalent to a separative atomless σ-closed poset and, consistently, to P/fin. In particular, this holds for each ultrahomogeneous structure X\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb{X}}$$\end{document} such that X\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb{X}}$$\end{document} or Xc\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb{X}^{c}}$$\end{document} is a disconnected structure and in this case Y\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb{Y}}$$\end{document} can be replaced by an ultrahomogeneous connected digraph. (shrink)

Split preorders are preordering relations on a domain whose composition is defined in a particular way by splitting the domain into two disjoint subsets. These relations and the associated composition arise in categorial proof theory in connection with coherence theorems. Here split preorders are represented isomorphically in the category whose arrows are binary relations and whose composition is defined in the usual way. This representation is related to a classical result of representation theory due to Richard Brauer.

We are concerned with the following problem. Suppose Γ and Σ are closed permutation groups on infinite sets C and W and ρ: Γ → Σ is a non-split, continuous epimorphism with finite kernel. Describe the possibilities for ρ. Here, we consider the case where ρ arises from a finite cover π: C → W. We give reasonably general conditions on the permutation structure W;Σ which allow us to prove that these covers arise in two possible ways. The first way, (...) reminiscent of covers of topological spaces, is as a covering of some Σ-invariant digraph on W. The second construction is less easy to describe, but produces the most familiar of these types of covers: a vector space covering its projective space. (shrink)

We now fix A ⊆ Q. We study a fundamental class of digraphs associated with A, which we call the A-digraphs. An A,kdigraph is a digraph (Ak,E), where E is an order invariant subset of A2k in the following sense. For all x,y ∈ A2k, if x,y have the same order type then x ∈ E ↔ y ∈ E.

Goldman (1971) analyzed interrelations between act-statements by inducing a structure by means of the relationship by, e.g.: "He turned on the light by flipping the switch." Generally, the structure is represented by act-diagrams, e.g. act-trees. In the present article the mathematical theory of directed graphs (digraphs), specifically the concepts of partially or strictly ordered sets, graph-theoretical trees, semi-lattices etc. are shown to be applicable and conducive to the formal and a more general description of networks of act statements generated (...) by a (relative) basic actionstatement and by the relation by. The well-known problem of identity of acts described by corresponding statements connected by by is differentiated by introducing the graph-theoretical equivalence relation of belonging to the same-graph {graph-sameness or graph-identity) admitting of a more refined classification and logical description of the interdependence of actions, acttypes, act-properties etc. (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)

A novel normal form for propositional theories underlies the logic pdl, which captures some essential features of natural discourse, independent from any particular subject matter and related only to its referential structure. In particular, pdlallows to distinguish vicious circularity from the innocent one, and to reason in the presence of inconsistency using a minimal number of extraneous assumptions, beyond the classical ones. Several, formally equivalent decision problems are identified as potential applications: non-paradoxical character of discourses, admissibility of arguments in argumentation (...) networks, propositional satisfiability, and the existence of kernels of directed graphs. Directed graphs provide the basis for the semantics of pdl and the paper concludes by an overview of relevant graph-theoretical results and their applications in diagnosing paradoxical character of natural discourses. (shrink)

This paper seeks to build on the extensive connections that have arisen between automata theory, combinatorics on words, fractal geometry, and model theory. Results in this paper establish a characterization for the behavior of the fractal geometry of “k-automatic” sets, subsets of $[0,1]^d$ that are recognized by Büchi automata. The primary tools for building this characterization include the entropy of a regular language and the digraph structure of an automaton. Via an analysis of the strongly connected components of such a (...) structure, we give an algorithmic description of the box-counting dimension, Hausdorff dimension, and Hausdorff measure of the corresponding subset of the unit box. Applications to definability in model-theoretic expansions of the real additive group are laid out as well. (shrink)

Goldman (1971) analyzed interrelations between act-statements by inducing a structure by means of the relationship by, e.g.: "He turned on the light by flipping the switch." Generally, the structure is represented by act-diagrams, e.g. act-trees. In the present article the mathematical theory of directed graphs (digraphs), specifically the concepts of partially or strictly ordered sets, graph-theoretical trees, semi-lattices etc. are shown to be applicable and conducive to the formal and a more general description of networks of act statements generated (...) by a (relative) basic actionstatement and by the relation by. The well-known problem of identity of acts described by corresponding statements connected by by is differentiated by introducing the graph-theoretical equivalence relation of belonging to the same-graph {graph-sameness or graph-identity) admitting of a more refined classification and logical description of the interdependence of actions, acttypes, act-properties etc. (shrink)

Asymptotic extremal combinatorics deals with questions that in the language of model theory can be re-stated as follows. For finite models M, N of an universal theory without constants and function symbols (like graphs, digraphs or hypergraphs), let p(M, N) be the probability that a randomly chosen sub-model of N with |M| elements is isomorphic to M. Which asymptotic relations exist between the quantities p(M₁, N),...,p(Mh, N), where M₁,...,Mh are fixed "template" models and |N| grows to infinity? In this (...) paper we develop a formal calculus that captures many standard arguments in the area, both previously known and apparently new. We give the first application of this formalism by presenting a new simple proof of a result by Fisher about the minimal possible density of triangles in a graph with given edge density. (shrink)

We show that arbitrary tautologies of Johansson’s minimal propositional logic are provable by “small” polynomial-size dag-like natural deductions in Prawitz’s system for minimal propositional logic. These “small” deductions arise from standard “large” tree-like inputs by horizontal dag-like compression that is obtained by merging distinct nodes labeled with identical formulas occurring in horizontal sections of deductions involved. The underlying geometric idea: if the height, h(∂), and the total number of distinct formulas, ϕ(∂), of a given tree-like deduction ∂ of a minimal (...) tautology ρ are both polynomial in the length of ρ, |ρ|, then the size of the horizontal dag-like compression ∂ᶜ is at most h(∂)×ϕ(∂), and hence polynomial in |ρ|. That minimal tautologies ρ are provable by tree-like natural deductions ∂ with |ρ|-polynomial h(∂) and ϕ(∂) follows via embedding from Hudelmaier’s result that there are analogous sequent calculus deductions of sequent ⇒ρ. The notion of dag-like provability involved is more sophisticated than Prawitz’s tree-like one and its complexity is not clear yet. Our approach nevertheless provides a convergent sequence of NP lower approximations of PSPACE-complete validity of minimal logic. (shrink)

Graph normal form, introduced earlier for propositional logic, is shown to be a normal form also for first-order logic. It allows to view syntax of theories as digraphs, while their semantics as kernels of these digraphs. Graphs are particularly well suited for studying circularity, and we provide some general means for verifying that circular or apparently circular extensions are conservative. Traditional syntactic means of ensuring conservativity, like definitional extensions or positive occurrences guaranteeing exsitence of fixed points, emerge as (...) special cases. (shrink)

Richard Levins has advocated the scientific merits of qualitative modeling throughout his career. He believed an excessive and uncritical focus on emulating the models used by physicists and maximizing quantitative precision was hindering biological theorizing in particular. Greater emphasis on qualitative properties of modeled systems would help counteract this tendency, and Levins subsequently developed one method of qualitative modeling, loop analysis, to study a wide variety of biological phenomena. Qualitative modeling has been criticized for being conceptually and methodologically problematic. As (...) a clear example of a qualitative modeling method, loop analysis shows this criticism is indefensible. The method has, however, some serious limitations. This paper describes loop analysis, its limitations, and attempts to clarify the differences between quantitative and qualitative modeling, in content and objective. Loop analysis is but one of numerous types of qualitative analysis, so its limitations do not detract from the currently underappreciated and underdeveloped role qualitative modeling could have within science. (shrink)

We can classify the (truth-theoretic) paradoxes according to their degrees of paradoxicality. Roughly speaking, two paradoxes have the same degrees of paradoxicality, if they lead to a contradiction under the same conditions, and one paradox has a (non-strictly) lower degree of paradoxicality than another, if whenever the former leads to a contradiction under a condition, the latter does so under the same condition. In this paper, we outline some results and questions around the degrees of paradoxicality and summarize recent progress.