For an ultrafilter [Formula: see text] on a cardinal [Formula: see text] we wonder for which pair [Formula: see text] of regular cardinals, we have: for any [Formula: see text]-saturated dense linear order [Formula: see text] has a cut of cofinality [Formula: see text] We deal mainly with the case [Formula: see text].

This paper presents a polarized phase semantics, with respect to which the linear fragment of second order polarized linear logic of Laurent [15] is complete. This is done by adding a topological structure to Girard's phase semantics [9]. The topological structure results naturally from the categorical construction developed by Hamano—Scott [12]. The polarity shifting operator ↓ (resp. ↑) is interpreted as an interior (resp. closure) operator in such a manner that positive (resp. negative) formulas correspond to open (resp. (...) closed) facts. By accommodating the exponentials of linear logic, our model is extended to the polarized fragment of the second order linear logic. Strong forms of completeness theorems are given to yield cut-eliminations for the both second order systems. As an application of our semantics, the first order conservativity of linear logic is studied over its polarized fragment of Laurent [16]. Using a counter model construction, the extension of this conservativity is shown to fail into the second order, whose solution is posed as an open problem in [16]. After this negative result, a second order conservativity theorem is proved for an eta expanded fragment of the second order linear logic, which fragment retains a focalized sequent property of [3]. (shrink)

Sufficient conditions for first-order-based sequent calculi to admit cut elimination by a Schütte–Tait style cut elimination proof are established. The worst case complexity of the cut elimination is analysed. The obtained upper bound is parameterized by a quantity related to the calculus. The conditions are general enough to be satisfied by a wide class of sequent calculi encompassing, among others, some sequent calculi presentations for the first order and the propositional versions of classical and intuitionistic logic, classical and intuitionistic modal (...) logic S4, and classical and intuitionistic linear logic and some of its fragments. Moreover the conditions are such that there is an algorithm for checking if they are satisfied by a sequent calculus. (shrink)

In lieu of an abstract, here is a brief excerpt of the content:Joanne Cutting-Gray HANNAH ARENDT'S RAHEL VARNHAGEN Hannah Arendt fled Nazi Germany in 1933, a year she called the end of Jewish history. She was 27 years old at the time and carried with her a manuscript that was later to become the peculiar biography of an eighteenth-century German-Jewish "pariah," Rahel Varnhagen (1771-1833). The Life of a fewish Woman, subtitle of the biography by Arendt, distills the largely unpublished Varnhagen (...) correspondence and marks the impact of that life upon German-Jewish history.1 Published more than "half a lifetime" later in 1957, it assays the politics of form in a highly unusual manner. By expunging all detail in order to analyze Varnhagen's introspection, Arendt implicitly questions selfhood as the form for identity and as the appropriate form for biography. She reveals that seeking to preserve the self determines the blank dumbness of an unnarratable life. Rahel Levin (Antonie Friederike Robert) Varnhagen, or simply "Rahel " as Arendt calls her, lived a life as complicated as her many names. The tortured relation she had to her identity, her insatiable preoccupation with self, reflects an effort to eradicate herJewishness by baptism and marriage and becomes a paradigm of a story about a woman lost to a sense of others and herself. Neither rich, cultivated, nor beautiful, Rahel lived her unhappiness fervently, with an ecstasy that made her appear to others as startlingly original. This helps to explain how she came to preside over the most important intellectual salon in Germany during the late eighteenth century. Princes, intellectuals, and artists flocked to her attic apartment, attracted by the impenetrable spectacle of her despair. Rahel's intensity pulled others into her orbit—including, one-hundred years later, the intense and self-absorbed Arendt at the beginning Philosophy and Literature, © 1991, 15: 229-245 230Philosophy and Literature of her university education.2 Each woman suffered the private failure of a love affair complicated by the broader, historical issue of racial identity that connected their lives. Prewar Nazi Germany taught Arendt what Varnhagen learned during the period of German-Jewish assimilation in the nineteenth century—"one does not escape Jewishness."3 It is no wonder that, in analogous moments of personal and civic upheaval, Rahel Varnhagen and Hannah Arendt "corresponded," the one by writing letters about her life, the other by giving that life to a world. Like Arendt, Varnhagen was unclassifiably exotic, an unattached, Jewish female seemingly without a history, aligned with no one and nothing. If"Jewishness" meant letting life "rain upon" her, Rahel Varnhagen let it strike her "like a storm without an umbrella." And like Arendt, she refused to hide the traits and talents of her personality under cover of morality and convention. Her letters are not self-congratulatory, for she never wittingly chose notoriety. Indeed, she spent much of her life trying to escape the stigma ofJewishness that marked her destiny. Notwithstanding the milieu of nineteenth-century German romanticism that drew the biographer toward her subject, various events surrounding the text make more compelling narratives than Varnhagen 's life: how the manuscript survived World War II, Arendt's emigration to the United States, and, especially, the public and private influence of Martin Heidegger.4 At the age of 18 (1925), Arendt had discovered Varnhagen during her brief love-affair with the 35-year-old philosophy professor at the University of Marburg. Though Heidegger would later call Arendt the "passion of his life" and inspiration for his work—he was writing Being and Time during that period—his brush with Nazism precipitated their breach. Since the Heidegger-Arendt correspondence remains closed, much about their youthful relationship and life-long intellectual affair remains a mystery open only to speculation. From Arendt's biographer, Elisabeth Young-Bruehl, we know that Varnhagen's story became a consolation to her in her sorrow, a means ofgiving significance to the ambiguities of a private relationship as it was caught up in public history.5 Certainly Heidegger's retreat from political events for the sake of thinking was as strong an influence on Arendt's political development as was Varnhagen's retreat from her Jewish destiny. Nonetheless, it would be a mistake to expect... (shrink)

Let ⪯R be the preorder of embeddability between countable linear orders colored with elements of Rado's partial order . We show that ⪯R has fairly high complexity with respect to Borel reducibility , although its exact classification remains open.

A many-valued modal logic, called linear abelian modal logic $\rm {\mathbf{LK(A)}}$ is introduced as an extension of the abelian modal logic $\rm \mathbf{K(A)}$. Abelian modal logic $\rm \mathbf{K(A)}$ is the minimal modal extension of the logic of lattice-ordered abelian groups. The logic $\rm \mathbf{LK(A)}$ is axiomatized by extending $\rm \mathbf{K(A)}$ with the modal axiom schemas $\Box(\varphi\vee\psi)\rightarrow(\Box\varphi\vee\Box\psi)$ and $(\Box\varphi\wedge\Box\psi)\rightarrow\Box(\varphi\wedge\psi)$. Completeness theorem with respect to algebraic semantics and a hypersequent calculus admitting cut-elimination are established. Finally, the correspondence between hypersequent calculi and (...) axiomatization is investigated. (shrink)

We address the following question: Can we expand an NIP theory by adding a linear order such that the expansion is still NIP? Easily, if acl(A)= A for all A, then this is true. Otherwise, we give counterexamples. More precisely, there is a totally categorical theory for which every expansion by a linear order has IP. There is also an ω-stable NDOP theory for which every expansion by a linear order interprets pseudofinite arithmetic.

We characterize the linear order types $\tau $ with the property that given any countable linear order $\mathcal {L}$, $\tau \cdot \mathcal {L}$ is a computable linear order iff $\mathcal {L}$ is a computable linear order, as exactly the finite nonempty order types.

A first-order temporal non-commutative logic TN[l], which has no structural rules and has some l-bounded linear-time temporal operators, is introduced as a Gentzen-type sequent calculus. The logic TN[l] allows us to provide not only time-dependent, resource-sensitive, ordered, but also hierarchical reasoning. Decidability, cut-elimination and completeness (w.r.t. phase semantics) theorems are shown for TN[l]. An advantage of TN[l] is its decidability, because the standard first-order linear-time temporal logic is undecidable. A correspondence theorem between TN[l] and a resource indexed non-commutative (...) logic RN[l] is also shown. This theorem is intended to state that “time” is regarded as a “resource”. (shrink)

A successivity in a linear order is a pair of elements with no other elements between them. A recursive linear order with recursive successivities U is recursively categorical if every recursive linear order with recursive successivities isomorphic to U is in fact recursively isomorphic to U . We characterize those recursive linear orders with recursive successivities that are recursively categorical as precisely those with order type k 1 + g 1 + k 2 + g 2 (...) +…+ g n -1 + k n where each k n is a finite order type, non-empty for i ϵ{2,…, n -1} and each g i is an order type from among {ω,ω * ,ω+ω * }∪{ k ·η: k. (shrink)

LetEbe a computably enumerable equivalence relation on the setωof natural numbers. We say that the quotient set$\omega /E$realizesa linearly ordered set${\cal L}$if there exists a c.e. relation ⊴ respectingEsuch that the induced structure is isomorphic to${\cal L}$. Thus, one can consider the class of all linearly ordered sets that are realized by$\omega /E$; formally,${\cal K}\left = \left\{ {{\cal L}\,|\,{\rm{the}}\,{\rm{order}}\, - \,{\rm{type}}\,{\cal L}\,{\rm{is}}\,{\rm{realized}}\,{\rm{by}}\,E} \right\}$. In this paper we study the relationship between computability-theoretic properties ofEand algebraic properties of linearly ordered sets realized (...) byE. One can also define the following pre-order$ \le _{lo} $on the class of all c.e. equivalence relations:$E_1 \le _{lo} E_2 $if every linear order realized byE1is also realized byE2. Following the tradition of computability theory, thelo-degrees are the classes of equivalence relations induced by the pre-order$ \le _{lo} $. We study the partially ordered set oflo-degrees. For instance, we construct various chains and anti-chains and show the existence of a maximal element among thelo-degrees. (shrink)

When a linear order has an order preserving surjection onto each of its suborders, we say that it is strongly surjective. We prove that the set of countable strongly surjective linear orders is a [Formula: see text]-complete set. Using hypotheses beyond ZFC, we prove the existence of uncountable strongly surjective orders.

A statement of hyperarithmetic analysis is a sentence of second order arithmetic S such that for every Y⊆ω, the minimum ω-model containing Y of RCA0 + S is HYP, the ω-model consisting of the sets hyperarithmetic in Y. We provide an example of a mathematical theorem which is a statement of hyperarithmetic analysis. This statement, that we call INDEC, is due to Jullien [13]. To the author's knowledge, no other already published, purely mathematical statement has been found with this property (...) until now. We also prove that, over RCA0, INDEC is implied by [Formula: see text] and implies ACA0, but of course, neither ACA0, nor ACA 0+ imply it. We introduce five other statements of hyperarithmetic analysis and study the relations among them. Four of them are related to finitely-terminating games. The fifth one, related to iterations of the Turing jump, is strictly weaker than all the other statements that we study in this paper, as we prove using Steel's method of forcing with tagged trees. (shrink)

This commentary discusses the division of labor between syntax and phonology, starting with the parallel model of grammar developed by Jackendoff. It is proposed that linear, left-to-right order of linguistic items is not represented in syntax, but in phonology. Syntax concerns the abstract relations of categories alone. All components of grammar contribute to linear order, by means of the interface rules.

We consider certain linear orders with a function on them, and discuss for which types of functions the resulting structure is or is not computably categorical. Particularly, we consider computable copies of the rationals with a fixed-point free automorphism, and also ω with a non-decreasing function.

Numerous results about capturing complexity classes of queries by means of logical languages work for ordered structures only, and deal with non-generic, or order-dependent, queries. Recent attempts to improve the situation by characterizing wide classes of finite models where linear order is definable by certain simple means have not been very promising, as certain commonly believed conjectures were recently refuted (Dawar's Conjecture). We take on another approach that has to do with normalization of a given order (rather than with (...) defining a linear order from scratch). To this end, we show that normalizability of linear order is a strictly weaker condition than definability (say, in the least fixpoint logic), and still allows for extending Immerman-Vardi-style results to generic queries. It seems to be the weakest such condition. We then conjecture that linear order is normalizable in the least fixpoint logic for any finitely axiomatizable class of rigid structures. Truth of this conjecture, which is a strengthened version of Stolboushkin's conjecture, would have the same practical implications as Dawar's Conjecture. Finally, we suggest a series of reductions of the two conjectures to specialized classes of graphs, which we believe should simplify further work. (shrink)

An observer attempts to infer the unobserved ranking of two ideal objects, A and B, from observed rankings in which these objects are `accompanied' by `noise' components, C and D. In the first ranking, A is accompanied by C and B is accompanied by D, while in the second ranking, A is accompanied by D and B is accompanied by C. In both rankings, noisy-A is ranked above noisy-B. The observer infers that ideal-A is ranked above ideal-B. This commonly used (...) inference rule is formalized for the case in which A,B,C,D are sets. Let X be a finite set and let be a linear ordering on 2X. The following condition is imposed on . For every quadruple (A,B,C,D)∈Y, where Y is some domain in (2X)4, if and , then . The implications and interpretation of this condition for various domains Y are discussed. (shrink)

The decision problem for positively quantified formulae in the theory of linearly ordered Heyting algebras is known, as a special case of work of Kreisel, to be solvable; a simple solution is here presented, inspired by related ideas in Gödel-Dummett logic.

In this paper, we give a classification of ℵ0-categorical coloured linear orders, generalizing Rosenstein's characterization of ℵ0-categorical linear orderings. We show that they can all be built from coloured singletons by concatenation and ℚn-combinations . We give a method using coding trees to describe all structures in our list.

A low linear order with no computable copy constructed by C. Jockusch and R. Soare has Hausdorff rank equal to$2$. In this regard, the question arises, how simple can be a low linear order with no computable copy from the point of view of the linear order type? The main result of this work is an example of a low strong$\eta $-representation with no computable copy that is the simplest possible example.

This work deals with the exponential fragment of Girard's linear logic without the contraction rule, a logical system which has a natural relation with the direct logic . A new sequent calculus for this logic is presented in order to remove the weakening rule and recover its behavior via a special treatment of the propositional constants, so that the process of cut-elimination can be performed using only “local” reductions. Hence a typed calculus, which admits only local rewriting rules, can (...) be introduced in a natural manner. Its main properties — normalizability and confluence — has been investigated; moreover this calculus has been proved to satisfy a Curry-Howard isomorphism with respect to the logical system in question. MSC: 03B40, 03F05. (shrink)

We introduce the logics GLP Λ, a generalization of Japaridze’s polymodal provability logic GLP ω where Λ is any linearly ordered set representing a hierarchy of provability operators of increasing strength. We shall provide a reduction of these logics to GLP ω yielding among other things a finitary proof of the normal form theorem for the variable-free fragment of GLP Λ and the decidability of GLP Λ for recursive orderings Λ. Further, we give a restricted axiomatization of the variable-free (...) fragment of GLP Λ. (shrink)

We re-express a previous general result in a way which seems easier to remember, using the terminology of infinite games. We show how this can be applied to construct recursive linear orderings, showing, for example, that if there is a ▵ 0 2β + 1 linear ordering of type τ, then there is a recursive ordering of type ω β · τ.

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 carry out a systematic investigation of the definability of linear order on classes of finite rigid structures. We obtain upper and lower bounds for the expressibility of linear order in various logics that have been studied extensively in finite model theory, such as least fixpoint logic LFP, partial fixpoint logic PFP, infinitary logic Lω∞ω with a finite number of variables, as well as the closures of these logics under implicit definitions. Moreover, we show that the upper and (...) lower bounds established here cannot be made substantially tighter, unless outstanding conjectures in complexity theory are resolved at the same time. (shrink)

The subtle, almost ineffable, and ineffable cardinals were introduced in an unpublished 1971 manuscript of R. Jensen and K. Kunen. The concepts were extended to that of k-subtle, k-almost ineffable, and k-ineffable cardinals in 1975 by J. Baumgartner. In this paper we give a self contained treatment of the basic facts about this level of the large cardinal hierarchy, which were established by J. Baumgartner. In particular, we give a proof that the k-subtle, k-almost ineffable, and k-ineffable cardinals define three (...) properly intertwined hierarchies with the same limit, lying strictly above “total indescribability” and strictly below “arrowing ω”. The innovation here is presented in Section 2, where we take a distinctly minimalist approach. Here the subtle cardinal hierarchy is characterized by very elementary properties that do not mention closed unbounded or stationary sets. This development culminates in a characterization of the hierarchy by means of a striking universal second-order property of linear orderings. (shrink)

A linear order is -decidable if its universe is and the relations defined by formulas are uniformly computable. This means that there is a computable procedure which, when applied to a formula and a sequence of elements of the linear order, will determine whether or not is true in the structure. A linear order is decidable if the relations defined by all formulas are uniformly computable. These definitions suggest two questions. Are there, for each , -decidable (...) class='Hi'>linear orders that are not -decidable? Are there linear orders that are -decidable for all but not decidable? The former was answered in the positive by Moses in 1993. Here we answer the latter, also positively. (shrink)

We compute the model-theoretic Grothendieck ring, \\), of a dense linear order with or without end points, \\), as a structure of the signature \, and show that it is a quotient of the polynomial ring over \ generated by \\) by an ideal that encodes multiplicative relations of pairs of generators. This ring can be embedded in the polynomial ring over \ generated by \. As a corollary we obtain that a DLO satisfies the pigeon hole principle for (...) definable subsets and definable bijections between them—a property that is too strong for many structures. (shrink)

