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...

A Kalmár-style completeness proof for the logics of the hierarchy $𝕀^{n} ℙ^{k}$

Víctor Fernández (2023)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

The logics of the family $𝕀^{n} ℙ^{k}$ := ${I^{n} P^{k}}_{(n, k) \in ω^{2}}$ are formally defined by means of finite matrices, as a simultaneous generalization of the weakly-intuitionistic logic $I^{1}$ and of the paraconsistent logic $P^{1}$ . It is proved that this family can be naturally ordered, and it is shown a sound and complete axiomatics for each logic of the form $I^{n} P^{k}$ . The involved completeness proof showed here is obtained by means of a generalization of the well-known Kalmár’s method, usually applied for many-valued logics.

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...

On the generalized vanishing conjecture

Zhenzhen Feng, Xiaosong Sun (2019)

Czechoslovak Mathematical Journal

Similarity:

We show that the GVC (generalized vanishing conjecture) holds for the differential operator $Λ = (\partial_{x} - Φ (\partial_{y})) \partial_{y}$ and all polynomials $P (x, y)$ , where $Φ (t)$ is any polynomial over the base field. The GVC arose from the study of the Jacobian conjecture.

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:

A topological duality for the $F$ -chains associated with the logic $C_{ω}$

Verónica Quiroga, Víctor Fernández (2017)

Mathematica Bohemica

Similarity:

In this paper we present a topological duality for a certain subclass of the $F_{ω}$ -structures defined by M. M. Fidel, which conform to a non-standard semantics for the paraconsistent N. C. A. da Costa logic $C_{ω}$ . Actually, the duality introduced here is focused on $F_{ω}$ -structures whose supports are chains. For our purposes, we characterize every $F_{ω}$ -chain by means of a new structure that we will call (DCC) here. This characterization will allow us to prove the dual equivalence between the category...

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:

A geometric construction for spectrally arbitrary sign pattern matrices and the $2 n$ -conjecture

Dipak Jadhav, Rajendra Deore (2023)

Czechoslovak Mathematical Journal

Similarity:

We develop a geometric method for studying the spectral arbitrariness of a given sign pattern matrix. The method also provides a computational way of computing matrix realizations for a given characteristic polynomial. We also provide a partial answer to $2 n$ -conjecture. We determine that the $2 n$ -conjecture holds for the class of spectrally arbitrary patterns that have a column or row with at least $n - 1$ nonzero entries.

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).

Results related to Huppert’s $ρ$ - $σ$ conjecture

Xia Xu, Yong Yang (2023)

Czechoslovak Mathematical Journal

Similarity:

We improve a few results related to Huppert’s $ρ$ - $σ$ conjecture. We also generalize a result about the covering number of character degrees to arbitrary finite groups.

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...