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~

  • $\begingroup$ 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 $\endgroup$
    – ju so
    Jan 14, 2021 at 14:26

1 Answer 1


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).


You must log in to answer this question.

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