I've just started learning set theory and my professor gave us some exercises with cartesian products.

I understand that $ \{0, 1 \}^n = \{0, 1\} \times \{0, 1\} \times ... \times \{0, 1\} $ But some exercises have expressions defined for all natural numbers, so I'm confused whether $ \{0, 1\}^1 $ even has any meaning. Any help?

For context, the expression above should define a set of ordered pairs of vectors.

Edit: In class cartesian product was defined as $ A \times B = \{(a, b) : a \in A, b \in B \} $

I was provided solutions to some problems, and for the n=1 case (expression $ \{0, 1\}^1 $ ) it says that there are 2 vectors (a list of 2 ordered pairs).

Another similar problem has this same expression $ \{0, 1\}^n $, but also defined for natural numbers and 0. So what does $ \{0, 1\}^0 $ mean?

  • $\begingroup$ This is just the set $\{0,1\}$ itself. $\endgroup$
    – Mark
    Sep 29 '21 at 23:50
  • 2
    $\begingroup$ How was the Cartesian product $S_1 \times S_2 \times \ldots \times S_n$ defined in your material in the first place? What are its elements? $\endgroup$ Sep 30 '21 at 0:15

Just like $3^2 = 3 \times 3$ and $3^1 = 3$, the notation of $\{0, 1\}^1$ represents just a single copy of the set $\{0, 1\}$.

  • $\begingroup$ True, I guess really it doesn't have a good meaning so I might remove that. $\endgroup$
    – ConMan
    Sep 30 '21 at 0:11
  • 1
    $\begingroup$ For most purposes (but not all?) we need not distinguish the object $x$ and the $1$-tuple $(x)$. $\endgroup$
    – GEdgar
    Sep 30 '21 at 0:14

Assuming we have defined the nonnegative integers, and the concept of a function f : S → X from a set S to a set X, we can define the cartesian power Xn of a set X as Xn = {f : {0, ...,n-1} → X}, the set of all functions from {0,...,n-1} —> X.

By this definition, X1 = {f : {0} → X}, which is a set whose members are determined by the single value f(0), which can be any member of X. So this set is naturally in one-to-one correspondence with the set X itself.

By the same token, X0 = {f : {} → X}, the set of all functions from the empty set to X. By the definition of a function between two sets, this means that X0 is the set whose members are sets of ordered pairs whose first element belongs to the empty set and whose second element belongs to X. But there are no elements in the empty set, so there are no such ordered pairs. Thus there are no such members, and so X0 = {}, the empty set.

  • $\begingroup$ If $X^n$ is the set of functions from an $n$-element set to $X$, then $X^0$ should be the set of functions from the empty set to $X$. You seem to be saying $X^0$ is the empty function. $\endgroup$ Sep 30 '21 at 1:16
  • $\begingroup$ I don't know what "the empty function" means. But since there do not exist any functions from the empty set to a set X, the set of all such functions is empty. $\endgroup$
    – Dan Asimov
    Sep 30 '21 at 1:25
  • $\begingroup$ Many people (I, for one) would disagree with the statement "there do not exist any functions from the empty set to a set X". Surely you can define one such function: it must be some set of pairs $(i,x)$ where $i \in \varnothing$ and $x \in X$. Since $\varnothing$ has no elements, the only way is to take no pairs. But the set of no pairs is a set, indeed the empty set. I think the empty set exists. $\endgroup$ Sep 30 '21 at 1:31
  • $\begingroup$ PS But I think I see what you mean, and I hope I have fixed my post now. $\endgroup$
    – Dan Asimov
    Sep 30 '21 at 1:31

The question does not specify how the $n$-fold Cartesian product $$ S_1 \times \ldots \times S_n $$ was defined in the first place in the relevant learning material. If there is a formal definition, the first thing to do would be to see what it says when $n=1$.

Usually (e.g. Wikipedia) one takes the $n$-fold Cartesian product to be the set of $n$-tuples $$ \{(x_1,\ldots,x_n) \;:\; x_1\!\in\!S_1, \,\ldots,\, x_n\!\in\!S_n \}. $$ Formally this means that the $1$-fold Cartesian product is the set of 1-tuples $(x)$ for all $x$ in the original set. If the original set is $\{0,1\}$, its $1$-fold Cartesian product would be $\{(0),(1)\}$, that is, it contains the two $1$-tuples.

As to what is an $n$-tuple, it is often defined as a function from the $n$-element index set $\{1,2,\ldots,n\}$ to the relevant domain (as explained in more detail in Dan Asimov's answer). Strictly speaking, an $1$-tuple of real numbers is then not a real number, but a function from $\{1\}$ to real numbers. But of course there is an obvious isomorphism.

However, for convenience or other reasons, one may want to simplify things and say that the $1$-fold Cartesian product is the original set itself. See, for example, Encyclopedia of Mathematics on direct product (a synonym for Cartesian product):

If $I$ consists of the single element ${1}$, then $\prod_I X_i = X_1$.

Then it proceeds to define the $n$-ary product inductively from the right, so using that definition the ternary product is $$\prod_{i=1}^3 X_i = \left(\prod_{i=1}^2 X_i\right) \times X_3 = \left(\left(\prod_{i=1}^1 X_i\right) \times X_2\right) \times X_3 = (X_1 \times X_2) \times X_3.$$ The EoM explicitly says that "sometimes one defines" it this way. The existence of different definitions is clearly acknowledged here. Note that in this inductive definition, EoM starts from $n=1$ (thus leaves the $n=0$ case undefined).

So the answer really is, "depends on your exact definition". There are in fact many questions on math.SE about how exactly the $n$-fold Cartesian product should be understood, for example whether $A \times B \times C = (A \times B) \times C$ or not. You may want to read them. Some examples:

EDIT (after edits on the question). According to the OP, in class they simply defined the binary Cartesian product $A \times B$. So strictly speaking the $n$-ary Cartesian product was not defined there, and it is up to the student's imagination (or the teacher's additional remarks) to extend it to $n \ne 2$.

If one defines it as the set of $n$-tuples, then $n=0$ leads to the set of $0$-tuples, which is a one-element set: $$ \{0,1\}^0 = \{()\}. $$ This has the expected cardinality $2^0 = 1$.

  • $\begingroup$ This makes more sense. But how about n=0? Please see the edit. $\endgroup$
    – user90237
    Sep 30 '21 at 0:37
  • $\begingroup$ @anon It is rude to change your question after it has received answers. But for $n=0$ you can think of $\{0,1\}^0$ as the set of all $0$-tuples with elements in $\{0,1\}$. There is only one such $0$-tuple: $()$. $\endgroup$ Sep 30 '21 at 0:57
  • $\begingroup$ Perhaps the esteemed downvoter would care to leave an illuminating comment on why exactly the answer is not useful? $\endgroup$ Oct 6 '21 at 15:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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