13 found
Order:
See also
Saeed Salehi
University of Tabriz
  1. There May Be Many Arithmetical Gödel Sentences.Kaave Lajevardi & Saeed Salehi - 2021 - Philosophia Mathematica 29 (2):278–287.
    We argue that, under the usual assumptions for sufficiently strong arithmetical theories that are subject to Gödel’s First Incompleteness Theorem, one cannot, without impropriety, talk about *the* Gödel sentence of the theory. The reason is that, without violating the requirements of Gödel’s theorem, there could be a true sentence and a false one each of which is provably equivalent to its own unprovability in the theory if the theory is unsound.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  2.  17
    On Constructivity and the Rosser Property: A Closer Look at Some Gödelean Proofs.Saeed Salehi & Payam Seraji - 2018 - Annals of Pure and Applied Logic 169 (10):971-980.
    The proofs of Kleene, Chaitin and Boolos for Gödel's First Incompleteness Theorem are studied from the perspectives of constructivity and the Rosser property. A proof of the incompleteness theorem has the Rosser property when the independence of the true but unprovable sentence can be shown by assuming only the (simple) consistency of the theory. It is known that Gödel's own proof for his incompleteness theorem does not have the Rosser property, and we show that neither do Kleene's or Boolos' proofs. (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  3.  35
    On the Diagonal Lemma of Gödel and Carnap.Saeed Salehi - 2020 - Bulletin of Symbolic Logic 26 (1):80-88.
    A cornerstone of modern mathematical logic is the diagonal lemma of Gödel and Carnap. It is used in e.g. the classical proofs of the theorems of Gödel, Rosser and Tarski. From its first explication in 1934, just essentially one proof has appeared for the diagonal lemma in the literature; a proof that is so tricky and hard to relate that many authors have tried to avoid the lemma altogether. As a result, some so called diagonal-free proofs have been given for (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  4.  94
    On the Arithmetical Truth of Self‐Referential Sentences.Kaave Lajevardi & Saeed Salehi - 2019 - Theoria 85 (1):8-17.
    We take an argument of Gödel's from his ground‐breaking 1931 paper, generalize it, and examine its validity. The argument in question is this: "the sentence G says about itself that it is not provable, and G is indeed not provable; therefore, G is true".
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  5.  18
    Herbrand Consistency of Some Arithmetical Theories.Saeed Salehi - 2012 - Journal of Symbolic Logic 77 (3):807-827.
    Gödel's second incompleteness theorem is proved for Herbrand consistency of some arithmetical theories with bounded induction, by using a technique of logarithmic shrinking the witnesses of bounded formulas, due to Z. Adamowicz [Herbrand consistency and bounded arithmetic, Fundamenta Mathematical vol. 171 (2002), pp. 279-292]. In that paper, it was shown that one cannot always shrink the witness of a bounded formula logarithmically, but in the presence of Herbrand consistency, for theories I∆₀+ Ωm, with m ≥ 2, any witness for any (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  6.  26
    Provably Total Functions of Basic Arithemtic.Saeed Salehi - 2003 - Mathematical Logic Quarterly 49 (3):316.
    It is shown that all the provably total functions of Basic Arithmetic BA, a theory introduced by Ruitenburg based on Predicate Basic Calculus, are primitive recursive. Along the proof a new kind of primitive recursive realizability to which BA is sound, is introduced. This realizability is similar to Kleene's recursive realizability, except that recursive functions are restricted to primitive recursives.
    Direct download  
     
    Export citation  
     
    Bookmark   3 citations  
  7.  33
    ‘Sometime a Paradox’, Now Proof: Yablo is Not First Order.Saeed Salehi - 2022 - Logic Journal of the IGPL 30 (1):71-77.
    Interesting as they are by themselves in philosophy and mathematics, paradoxes can be made even more fascinating when turned into proofs and theorems. For example, Russell’s paradox, which overthrew Frege’s logical edifice, is now a classical theorem in set theory, to the effect that no set contains all sets. Paradoxes can be used in proofs of some other theorems—thus Liar’s paradox has been used in the classical proof of Tarski’s theorem on the undefinability of truth in sufficiently rich languages. This (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  8.  11
    Tarski’s Undefinability Theorem and the Diagonal Lemma.Saeed Salehi - 2022 - Logic Journal of the IGPL 30 (3):489-498.
    We prove the equivalence of the semantic version of Tarski’s theorem on the undefinability of truth with the semantic version of the diagonal lemma and also show the equivalence of a syntactic version of Tarski’s undefinability theorem with a weak syntactic diagonal lemma. We outline two seemingly diagonal-free proofs for these theorems from the literature and show that the syntactic version of Tarski’s theorem can deliver Gödel–Rosser’s incompleteness theorem.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  9.  34
    Gödel’s Second Incompleteness Theorem: How It is Derived and What It Delivers.Saeed Salehi - 2020 - Bulletin of Symbolic Logic 26 (3-4):241-256.
    The proofs of Gödel (1931), Rosser (1936), Kleene (first 1936 and second 1950), Chaitin (1970), and Boolos (1989) for the first incompleteness theorem are compared with each other, especially from the viewpoint of the second incompleteness theorem. It is shown that Gödel’s (first incompleteness theorem) and Kleene’s first theorems are equivalent with the second incompleteness theorem, Rosser’s and Kleene’s second theorems do deliver the second incompleteness theorem, and Boolos’ theorem is derived from the second incompleteness theorem in the standard way. (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  10.  17
    Intuitionistic Axiomatizations for Bounded Extension Kripke Models.Mohammad Ardeshir, Wim Ruitenburg & Saeed Salehi - 2003 - Annals of Pure and Applied Logic 124 (1-3):267-285.
    We present axiom systems, and provide soundness and strong completeness theorems, for classes of Kripke models with restricted extension rules among the node structures of the model. As examples we present an axiom system for the class of cofinal extension Kripke models, and an axiom system for the class of end-extension Kripke models. We also show that Heyting arithmetic is strongly complete for its class of end-extension models. Cofinal extension models of HA are models of Peano arithmetic.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  11.  65
    Herbrand Consistency of Some Finite Fragments of Bounded Arithmetical Theories.Saeed Salehi - 2013 - Archive for Mathematical Logic 52 (3-4):317-333.
    We formalize the notion of Herbrand Consistency in an appropriate way for bounded arithmetics, and show the existence of a finite fragment of IΔ0 whose Herbrand Consistency is not provable in IΔ0. We also show the existence of an IΔ0-derivable Π1-sentence such that IΔ0 cannot prove its Herbrand Consistency.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  12.  12
    Gödel’s Incompleteness Phenomenon—Computationally.Saeed Salehi - 2014 - Philosophia Scientae 18:23-37.
    We argue that Gödel's completeness theorem is equivalent to completability of consistent theories, and Gödel's incompleteness theorem is equivalent to the fact that this completion is not constructive, in the sense that there are some consistent and recursively enumerable theories which cannot be extended to any complete and consistent and recursively enumerable theory. Though any consistent and decidable theory can be extended to a complete and consistent and decidable theory. Thus deduction and consistency are not decidable in logic, and an (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  13.  17
    Polynomially Bounded Recursive Realizability.Saeed Salehi - 2005 - Notre Dame Journal of Formal Logic 46 (4):407-417.
    A polynomially bounded recursive realizability, in which the recursive functions used in Kleene's realizability are restricted to polynomially bounded functions, is introduced. It is used to show that provably total functions of Ruitenburg's Basic Arithmetic are polynomially bounded (primitive) recursive functions. This sharpens our earlier result where those functions were proved to be primitive recursive. Also a polynomially bounded schema of Church's Thesis is shown to be polynomially bounded realizable. So the schema is consistent with Basic Arithmetic, whereas it is (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   1 citation