2
$\begingroup$

$ST$ is the weak set theory built upon identity theory and containing

  1. the axiom for empty set,
  2. the axiom for adjunction and
  3. the axiom for extensionality.

It is known that $ST$ interprets Robinson Arithmetic, and so $ST$ is incomplete.

Is there a very weak set theory $ST^*$ which is like $ST$ minus the axiom for extensionality, though possibly with some other very weak principles, so that $ST^*$ is incomplete for Gödelian reasons by supporting arithmetization and the definition of a Gödelian provability predicate and the Gödel-Carnap diagonal lemma?

For some notions, cfr. General Set Theory in Wikipedia.

Improve this question
$\endgroup$
10
  • $\begingroup$ Your question confuses me. If ST* is weak, then it will be incomplete, because it will neither prove (nor refute) the axioms of a stronger theory, such as ZFC. $\endgroup$
    – Joel David Hamkins
    Commented Oct 29, 2015 at 12:52
  • $\begingroup$ @Joel David Hamkins The question is whether $ST^*$ is also strong enough to have its own coding so as to have its Gödelian provability predicate. As an example, Presburger Arithmetic is complete, though it will not prove all theorems of the stronger theory Peano Arithmetic. $\endgroup$
    – Frode Alfson Bjørdal
    Commented Oct 29, 2015 at 13:05
  • $\begingroup$ In the usual terminology, a theory $T$ is complete with respect to a language, if for every sentence $\sigma$ in that language, either $T\vdash\sigma$ or $T\vdash\neg\sigma$ (some people also insist that $T$ should be consistent). In this terminology, although Presburger arithmetic is complete in the language of addition, it is not complete in the language of arithmetic, because it neither proves nor refutes the axioms of PA. In your case, are you proposing to change the language of set theory? If not, then your weak theory will be incomplete, whether or not it supports coding. $\endgroup$
    – Joel David Hamkins
    Commented Oct 29, 2015 at 13:18
  • $\begingroup$ @Joel David Hamkins I see that point. However, I want the theory $ST^*$ to be incomplete for Gödelian reasons; more precisely, it is the possibility to define the Gödelian provability predicate and derive the Gödel-Carnap diagonal lemma in $ST^*$ which is the center of my attention. $\endgroup$
    – Frode Alfson Bjørdal
    Commented Oct 29, 2015 at 13:23
  • 1
    $\begingroup$ It is well known that ST^* (with no additional principles) interprets Robinson's arithmetic, see e.g. Section 3.3 in Albert Visser's "Pairs, Sets and Sequences in First Order Theories". $\endgroup$
    – Emil Jeřábek
    Commented Oct 29, 2015 at 14:52

1 Answer 1

Reset to default
3
$\begingroup$

$\newcommand\ST{\text{ST}}$Here is an example of a set theory $\ST^*$ with your properties. Let $\ST^*$ be the theory that is just like $\ST$, but it asserts extensionality only for nonempty sets. So $\ST^*$ is consistent with the existence of multiple empty sets, and therefore it does not prove extensionality. But we can interpret $\ST$ in $\ST^*$, simply by using only one of the empty sets (and restricting to those sets that do not use the other one in their transitive closures), or alternatively, by identifying the two empty sets hereditarily.

So this is a weak set theory, a proper subtheory of $\ST$, which does not prove extensionality, but which still supports coding.

There are many other similar such theories, by allowing extensionality to be violated in a controlled manner, in such a way that you can still interpret $\ST$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for this! I am interested in some theory where extensionality fails utterly. May one achieve this by bisimulation, I wonder. In other words: if $ST^-$ is $ST$ minus extensionality, may it be that $ST^-$ interprets $ST$ or enough of $ST$ to arithmetize? \vspace{2pt} On the other hand. The sets created by adjunction over one empty set only invoke identity, and I do not have problems with identity. So it seems that I can accept the controlled manner you invoke for doing the coding ... $\endgroup$
    – Frode Alfson Bjørdal
    Commented Oct 29, 2015 at 13:55
  • $\begingroup$ Well, you could have a theory that says ST holds on a part of the universe, and then there is another part which may be totally crazy, with extensionality failing utterly there. This would still support coding, because of the sane part. $\endgroup$
    – Joel David Hamkins
    Commented Oct 29, 2015 at 14:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .