# About proof writing in axiomatic set theory

I meet question as following:

i) Show that the mappings $f: X \rightarrow Y$ from one given set $X$ into another given set $Y$ themselves form a set $M(X, Y)$.

ii) Verify that if $R$ is a set of ordered pairs (that is, a relation), then the first elements of the pairs belonging to $R$ (like the second elements) form a set.

It comes from Zorich's Mathmatical Analysis I again...the book has interpreted following axiom in set theory: Axiom of extensionality, axiom of separation, union axiom, pairing axiom, power set axiom, axiom of infinity, axiom of replacement(do not actually use in this book) and axiom of choice.

While ordered pair is defined as $(X, Y)=\{\{X,X\}, \{X,Y\}\}$.

What makes me confused is that I don't get the key to use those axiom in a proper way to write a rigorous proof, even in this kind of intuitive case.

For i) I think $M(X, Y)$ is but a subset of the power set of direct product $X \times Y$, that is, $P(X \times Y)$. But I even don't know how to explain the concept of subset by axioms.

For ii) I want to "pick up" each ordered pair and just find the intersection of the two elements in the pair, i.e. $\{X, X\} \cap \{X,Y\}=\{X\}$ and then the first elements is the union set of those set. Yet I don't know how to realize it again.

Bad questions maybe. And here is an even worse additional question: What is it actually mean when we say $x$ is a set in axiomatic set theory? I think I got totally confused.

• Are you using ZFC or NBGC as your axiom system? Questions i) and ii) as written do not actually make sense in ZFC: e.g. "the mappings" are either a set or do not exist at all. That question makes sense in NBG, where there is the additional possibilities of a proper class. – Rory Daulton Aug 30 '15 at 16:48
• @RoryDaulton Not quite sure but my book seems to be using ZFC. The term "Mapping" is defined as relation (set of ordered pairs) $f$ between two sets $X$ and $Y$ s.t. for any $x \in X$, $y_1,y_2 \in Y$, if $(x, y_1) \in f$ and $(x, y_2) \in f$ then $y_1=y_2$. So I don't quite understand why the set of mappings does not exist. – Asydot Aug 30 '15 at 16:57
• The set of mappings does exist: that is what you are to prove. My point is if it were not a set, you could not even talk about "the mappings" in ZFC. The questions are just poorly worded in ZFC. – Rory Daulton Aug 30 '15 at 18:15

Hint

You must supplement your textbook with some book on set theory, like e.g. :

Patrick Suppes, Axiomatic set theory (1960 - Dover reprint).

See page 22 for the usual definition of the "inclusion" relation : $A \subseteq B \leftrightarrow \forall x ( x \in A \to x \in B)$ and page 47 for the definition of the power set : $\mathcal P(A) = \{ B : B \subseteq A \}$.

The Power set axiom [see page 47] guarantees the existence of $\mathcal P(A)$ for any set $A$.

With this axiom, the proof of : $B \in \mathcal P(A) \leftrightarrow B \subseteq A$ is straightforward.

With the Power set axiom and a suitable instance of the Axiom schema of separation [i.e. : $\exists C \ \forall x \ (x \in C \leftrightarrow x \in \mathcal P(\mathcal P(A \cup B)) \land \exists y \ \exists z \ (y \in A \land z \in B \land x= \langle y, z \rangle))$ ], we can prove that $A \times B$ exists, for any $A,B$.

Now, having proved that $A \times B$ exists, by Power set we have also $\mathcal P(A \times B)$.

The last step will be to "separate" from $\mathcal P(A \times B)$ the set of those relations that are "functional" [see Zorich, page 21], i.e. the set of mappings from $A$ into $B$.