It has come to my attention that the pairing axiom and the separation axiom schema are rarely listed since they follows from the replacement axioms. I see how this works for the pairing axiom, since we can take some set, say $A=\{\emptyset,\{\emptyset\}\}$, which exists by the power set axiom and the existence of the emptyset, and define a nominating formula on $A$ by $ \phi(u,v)\colon (u=\emptyset\land v=a)\lor(u\neq\emptyset\land v=b) $ to see that $\{a,b\}$ is a set for any sets $a$ and $b$. However, I don't see it for the separation schema. Could someone enlighten me on how they follow? Thanks.
How do the separation axioms follow from the replacement axioms?
4 Answers
The replacement axiom (axiom scheme) is the most general form you need, essentially saying that if you have a function whose domain is a set then the image is also a set. Furthermore, the empty set can be inferred by an existence of any set at all, when combined with separation (and hence, can be inferred by replacement).
Formally speaking the replacement schema says that for every formula $\varphi(u,v,p_1,\ldots,p_n)$, fix the parameters $p_1,\ldots,p_n$ and pick any set $A$, whenever $u\in A$ has at most one $v$ for which $\varphi(u,v,p_1,\ldots,p_n)$ is true, then the collection of $\{v\mid\varphi(u,v,p_1,\ldots,p_n), u\in A\}$ is also a set.
How to infer separation and pairing? Simple.
First we infer separation. Given $\phi(x)$, we simply define $\varphi(u,v,p)$ to be $\varphi(u,v,p)\stackrel{\text{def}}{=} u=v\land u\in p\land\phi(u)$ This is a functional formula (i.e. for every $u$ there is at most a single $v$ for which $\varphi(u,v,p)$ holds) and it is easy to verify that the image of $\varphi(u,v,a)$ is indeed $\{x\in a\mid \phi(x)\}$.
The empty set exists by separation - simply take some $a$ (which exists because we assume there is some set in the universe) and the function $\phi(x)\colon = x\neq x$.
As you noted, $\{\emptyset ,P(\emptyset)\}$ exists by the Power set axiom.
Now for a given $x,y$ we want to have $\{x,y\}$ so we define the following $\varphi(u,v)$ as following: $\varphi(u,v) \colon = (u=\emptyset\wedge v=x)\vee (u=P(\emptyset)\wedge v=y)$
Note that $\varphi$ is a functional formula, i.e. for a given $u$ there is only one $v$ for which $\varphi(u,v)$ is true. By the axiom of replacement we have now that $\{x,y\}$ is a set. Therefore the axiom of pairing holds if we assume Power set and Replacement.
Now we have two ways of looking at ZFC. Sometimes we want to prove that something is a model for ZFC and need to verify the list of axioms in which case proving both Separation and Replacement is completely redundant. At other times we want to prove certain things which are quicker when using the more specific axioms (e.g. pairing (or even ordered pairing, which can be quickly inferred from pairing itself)).
This is a sort of freedom that we allow ourselves. We add extra axioms that we don't really need. Then if we want to ensure all the axioms hold we check for the "core" of the axiomatic system, and when we want to ease on ourselves in other cases we can just use the extra axioms for our convenience.
-
0@Luca: Ah, I see where you're driving at. I had a typo and I wrote $\varphi$ instead of $\phi$. I'm still not 100% clear about what you'd meant in the second question. Perhaps you should write a new question. Not limited by the comment box you could expand a bit more, and then things can be clearer (and it is possible that while writing your question, you'll understand the answer too). ā 2013-05-30
Given a set $A$ and a formula $\phi(x)$ we create the function-class that sends every element $a\in A$ to $\{a\}$ if $\phi(a)$ and to $\varnothing$ otherwise. Typically this would be written $\psi(x,y): (\phi(x)\to y=\{x\})\land(\lnot\phi(x)\to y=\varnothing)$
Then taking the union of the set that is produced through the axiom of replacement you get what you are looking for.
-
0@objectivesea: I hadn't seen your comment. You don't need separation to show that $\{x\}$ is a set. Pairing (and extension) is enough, you just take $x=y$. Still, Asaf's answer is the standard solution to this problem. ā 2014-02-23
Let $A$ be a set. We want to prove the existence of the set $X$ of all elements of $A$ which satisfy a certain formula $\phi$. If no element of $A$ satisfies $\phi$, the existence of $X$ is easy.
Otherwise, suppose that $a \in A$ satisfies $\phi$. Define the functional relation $\rho$ by $\rho(x,a)$ if $x$ does not satisfy $\phi$, and $\rho(x,x)$ if $x$ satisfies $\phi$. Then $X$ is the "range" of $\rho$ as $x$ travels over $A$.
-
0@objectivesea it depends on the exact formulation of Replacement. If in your formulation, functions are defined on the entire domain, and you say that $F[A]$ is a set whenever $A\subseteq dom(F)$ is a set, then you do have a problem. But if you just say that $F[A]$ is a set whenever $A$ is a set, then the relation $F=\{
\mid x\ne x\}$ will give $F[A]=\varnothing$ for any $A$. Also if you formulate it as Asaf did - that every uāA has at most one v etc. then you are OK. ā 2018-04-17
The formulation of Replacement in the book Set Theory:An Introduction to Independence Proofs, by K. Kunen,is different : When $f$ is a formula whose free variables are among $x,y,A,v_1,...,v_n$ then $\forall A\;\forall_{j=1}^nv_i\;[\;\forall x\in A\;\exists! y\;(f) \implies \exists Y\;\forall x\in A\;\exists y\in Y\;(f)\;].$ This is weaker than $\forall A\;\;\forall_{j=1}^nv_i\;[ \;\forall x\in A\;\exists!y\;(f)\implies\exists Y\;\forall y \;(\;y\in Y\iff \exists x\in X \;(f)\;)\;].$ The latter can be deduced by combining Replacement and Comprehension (Separation). This approach goes back a long time. Godel showed that in ZF minus the Axiom of Infinity minus Comprehension, the Comprehension schema can be replaced by a collection of $ 8$ axioms which he explicitly wrote out. (Or,if you want, by one rather long single sentence.) Comprehension replaces the earlier, naive, schema of Abstraction, which is $\exists Y \;\forall y\;[y\in Y\iff f]$ which leads to paradoxes, e.g. Russell's Paradox.