# Is Extensionality needed for the incompleteness of very weak set theories?

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

• 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. – Joel David Hamkins Oct 29 '15 at 12:52
• @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. – Frode Bjørdal Oct 29 '15 at 13:05
• 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. – Joel David Hamkins Oct 29 '15 at 13:18
• @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. – Frode Bjørdal Oct 29 '15 at 13:23
• 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". – Emil Jeřábek Oct 29 '15 at 14:52

$\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$.
• 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 ... – Frode Bjørdal Oct 29 '15 at 13:55
• Would I need as an axiomatic principle something like $C(x)\leftrightarrow (x=\{y|y\neq y\}\vee\exists y, z(C(y)\wedge C(z)\wedge x=\{w|w\in y\vee w= z\})$? – Frode Bjørdal Oct 29 '15 at 14:09