Nondeterministic exponential time complexity bounds are established for recognizing true propositional formulas with partially ordered quantifiers on propositional variables.

Following Henkin's discovery of partially-ordered (branching) quantification (POQ) with standard quantifiers in 1959, philosophers of language have attempted to extend his definition to POQ with generalized quantifiers. In this paper I propose a general definition of POQ with 1-place generalized quantifiers of the simplest kind: namely, predicative, or "cardinality" quantifiers, e.g., "most", "few", "finitely many", "exactly α", where α is any cardinal, etc. The definition is obtained in a series of generalizations, extending the original, (...) Henkin definition first to a general definition of monotone-increasing (M↑) POQ and then to a general definition of generalized POQ, regardless of monotonicity. The extension is based on (i) Barwise's 1979 analysis of the basic case of M↑ POQ and (ii) my 1990 analysis of the basic case of generalized POQ. POQ is a non-compositional Ist-order structure, hence the problem of extending the definition of the basic case to a general definition is not trivial. The paper concludes with a sample of applications to natural and mathematical languages. (shrink)

Following Henkin’s discovery of partially-ordered (branching) quantification (POQ) with standard quantifiers in 1959, philosophers of language have attempted to extend his definition to POQ with generalized quantifiers. In this paper I propose a general definition of POQ with 1-place generalized quantifiers of the simplest kind: namely, predicative, or “cardinality” quantifiers, e.g., “most”, “few”, “finitely many”, “exactly α ”, where α is any cardinal, etc. The definition is obtained in a series of generalizations, extending the (...) original, Henkin definition first to a general definition of monotone-increasing (M↑) POQ and then to a general definition of generalized POQ, regardless of monotonicity. The extension is based on (i) Barwise’s 1979 analysis of the basic case of M↑ POQ and (ii) my 1990 analysis of the basic case of generalized POQ. POQ is a non-compositional 1st-order structure, hence the problem of extending the definition of the basic case to a general definition is not trivial. The paper concludes with a sample of applications to natural and mathematical languages. (shrink)

Connections between partially ordered connectives and Henkin quantifiers are considered. It is proved that the logic with all partially ordered connectives and the logic with all Henkin quantifiers coincide. This implies that the hierarchy of partially ordered connectives is strongly hierarchical and gives several nondefinability results between some of them. It is also deduced that each Henkin quantifier can be defined by a quantifier of the form equation imagewhat is a strengthening of (...) the Walkoe result. MSC: 03C80. (shrink)

Motivated by constraint satisfaction problems, Feder and Vardi (SIAM Journal of Computing, 28, 57–104, 1998) set out to search for fragments of satisfying the dichotomy property: every problem definable in is either in P or else NP-complete. Feder and Vardi considered in this connection two logics, strict NP (or SNP) and monadic, monotone, strict NP without inequalities (or MMSNP). The former consists of formulas of the form , where is a quantifier-free formula in a relational vocabulary; and the latter is (...) the fragment of SNP whose formulas involve only negative occurrences of relation symbols, only monadic second-order quantifiers, and no occurrences of the equality symbol. It remains an open problem whether MMSNP enjoys the dichotomy property. In the present paper, SNP and MMSNP are characterized in terms of partially ordered connectives. More specifically, SNP is characterized using the logic D of partially ordered connectives introduced in Blass and Gurevich (Annals of Pure and Applied Logic, 32, 1–16, 1986), Sandu and Väänänen (Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 38, 361–372 1992), and MMSNP employing a generalization C of D introduced in the present paper. (shrink)

This paper uses a partially ordered set of syntactic categories to accommodate optionality and licensing in natural language syntax. A complex but well-studied data set pertaining to the syntax of quantifier scope and negative polarity licensing in Hungarian is used to illustrate the proposal. The presentation is geared towards both linguists and logicians. The paper highlights that the main ideas can be implemented in different grammar formalisms, and discusses in detail an implementation where the partial ordering on categories (...) is given by the derivability relation of a calculus with residuated and Galois-connected unary operators. (shrink)

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)

Szymanik (2007) suggested that the distinction between first-order and higher-order quantifiers does not coincide with the computational resources required to compute the meaning of quantifiers. Cognitive difficulty of quantifier processing might be better assessed on the basis of complexity of the minimal corresponding automata. For example, both logical and numerical quantifiers are first-order. However, computational devices recognizing logical quantifiers have a fixed number of states while the number of states in automata corresponding to numerical quantifiers (...) grows with the rank of the quantifier. This observation partially explains the differences in processing between those two types of quantifiers (Troiani et al. 2009) and links them to the computational model. Taking this perspective, below, we suggest the experimental setting extending the one by McMillan et al. (2005) and Troiani et al. (2009). (shrink)

We investigate the extension of monadic second-order logic of order with cardinality quantifiers "there exists uncountably many sets such that... " and "there exists continuum many sets such that... ". We prove that over the class of countable linear orders the two quantifiers are equivalent and can be effectively and uniformly eliminated. Weaker or partial elimination results are obtained for certain wider classes of chains. In particular, we show that over the class of ordinals the uncountability quantifier can (...) be effectively and uniformly eliminated. Our argument makes use of Shelah's composition method and Ramsey-like theorem for dense linear orders. (shrink)

Quantified propositional intuitionistic logic is obtained from propositional intuitionistic logic by adding quantifiers ∀p, ∃p, where the propositional variables range over upward-closed subsets of the set of worlds in a Kripke structure. If the permitted accessibility relations are arbitrary partial orders, the resulting logic is known to be recursively isomorphic to full second-order logic (Kremer, 1997). It is shown that if the Kripke structures are restricted to trees of at height and width at most ω, the resulting logics are (...) decidable. This provides a partial answer to a question by Kremer. The result also transfers to modal S4 and some Gödel-Dummett logics with quantifiers over propositions. (shrink)

LetMbe a countably infinite ω-categorical structure. Consider Aut(M) as a complete metric space by definingd(g, h) = Ω{2−n:g(xn) ≠h(xn) org−1(xn) ≠h−1(xn)} where {xn:n∈ ω} is an enumeration ofMAn automorphism α ∈ Aut(M) is generic if its conjugacy class is comeagre. J. Truss has shown in [11] that if the set P of all finite partial isomorphisms contains a co-final subset P1closed under conjugacy and having the amalgamation property and the joint embedding property then there is a generic automorphism. In the (...) present paper we give a weaker condition of this kind which is equivalent to the existence of generic automorphisms. Really we give more: a characterization of the existence of generic expansions (defined in an appropriate way) of an ω-categorical structure. We also show that Truss' condition guarantees the existence of a countable structure consisting of automorphisms ofMwhich can be considered as an atomic model of some theory naturally associated toM. We do it in a general context of weak models for second-order quantifiers.The author thanks Ludomir Newelski for pointing out a mistake in the first version of Theorem 1.2 and for interesting discussions. Also, the author is grateful to the referee for very helpful remarks. (shrink)

A proof-theoretical analysis of elementary theories of order relations is effected through the formulation of order axioms as mathematical rules added to contraction-free sequent calculus. Among the results obtained are proof-theoretical formulations of conservativity theorems corresponding to Szpilrajn’s theorem on the extension of a partial order into a linear one. Decidability of the theories of partial and linear order for quantifier-free sequents is shown by giving terminating methods of proof-search.

We consider a family U of finite universes. The second order existential quantifier QR. means for each U ϵ U quantifying over a set of n(R)-place relations isomorphic to a given relation. We define a natural partial order on such quantifiers called interpretability. We show that for every QR. either QR is interpretable by quantifying over subsets of U and one to one functions on U both of bounded order, or the logic L(QR) (first order logic plus the quantifier (...) QR) is undecidable. (shrink)

The provocation defence, which militates against full legal responsibility for unjustified killings in several common law jurisdictions, has been the subject of considerable controversy during recent decades. Much of the criticism focused on substantive legal issues. This article examines the philosophical bases for the defence in hopes of establishing a theoretical groundwork for future debate on the legal defence. The defence originated on desert bases and continues to be understood on those grounds. This article thus examines it in light of (...) two dominant desert-based theories of punishment originating with Aristotle and Immanuel Kant respectively.Ultimately, the best theory of punishment and the best theory of defence are provided by different approaches. The more plausible and robust Kantian theory of punishment can nonetheless be supplemented by the Aristotelean theory of defence as a continent sociological morality to create a more nuanced account of defence that better explains both excuses in general and the provocation defence in particular. From a substantive legal perspective, this position justifies continued use of the provocation defence in our imperfect legal order, but the partial excuse of provocation will not exist in the ideal legal order. An ideal political order will sufficiently control its citizens’ emotions such that the defence cannot be justified. A partial excuse of provocation is only necessary in the interim. (shrink)

Branching quantifiers were first introduced by L. Henkin in his 1959 paper ‘Some Remarks on Infmitely Long Formulas’. By ‘branching quantifiers’ Henkin meant a new, non-linearly structured quantiiier-prefix whose discovery was triggered by the problem of interpreting infinitistic formulas of a certain form} The branching (or partially-ordered) quantifier-prefix is, however, not essentially infinitistic, and the issues it raises have largely been discussed in the literature in the context of finitistic logic, as they will be here. Our (...) discussion transcends, however, the resources of standard lst-order languages and we will consider the new form in the context of 1st-order logic with 1- and 2-place ‘Mostowskian` generalized quantifiers.2.. (shrink)

Entanglement measures quantify the amount of quantum entanglement that is contained in quantum states. Typically, different entanglement measures do not have to be partially ordered. The presence of a definite partial order between two entanglement measures for all quantum states, however, allows for meaningful conceptualization of sensitivity to entanglement, which will be greater for the entanglement measure that produces the larger numerical values. Here, we have investigated the partial order between the normalized versions of four entanglement measures based (...) on Schmidt decomposition of bipartite pure quantum states, namely, concurrence, tangle, entanglement robustness and Schmidt number. We have shown that among those four measures, the concurrence and the Schmidt number have the highest and the lowest sensitivity to quantum entanglement, respectively. Further, we have demonstrated how these measures could be used to track the dynamics of quantum entanglement in a simple quantum toy model composed of two qutrits. Lastly, we have employed state-dependent entanglement statistics to compute measurable correlations between the outcomes of quantum observables in agreement with the uncertainty principle. The presented results could be helpful in quantum applications that require monitoring of the available quantum resources for sharp identification of temporal points of maximal entanglement or system separability. (shrink)

We introduce an atomic formula ${\vec{y} \bot_{\vec{x}}\vec{z}}$ intuitively saying that the variables ${\vec{y}}$ are independent from the variables ${\vec{z}}$ if the variables ${\vec{x}}$ are kept constant. We contrast this with dependence logic ${\mathcal{D}}$ based on the atomic formula = ${(\vec{x}, \vec{y})}$ , actually equivalent to ${\vec{y} \bot_{\vec{x}}\vec{y}}$ , saying that the variables ${\vec{y}}$ are totally determined by the variables ${\vec{x}}$ . We show that ${\vec{y} \bot_{\vec{x}}\vec{z}}$ gives rise to a natural logic capable of formalizing basic intuitions about independence and dependence. (...) We show that ${\vec{y} \bot_{\vec{x}}\vec{z}}$ can be used to give partially ordered quantifiers and IF-logic an alternative interpretation without some of the shortcomings related to so called signaling that interpretations using = ${(\vec{x}, \vec{y})}$ have. (shrink)

In this paper we study the logic of relational and partial variable sets, seen as a generalization of set-valued presheaves, allowing transition functions to be arbitrary relations or arbitrary partial functions. We find that such a logic is the usual intuitionistic and co-intuitionistic first order logic without Beck and Frobenius conditions relative to quantifiers along arbitrary terms. The important case of partial variable sets is axiomatizable by means of the substitutivity schema for equality. Furthermore, completeness, incompleteness and independence results (...) are obtained for different kinds of Beck and Frobenius conditions. (shrink)

In this paper we show that first-order languages extended with partially ordered connectives and partially ordered quantifiers define, under a certain interpretation, their own truth-predicate. The interpretation in question is in terms of games of imperfect information. This result is compared with those of Kripke and Feferman.

The question motivating my investigation is: Are the basic philosophical principles underlying the "core" system of contemporary logic exhausted by the standard version? In particular, is the accepted narrow construal of the notion "logical term" justified? ;As a point of comparison I refer to systems of 1st-order logic with generalized quantifiers developed by mathematicians and linguists . Based on an analysis of the Tarskian conception of the role of logic I show that the standard division of terms into logical (...) and extra-logical is partly arbitrary. I argue that the semantic principles of Tarskian logic allow any higher order mathematical predicate or relation to function as a logical term in a 1st-order system, provided it is introduced in the right way into the syntactic-semantic apparatus. ;Formally, I propose a new, "constructive", semantic characterization of logical terms. A logical term is defined by a function which, given a model, "shows" how to construct relations, sets, or n-tuples of individuals which satisfy it. I discuss the linguistic applicability of the extended logic and bring numerous examples. ;One chapter is devoted to branching quantification--a non-standard logico-linguistic construction obtained by affixing a non-linear, partially-ordered quantifier-prefix to a well-formed formula. Although standard branching quantifiers were given a complete account by Henkin and Walkoe, it is not altogether clear what the meaning of branching generalized quantifiers is. I propose a new analysis of the generalized branching prefix which extends the existent, partial, definitions due to Barwise, and I develop a generalization leading to a "family" of branching structures. ;In conclusion I discuss the philosophical impact of the generalized conception of logic on such issues as the logicist thesis, the interaction between mathematics and logic, ontological commitment via logic, metaphysics and logical semantics. (shrink)

This article builds on Humberstone’s idea of defining models of propositional modal logic where total possible worlds are replaced by partial possibilities. We follow a suggestion of Humberstone by introducing possibility models for quantified modal logic. We show that a simple quantified modal logic is sound and complete for our semantics. Although Holliday showed that for many propositional modal logics, it is possible to give a completeness proof using a canonical model construction where every possibility consists of finitely many formulas, (...) we show that this is impossible to do in the first-order case. However, one can still construct a canonical model where every possibility consists of a computable set of formulas and thus still of finitely much information. (shrink)

The dissertation is an attempt to provide a formal semantics for occurrences of anaphoric pronouns and definite descriptions whose quantifier antecedents occur in sentences other than those in which the anaphoric pronouns and descriptions themselves occur, . The predominant view of anaphoric pronouns whose quantifier antecedents occur in the same sentence as they do is that they function as bound variables . Chapter 1 of this dissertation is constituted by a series of arguments against a bound variable treatment of q (...) - terms and the observation that the semantic behavior of q - terms is similar to that of certain singular terms in English arguments. Given the similarity of semantic behavior between the latter and q - terms, it seems plausible to suppose that a theory of the semantic behavior of these singular terms in English arguments would provide a model for the eventual production of a semantic theory of q - terms. In Chapter 2, a formal semantics for these singular terms in arguments is produced. In Chapter 3, a formal semantics for q - terms is produced, on the model of the semantics in Chapter 2. Finally, in Chapter 4 it is shown that the formal semantics of Chapter 3 can be extended to handle pronouns in discourses containing verbs of propositional attitudes such as 'wants', 'dreams' etc. It is also shown that some occurrences of sentences containing q - terms have truth conditions not expressible by any quantified first order sentence. One must use finite partially ordered quantifiers to express the truth conditions of such occurrences of sentences. ;The dissertation contains two appendices: the first is a technical discussion of the formal semantics of Hans Kamp which shows that his theory cannot accomodate the linguistic data mine is designed to handle. The second examines the views of Gareth Evans, Charles Chastain and Keith Donnellan on certain anaphoric pronouns. (shrink)

We obtain in this paper a representation of the formulae of extensions ofL by generalized quantifiers through functors between categories of first-order structures and partial isomorphisms. The main tool in the proofs is the back-and-forth technique. As a corollary we obtain the Caicedo's version of Fraïssés theorem characterizing elementary equivalence for such languages. We also discuss informally some geometrical interpretations of our results.

THEOREM 1. (⋄ ℵ 1 ) If B is an infinite Boolean algebra (BA), then there is B 1 such that $|\operatorname{Aut} (B_1)| \leq B_1| = \aleph_1$ and $\langle B_1, \operatorname{Aut} (B_1)\rangle \equiv \langle B, \operatorname{Aut}(B)\rangle$ . THEOREM 2. (⋄ ℵ 1 ) There is a countably compact logic stronger than first-order logic even on finite models. This partially answers a question of H. Friedman. These theorems appear in §§ 1 and 2. THEOREM 3. (a) (⋄ ℵ 1 ) (...) If B is an atomic ℵ 1 -saturated infinite BA, ψ ε L ω 1ω and $\langle B, \operatorname{Aut} (B)\rangle \models\psi$ then there is B 1 such that $|\operatorname{Aut}(B_1)| \leq |B_1| = \aleph_1$ and $\langle B_1, \operatorname{Aut}(B_1)\rangle\models\psi$ . In particular if B is 1-homogeneous so is B 1 . (b) (a) holds for B = P(ω) even if we assume only CH. (shrink)

The 3-valued paraconsistent logic Ciore was developed by Carnielli, Marcos and de Amo under the name LFI2, in the study of inconsistent databases from the point of view of logics of formal inconsistency (LFIs). They also considered a first-order version of Ciore called LFI2*. The logic Ciore enjoys extreme features concerning propagation and retropropagation of the consistency operator: a formula is consistent if and only if some of its subformulas is consistent. In addition, Ciore is algebraizable in the sense of (...) Blok and Pigozzi. On the other hand, the logic LFI2* satisfies a somewhat counter-intuitive property: the universal and the existential quantifier are inter-definable by means of the paraconsistent negation, as it happens in classical first-order logic with respect to the classical negation. This feature seems to be unnatural, given that both quantifiers have the classical meaning in LFI2*, and that this logic does not satisfy the De Morgan laws with respect to its paraconsistent negation. The first goal of the present article is to introduce a first-order version of Ciore (which we call QCiore) preserving the spirit of Ciore, that is, without introducing unexpected relationships between the quantifiers. The second goal of the article is to adapt to QCiore the partial structures semantics for the first-order paraconsistent logic LPT1 introduced by Coniglio and Silvestrini, which generalizes the semantic notion of quasi-truth considered by Mikeberg, da Costa and Chuaqui. Finally, some important results of classical Model Theory are obtained for this logic, such as Robinson’s joint consistency theorem, amalgamation and interpolation. Although we focus on QCiore, this framework can be adapted to other 3-valued first-order LFIs. (shrink)

We describe a knowledge representation and inference formalism, based on an intensional propositional semantic network, in which variables are structures terms consisting of quantifier, type, and other information. This has three important consequences for natural language processing. First, this leads to an extended, more natural formalism whose use and representations are consistent with the use of variables in natural language in two ways: the structure of representations mirrors the structure of the language and allows re-use phenomena such as pronouns and (...) ellipsis. Second, the formalism allows the specification of description subsumption as a partial ordering on related concepts (variable nodes in a semantic network) that relates more general concepts to more specific instances of that concept, as is done in language. Finally, this structured variable representation simplifies the resolution of some representational difficulties with certain classes of natural language sentences, namely, donkey sentences and sentences involving branching quantifiers. The implementation of this formalism is called ANALOG (A NAtural LOGIC) and its utility for natural language processing tasks is illustrated. (shrink)

In this paper, we study natural language constructions which were first examined by Barwise: The richer the country, the more powerful some of its officials. Guided by Barwise’s observations, we suggest that conceivable interpretations of such constructions express the existence of various similarities between partial orders such as homomorphism or embedding. Semantically, we interpret the constructions as polyadic generalized quantifiers restricted to finite models. We extend the results obtained by Barwise by showing that similarity quantifiers are not expressible (...) in elementary logic over finite models. We also investigate whether the proposed readings are sound from the cognitive perspective. We prove that almost all similarity quantifiers are intractable. This leads us to first-order variants, which only approximate the strong readings, but are cognitively more plausible. Driven by the question of ambiguity, we recall Barwise’s argumentation in favour of strong readings, enriching it with some arguments of our own. Given that Barwise-like sentences are indeed ambiguous, we use a generalized Strong Meaning Hypothesis to derive predictions for their verification. Finally, we propose a hypothesis according to which conflicting pressures of communication and cognition might give rise to an ambiguous construction, provided that different semantic variants of the construction withstand different pressures involved in its usage. (shrink)

The consistency strength of the ∑2 priority method is I∑2, yet classical theorems proven by this method have been proved from I∑1. Is there a statement about the structure of the r.e. degrees that can be proved using a ∑2 argument and cannot be proved from I∑1?We rule out statements in the language of partial orderings of the form …[], where is quantifier-free, by showing that the following can be proved in I∑1.If P is any recursive partial ordering with a (...) maximal point d, and a is any nonrecursive incomplete r.e. degree, then P can be embedded into the r.e. degrees by an embedding sending d to a. (shrink)

One well known problem regarding quantifiers, in particular the 1st order quantifiers, is connected with their syntactic categories and denotations.The unsatisfactory efforts to establish the syntactic and ontological categories of quantifiers in formalized first-order languages can be solved by means of the so called principle of categorial compatibility formulated by Roman Suszko, referring to some innovative ideas of Gottlob Frege and visible in syntactic and semantic compatibility of language expressions. In the paper the principle is introduced for (...) categorial languages generated by the Ajdukiewicz’s classical categorial grammar. The 1st-order quantifiers are typically ambiguous. Every 1st-order quantifier of the type k > 0 is treated as a two-argument functor-function defined on the variable standing at this quantifier and its scope (the sentential function with exactly k free variables, including the variable bound by this quantifier); a binary function defined on denotations of its two arguments is its denotation. Denotations of sentential functions, and hence also quantifiers, are defined separately in Fregean and in situational semantics. They belong to the ontological categories that correspond to the syntactic categories of these sentential functions and the considered quantifiers. The main result of the paper is a solution of the problem of categories of the 1st-order quantifiers based on the principle of categorial compatibility. (shrink)

We show that a coherent theory of partially ordered connectives can be developed along the same line as partially ordered quantification. We estimate the expressive power of various partially ordered connectives and use methods like Ehrenfeucht games and infinitary logic to get various undefinability results.

The paper presents predicate logical extensions of some subintuitionistic logics. Subintuitionistic logics result if conditions of the accessibility relation in Kripke models for intuitionistic logic are dropped. The accessibility relation which interprets implication in models for the propositional base subintuitionistic logic considered here is neither persistent on atoms, nor reflexive, nor transitive. Strongly complete predicate logical extensions are modeled with a second accessibility relation, which is a partial order, for the interpretation of the universal quantifier.

A partial ordering P is said to have the weak Freese-Nation property if there is a mapping tf : P → [P]0 such that, for any a, b ε P, if a b then there exists c ε tf∩tf such that a c b. In this note, we study the WFN and some of its generalizations. Some features of the class of Boolean algebras with the WFN seem to be quite sensitive to additional axioms of set theory: e.g. under CH, (...) every ccc complete Boolean algebra has this property while, under b 2, there exists no complete Boolean algebra with the WFN. (shrink)

In the context of proliferation of many logical systems in the area of mathematical logic and computer science, we present a generalization of forcing in institution-independent model theory which is used to prove two abstract results: Downward Löwenheim-Skolem Theorem and Omitting Types Theorem . We instantiate these general results to many first-order logics, which are, roughly speaking, logics whose sentences can be constructed from atomic formulas by means of Boolean connectives and classical first-order quantifiers. These include first-order logic , (...) logic of order-sorted algebras , preorder algebras , as well as their infinitary variants \ , \ , \ . In addition to the first technique for proving OTT, we develop another one, in the spirit of institution-independent model theory, which consists of borrowing the Omitting Types Property from a simpler institution across an institution comorphism. As a result we export the OTP from FOL to partial algebras and higher-order logic with Henkin semantics , and from the institution of \ to \ and \ . The second technique successfully extends the domain of application of OTT to non conventional logical systems for which the standard methods may fail. (shrink)

We prove a theorem (1.7) about partial orders which can be viewed as a version of the Barwise compactness theorem which does not mention logic. The Barwise compactness theorem is easily equivalent to 1.7 + "Every Henkin set has a model". We then make the observation that 1.7 gives us the definability of forcing for quantifier-free sentences in the forcing language and use this to give a direct proof of the truth and definability lemmas of forcing.

One well known problem regarding quantifiers, in particular the 1storder quantifiers, is connected with their syntactic categories and denotations. The unsatisfactory efforts to establish the syntactic and ontological categories of quantifiers in formalized first-order languages can be solved by means of the so called principle of categorial compatibility formulated by Roman Suszko, referring to some innovative ideas of Gottlob Frege and visible in syntactic and semantic compatibility of language expressions. In the paper the principle is introduced for (...) categorial languages generated by the Ajdukiewicz’s classical categorial grammar. The 1st-order quantifiers are typically ambiguous. Every 1st-order quantifier of the type k > 0 is treated as a two-argument functorfunction defined on the variable standing at this quantifier and its scope (the sentential function with exactly k free variables, including the variable bound by this quantifier); a binary function defined on denotations of its two arguments is its denotation. Denotations of sentential functions, and hence also quantifiers, are defined separately in Fregean and in situational semantics. They belong to the ontological categories that correspond to the syntactic categories of these sentential functions and the considered quantifiers. The main result of the paper is a solution of the problem of categories of the 1st-order quantifiers based on the principle of categorial compatibility. (shrink)

Second-order quantifier elimination in the context of classical logic emerged as a powerful technique in many applications, including the correspondence theory, relational databases, deductive and knowledge databases, knowledge representation, commonsense reasoning and approximate reasoning. In the current paper we first generalize the result of Nonnengart and Szałas [17] by allowing second-order variables to appear within higher-order contexts. Then we focus on a semantical analysis of conditionals, using the introduced technique and Gabbay’s semantics provided in [10] and substantially using a third-order (...) accessibility relation. The analysis is done via finding correspondences between axioms involving conditionals and properties of the underlying third-order relation. (shrink)

In this article we characterize a countable ordinal known as the big Veblen number in terms of natural well-partially ordered tree-like structures. To this end, we consider generalized trees where the immediate subtrees are grouped in pairs with address-like objects. Motivated by natural ordering properties, extracted from the standard notations for the big Veblen number, we investigate different choices for embeddability relations on the generalized trees. We observe that for addresses using one finite sequence only, the embeddability coincides (...) with the classical tree-embeddability, but in this article we are interested in more general situations. We prove that the maximal order type of some of these new embeddability relations hit precisely the big Veblen ordinal ϑΩΩ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\vartheta \Omega^{\Omega}}$$\end{document}. Somewhat surprisingly, changing a little bit the well-partially ordered addresses, the maximal order type hits an ordinal which exceeds the big Veblen number by far, namely ϑΩΩΩ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\vartheta \Omega^{\Omega^\Omega}}$$\end{document}. Our results contribute to the research program on classifying properties of natural well-orderings in terms of order-theoretic properties of the functions generating the orderings. (shrink)

Salmon and Soames argue against nominalism about numbers and sentence types. They employ (respectively) higher-order and first-order logic to model certain natural language inferences and claim that the natural language conclusions carry commitment to abstract objects, partially because their renderings in those formal systems seem to do that. I argue that this strategy fails because the nominalist can accept those natural language consequences, provide them with plausible and non-committing truth conditions and account for the inferences made without committing themselves (...) to abstract objects. I sketch a modal account of higher-order quantification, on which instead of ranging over sets, higher order quantifiers are used to make (logical) possibility claims about which predicate tokens can be introduced. This approach provides an alternative account of truth conditions for natural language sentences which seem to employ higher-order quantification, thus allowing the nominalist to evade Salmon’s argument. I also show how the nominalist can account for the occurrence of apparently singular abstract terms in certain true statements. I argue that the nominalist can achieve this by, first, dividing singular terms into real singular terms (referring to concrete objects) and only apparent singular terms (called onomatoids), introduced for the sake of brevity and simplicity, and then providing an account of nominalistically acceptable truth conditions of sentences containing onomatoids. I develop such an account in terms of modally interpreted abstraction principles and argue that applying this strategy to Soames’s argument allows the nominalists to defend themselves. (shrink)

Interest surges in a distinctively metaphysical notion of ground. But a Schism has emerged between Orthodoxy’s view of ground as inducing a strict partial order structure on reality and Heresy’s rejection of this view. What’s at stake is the structure of reality (for proponents of ground), or even ground itself (for those who think this Schism casts doubt upon its coherence). I defend Orthodoxy against Heresy.

This paper studies the expressive power that an extra first order quantifier adds to a fragment of monadic second order logic, extending the toolkit of Janin and Marcinkowski [JM01].We introduce an operation existsn on properties S that says "there are n components having S". We use this operation to show that under natural strictness conditions, adding a first order quantifier word u to the beginning of a prefix class V increases the expressive power monotonically in u. As a corollary, if (...) the first order quantifiers are not already absorbed in V, then both the quantifier alternation hierarchy and the existential quantifier hierarchy in the positive first order closure of V are strict.We generalize and simplify methods from Marcinkowski [Mar99] to uncover limitations of the expressive power of an additional first order quantifier, and show that for a wide class of properties S, S cannot belong to the positive first order closure of a monadic prefix class W unless it already belongs to W.We introduce another operation alt on properties which has the same relationship with the Circuit Value Problem as reach has with the Directed Reachability Problem. We use alt to show that Πn⊈ FO, Σn⊈ FO, and Δn+1⊈ FOB, solving some open problems raised in [Mat98]. (shrink)