Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm trying to understand the axiom of reeplacement in set theory. To my understanding, please tell me if I'm wrong, if there is a logical proposition $\varphi(x,y,w_{1},...,w_{n})$ and an arbitrary set $A$, then we can have the set $B=\{y:\exists x\in A(\varphi(x,y,w_{1},...,w_{n}))\}$.

Now, HERE is my problem. The formulation of the axiom in terms of logic makes explicit the fact that $\exists!y(x,y,w_{1},...,w_{n})$. This means then that the logical proposition needs to be a function. So basically I'm asking for examples where logical propositions are not functions. (To make this clearer, there is something I'm missing because I think that all proposition ar functions. For example the statemet $\forall x(x<y)\wedge (y+z=10)$ is a function of the variables $y$ and $z$, etc.)

share|cite|improve this question
How is the statement that you put in your question a function? – Apostolos Jul 16 '13 at 16:26
@Apostolos Because for every $y$ and $z$ there is only one value that the function $\varphi(y,z)=\forall x(x<y)\wedge(y+z=10)$ assigns to them. – Daniela Diaz Jul 16 '13 at 16:30
When we say that a formula $\varphi(x,y)$ is functional we mean that for every $x$ there is a unique $y$ such that $\varphi(x,y)$ is true. That is $x$ is the argument and $y$ is the output of the function. For example the formula $y=x+1$ has this property, because the successor of $x$ is unique. On the other hand the formula $(x=x\land y=y)$ is not functional. Because given a fixed $x$ there are more than one $y$ (in fact all $y$) that satisfy $\varphi(x,y)$. – Apostolos Jul 16 '13 at 16:34
up vote 2 down vote accepted

Consider $\varphi(x,y)= y\in x$. This is not a function because $x=\{\varnothing,\{\varnothing\}\}$ does not have a unique $y$ satisfying this formula with $x$.

In fact, unless $A$ is a set of singletons, $\varphi(x,y)$ will not define a function on $A$.

Here is an example of why we must require that $\varphi$ is a function (after fixing the parameters) on the set $A$. Consider $A=\{\varnothing\}$ and $\psi(x,y)$ stating that $x\subseteq y$, formally: $$\psi(x,y)=\forall z(z\in x\rightarrow z\in y)$$

Now the collection $\{y\mid\exists x\in A.\psi(x,y)\}=\{y\mid y=y\}$, every set is a superset of the empty set. So this would be a proper class, which we already know is not a set. The axiom of replacement, as Hagen says, is telling us that if we can "uniformly rename all the elements of $A$" then the result is a set.

share|cite|improve this answer

In your proposed formulation of Replacement, let $A$ be any nonempty set and $\phi(x,y)\equiv x=x$. Then your $B$ would be tha all-class, which is not a set.

As you want to replace each element of $A$ with a single(!) new object $y$, you need the restriction mentioned, namely that (dropping the parameters $w_1,\ldots,w_m$ for simplicity) for all $x\in A$ there exists exactly* one object $y$ such that $\phi(x,y)$ holds. That is we can view $\phi$ not as a function from Sets$\times$Sets to $\{T,F\}$, but rather we have a function $$ x\mapsto \text{the unique }y\text{ such that }\phi(x,y)$$ * One could also work with at most one

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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