0
$\begingroup$

Although ZFC stands tall as the standard set theory, there is no shortage of alternative set theories. Many of which differ on fundamental theories. This has me wondering, assuming first order logic (FOL),

What statements are true within all set theories?

Or in other words,

Which FOL statements are vacuously true, assuming no axioms?


My work: Initially, I thought this was a trivial problem, as for any vacuously true zeroth-order logic statement, like $\phi\implies \phi$, we can substitute $\phi\mapsto a\in a$, (since the atoms of FOL set theory are of the form $x \in y$), then append a universal quantifier such as $$\forall a(a\in a\implies a\in a),$$

and we get a vacuously true statement. I'll call these types of vacuously true statements the "trivial" ones, as it wasn't long before I realized there were less obvious FOL statements which must be vacuously true and are not constructed in this way. A prime example is the statement $$\forall x \exists y(y\in x \iff y\in y).$$ This must be vacuously true, as if it weren't, Russell's Paradox ensues. We can classify these types of non-trivials as follows:

For any condition $\phi(x,w_1,\cdots,w_n)$ which fails as a zeroeth order logic statement if all arguments are the same (i.e; $\neg\phi(x,x,\cdots,x)$) then the statement $$\forall x\exists w_1\cdots \exists w_n[\neg\phi(x,w_1,\cdots,w_n)]$$ is vacuously true. For example, taking $\phi(x,y)\equiv y\in x\iff x\notin x$, as in the example of Russell's Paradox, fails when $x=y$.

Are these the only two methods of producing vacuously true FOL statements of set theory, or are there more?

If so, what is the best way to classify them all?

$\endgroup$

1 Answer 1

3
$\begingroup$

The answer is actually as complicated as it's possible to be. For any pair of sentences $\theta,\varphi$ in the language of set theory, we have that $\theta\rightarrow\varphi$ is a tautology (= provable without using any axioms at all) iff $\theta\vdash\varphi$. But there are quite complicated finitely-axiomatizable theories in the language $\{\in\}$!

In particular, let $T$ be a "large enough" finite subtheory of $\mathsf{ZFC}$. Then we can let $\theta$ be the conjunction of all the axioms of $T$, and the set of set-theoretic tautologies is then at least as complicated as the set of theorems of $T$ - which, since $T$ is "large enough," is as complicated as it could possibly be (namely as complicated as the halting problem).

(As a tangential coda, note that the above fact is related to the fact that, for example, $\mathsf{Q}$ has no decidable subtheories - see here.)

$\endgroup$
1
  • $\begingroup$ That is truly fascinating. Do you know of any resources, or related searchable keywords, which study this sort of thing? I am quite curious of what can be known about axiom-less-theories, particular of set theory. $\endgroup$
    – Graviton
    Nov 17, 2022 at 5:01

You must log in to answer this question.

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