Given sets $A$ and $Y$, I want to show that there is a set $T$ such that given $a\in A$ an $y\in Y$ the ordered pair $(a,y)$ belongs to $T$.


In other words we want to show that the existence of the set of ordered pairs $A\times Y$, or not?

For that do we have to apply the axioms of sets?

  • $\begingroup$ From this axiom there is a function $f$ for a set $S$ such that $f(S)\in S$, correct? From that aiom we also get that "Given any family of nonempty sets, their Cartesian product is a nonempty set.", right? Is this taht we need to show that existence? @Peter $\endgroup$
    – Mary Star
    Aug 30 '19 at 15:08
  • $\begingroup$ Also math.stackexchange.com/questions/26497/… $\endgroup$ Aug 30 '19 at 15:16
  • 1
    $\begingroup$ @Peter finite/infinite has nothing to do with it. Nor does the axiom of choice. The Cartesian product is a definable subset of $P^2(A\cup Y)$ whose existence follows from pairing/powerset/union . Refinements of this are possible but the point is it comes from other naive set operations that the axioms guarantee. $\endgroup$ Aug 30 '19 at 15:34
  • 1
    $\begingroup$ I’m not experienced in Set Theory, so I’ll ask my prof, but it’s my understanding that you only need AC when it’s the product of an arbitrary family of sets, not for the product of two sets which may each be uncountable. $\endgroup$
    – Joe
    Aug 30 '19 at 15:35
  • 3
    $\begingroup$ @Peter Choice is totally irrelevant here. First of all, choice isn't used to construct sets of functions, it's used to show that those sets are nonempty: showing that $\prod_{i\in I}X_i$ is nonempty, just knowing that each $X_i$ is nonempty, may indeed require choice, but forming $\prod_{i\in I}X_i$ itself doesn't (that is, ZF alone proves that arbitrary products exist). Moreover, even looking at nonemptiness, the thing which matters isn't the size of the sets involved in the product but the number of sets in the product: ZF alone proves that $X\times Y$ is nonempty whenever $X$ and $Y$ are. $\endgroup$ Aug 30 '19 at 16:35

Assuming that the ordered pair $(a,y)$ is defined via the Kuratowski definition, $$(a,y) = \Bigl\{ \{a\}, \{a,y\}\Bigr\}$$ and that you are working with ZF theory, this is relatively straightforward.

By the Axiom of Pairs, there is a set $X=\{A,Y\}$. By the Axiom of Unions, there is a set $B=\bigcup X = \{x\mid x\in A\text{ or }x\in Y\}$. In particular, if $a\in A$ and $y\in Y$, then $a,y\in B$. By the Axiom of Separation, $\{a\}$ and $\{a,y\}$ are sets, $\{a\}\subseteq B$ and $\{a,y\}\subseteq B$.

By the Axiom of the Power Set, $\{a\}$ and $\{a,y\}$ are elements of $P(B)$, the power set of $B$. Therefore, by the Axiom of Separation, $\{ \{a\},\{a,y\}\}$ is a set, and since it is a subset of $P(B)$, hence by the Axiom of the Power Set, $(a,b)$ is an element of $P(P(B))$.

By the Axiom of separation, $\{ x\in P(P(B))\mid \text{there exists }a\in A,y\in Y\text{ such that }x=(a,y)\}$ is a set. This is exactly the set $A\times Y$.

(Note: There is a subtle issue with Separation above in that the formula has two free variables, but this can be solved using the Axiom of Replacement)

If you have a different definition of the pair, then similar arguments can be made, though the precise sequence of axioms and operations may differ.

Note: the Axiom of Choice is not required. This party can happen in ZF.


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