An approach to infinitary temporal proof theory

Aim of this work is to investigate from a proof-theoretic viewpoint a propositional and a predicate sequent calculus with an –type schema of inference that naturally interpret the propositional and the predicate until–free fragments of Linear Time Logic LTL respectively. The two calculi are based on a natural extension of ordinary sequents and of standard modal rules. We examine the pure propositional case (no extralogical axioms), the propositional and the first order predicate cases (both with a possibly infinite set of extralogical axioms). For each system we provide a syntactic proof of cut elimination and a proof of completeness.Supported by MIUR COFIN 02 Teoria dei Modelli e Teoria degli Insiemi, loro interazioni ed applicazioni.Supported by MIUR COFIN 02 PROTOCOLLO.Mathematics Subject Classification (2000):03B22, 03B45, 03F05     

The Gödel-McKinsey-Tarski embedding for infinitary intuitionistic logic and its extensions

The Gödel-McKinsey-Tarski embedding allows to view intuitionistic logic through the lenses of modal logic. In this work, an extension of the modal embedding to infinitary intuitionistic logic is introduced. First, a neighborhood semantics for a family of axiomatically presented infinitary modal logics is given and soundness and completeness are proved via the method of canonical models. The semantics is then exploited to obtain a labelled sequent calculus with good structural properties. Next, soundness and faithfulness of the embedding are established by transfinite induction on the height of derivations: the proof is obtained directly without resorting to non-constructive principles. Finally, the modal embedding is employed in order to relate classical, intuitionistic and modal derivability in infinitary logic extended with axioms.     

The Axiom of Choice in Second-Order Predicate Logic

The present article deals with the power of the axiom of choice (AC) within the second-order predicate logic. We investigate the relationship between several variants of AC and some other statements, known as equivalent to AC within the set theory of Zermelo and Fraenkel with atoms, in Henkin models of the one-sorted second-order predicate logic with identity without operation variables. The construction of models follows the ideas of Fraenkel and Mostowski. It is e. g. shown that the well-ordering theorem for unary predicates is independent from AC for binary predicates and from the trichotomy law for unary predicates. Moreover, we show that the AC for binary predicates follows neither from the trichotomy law for unary predicates nor from Zorn's lemma for unary predicates nor from the formalization of the axiom of choice for disjoint families of sets for binary predicates, and that the trichotomy law for unary predicates does not follow from AC for binary predicates. Mathematics Subject Classification: 03B15, 03E25, 04A25.     

Non decomposable connectives of linear logic

This paper studies the so-called generalized multiplicative connectives of linear logic, focusing on the question of finding the “non-decomposable” ones, i.e., those that cannot be expressed as combinations of the default binary connectives of multiplicative linear logic, ⊗ (times) and ⅋ (par). In particular, we concentrate on generalized connectives of a surprisingly simple form, called “entangled connectives”, and prove a characterization theorem giving a criterion for identifying the undecomposable entangled ones.     

Rigid Unary Functions and the Axiom of Choice

We shall investigate certain statements concerning the rigidity of unary functions which have connections with (weak) forms of the axiom of choice.     

Paracompactness of Metric Spaces and the Axiom of Multiple Choice

The axiom of multiple choice implies that metric spaces are paracompact but the reverse implication cannot be proved in set theory without the axiom of choice.     

The Compactness of 2ℝ and the Axiom of Choice

We show that for every we ordered cardinal number m the Tychonoff product 2^m is a compact space without the use of any choice but in Cohen's Second Mode 2^ℝ is not compact.     

Extending Independent Sets to Bases and the Axiom of Choice

We show that the both assertions “in every vector space B over a finite element field every subspace V ? B has a complementary subspace S” and “for every family ?? of disjoint odd sized sets there exists a subfamily ?={F_j:j ?ω} with a choice function” together imply the axiom of choice AC. We also show that AC is equivalent to the statement “in every vector space over ? every generating set includes a basis”.     

Properties of the real line and weak forms of the Axiom of Choice

We investigate, within the framework of Zermelo‐Fraenkel set theory ZF, the interrelations between weak forms of the Axiom of Choice AC restricted to sets of reals. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

The Hahn-Banach Property and the Axiom of Choice

