Proving by induction how many elements are in the $n$-ary cartesian product between the two same sets.

Question

Here's a question that has been bugging me for a while.

Let $A$ be a set such that $A = \{a, b\}$. Then, $A_1 = A$, $\;A_2 = A \times A$, and for $n \in \mathbb{N}$, $A_n = A_{n-1} \times A$. How many elements are in $A_n$? Prove by induction.

Intuitively, it's easy to see that $A_n$ would have $2^n$ elements, as we are simply multiplying by an additional $2$ elements, $\{a, b\}$ by our previous iteration. I am also not allowed to use the cardinality of sets.

Any ideas? My attempt looked something like this:

Claim$(n)$: Let the cartesian product of $A$ be defined recursively as $A_n = A_{n-1} \times A$, where $A_n$ contains $2^n$ elements.

Claim$(1)$: $A_1 = A$, which has $2^{1}$ elements.

Claim$(k)$: Assume for all $k \in \mathbb{N}$, $A_k = A_{k-1} \times A$, where $A_k$ contains $2^k$ elements, as $2^k = 2^{k-1} \times 2$.

Claim$(k+1)$: We want to show that Claim$(k)$ holds for $A_{k+1} = A_k \times A$, where $A_{k+1}$ contains $2^{k+1}$ elements.

Next, I just did some simple arithmetic and showed that $2^{k+1} = 2^{k-1} \times 2^2$ which are just elements of previous iterations of our product. My prof said it wasn't enough, because I wasn't using the sets (?). Anyway, I'm stumped so any comments would be helpful.

Answer 1

First let's notice that, if $A, B$ are any finite sets, then, $|A\times B| = |A||B|$.

Let $P(n)$ be the predicate that $A_n$ has $2^n$ elements, for any positive integer $n$. $P(1)$ is true since $|A_1|=|A|=|\{a,b\}|=2^1=2$. Now, pick any $k \ge 1$ and suppose $P(k)$ were true. By definition $A_{k+1} = A_k \times A$. Therefore, $|A_{k+1}| = |A_k| |A| = 2^k \cdot 2 = 2^{k+1}$, using the fact that $P(k)$ is true. Therefore, by the standard inductive argument, $P(k)$ is true for all positive integer $k$.

Answer 2

You have most of the right ideas, but they're kind of swimming around in a way that makes the argument difficult to discern. I agree with your professor's criticism that you don't explicitly tie things back to the sets.

Notation: The size (often called cardinality) of a finite set $A$ is denoted $|A|$.

Let's prove the following claim.

$|A_n| = 2^n$ for each $n \in \mathbb{N}$.

The base case for induction is $n=1$, where we can see that $|A_1| = |A| = |\{a, b\}| = 2$.

Now suppose that $|A_k| = 2^k$ for some $k \geq 1$. We would like to show that $|A_{k+1}| = 2^{k+1}$. By the definition of these iterated cartesian products, $A_{k+1} = A_k \times A = A_k \times \{a, b\}$. This set consists of pairs $(x, y)$, where $x \in A_k$ and either $y=a$ or $y=b$. Hence, we can sort the elements into two bins: $\{(x, a)\}$ and $\{(x, b)\}$, and since the second element in each case is a singleton, each of these subsets can be identified with $A_k$ itself. They don't overlap since the second element differs between the two subsets. Therefore, $$ |A_{k+1}| = |A_k \times A| = |A_k| + |A_k| = 2 \cdot |A_k| = 2 \cdot 2^k = 2^{k+1}, $$ as desired.