Three-valued logic and cut-elimination: The actual meaning of Takeuti's conjecture

J. Y. Girard

Displaying similar documents to “Three-valued logic and cut-elimination: The actual meaning of Takeuti's conjecture”

A Hanf number for saturation and omission

John T. Baldwin, Saharon Shelah (2011)

Fundamenta Mathematicae

Similarity:

Suppose t = (T,T₁,p) is a triple of two countable theories T ⊆ T₁ in vocabularies τ ⊂ τ₁ and a τ₁-type p over the empty set. We show that the Hanf number for the property ’there is a model M₁ of T₁ which omits p, but M₁ ↾ τ is saturated’ is essentially equal to the Löwenheim number of second order logic. In Section 4 we make exact computations of these Hanf numbers and note some distinctions between ’first order’ and ’second order quantification’. In particular, we show that if κ is...

On normalization of proofs in set theory

Lars Hallnäs

Similarity:

CONTENTSIntroduction..............................................................................................................................................5I. Naive set theory.....................................................................................................................................61. The formal system................................................................................................................................62. Inversion and reduction...

Formally self-referential propositions for cut free classical analysis and related systems

G. Kreisel, G. Takeuti

Similarity:

CONTENTSIntroduction............................................................................................................................................................................................................ 5 I. Results on self-referential propositions............................................................................................................................. 11 1. Definitions of some principal metamathematical notions......................................................................

Completeness properties of classical theories of finite type and the normal form theorem

Peter Päppinghaus

Similarity:

CONTENTSIntroduction........................................................................................................................................................................................................................50. Terminology and preliminaries......................................................................................................................................................................................121. The extent of cut elimination by...

Diagonalization in proof complexity

Jan Krajíček (2004)

Fundamenta Mathematicae

Similarity:

We study diagonalization in the context of implicit proofs of [10]. We prove that at least one of the following three conjectures is true: ∙ There is a function f: 0,1* → 0,1 computable in that has circuit complexity $2^{Ω (n)}$ . ∙ ≠ co . ∙ There is no p-optimal propositional proof system. We note that a variant of the statement (either ≠ co or ∩ co contains a function $2^{Ω (n)}$ hard on average) seems to have a bearing on the existence of good proof complexity generators. In particular, we prove that...

Selection principles and upper semicontinuous functions

Masami Sakai (2009)

Colloquium Mathematicae

Similarity:

In connection with a conjecture of Scheepers, Bukovský introduced properties wQN* and SSP* and asked whether wQN* implies SSP*. We prove it in this paper. We also give characterizations of properties S₁(Γ,Ω) and $S_{f i n} (Γ, Ω)$ in terms of upper semicontinuous functions

$α$ -continuous multivalued maps

J. Eweret (1989)

Matematički Vesnik

Similarity:

Propositional extensions of $L_{ω} 1_{ω}$

Richard Gostanian, Karel Hrbacek

Similarity:

CONTENTS0. Preliminaries....................................................................... 71. Adding propositional connectives to $L_{ω} 1_{ω}$ ............... 82. The propositional part of $L_{ω} 1_{ω}$ (S)............................. 103. The operation S and the Boolean algebra $B_{S}$ ............... 114. General model-theoretic properties of $L_{ω} 1_{ω}$ (S)...... 175. Hanf number computations...................................................... 226. Negative results for $L_{ω} 1_{ω}$ (S)...........................................

On a number theoretic conjecture on positive integral points in a 5-dimensional tetrahedron and a sharp estimate of the Dickman–De Bruijn function

Ke-Pao Lin, Xue Luo, Stephen S.-T. Yau, Huaiqing Zuo (2014)

Journal of the European Mathematical Society

Similarity:

It is well known that getting the estimate of integral points in right-angled simplices is equivalent to getting the estimate of Dickman-De Bruijn function $ψ (x, y)$ which is the number of positive integers $\leq x$ and free of prime factors $> y$ . Motivating from the Yau Geometry Conjecture, the third author formulated the Number Theoretic Conjecture which gives a sharp polynomial upper estimate that counts the number of positive integral points in n-dimensional ( $n \geq 3$ ) real right-angled simplices. In this...

Uncountable cardinals have the same monadic ∀₁¹ positive theory over large sets

Athanassios Tzouvaras (2004)

