Suppose that Replacement holds only for parameter-free formulas. I need to Prove that the full schema of Replacement holds.

the full schema of Replacement states: If $ϕ(u,v,p_1,...,p_n)$ is a formula in the language of set theory, for every choice of parameters $p_1,...,p_n$, if for some x we can prove that for u ∈ x there exists exactly one v such that $ϕ(u,v,p_1,...,p_n)$ holds, namely that $ϕ$ defines a function on $x$, then there is $y$ which is the range of this function;

$${\forall p_1,\ldots,p_n}~{{\Big(\forall x~\big((\forall u {\in} x)(∃!v~ϕ(u,v,p_1,...,p_n))\big)}\to{\big(\exists y~\forall v~(v{\in}y \gets\hspace{-2ex}\to(\exists u {\in} x)~ϕ(u,v,p_1,...,p_n))\big)\Big)}}$$

I have three questions:

  1. who are , $p_1,...,p_n$? are they variables of the language, or are they sets? and how are they different from $u$ and $v$?
  2. can I get an example of a formula ϕ(u,v,p1,...,pn) please?
  3. how can the statement be proven?
  • $\begingroup$ This is not a trivial theorem at all. Do you know the analogous theorem for PA, that you can use only parameter-free induction axioms? The proofs are a bit similar, but I think the PA one is a bit easier to grasp, since it is easier to understand the natural numbers. $\endgroup$ – Asaf Karagila Aug 25 '17 at 10:23
  • $\begingroup$ Also, if you don't know yet that parameters are variables, and that all objects in the case of ZFC are sets, then perhaps you're not ready for this sort of theorem. $\endgroup$ – Asaf Karagila Aug 25 '17 at 10:24
  • $\begingroup$ When I studied logic we never used the term "parameter", only "variables". and since this formula is written in a first order language, I assumed that ,p1,...,pn are variables. I'll ask it differently: $\endgroup$ – Mike. R. Aug 25 '17 at 11:08
  • $\begingroup$ I'll ask it differently: 1. these axioms are written in a specific first order language we call the language of set theory .thus, u, v, etc. are variables of the language. if we could find a collection of objects that satisfies these axioms, namely - if we can find a model for our axioms, then the objects of this structure are called "sets". is that right? 2. when it says " parameter-free formulas", dos that mean with out p1,...,pn, or with out u,v,p1,...,pn? I dont know the analogous theorem for PA. $\endgroup$ – Mike. R. Aug 25 '17 at 11:24
  • $\begingroup$ (1) Yes. (2) Yes. It means that the formula has a single free variable, so it is $\phi(u)$, and not $\phi(u,p_1,\ldots,p_n)$. (3) The first-order axiomatization of Peano Arithmetic has an induction schema, which also utilizes parameters, and there too you have a theorem that parameter-free induction is enough. $\endgroup$ – Asaf Karagila Aug 25 '17 at 11:36

A comment by Goldstern to a related MO question provides a link to a beautiful note by Schindler and Schlicht that contains all the details. The idea of the proof is to encode all parameters into $x$ using ordered pairs. These are later decoded by a suitably modified formula $\phi$. As it is written in the note, result itself is due to Levy.

I believe that questions 1 and 2 were sufficiently addressed in the comments by Asaf Karagila.


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.