We work in set theory ZF without axiom of choice. Though the Hahn-Banach theorem cannot be proved in ZF, we prove that every Gateaux-differentiable uniformly convex Banach space E satisfies the following continuous Hahn-Banach property: if p is a continuous sublinear functional on E, if F is a subspace of E, and if f: F → ? is a linear functional such that f ≤ p|F then there exists a linear functional g : E → ? such that g extends f and g ≤ p. We also prove that the continuous Hahn-Banach property on a topological vector space E is equivalent to the classical geometrical forms of the Hahn-Banach theorem on E. We then prove that the axiom of Dependent choices DC is equivalent to Ekeland's variational principle, and that it implies the continuous Hahn-Banach property on Gateaux-differentiable Banach spaces. Finally, we prove that, though separable normed spaces satisfy the continuous Hahn-Banach property, they do not satisfy the whole Hahn-Banach property in ZF+DC.     

Filters,Antichains and Towers in Topological Spaces and the Axiom of Choice

We find some characterizations of the Axiom of Choice (AC) in terms of certain families of open sets in T₁ spaces.     

Weak Forms of the Axiom of Choice and the Generalized Continuum Hypothesis

In this paper we study some statements similar to the Partition Principle and the Trichotomy. We prove some relationships between these statements, the Axiom of Choice, and the Generalized Continuum Hypothesis. We also prove some independence results. MSC: 03E25, 03E50, 04A25, 04A50.     

The Vector Space Kinna‐Wagner Principle is Equivalent to the Axiom of Choice

We show that the axiom of choice AC is equivalent to the Vector Space Kinna‐Wagner Principle, i.e., the assertion: “For every family 𝒱= {V_i : i ∈ k} of non trivial vector spaces there is a family ℱ = {F_i : i ∈ k} such that for each i ∈ k, F_i is a non empty independent subset of V_i”. We also show that the statement “every vector space over ℚ has a basis” implies that every infinite well ordered set of pairs has an infinite subset with a choice set, a fact which is known not to be a consequence of the axiom of multiple choice MC.     

A Cut‐free Proof System for Bounded Metric Temporal Logic Over a Dense Time Domain

We present a complete and cut‐free proof‐system for a fragment of MTL, where modal operators are only labelled by bounded intervals with rational endpoints.     

On κ‐hereditary Sets and Consequences of the Axiom of Choice

We will prove that some so‐called union theorems (see [2]) are equivalent in ZF⁰ to statements about the transitive closure of relations. The special case of “bounded” union theorems dealing with κ‐hereditary sets yields equivalents to statements about the transitive closure of κ‐narrow relations. The instance κ = ω₁ (i. e., hereditarily countable sets) yields an equivalent to Howard‐Rubin's Form 172 (the transitive closure Tc(x) of every hereditarily countable set x is countable). In particular, the countable union theorem (Howard‐Rubin's Form 31) and, a fortiori, the axiom of countable choice imply Form 172.     

Arrow's Theorem,Weglorz' Models and the Axiom of Choice

Applying Weglorz' mode s of set theory without the axiom of choice, we investigate Arrow‐type social we fare functions for infinite societies with restricted coalition algebras. We show that there is a reasonable, nondictatorial social welfare function satisfying “finite discrimination”, if and only if in Weglorz' mode there is a free ultrafilter on a set representing the individuals.     

Some Weak Forms of the Axiom of Choice Restricted to the Real Line

It is shown that AC(ℝ), the axiom of choice for families of non‐empty subsets of the real line ℝ, does not imply the statement PW(ℝ), the powerset of ℝ can be well ordered. It is also shown that (1) the statement “the set of all denumerable subsets of ℝ has size 2 ${}^{\text{ℵ}{}_{\text{0}}}$ ” is strictly weaker than AC(ℝ) and (2) each of the statements (i) “if every member of an infinite set of cardinality 2 ${}^{\text{ℵ}{}_{\text{0}}}$ has power 2 ${}^{\text{ℵ}{}_{\text{0}}}$ , then the union has power 2 ${}^{\text{ℵ}{}_{\text{0}}}$ ” and (ii) “ℵ(2 ${}^{\text{ℵ}{}_{\text{0}}}$ ) ≠ ℵ_ω” (ℵ(2 ${}^{\text{ℵ}{}_{\text{0}}}$ ) is Hartogs' aleph, the least ℵ not ≤ 2 ${}^{\text{ℵ}{}_{\text{0}}}$ ), is strictly weaker than the full axiom of choice AC.