After the three families divided up the state of Jin and the Tian family took over Qi, the political situation in the fourth century B.C.E. appeared even more chaotic. Wei conquered Chu's Luyang and Qin's Xihe, Qin defeated Wei at Shimen , and again at Shaoliang , and Wei moved its capital to Daliang. During the mid-Warring States period, Qin became dominant in the west, Qi in the east, Chu in the south, and Wei in the center. Rapid changes occurred (...) one after another; trickery and conflict were rampant. However, the shi , the intelligentsia, actually managed to expand their spheres of existence and activity accordingly in this state of tension between countries, states, and men. A few major states assembled quite a number of literati; and those men of the villages, who had in earlier times merely waited passively for opportunities to fall into their laps, crisscrossed the various feudal states; literati who previously had no cause to use military force became, one by one, the honored guests of the feudal lords. With the breakdown of the previously simple and obvious order, the gradually dismantling of the common body of the ancestral clan of the past, and the increasing complexities of social relationships after the dissolution of blood ties, social order became a matter of concern. Or, to reword this most practical issue: How could this universally chaotic society go from disorder to order? (shrink)

We calculate the complexity of Scott sentences of scattered linear orders. Given a countable scattered linear order L of Hausdorff rank $\alpha $ we show that it has a ${d\text {-}\Sigma _{2\alpha +1}}$ Scott sentence. It follows from results of Ash [2] that for every countable $\alpha $ there is a linear order whose optimal Scott sentence has this complexity. Therefore, our bounds are tight. We furthermore show that every Hausdorff rank 1 linear order has an optimal (...) ${\Pi ^{\mathrm {c}}_{3}}$ or ${d\text {-}\Sigma ^{\mathrm {c}}_{3}}$ Scott sentence and give a characterization of those linear orders of rank $1$ with ${\Pi ^{\mathrm {c}}_{3}}$ optimal Scott sentences. At last we show that for all countable $\alpha $ the class of Hausdorff rank $\alpha $ linear orders is $\boldsymbol {\Sigma }_{2\alpha +2}$ complete and obtain analogous results for index sets of computable linear orders. (shrink)

Many academics extol chaos theory and the science of complexity as significant scientific advances with application in such diverse fields as biology, anthropology, economics, and history. In this paper we focus our attention on structure‐within‐chaos and the dynamic self‐organization of complex systems in the context of social philosophy. Although the modern formulation of the science of complexity has developed out of late‐twentieth‐century physics and computational mathematics, its roots may extend much deeper into classical thinking. We argue here that the essential (...) ideas and predictions of the science of complexity are found within the social ordering principle of li (the rites) in Confucius's Analects. (shrink)

This research is motivated by the program of Reverse Mathematics. We investigate basic part of complex analysis within some weak subsystems of second order arithmetic, in order to determine what kind of set existence axioms are needed to prove theorems of basic analysis. We are especially concerned with Cauchy’s integral theorem. We show that a weak version of Cauchy’s integral theorem is proved in RCAo. Using this, we can prove that holomorphic functions are analytic in RCAo. On the (...) other hand, we show that a full version of Cauchy’s integral theorem cannot be proved in RCAo but is equivalent to weak König’s lemma over RCAo. (shrink)

Much previous work has suggested that word order preferences across languages can be explained by the dependency distance minimization constraint (Ferrer‐i Cancho, 2008, 2015; Hawkins, 1994). Consistent with this claim, corpus studies have shown that the average distance between a head (e.g., verb) and its dependent (e.g., noun) tends to be short cross‐linguistically (Ferrer‐i Cancho, 2014; Futrell, Mahowald, & Gibson, 2015; Liu, Xu, & Liang, 2017). This implies that on average languages avoid inefficient or complex structures for simpler structures. (...) But a number of studies in psycholinguistics (Konieczny, 2000; Levy & Keller, 2013; Vasishth, Suckow, Lewis, & Kern, 2010) show that the comprehension system can adapt to the typological properties of a language, for example, verb‐final order, leading to more complex structures, for example, having longer linear distance between a head and its dependent. In this paper, we conduct a corpus study for a group of 38 languages, which were either Subject–Verb–Object (SVO) or Subject–Object–Verb (SOV), in order to investigate the role of word order typology in determining syntactic complexity. We present results aggregated across all dependency types, as well as for specific verbal (objects, indirect objects, and adjuncts) and nonverbal (nominal, adjectival, and adverbial) dependencies. The results suggest that dependency distance in a language is determined by the default word order of a language, and crucially, the direction of a dependency (whether the head precedes the dependent or follows it; e.g., whether the noun precedes the verb or follows it). Particularly we show that in SOV languages (e.g., Hindi, Korean) as well as SVO languages (e.g., English, Spanish), longer linear distance (measured as number of words) between head and dependent arises in structures when they mirror the default word order of the language. In addition to showing results on linear distance, we also investigate the influence of word order typology on hierarchical distance (HD; measured as number of heads between head and dependent). The results for HD are similar to that of linear distance. At the same time, in comparison to linear distance, the influence of adaptability on HD seems less strong. In particular, the results show that most languages tend to avoid greater structural depth. Together, these results show evidence for “limited adaptability” to the default word order preferences in a language. Our results support a large body of work in the processing literature that highlights the importance of linguistic exposure and its interaction with working memory constraints in determining sentence complexity. Our results also point to the possible role of other factors such as the morphological richness of a language and a multifactor account of sentence complexity remains a promising area for future investigation. (shrink)

We consider first order modal logic C firstly defined by Carnap in “Meaning and Necessity” [1]. We prove elimination of nested modalities for this logic, which gives additionally the Skolem-Löwenheim theorem for C. We also evaluate the degree of unsolvability for C, by showing that it is exactly 0′. We compare this logic with the logics of Henkin quantifiers, Σ11 logic, and SO. We also shortly discuss properties of the logic C in finite models.

Evolution, Order and Complexity reflects topical interest in the relationship between the social and natural worlds. It represents the cutting edge of current thinking which challenges the natural/social dichotomy thesis by showing how the application of ideas which derive from biology can be applied and offer insight into the social realm. This is done by introducing the general system theory to the methodological debate on the relation of human and natural sciences.

We study the computational complexity of the universal theory of residuated ordered groupoids, which are algebraic structures corresponding to Nonassociative Lambek Calculus. We prove that the universal theory is co $$\textsf {NP}$$ -complete which, as we observe, is the lowest possible complexity for a universal theory of a non-trivial class of structures. The universal theories of the classes of unital and integral residuated ordered groupoids are also shown to be co $$\textsf {NP}$$ -complete. We also prove the co $$\textsf {NP}$$ (...) -completeness of the universal theory of classes of residuated algebras, algebraic structures corresponding to Generalized Lambek Calculus. (shrink)

This paper obtains lower and upper bounds for the number of alternations of bounded quantifiers needed to express all formulas in certain ordered Abelian groups admitting elimination of unbounded quantifiers. The paper also establishes model-theoretic tests for equivalence to a formula with a given number of alternations of bounded quantifiers.

The model-checking problem for a logic L on a class C of structures asks whether a given L-sentence holds in a given structure in C. In this paper, we give super-exponential lower bounds for fixed-parameter tractable model-checking problems for first-order and monadic second-order logic. We show that unless PTIME=NP, the model-checking problem for monadic second-order logic on finite words is not solvable in time f·p, for any elementary function f and any polynomial p. Here k denotes the (...) size of the input sentence and n the size of the input word. We establish a number of similar lower bounds for the model-checking problem for first-order logic, for example, on the class of all trees. (shrink)

We show that for random bit strings, Up, with probability, image, the first order quantifier depth D) needed to distinguish non-isomorphic structures is Θ, with high probability. Further, we show that, with high probability, for random ordered graphs, G≤,p with edge probability image, D)=Θ, contrasting with the results for random graphs, Gp, given by Kim et al. [J.H. Kim, O. Pikhurko, J. Spencer, O. Verbitsky, How complex are random graphs in first order logic? Random Structures and Algorithms 26 (...) 119–145] of D)=log1/pn+O. (shrink)

We show that for random bit strings, Up, with probability, image, the first order quantifier depth D) needed to distinguish non-isomorphic structures is Θ, with high probability. Further, we show that, with high probability, for random ordered graphs, G≤,p with edge probability image, D)=Θ, contrasting with the results for random graphs, Gp, given by Kim et al. [J.H. Kim, O. Pikhurko, J. Spencer, O. Verbitsky, How complex are random graphs in first order logic? Random Structures and Algorithms 26 (...) 119–145] of D)=log1/pn+O. (shrink)

First we prove that the set of countable linear orders of the form I + I form a complete analytic set. As a consequence of this we improve a result of Humke and Laczkovich, who showed in [HL] that the set of functions of the form f ⚬ f form a true analytic set in C[0, 1]. We show that these functions form a complete analytic set, solving a problem mentioned on p. 215 of [K1] and on p. 4 of (...) [B]. (shrink)

We introduce SO-HORNr which is a revised version of SO-HORN and show that SO-HORNr captures equation image on ordered finite structures. We also introduce second-order extended Horn logic SO-EHORN and a superclass SO-EHORNr of it. We show that both of them capture equation image on ordered finite structures by proving that SO-EHORN and SO-EHORNr have the same expressive power when only consider ordered structures.

In this article, we formally define and investigate the computational complexity of the definability problem for open first-order formulas with equality. Given a logic $\boldsymbol{\mathcal{L}}$, the $\boldsymbol{\mathcal{L}}$-definability problem for finite structures takes as an input a finite structure $\boldsymbol{A}$ and a target relation $T$ over the domain of $\boldsymbol{A}$ and determines whether there is a formula of $\boldsymbol{\mathcal{L}}$ whose interpretation in $\boldsymbol{A}$ coincides with $T$. We show that the complexity of this problem for open first-order formulas is coNP-complete. (...) We also investigate the parametric complexity of the problem and prove that if the size and the arity of the target relation $T$ are taken as parameters, then open definability is $\textrm{coW}[1]$-complete for every vocabulary $\tau $ with at least one, at least binary, relation. (shrink)

A partir da experiência quotidiana do direito, Eric Voegelin penetra pela sua superfície fenome­nal para averiguar da existência de um núcleo ontológico. Fiel à tomista possibilidade do conhe­cimento modesto de coisas supremas, primeiro considera que o direito é mera consequência da sociedade, porquanto a ordem jurídica deriva da ordem da sociedade, para, em seguida, considerar a ordem da sociedade proveniente de um todo maior e anterior à mesma: a ordem do mundo que se identifica com a própria ordem do ser. (...) Em Voegelin, o direito é entendido como tendo por natureza ontológica a estrutura da sociedade cujo direito a sociedade é, e como tendo por critério a relação do homem com o ser tal como nós podemos sabê-lo através da filosofia e da revelação, num exemplo moderno de filosofar ao estilo clássico. (shrink)

Cognitive Science, Volume 45, Issue 11, November 2021.

We consider the problem of obtaining logical characterisations of oracle complexity classes. In particular, we consider the complexity classes LOGSPACENP and PTIMENP. For these classes, characterisations are known in terms of NP computable Lindström quantifiers which hold on ordered structures. We show that these characterisations are unlikely to extend to arbitrary structures, since this would imply the collapse of certain exponential complexity hierarchies. We also observe, however, that PTIMENP can be characterised in terms of Lindström quantifers , though it remains (...) open whether this can be done for LOGSPACENP. (shrink)

In this paper, we solve a long-standing open question, about the spectrum of the successivity relation on a computable linear ordering. We show that if a computable linear ordering [Formula: see text] has infinitely many successivities, then the spectrum of the successivity relation is closed upwards in the computably enumerable Turing degrees. To do this, we use a new method of constructing [Formula: see text]-isomorphisms, which has already found other applications such as Downey, Kastermans and Lempp [9] and is of (...) independent interest. It would seem to promise many further applications. (shrink)

We refine the constructions of Ferrante-Rackoff and Solovay on iterated definitions in first-order logic and their expressibility with polynomial size formulas. These constructions introduce additional quantifiers; however, we show that these extra quantifiers range over only finite sets and can be eliminated. We prove optimal upper and lower bounds on the quantifier complexity of polynomial size formulas obtained from the iterated definitions. In the quantifier-free case and in the case of purely existential or universal quantifiers, we show that Ω (...) quantifiers are necessary and sufficient. The last lower bounds are obtained with the aid of the Yao-Håstad switching lemma. (shrink)

A new science, the science of complexity, is birthing. This science boldly promises to transform the biological and social sciences in the forthcoming century. My own book, Origins of Order: Self Organization and Selection in Evolution, (Kauffman, 1992), is at most one strand in this transformation. I feel deeply honored that Marjorie Grene undertook organizing a session at the Philosophy of Science meeting discussing Origins, and equally glad that Dick Burian, Bob Richardson and Rob Page have undertaken their reading (...) of the manuscript and careful thoughts. In this article I shall characterize the book, but more importantly, set it in the broader context of the emerging sciences of complexity. Although the book is not yet out of Oxford press’s quiet womb, my own thinking has moved beyond that which I had formulated even a half year ago. Meanwhile, in the broader scientific community, the interest in “complexity” is exploding. (shrink)

This article discusses my book, Origins of Order: Self Organization and Selection in Evolution, in the context of the emerging sciences of complexity. Origins, due out of Oxford University Press in early 1992, attempts to lay out a broadened theory of evolution based on the marriage of unexpected and powerful properties of self organization which arises in complex systems, properties which may underlie the origin of life itself and the emergence of order in ontogeny, and the continuing action (...) of natural selection. The three major themes are: 1) that such self organized properties lie to hand for selection's further molding; 2) hence that the order we see is not due to selection alone, but in part reflects the order selection has always acted upon; 3) and finally that the marriage of natural order and natural selection may inevitably lead living entitites to a novel organized state, lying on the edge between order and chaos, as the inevitable evolutionary attractor of selection for the capacity to adapt. (shrink)

Aleksandar Ignjatović. Delineating Classes of Computational Complexity via Second Order Theories with Weak Set Existence Principles (I).