1

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?

Asaf Karagila
  • 393,674
user90237
  • 11

3 Answers3

1

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\}$.

ConMan
  • 24,300
0

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

Jukka Kohonen
  • 2,729
  • This makes more sense. But how about n=0? Please see the edit. – user90237 Sep 30 '21 at 00:37
  • @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: $()$. – Misha Lavrov Sep 30 '21 at 00:57
  • Perhaps the esteemed downvoter would care to leave an illuminating comment on why exactly the answer is not useful? – Jukka Kohonen Oct 06 '21 at 15:59
0

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.

Dan Asimov
  • 1,157
  • 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. – Jukka Kohonen Sep 30 '21 at 01:16
  • 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. – Dan Asimov Sep 30 '21 at 01:25
  • 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. – Jukka Kohonen Sep 30 '21 at 01:31
  • PS But I think I see what you mean, and I hope I have fixed my post now. – Dan Asimov Sep 30 '21 at 01:31