If I were to add the axiom schema of (restricted) comprehension to my "reduced" set theory, would I be able to prove any new propositions?

138 Views Asked by At

Suppose I had the following axioms: extensionality, nullset, pairs, unions, and powerset. Would adding comprehension (the axiom of separation) allow me to prove any new propositions? If so, could you provide an example?

1

There are 1 best solutions below

4
On BEST ANSWER

Let's write $T$ for your "reduced set theory": extensionality, nullset, pairs, unions, and powerset. And let's write $\text{Inf}$ for the axiom of infinity and $\text{Comp}$ for the schema of comprehension.

Now for any sentence $\varphi$, just by basic logic, we have $$T+\text{Inf}\vdash \varphi \quad \text{if and only if} \quad T\vdash \text{Inf}\rightarrow \varphi.$$ And $$T+\text{Inf}+\text{Comp}\vdash \varphi \quad \text{if and only if} \quad T+\text{Comp}\vdash \text{Inf}\rightarrow \varphi.$$

I assume you agree that the schema of comprehension allows $T+\text{Inf}$ to prove new propositions. So if we let $\varphi$ be some sentence such that $T+\text{Inf}+\text{Comp}\vdash \varphi$ and $T+\text{Inf}\not\vdash \varphi$, then we have $T+\text{Comp}\vdash \text{Inf}\rightarrow \varphi$ and $T\not\vdash \text{Inf}\rightarrow \varphi$.

So yes, adding the schema of comprehension to $T$ does allow us to prove new propositions.

A more interesting question is whether the theory $T+\lnot\text{Inf}$ (with the negation of the axiom of infinity) proves all instances of the comprehension schema. I agree that intuitively it should... but this might be sensitive to exactly how one phrases the infinity axiom...