Skip to main content
Delta_0 separation is okay to assume too
Source Link
Mike Shulman
  • 66.8k
  • 7
  • 162
  • 368

In ordinary membership-based set theory, the axiom schema of replacement states that if $\phi$ is a first-order formula, and $A$ is a set such that for any $x\in A$ there exists a unique $y$ such that $\phi(x,y)$, then there exists a set $B$ such that $y\in B$ if and only if $\phi(x,y)$ for some $x\in A$. That is, $B$ is the "image" of $A$ under the "definable class function" $\phi$.

The related axiom schema of collection modifies this by not requiring $y$ to be unique, but only requiring $B$ to contain some $y$ for each $x$ rather than all of them. However, there are at least two different versions of this.

  1. If for all $x\in A$ there exists a $y$ with $\phi(x,y)$, then there exists a set $B$ such that for all $x\in A$ there is a $y\in B$ with $\phi(x,y)$ (this is Wikipedia's version; I'll call it "weak collection").

  2. If for all $x\in A$ there exists a $y$ with $\phi(x,y)$, then there exists a set $B$ such that (1) for all $x\in A$ there is a $y\in B$ with $\phi(x,y)$, and (2) for all $y\in B$ there is an $x\in A$ with $\phi(x,y)$ (I'll call this "strong collection").

The third possibly relevant axiom is the axiom schema of separation, which states that for any $\phi$ and any set $A$ there exists a set $B\subseteq A$ such that $x\in B$ if and only if $x\in A$ and $\phi(x)$.

I know the following implications between these axioms:

  • Strong collection implies weak collection, since it has the same hypotheses and a stronger conclusion.
  • Strong collection implies replacement, since it has a weaker hypothesis and the same conclusion.
  • Replacement implies separation (assuming excluded middle): apply replacement to the formula "($\phi(x)$ and $y=\lbrace x\rbrace$) or ($\neg\phi(x)$ and $y=\emptyset$)" and take the union of the resulting set.
  • Together with AC and foundation, replacement implies weak collection: let $\psi(x,V)$ assert that $V=V_\alpha$ is the smallest level of the von Neumann hierarchy such that there exists a $y\in V_\alpha$ with $\phi(x,y)$, apply replacement to $\psi$ and take the union of all the resulting $V_\alpha$.
  • Weak collection and separation together imply strong collection: separation cuts out the subset of $B$ consisting of those $y$ such that $\phi(x,y)$ for some $x\in A$.

My question is: does weak collection imply replacement (and hence also separation and strong collection) without assuming separation to hold a priori? Feel free to assume all the other axioms of ZFC (including $\Delta_0$-separation). I'm fairly sure the answer is "no," but several sources I've read seem to assume that it does. Can someone give a definitive answer, and ideally a reference?

In ordinary membership-based set theory, the axiom schema of replacement states that if $\phi$ is a first-order formula, and $A$ is a set such that for any $x\in A$ there exists a unique $y$ such that $\phi(x,y)$, then there exists a set $B$ such that $y\in B$ if and only if $\phi(x,y)$ for some $x\in A$. That is, $B$ is the "image" of $A$ under the "definable class function" $\phi$.

The related axiom schema of collection modifies this by not requiring $y$ to be unique, but only requiring $B$ to contain some $y$ for each $x$ rather than all of them. However, there are at least two different versions of this.

  1. If for all $x\in A$ there exists a $y$ with $\phi(x,y)$, then there exists a set $B$ such that for all $x\in A$ there is a $y\in B$ with $\phi(x,y)$ (this is Wikipedia's version; I'll call it "weak collection").

  2. If for all $x\in A$ there exists a $y$ with $\phi(x,y)$, then there exists a set $B$ such that (1) for all $x\in A$ there is a $y\in B$ with $\phi(x,y)$, and (2) for all $y\in B$ there is an $x\in A$ with $\phi(x,y)$ (I'll call this "strong collection").

The third possibly relevant axiom is the axiom schema of separation, which states that for any $\phi$ and any set $A$ there exists a set $B\subseteq A$ such that $x\in B$ if and only if $x\in A$ and $\phi(x)$.

I know the following implications between these axioms:

  • Strong collection implies weak collection, since it has the same hypotheses and a stronger conclusion.
  • Strong collection implies replacement, since it has a weaker hypothesis and the same conclusion.
  • Replacement implies separation (assuming excluded middle): apply replacement to the formula "($\phi(x)$ and $y=\lbrace x\rbrace$) or ($\neg\phi(x)$ and $y=\emptyset$)" and take the union of the resulting set.
  • Together with AC and foundation, replacement implies weak collection: let $\psi(x,V)$ assert that $V=V_\alpha$ is the smallest level of the von Neumann hierarchy such that there exists a $y\in V_\alpha$ with $\phi(x,y)$, apply replacement to $\psi$ and take the union of all the resulting $V_\alpha$.
  • Weak collection and separation together imply strong collection: separation cuts out the subset of $B$ consisting of those $y$ such that $\phi(x,y)$ for some $x\in A$.

My question is: does weak collection imply replacement (and hence also separation and strong collection) without assuming separation to hold a priori? Feel free to assume all the other axioms of ZFC. I'm fairly sure the answer is "no," but several sources I've read seem to assume that it does. Can someone give a definitive answer, and ideally a reference?

In ordinary membership-based set theory, the axiom schema of replacement states that if $\phi$ is a first-order formula, and $A$ is a set such that for any $x\in A$ there exists a unique $y$ such that $\phi(x,y)$, then there exists a set $B$ such that $y\in B$ if and only if $\phi(x,y)$ for some $x\in A$. That is, $B$ is the "image" of $A$ under the "definable class function" $\phi$.

The related axiom schema of collection modifies this by not requiring $y$ to be unique, but only requiring $B$ to contain some $y$ for each $x$ rather than all of them. However, there are at least two different versions of this.

  1. If for all $x\in A$ there exists a $y$ with $\phi(x,y)$, then there exists a set $B$ such that for all $x\in A$ there is a $y\in B$ with $\phi(x,y)$ (this is Wikipedia's version; I'll call it "weak collection").

  2. If for all $x\in A$ there exists a $y$ with $\phi(x,y)$, then there exists a set $B$ such that (1) for all $x\in A$ there is a $y\in B$ with $\phi(x,y)$, and (2) for all $y\in B$ there is an $x\in A$ with $\phi(x,y)$ (I'll call this "strong collection").

The third possibly relevant axiom is the axiom schema of separation, which states that for any $\phi$ and any set $A$ there exists a set $B\subseteq A$ such that $x\in B$ if and only if $x\in A$ and $\phi(x)$.

I know the following implications between these axioms:

  • Strong collection implies weak collection, since it has the same hypotheses and a stronger conclusion.
  • Strong collection implies replacement, since it has a weaker hypothesis and the same conclusion.
  • Replacement implies separation (assuming excluded middle): apply replacement to the formula "($\phi(x)$ and $y=\lbrace x\rbrace$) or ($\neg\phi(x)$ and $y=\emptyset$)" and take the union of the resulting set.
  • Together with AC and foundation, replacement implies weak collection: let $\psi(x,V)$ assert that $V=V_\alpha$ is the smallest level of the von Neumann hierarchy such that there exists a $y\in V_\alpha$ with $\phi(x,y)$, apply replacement to $\psi$ and take the union of all the resulting $V_\alpha$.
  • Weak collection and separation together imply strong collection: separation cuts out the subset of $B$ consisting of those $y$ such that $\phi(x,y)$ for some $x\in A$.

My question is: does weak collection imply replacement (and hence also separation and strong collection) without assuming separation to hold a priori? Feel free to assume all the other axioms of ZFC (including $\Delta_0$-separation). I'm fairly sure the answer is "no," but several sources I've read seem to assume that it does. Can someone give a definitive answer, and ideally a reference?

Source Link
Mike Shulman
  • 66.8k
  • 7
  • 162
  • 368

When does collection imply replacement?

In ordinary membership-based set theory, the axiom schema of replacement states that if $\phi$ is a first-order formula, and $A$ is a set such that for any $x\in A$ there exists a unique $y$ such that $\phi(x,y)$, then there exists a set $B$ such that $y\in B$ if and only if $\phi(x,y)$ for some $x\in A$. That is, $B$ is the "image" of $A$ under the "definable class function" $\phi$.

The related axiom schema of collection modifies this by not requiring $y$ to be unique, but only requiring $B$ to contain some $y$ for each $x$ rather than all of them. However, there are at least two different versions of this.

  1. If for all $x\in A$ there exists a $y$ with $\phi(x,y)$, then there exists a set $B$ such that for all $x\in A$ there is a $y\in B$ with $\phi(x,y)$ (this is Wikipedia's version; I'll call it "weak collection").

  2. If for all $x\in A$ there exists a $y$ with $\phi(x,y)$, then there exists a set $B$ such that (1) for all $x\in A$ there is a $y\in B$ with $\phi(x,y)$, and (2) for all $y\in B$ there is an $x\in A$ with $\phi(x,y)$ (I'll call this "strong collection").

The third possibly relevant axiom is the axiom schema of separation, which states that for any $\phi$ and any set $A$ there exists a set $B\subseteq A$ such that $x\in B$ if and only if $x\in A$ and $\phi(x)$.

I know the following implications between these axioms:

  • Strong collection implies weak collection, since it has the same hypotheses and a stronger conclusion.
  • Strong collection implies replacement, since it has a weaker hypothesis and the same conclusion.
  • Replacement implies separation (assuming excluded middle): apply replacement to the formula "($\phi(x)$ and $y=\lbrace x\rbrace$) or ($\neg\phi(x)$ and $y=\emptyset$)" and take the union of the resulting set.
  • Together with AC and foundation, replacement implies weak collection: let $\psi(x,V)$ assert that $V=V_\alpha$ is the smallest level of the von Neumann hierarchy such that there exists a $y\in V_\alpha$ with $\phi(x,y)$, apply replacement to $\psi$ and take the union of all the resulting $V_\alpha$.
  • Weak collection and separation together imply strong collection: separation cuts out the subset of $B$ consisting of those $y$ such that $\phi(x,y)$ for some $x\in A$.

My question is: does weak collection imply replacement (and hence also separation and strong collection) without assuming separation to hold a priori? Feel free to assume all the other axioms of ZFC. I'm fairly sure the answer is "no," but several sources I've read seem to assume that it does. Can someone give a definitive answer, and ideally a reference?