The idea of this paper is to approach linear orderings as generalized ordinals and to study how they are made from their initial segments. First we look at how the equality of two linear orderings can be expressed in terms of equality of their initial segments. Then we shall use similar methods to define functions by recursion with respect to the initial segment relation. Our method is based on the use of a game where smaller and (...) smaller initial segments of linear orderings are considered. The length of the game is assumed to exceed that of the descending sequences of elements of the linear orderings considered. By use of such game-theoretical methods we can for example extend the recursive definitions of the operations of sum, product and exponentiation of ordinals in a unique and natural way for arbitrary linear orderings. Extensions coming from direct limits do not satisfy our game-theoretic requirements in general. We also show how our recursive definitions allow very simple constructions for fixed points of functions, giving rise to certain interesting linear orderings. (shrink)

Three classes of decidable discrete linear orders with varying degrees of effectiveness are investigated. We consider how a classical order type may lie in relation to these three classes, and we characterize by their order types elements of these classes that have effective nontrivial self-embeddings.

Let DO denote the principle: Every infinite set has a dense linear ordering. DO is compared to other ordering principles such as O, the Linear Ordering principle, KW, the Kinna-Wagner Principle, and PI, the Prime Ideal Theorem, in ZF, Zermelo-Fraenkel set theory without AC, the Axiom of Choice. The main result is: Theorem. $AC \Longrightarrow KW \Longrightarrow DO \Longrightarrow O$ , and none of the implications is reversible in ZF + PI. The first and third implications and their (...) irreversibilities were known. The middle one is new. Along the way other results of interest are established. O, while not quite implying DO, does imply that every set differs finitely from a densely ordered set. The independence result for ZF is reduced to one for Fraenkel-Mostowski models by showing that DO falls into two of the known classes of statements automatically transferable from Fraenkel-Mostowski to ZF models. Finally, the proof of PI in the Fraenkel-Mostowski model leads naturally to versions of the Ramsey and Ehrenfeucht-Mostowski theorems involving sets that are both ordered and colored. (shrink)

A choice set for a computable linear ordering is a set which contains one element from each maximal block of the ordering. We obtain a partial characterization of the computable linear order-types for which each computable model has a computable choice set, and a full characterization in the relativized case; Every model of the linear order-type α of degree ≤ d has a choice set of degree ≤ d iff α can written as a finite sum of (...) order-types, each of which either has finitely many blocks, or has order-type n · η for some integer n. (shrink)

The block relation B(x,y) in a linear order is satisfied by elements that are finitely far apart; a block is an equivalence class under this relation. We show that every computable linear order with dense condensation-type (i.e., a dense collection of blocks) but no infinite, strongly η-like interval (i.e., with all blocks of size less than some fixed, finite k ) has a computable copy with the nonblock relation ¬ B(x,y) computably enumerable. This implies that every computable (...) class='Hi'>linear order has a computable copy with a computable nontrivial self-embedding and that the long-standing conjecture characterizing those computable linear orders every computable copy of which has a computable nontrivial self-embedding (as precisely those that contain an infinite, strongly η-like interval) holds for all linear orders with dense condensation-type. (shrink)

It is well known that infinite minimal sets for continuous functions on the interval are Cantor sets; that is, compact zero dimensional metrizable sets without isolated points. On the other hand, it was proved in Alcaraz and Sanchis (Bifurcat Chaos 13:1665–1671, 2003) that infinite minimal sets for continuous functions on connected linearly ordered spaces enjoy the same properties as Cantor sets except that they can fail to be metrizable. However, no examples of such subsets have been known. In this note (...) we construct, in ZFC, ${2^{\mathfrak{c}}}$ non-metrizable infinite pairwise non-homeomorphic minimal sets on compact connected linearly ordered spaces. (shrink)