Fundamenta Mathematicae

Similarity:

We show that uncountable cardinals are indistinguishable by sentences of the monadic second-order language of order of the form (∀X)ϕ(X) and (∃X)ϕ(X), for ϕ positive in X and containing no set-quantifiers, when the set variables range over large (= cofinal) subsets of the cardinals. This strengthens the result of Doner-Mostowski-Tarski [3] that (κ,∈), (λ,∈) are elementarily equivalent when κ, λ are uncountable. It follows that we can consistently postulate that the structures $(2^{κ}, {[2^{κ}]}^{> κ}, <)$ , $(2^{λ}, {[2^{λ}]}^{> λ}, <)$ are...

Characterizing the powerset by a complete (Scott) sentence

Ioannis Souldatos (2013)

Fundamenta Mathematicae

Similarity:

This paper is part II of a study on cardinals that are characterizable by a Scott sentence, continuing previous work of the author. A cardinal κ is characterized by a Scott sentence $ϕ_{ℳ}$ if $ϕ_{ℳ}$ has a model of size κ, but no model of size κ⁺. The main question in this paper is the following: Are the characterizable cardinals closed under the powerset operation? We prove that if $ℵ_{β}$ is characterized by a Scott sentence, then $2^{ℵ_{β + β ₁}}$ is (homogeneously) characterized by a Scott sentence, for all 0 <...

Greenberg’s conjecture for $ℤ_{p}^{d}$ -extensions

Andrea Bandini (2003)

Acta Arithmetica

Similarity:

On the Brocard-Ramanujan problem and generalizations

Andrzej Dąbrowski (2012)

Colloquium Mathematicae

Similarity:

Let $p_{i}$ denote the ith prime. We conjecture that there are precisely 28 solutions to the equation $n ² - 1 = p ₁^{α ₁} \dots p_{k}^{α_{k}}$ in positive integers n and α₁,..., $α_{k}$ . This conjecture implies an explicit description of the set of solutions to the Brocard-Ramanujan equation. We also propose another variant of the Brocard-Ramanujan problem: describe the set of solutions in non-negative integers of the equation n! + A = x₁²+x₂²+x₃² (A fixed).

On coarse embeddability into $ℓ_{p}$ -spaces and a conjecture of Dranishnikov

Piotr W. Nowak (2006)

Fundamenta Mathematicae

Similarity:

We show that the Hilbert space is coarsely embeddable into any $ℓ_{p}$ for 1 ≤ p ≤ ∞. It follows that coarse embeddability into ℓ₂ and into $ℓ_{p}$ are equivalent for 1 ≤ p < 2.

Subfields of henselian valued fields

Ramneek Khassa, Sudesh K. Khanduja (2010)

Colloquium Mathematicae

Similarity:

Let (K,v) be a henselian valued field of arbitrary rank which is not separably closed. Let k be a subfield of K of finite codimension and $v_{k}$ be the valuation obtained by restricting v to k. We give some necessary and sufficient conditions for $(k, v_{k})$ to be henselian. In particular, it is shown that if k is dense in its henselization, then $(k, v_{k})$ is henselian. We deduce some well known results proved in this direction through other considerations.

Car-Pólya and Gel’fond’s theorems for $_{q} [T]$

David Adam (2004)

Acta Arithmetica

Similarity:

On fixed point free involutions of $R^{1} \times S^{2}$

Gerhard X. Ritter (1976)

Colloquium Mathematicae

Similarity:

A López-Escobar theorem for metric structures, and the topological Vaught conjecture

Samuel Coskey, Martino Lupini (2016)

Fundamenta Mathematicae

Similarity:

We show that a version of López-Escobar’s theorem holds in the setting of model theory for metric structures. More precisely, let denote the Urysohn sphere and let Mod(,) be the space of metric -structures supported on . Then for any Iso()-invariant Borel function f: Mod(,) → [0,1], there exists a sentence ϕ of $_{ω ₁ ω}$ such that for all M ∈ Mod(,) we have $f (M) = ϕ^{M}$ . This answers a question of Ivanov and Majcher-Iwanow. We prove several consequences, for example every orbit equivalence relation of...

Products of n open subsets in the space of continuous functions on [0,1]

Ehrhard Behrends (2011)

Studia Mathematica

Similarity:

Let O₁,...,Oₙ be open sets in C[0,1], the space of real-valued continuous functions on [0,1]. The product O₁ ⋯ Oₙ will in general not be open, and in order to understand when this can happen we study the following problem: given f₁,..., fₙ ∈ C[0,1], when is it true that f₁ ⋯ fₙ lies in the interior of $B_{ε} (f ₁) \dots B_{ε} (f ₙ)$ for all ε > 0 ? ( $B_{ε}$ denotes the closed ball with radius ε and centre f.) The main result of this paper is a characterization in terms of the walk t ↦ γ(t): = (f₁(t),..., fₙ(t)) in ℝⁿ....

Recent progress on the Jacobian Conjecture

Michiel de Bondt, Arno van den Essen (2005)

Annales Polonici Mathematici

Similarity:

We describe some recent developments concerning the Jacobian Conjecture (JC). First we describe Drużkowski’s result in [6] which asserts that it suffices to study the JC for Drużkowski mappings of the form $x + {(A x)}^{* 3}$ with A² = 0. Then we describe the authors’ result of [2] which asserts that it suffices to study the JC for so-called gradient mappings, i.e. mappings of the form x - ∇f, with $f \in k^{[n]}$ homogeneous of degree 4. Using this result we explain Zhao’s reformulation of the JC which asserts the...

The decidability of some $ℵ_{0}$ -categorical theories

James H. Schmerl (1976)

Colloquium Mathematicae

Similarity:

Some remarks providing discontinuous maps on some $C_{p} (X)$ spaces

S. Moll (2008)

Banach Center Publications

Similarity:

Let X be a completely regular Hausdorff topological space and $C_{p} (X)$ the space of continuous real-valued maps on X endowed with the pointwise topology. A simple and natural argument is presented to show how to construct on the space $C_{p} (X)$ , if X contains a homeomorphic copy of the closed interval [0,1], real-valued maps which are everywhere discontinuous but continuous on all compact subsets of $C_{p} (X)$ .

A generalization of a formalized theory of fields of sets on non-classical logics

Helena Rasiowa

Similarity:

Contents Introduction.................................................................................................................................................. 3 § 1. System $𝒮$ of a propositional calculus...................................................................... 4 § 2. System $𝒮 *$ ..................................................................................................................... 5 § 3. $𝒮 *$ -algebras.....................................................................................................................

General operators binding variables in the interpreted modal calculus $\mathcal{MC}^{\nu}$

Aldo Bressan, Alberto Zanardo (1981)

Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti Lincei. Matematica e Applicazioni

Similarity:

Si considera il calcolo modale interpretato $\mathcal{MC}^{\nu}$ , che è basato su un sistema di tipi con infiniti livelli, contiene descrizioni, ed è dotato di una semantica di tipo generale - v. [2], o [3], o [4], o [5]. In modo semplice e naturale si introducono in $\mathcal{MC}^{\nu}$ operatori vincolanti variabili, di tipo generale. Per teorie basate sul calcolo logico risultante $\mathcal{MC}^{\nu}$ vale un teorema di completezza, che si dimostra in modo immediato sulla base dell'estensione del teorema parziale di completezza stabilito...

A note on Nakai’s conjecture for the ring $K [X ₁, . . ., X ₙ] / (a ₁ X ₁^{m} + \dots + a ₙ X ₙ^{m})$

Paulo Roberto Brumatti, Marcelo Oliveira Veloso (2011)

Colloquium Mathematicae

Similarity:

$H^{\infty}$ functional calculus for sectorial and bisectorial operators

Giovanni Dore, Alberto Venni (2005)

Studia Mathematica

Similarity:

We give a concise exposition of the basic theory of $H^{\infty}$ functional calculus for N-tuples of sectorial or bisectorial operators, with respect to operator-valued functions; moreover we restate and prove in our setting a result of N. Kalton and L. Weis about the boundedness of the operator $f (T ₁, . . ., T_{N})$ when f is an R-bounded operator-valued holomorphic function.

Banach-space-valued stationary processes and their linear prediction

S. A. Chobanyan, A. Weron

Similarity:

Contents0. Introduction............................................................................................................................................. 51. Linear operators generated by random elements.......................................................................... 62. Covariance operator of generalized random elements................................................................. 93. The space of generalized random elements of the second-order as an LVH-space.................