Families

Everything I said about $n$-tuples can also be said about "$I$-tuples", where $I$ is now an arbitrary set. What I mean by this is that we can define an $I$-tuple to be a function with domain $I$. If we set $I=n$, we just get the notion of an $n$-tuple! However, in this case we usually don't use the term "tuple", but rather a family. So, a family indexed by set $I$ is just a function with domain $I$. An $n$-tuple is then a family indexed by $n$. A family of elements of $X$ (indexed by $I$) is a function

$$s:I⟶X.$$

We sometimes write $(a_i:i\in I)$ to denote the family $s$ indexed by $I$ such that $s(i)=a_i$ for all $i\in I$. 

If $(A_i:i\in I)$ is a family (of sets), we define its product

$$\prod _{i\in I}{A}_i$$

to be the class consisting of all families $s$ indexed by $I$ which satisfy that $s(i)\in A_i$ for all $i\in I$. If we have that $A_i=X$ for all $i\in I$, we use the notation

$$X^I:=\prod _{i\in I}X=\{s:s:I\to X\}.$$

This is exactly the set of all families of elements of $X$ indexed by $I$. 

As in the case of $n$-tuples, class $X^I$ is really a set. However, in the case of $n$-tuples, i.e. $I=n$, the proof of this fact was constructive. In other words, we showed that this is a set by running an induction on $n$. In the inductive step, we gave an explicit explanation why $X^{n+1}$ is a set provided that $X^n$ is so: $X^{n+1}$ is equal to $X^n\times X$, after replacing $⟨s,x⟩\in X^n\times X$ with $s\cup \{⟨n,x⟩\}$. However, in the case of general families we can't really do this: there is no clear way to "induct" over $I$.

The proof itself is relatively easy. Notice that every element $s\in X^I$ is a function from $I$ to $X$. This means that $s\subseteq I\times X$, or equivalently, $s\in P(I\times X)$. This means that

$$X^I\subseteq P(I\times X),$$

while $P(I\times X)$ is a set. (Recall that $P(x)$ denotes the powerset of $x$.) A class that is contained in a set is itself a set, and we are done. What you should notice is that we used Axiom of Powerset. This axiom asserts that the set of all subsets of a given set exists, but it doesn't explain where this powerset comes from. This is the non-constructive part. I'll have to come back to this later, but here's a very brief explanation.

Let's look at $\omega$ and $P(\omega )$. Suppose that you come up with a way to describe subsets of $\omega$. Say, for example, you have a program which takes an input $n$ and spits out "yes" or "no". We can interpret this answer as "yes, it belongs to the subset" or "no, it doesn't belong to the subset". Then you got yourself a definition of a subset of $\omega$! The issue is that if you have all such programs, you can list them as in a dictionary and enumerate by natural numbers. This means that you can also enumerate all the subsets of $\omega$ that can be described in this way. Now, even though sets $\omega$ and $P(\omega )$ are both infinite, they can nevertheless be compared in size. It turns out that the set $P(\omega )$ has more elements then set $\omega$! This means that your programs can't possibly list all the subsets! The same is true for any kind of language or system of description that you might come up with.

Leaving this digression aside, we have a proof that $X^I$ is a set and that proof uses Axiom of Powerset. In a sense, this is inevitable: $P(I)$ is essentially the same object as $2^I$. I'll explain. Look at a subset $A$ of $I$. You can define an indicator function for this set:

$${\chi }_A(i):=\{\begin{array}{ll}1,& i\in A\\ 0,& i\notin A\end{array}$$

(for $i\in I$). This function essentially answers yes/no to the question of whether $i\in A$. So, you get an element of $2^I$. On the other hand, if you start from an element $f$ of $2^I$, you can define the subset

$$S_f:=\{i\in I:f(i)=1\}$$

of $I$. Function $f$ can be thought of as an oracle which answers yes/no when asked about an element $i\in I$ and set $S_f$ is just the set of elements of $I$ for which $f$ answers "yes". It's not hard to see that

$$S_{{\chi }_A}=A\text{ and }{\chi }_{S_f}=f.$$

What we essentially did here is to define a function $\chi :P(I)\to 2^I$ which maps a subset $A$ of $I$ to the family $\chi (A):={\chi }_A\in 2^I$. This function has two every nice properties. Firstly, different subsets of $I$ are mapped to different families. To see this, let's say $A\ne B$ are two subsets. Then there exists $i\in I$ which belongs to one of them, but not to the other. We may assume that $i\in A$, but $i\notin B$. Then we have

$${\chi }_A(i)=1\ne 0={\chi }_B(i),$$

which shows that $\chi (A)\ne \chi (B)$. Secondly, every element of $2^I$ is an image of a subset of $I$ via $\chi$: a family $f:I\to 2$ is an image of $S_f\subseteq I$, i.e. $f=\chi (S_f)$.

Functions having the two properties that I've just described are called bijections. Thus, $\chi :P(I)\to 2^I$ is a bijection. The function $S:2^I\to P(I)$ defined by $S(f):=S_f\subseteq I$ for $f\in 2^I$ is also a bijection. I leave it to you to verify this. These two functions are closely related to each other. They're inverses of each other. This is just a fancy way of saying that for all $A\subseteq I$ and for all $f:I\to 2$, we have that

$$\chi (S(f))=f\text{ and }S(\chi (A))=A.$$

Now, back to families. Long story short, we showed that class $X^I$ is a set, for all $X$ and all $I$. We can then show that the class

$$\prod _{i\in I}{A}_i$$

is also a set, for all families of sets $(A_i:i\in I)$. The reason for this is simply that this class is contained inside the class

$${\left(\bigcup _{i\in I}{A}_i\right)}^I,$$

which is itself a set. (To see that this containment is true, you can reason in the same way as for tuples.) So at the end of the day, we've gotten ourselves a new way of constructing sets: by taking products of sets that we already have! However, this operation is not as simple as it might look like. A good deal of Set Theory is about understanding this operation. To get a gist of it, say all sets $A_i$ are non-empty. Is the set $\prod _{i\in I}{A}_i$ non-empty? It turns out that, based solely on the axioms that we've introduced so far, i.e. the axioms of ZF, we cannot answer this question! The positive answer to it is in fact equivalent to the final axiom, which I still haven't introduced, and which is called Axiom of Choice.