# Proof verification for exercise 3.5.2 in Tao's Analysis I: Prove that the generalized definition of a Cartesian product is a set

The second portion of Exercise 3.5.2 in Tao's Analysis I reads as follows:

Suppose we define an ordered $$n$$-tuple to be a surjective function $$x:\{i \in \mathbb N : 1 \leq i \leq n \} \to X$$ whose range is some arbitrary set $$X$$ (so different ordered $$n$$-tuples are allowed to have different ranges); we then write $$x_i$$ for $$x(i)$$, and also write $$x$$ as $$(x_i)_{1 \leq i \leq n}$$. Show that if $$(X_i)_{1 \leq i \leq n}$$ are an ordered $$n$$-tuple of sets, then the Cartesian product, as defined in Definition 3.5.7, is indeed a set. (Hint: use exercise 3.4.7 and the axiom of specification.

Definition 3.5.7: $$\prod\limits_{1\leq i \leq n } X_i :=\{(x_i)_{1\leq i \leq n}:x_i \in X_i \text{ for all } 1 \leq i \leq n \}$$.

Conclusion of Exercise 3.4.7 (proven earlier): The collection of all partial functions from $$X$$ to $$Y$$ is itself a set. Here, a partial function from $$X$$ to $$Y$$ is defined as any function $$f: X' \to Y'$$ whose domain $$X'$$ is a subset of $$X$$ and whose range $$Y'$$ is a subset of $$Y$$.

Axiom of Specification: Let $$A$$ be a set, and for each $$x \in A$$, let $$P(x)$$ be a property pertaining to $$x$$. Then there exists a set, called $$\{x \in A: P(x) \text{ is true}\}$$ whose elements are precisely the elements $$x$$ in $$A$$ for which $$P(x)$$ is true.

I am seeking clarification regarding the validity of my proof.

I also invoked the Axiom of Union, which Tao states as follows: Let $$A$$ be a set, all of whose elements are themselves sets. Then there exists a set $$\bigcup A$$ whose elements are precisely those objects which are elements of the elements of $$A$$.

Here is the proof:

Assume there exists a set $$\mathbb W = \{A,B,C,D,...\}$$

Let $$X$$ be a function defined as $$X:\{1,2,...,n\} \to \mathbb W$$. Therefore, as a hypothetical example, $$X_1 = A$$, $$X_2 =D$$, etc. (Here, $$X_1=A$$ can be interpreted to mean $$X(1)=A$$...i.e. $$X$$ is mapping the element $$1$$ to the set $$A$$)

Consider the overarching domain and codomain: $$\mathbb N \to \bigcup \mathbb W$$.

Let $$\Psi ': \{1,2,...,n\} \to Y'$$ where $$Y' \subseteq \bigcup \mathbb W$$ and, obviously, $$\{1,2,...,n\} \subseteq \mathbb N$$.

Clearly, $$\Psi'$$ is a partial function from $$\mathbb N \to \bigcup \mathbb W$$.

Let $$\Omega$$ be the set of all partial functions, of which $$\Psi'$$ is certainly a member. (This set exists by exercise 3.4.7)

Now, let's further equip $$\Psi'$$ with some arbitrary (but strategic) mapping rule of the following form: $$\Psi': 1 \mapsto a' \in X_1$$, $$\Psi': 2 \mapsto b' \in X_2$$, $$\Psi': 3 \mapsto c' \in X_3$$, ... etc. In line with Tao's notation, we would say $$\Psi'_1 = \Psi' (1) = a'$$.

We can imagine that there are many other partial functions in $$\Omega$$ that share a similar mapping strategy to $$\Psi'$$.

For example, $$\Psi'': \{1,2,...,n\} \to Y''$$ where $$\Psi'': 1 \mapsto a'' \in X_1$$, $$\Psi'': 2 \mapsto b'' \in X_2$$, $$\Psi'': 3 \mapsto c'' \in X_3$$, ... etc.

It is apparent that $$\Psi'$$ (and its other variants) are behaving like the ordered $$n$$-tuple function $$(x_i)_{1 \leq i \leq n}$$ that Tao described earlier.

Therefore, using the Axiom of Specification, we can hand pick these functions from $$\Omega$$ and form a set out of them:

$$\{\Psi:\Psi \in \Omega\ \text { and }\forall i \text { such that } 1 \leq i \leq n \ \Psi_i \in X_i \}$$

My claim is that this is identical to the Cartesian set definition and therefore I have demonstrated that this is, indeed, a set.

Any critiques would be greatly appreciated! Cheers~

• I think that the step making each function in the set {Ψ:Ψ∈Ω and ∀i such that 1≤i≤n Ψi∈Xi} into surjective function is missing Jan 14, 2021 at 14:26

Long comment

The proof is a little bit long but simple.

We start with the concept of "indexed family" $$X_i$$ for set $$I$$ whatever; it is simply a function $$\{ (i,X_i) \mid i \in I \}$$.

Obviously, for every $$i \in I$$ we have exactly one $$X_i$$; thus, by Replacement (see your previous post), this "family" is a set (and thus a function).

The next step is to use Union to generate the set $$\bigcup \{ X_i \mid i \in I \}$$.

Then, given $$x_i \in X_i$$, we define a function $$f$$ from $$I$$ to $$\bigcup \{ X_i \mid i \in I \}$$ such that $$f(i)=x_i$$.

This function is a "sequence" $$(x_i)_{i \in I}$$.

The set of all such "sequences" is the generalized cartesian product

$$\Pi_{i \in I} X_i = \{ f \mid f \text { is a function with domain } I \text { and for each } i \in I, f(i) \in X_i \}.$$

Tao's exercise is limited to the finite case where $$I = \{ i \in \mathbb N \mid 1 \le i \le n \}$$.

Please, note that in the above sketch of a proof I've omitted the crucial fact that, in order to prove that the generalized cartesian product of an "indexed family" of non-empty sets is itself not empty, the $$\mathsf{AC}$$ axiom is needed.

This axiom is not needed for the restricted case of finite $$I$$ (the case in Tao's exercise).