4
$\begingroup$

In this question we assume that all formulae are in the language of $\sf ZFC$ and that $\sf ZFC$ is consistent.

Recall that we say that a formula $\varphi(x,y)$ represents a set-like class relation iff for every $x$ the class of all $y$ such that $\varphi(x,y)$ forms a set (for example, $y\in x,\,y\subset x,\,x=y,\,y=\varnothing$ are set-like, but $x\in y,\,x\ne y,\,x=x$ are not).

Consider the following proposition schema (we may call it the Schema of Transitive Closure for set-like relations):

For every set-like relation $\varphi$ and every set $u$ there is a set $v$ that is a superset of $u$ and is closed under $\varphi$. More formally, if $\varphi$ does not have any of the variables $z, u, v$ free, $$\forall x\exists z\forall y\left[\varphi(x,y)\Rightarrow y\in z\right]\,\Rightarrow\,\forall u\exists v\left[u\subseteq v\land\forall x\forall y\left(x\in v\land\varphi(x,y)\Rightarrow y\in v\right)\right]$$

If we add this schema as an axiom and drop the usual axioms of Pair, Union, Infinity and Replacement, can we prove the dropped axioms as theorems in this theory? Is this theory equivalent to $\sf ZFC$?

$\endgroup$
  • $\begingroup$ This is off-topic, but I find the name somewhat missleading. Neither $u$ nor the relation $(u, \{(x,y) \mid x \in u \wedge y \in u \wedge \phi(x,y) \})$ is transitive in general. While I'm not happy with it either, I'd prefer something along the lines of "Schema of Set-Like Closure" or "Schema of Transitive Hulls". $\endgroup$ – Stefan Mesken Mar 6 '16 at 6:30
  • $\begingroup$ Let me also add to the off topic comment by @Stefan, usually set-like means that $\varphi(\cdot,x)$ is a set for all $x$, rather than $\varphi(x,\cdot)$. You can remember this by noting that $x\in y$ is set-like, but not according to your definition. $\endgroup$ – Asaf Karagila Mar 6 '16 at 13:30
  • $\begingroup$ @AsafKaragila I agree that the opposite order of parameters would look more natural. I was just following the definition from the Wikipedia. $\endgroup$ – Vladimir Reshetnikov Mar 6 '16 at 17:57
  • $\begingroup$ Then you misread the definition, since Wikipedia is in agreement with me. $\endgroup$ – Asaf Karagila Mar 7 '16 at 7:03
  • $\begingroup$ @AsafKaragila Yes, you are right. My mistake. $\endgroup$ – Vladimir Reshetnikov Mar 7 '16 at 17:41
3
$\begingroup$

This is certainly a consequence of ZFC: for $\varphi$ set-like and "initial set" $u$, we can define by induction the sets $u_n$ for each $n\in\omega$ as $u_0=u$, $u_{n+1}=u_n\cup\{y: \exists x\in u_n(\varphi(x, y))\}$; and we can show that the sequence $\langle u_i\rangle_{i\in\omega}$ exists (and hence the desired "$u_\omega$") by Replacement.

As to its consequences:

  • It implies Replacement over $Z$: given an instance $\varphi, u$ of Replacement, consider the formula $\varphi'$ gotten by restricting $\varphi$ to $u$.

  • It implies Infinity over $Z-Inf$: take $\varphi$ to define the ordinal successor (if the input is an ordinal, and $0$ otherwise), and apply to $\{\emptyset\}$.

Now let "$(*)$" be "For all $x$, $\{x\}$ is a set." Note that $(*)$ is usually proved by Pairing; in lieu of Pairing, it sees we need $(*)$ to do anything interesting:

  • It implies Pairing over Separation + $(*)$: given $a, b$, consider $\varphi: x\mapsto b$, applied to $\{a\}$.

  • It implies Union over $(*)$ + Separation: consider the formula $\varphi(a, b)\iff b\in a$.

$\endgroup$
  • 1
    $\begingroup$ Thanks! It looks like $(*)$ follows from Powerset + Separation. $\{x\}\subset\mathcal P(x)$. $\endgroup$ – Vladimir Reshetnikov Mar 5 '16 at 21:21
  • $\begingroup$ @VladimirReshetnikov That's right, I misread your question and thought you were also interested in getting rid of Powerset. $\endgroup$ – Noah Schweber Mar 5 '16 at 21:36
  • $\begingroup$ So, by taking the Extensionality, Foundation, Separation, Powerset, Choice and the Transitive Closure as axioms, we get a theory equivalent to $\sf ZFC$, right? $\endgroup$ – Vladimir Reshetnikov Mar 5 '16 at 21:44
  • $\begingroup$ @VladimirReshetnikov Yup, looks like it. $\endgroup$ – Noah Schweber Mar 5 '16 at 21:46
  • 1
    $\begingroup$ @Vladimir: These axioms are not ad hoc at all. They come to describe our intuitive understanding of what sets should do. For example, there is an infinite set, the natural numbers are an infinite set and we expect this to hold in the universe of sets. We also expect our universe to be closed under unions, because if we have a set of sets, we expect the union to be a set also. And so on. $\endgroup$ – Asaf Karagila Mar 6 '16 at 5:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.