For the following question, there is likely terminology that I am not privy to that should be used. I apologize in advanced for this, as I am asking a question about a territory of math I am not overly familiar with.

In Tao's Analysis I, the Axiom of Replacement is stated as follows:

Let $A$ be a set. For any object $x \in A$, and any object $y$, suppose we have a statement $P(x,y)$ pertaining to $x$ and $y$, such that for each $x \in A$ there is at most one $y$ for which $P(x,y)$ is true. Then there exists a set $\{y:P(x,y)$ is true for some $x \in A \}$, such that for any object $z$, $z\in\{y:P(x,y)$ is true for some $x \in A\} \iff P(x,z)$ is true for some $x \in A$.

For quite some time, I thought this axiom was restricted to depicting scenarios where functions would map between "common objects". For example, consider the function $f: \mathbb R \to \mathbb R$ where $f$ is defined as $x \mapsto 2x$, i.e. $f(x)=2x$.

Or, alternatively, consider the function $f: \mathbb R \to \mathbb Z$ where $f$ is defined as $x \mapsto \lfloor x \rfloor$.

In either case, the idea that I thought was being captured (and therefore in agreement with my understanding of what was implied by the Axiom of Replacement) was that a number was being mapped to a number. i.e. "common objects/things/items" were being mapped to one another.

However, I recently encountered an exercise that required me to employ the Axiom of Replacement in ways that I have not previously explored.

The exercise, ($3.5.1$), asks the reader to demonstrate that the Cartesian product $X \times Y$ is a set. In order to carry this out, I first created a function of the following form:

$f_x(y) = \Big\{\{x\},\{x,y\}\Big\}$

i.e. this function takes any object $y$ in set $Y$ and maps it to the following different object: $\Big\{\{x\},\{x,y\}\Big\}$... where $x$, an element of $X$, is fixed

After this, I created a set invoking the Axiom of Replacement:

$Y_x = \bigg\{\Big\{\{x\},\{x,y\}\Big\}: \forall y \in Y, f_x(y)=\Big\{\{x\},\{x,y\}\Big\}\bigg\}$

Now, I basically made arbitrarily many of these functions...e.g. :

$f_{x'}(y) = \Big\{\{x'\},\{x',y\}\Big\}$

$f_{x''}(y) = \Big\{\{x''\},\{x'',y\}\Big\}$

ect ect...where $x'$, $x''$, etc are all different elements of $X$...resulting in all of the following different sets:

$Y_{x'} = \bigg\{\Big\{\{x'\},\{x',y\}\Big\}: \forall y \in Y, f_{x'}(y)=\Big\{\{x'\},\{x',y\}\Big\}\bigg\}$

$Y_{x''} = \bigg\{\Big\{\{x''\},\{x'',y\}\Big\}: \forall y \in Y, f_{x''}(y)=\Big\{\{x''\},\{x'',y\}\Big\}\bigg\}$ etc etc

I lingered on this for a bit, recognizing that $y$ and $\{\{x'\},\{x',y\}\}$ are, somehow, not "the same thing"...but continued on nonetheless.

Finally, I made the function $g(x) = Y_x$, which is even more bizarre to me, because this is effectively saying:

$g: x\mapsto \bigg\{\Big\{\{x\},\{x,a\}\Big\},\Big\{\{x\},\{x,b\}\Big\}, \Big\{\{x\},\{x,c\}\Big\}...\bigg\}$ where $a,b,c,...$ etc are all elements of $Y$.

Invoking the Axiom of Replacement one last time:

$Z=\{Y_x: \forall x \in X, g(x) = Y_x\}$. Following this with the Axiom of Union, I successfully generate the set of all ordered pairs (as defined through the Kuratowski notation), thus demonstrating that the Cartesian product is, in fact, a set.

The idea of what a function can do, and what the Axiom of Replacement entails, seems significantly richer than I initially imagined. In the above example, it is evident to me that I am mapping (for a lack of a better word), lower-tiered objects to higher-tiered objects. For example, in function $g$, it seems clear to me that an element $g(x)$ has significantly "more structure" than the element $x$ that maps to it. (Perhaps a better way of phrasing it is that $g(x)$ sits higher on some sort of set construction hierarchy than the element $x$)

So, really, my question is fairly simple. Is there a name for what I am observing? And, further, is there any significance to this concept?


1 Answer 1


Long comment

The Axiom does not "use" a function in the universe of sets (i.e. a set) but a formula $P(x,y)$ of the language of the theory of sets that "behaves like a function", i.e. such that it satisfies the condition

"that for each $x ∈ A$ there is at most one $y$ for which $P(x,y)$ holds."

The key points of the Axiom is the set $A$ above.

Per se, a "functional" formula $P(x,y)$ does not license us to assert that a corresponding set exists.

What does it mean ?

Consider the collection of pairs $\{ (x,y) \mid P(x,y) \text { holds, for some } x \}$.

If such a collection is a set, clearly it will be a function. But thus, we can use it to carve out the collection of all first "coordinates" of the pairs it contains.

Clearly, such a collection is the "universe" $V$ itself, and we know that in $\mathsf {ZFC}$ the universe is not a set.

Thus, neither the collection above is a set.

What the Axiom of Replacement asserts is that, for a set $A$ whatever, there is a set $Y$ consisting of all those $y$ such that $P(x,y)$ holds for some $x \in A$.

But then, all pairs $(x,y)$ are elements of $A \times Y$ and thus, by Separation, the collection of pairs $\{ (x,y) \in A \times Y \mid P(x,y) \text { holds } \}$ is a set.

Because the formula $P(x,y)$ "behaves like a function", that set is indeed a function.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .