# Set Existence - Apply Function to Each Element of Existing Set

I have a question regarding the existence of certain types of sets in axiomatic set theory.

Let $A$ be an existing set. It is not uncommon in mathematics to see a new set, $X$, defined in some form as

$$X = \{f(x) : x \in A \}$$

i.e. by taking each element in the existing set and applying some function to it. Now, as my question stands I know I just described $X$ as basically the image of $f$.

However, sometimes you are trying to do something more complex. Imagine I have a set, $A$, of all ordered pairs consisting of elements from some unknown set. Could you define, for example, a set $X$ to be the set of all first elements in this set of ordered pairs. Something like:

$$X = \{m : \left<m, n \right> \in A\}$$

I've seen examples of sets defined like this and see no axiomatic reason they must exist. Formally I can't define $m$ to be the subset of some larger set because I don't know which set the ordered pairs were constructed from. This may seem like a forced example, but imagine I was trying to disprove the existence of a set containing all possible sets of ordered pairs and needed to show that I could construct the universal set from the set of all ordered pairs and arrive at a contradiction.

Hope that question makes sense.

Edit: I am talking about ZFC.

• You're probably asking about ZF set theory, right? Feb 16, 2017 at 6:00
• @ChrisCulter Spot on. Feb 16, 2017 at 6:59

Proposition. For each set $R$ of ordered pairs,

• There exists a unique set whose elements are exactly those elements $a$ such that $\left(a,b\right)\in R$.
• There exists a unique set whose elements are exactly those elements $b$ such that $\left(a,b\right)\in R$.

Proof. Let $R$ be an arbitrary set of ordered pairs.

• Define $A:=\left\{a\in \bigcup\bigcup R:\left(\exists b\in \bigcup\bigcup R\right)\left[\left(a,b\right)\in R\right]\right\}$. Therefore $A$ is a set whose elements are exactly those elements $a$ such that $\left(a,b\right)\in R$ and $A$ is unique.
• Define $B:=\left\{b\in \bigcup\bigcup R:\left(\exists a\in \bigcup\bigcup R\right)\left[\left(a,b\right)\in R\right]\right\}$. Therefore $B$ is a set whose elements are exactly those elements $b$ such that $\left(a,b\right)\in R$ and $B$ is unique.

Definition. Let $R$ be a set of ordered pairs.

• The projection of $R$ onto the first coordinate is the set whose elements are exactly those elements $a$ such that $\left(a,b\right)\in R$.
• The projection of $R$ onto the second coordinate is the set whose elements are exactly those elements $b$ such that $\left(a,b\right)\in R$.

Remarks.

• You do not need to use the axiom of replacement.
• The axiom of union and the axiom (schema) of specification play an important part.
• The axiom of pairing is needed to have a notion of an "ordered pair": $(a,b):=\{\{a\},\{a,b\}\}$
• The axiom of extensionality is needed to be able to define "projection onto first/second coordinate." I.e. uniqueness is necessary to give a well-defined definition.

In formal set theory, it is the axiom of replacement that guarantees images of sets under maps, including the existence of sets like $\{f(x) : x \in A \}$ and $\{\text{proj}_1(m) : \left<m, n \right> \in A\}$. Or you could replace the projection map here by any other function.

In general replacement is required to build the images of sets under functions. For example, you cannot prove that the limit ordinal $\omega+\omega$ exists without replacement. It is the image under the map $n\mapsto \omega + n$ of the set $\omega$.

Edit: Note that here I use the word "function" in a loose sense: if $f$ is literally a set-theoretic function, i.e. a subset of the Cartesian product of its domain and codomain, its image already exists as a subset of its codomain without invoking replacement. Replacement is needed when we have a function-like predicate (class function) whose codomain we don't already need.

• "In general replacement is required to build the images of sets under functions." - it is only needed to build the images of sets under mappings (sometimes also called class functions). A function is usually defined as a set of certain ordered pairs, and in that setting you don't need replacement to show that the image is a set. Just a minor point, but I think in this context one shouldn't use mapping and function interchargeably. Feb 16, 2017 at 6:30
• @relep good point, I added a comment to that effect Feb 16, 2017 at 13:13

You can view the second type of set as one of the first, by defining a projection map from $A$. Say that $A$ is a set of ordered pairs, $$A \subset B \times B$$Then we define $f:A \to B$ by $f(b_1,b_2) = b_1$. This is often called the projection onto the first factor. Given this, the set you want to talk about is exactly $f(A)$.

Of course, we can also project onto the second factor, $g:A \to B$ by $f(b_1,b_2) = b_2$. Furthermore, there's really no reason to assume that $A$ is a subset of $B \times B$, it could be a subset of $B \times C$, and we can likewise define projections.