We examine second order intuitionistic propositional logic, IPC². Let $F_\exists $ be the set of formulas with no universal quantification. We prove Glivenko's theorem for formulas in $F_\exists $ that is, for φ € $F_\exists $ φ is a classical tautology if and only if ¬¬φ is a tautology of IPC². We show that for each sentence φ € $F_\exists $ (without free variables), φ is a classical tautology if and only if φ is an intuitionistic tautology. As a corollary (...) we obtain a semantic argument that the quantifier V is not definable in IPC² from ⊥, V, ^, →. (shrink)

Building on our diverse research traditions in the study of reasoning, language and communication, the Polish School of Argumentation integrates various disciplines and institutions across Poland in which scholars are dedicated to understanding the phenomenon of the force of argument. Our primary goal is to craft a methodological programme and establish organisational infrastructure: this is the first key step in facilitating and fostering our research movement, which joins people with a common research focus, complementary skills and an enthusiasm to work (...) together. This statement—the Manifesto—lays the foundations for the research programme of the Polish School of Argumentation. (shrink)

The provability problem in intuitionistic propositional second-order logic with existential quantifier and implication (∃,→) is proved to be undecidable in presence of free type variables (constants). This contrasts with the result that inutitionistic propositional second-order logic with existential quantifier, conjunction and negation is decidable.

We investigate theories of initial segments of the standard models for arithmetics. It is easy to see that if the ordering relation is definable in the standard model then the decidability results can be transferred from the infinite model into the finite models. On the contrary we show that the Σ₂—theory of multiplication is undecidable in finite models. We show that this result is optimal by proving that the Σ₁—theory of multiplication and order is decidable in finite models as well (...) as in the standard model. We show also that the exponentiation function is definable in finite models by a formula of arithmetic with multiplication and that one can define in finite models the arithmetic of addition and multiplication with the concatenation operation. We consider also the spectrum problem. We show that the spectrum of arithmetic with multiplication and arithmetic with exponentiation is strictly contained in the spectrum of arithmetic with addition and multiplication. (shrink)

It is known that various complexity-theoretical problems can be translated into some special spectra problems. Thus, questions about complexity classes are translated into questions about the expressive power of some languages. In this paper we investigate the spectra of some logics with Henkin quantifiers in the empty vocabulary.

It is known that various complexity-theoretical problems can be translated into some special spectra problems (see e.g. Fagin [Fa74] or Blass and Gurevich, [Bl-Gu86]). So questions about complexity classes are translated into questions about the expressive power of some languages. In this paper we investigate the spectra of some logics with Henkin quanti fiers in the empty vocabulary. This problem has been investigated fi rstly by Krynicki and Mostowski in [Kr-Mo 92] and [Kr- Mo 95]. All presented results can be (...) also treated as results about the expressive power of certain languages in fi nite models. (shrink)

We prove that for each β, γ < ε0 there existsα < ε0 such that whenever A ⊆ ω is α ‐large and G: A → β is such that (∀a ∈ A)(psn(G (a)) ≤ a), then there exists a γ ‐large C ⊆ A on which G is nondecreasing. Moreover, we give upper bounds for α for small ordinals β ≤ ω (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim).

We investigate some logics with Henkin quantifiers. For a given logic L, we consider questions of the form: what is the degree of the set of L–tautologies in a poor vocabulary (monadic or empty)? We prove that the set of tautologies of the logic with all Henkin quantifiers in empty vocabulary L*∅ is of degree 0’. We show that the same holds also for some weaker logics like L ∅(Hω) and L ∅(Eω). We show that each logic of the form (...) L ∅ (k)(Q), with the number of variables restricted to k, is decidable. Nevertheless – following the argument of M. Mostowski from [Mos89] – for each reasonable set theory no concrete algorithm can provably decide L (k) (Q), for some (Q). We improve also some results related to undecidability and expressibility for logics L(H4) and L(F2) of Krynicki and M. Mostowski from [KM92]. (shrink)