Is there a natural bijective proof of the identity $(2^i)^j = (2^j)^i$?

Question

As is well-known, iterating exponentials is a commutative operation. Assuming that $i$ and $j$ are positive integers, one way to view the integer $2^i$ is as the cardinality of the power set $2^{\{ 1 , \dots , i \}}$ (and likewise for $2^j$).

The equality $(2^i)^j = (2^j)^i$ implies that the sets $(2^{\{ 1 , \dots , i \}})^{\times j}$ (this means take the Cartesian product with itself $j$ times) and $(2^{\{ 1 , \dots , j \} })^{\times i}$ are in bijection with each other. My question is the following: is there a natural choice of bijection between these two sets that implies the equality $(2^i)^j = (2^j)^i$?

Just as an example: we know that $(2^1)^2 = (2^2)^1$. Enumerating $(2^{\{ 1 \} })^2$ and $2^{\{1,2 \}}$, the most natural correspondence between these two sets seems to be the following: $$(\varnothing , \varnothing) \leftrightarrow \varnothing,$$ $$(\{ 1 \} , \varnothing) \leftrightarrow \{1 \},$$ $$( \varnothing , \{ 1 \} ) \leftrightarrow \{ 2 \},$$ $$(\{ 1 \} , \{ 1 \}) \leftrightarrow \{ 1 , 2 \}.$$ It seems then that one way to make this task a little easier is to take advantage of the Boolean poset structure, since the product of ranked posets remains a ranked poset. This means we really reduce the problem to finding a bijection between elements of the same rank in the corresponding posets... in any case, I assume that this bijection is considered standard, I just don't know what it should be.

Edit: In view of the answers below, it seems that the correct way to do this naturally is to identify the power set $2^S$ with $\{ 0 , 1 \}^{S} := \operatorname{Hom} (S , \{ 0 ,1 \})$ (in the category of sets), then use the naturality of the bijection $(A^B)^C = A^{B \times C} = (A^C)^B$.

Following this bijection along explicitly, this corresponds to ``repacking" your brackets. What I mean by this is the following: let $(\{1 \} , \{ 2 \} , \{ 1,2 \} ) \subset (2^{\{ 1 , 2 \}})^3$. We know that this should correspond to a tuple $(2^{1,2,3})^2$. This is done by the following string of identifications: $$(\{ 1 \} , \{2 \} , \{ 1,2 \} ) \leftrightarrow ( \{ 1,0 \} , \{ 0 ,1 \} , \{ 1,1 \} )$$ $$\leftrightarrow (1,0,0,1,1,1 )$$ $$\leftrightarrow ( \{ 1 , 0, 0 \} , \{ 1 ,1,1 \} ) \leftrightarrow (\{1 \} , \{ 1,2,3 \} ) \in (2^{\{1,2,3\}})^2.$$ So, to recover the anticipated correspondence from my original question we see: $$(\varnothing , \varnothing ) \leftrightarrow ( \{ 0 \} , \{ 0 \} ) \leftrightarrow (\{ 0 , 0 \} ) \leftrightarrow \varnothing,$$ $$(\{1 \} , \varnothing ) \leftrightarrow ( \{ 1 \} , \{ 0 \} ) \leftrightarrow (\{ 1 ,0 \} ) \leftrightarrow \{ 1 \},$$ $$( \varnothing , \{ 1 \} ) \leftrightarrow ( \{ 0 \} , \{ 1 \} ) \leftrightarrow (\{ 0 ,1 \} ) \leftrightarrow \{ 2 \},$$ $$(\{ 1 \} , \{ 1 \} ) \leftrightarrow (\{ 1 \} , \{ 1 \} ) \leftrightarrow (\{ 1 , 1 \} ) \leftrightarrow \{ 1 ,2 \}.$$

Answer 1

I think the easiest way to understand this is by thinking in terms of functions. Letting $X^Y$ denote the set of functions from $Y$ to $X$ (and noting that this is appropriate in the sense that $\vert X^Y\vert=(\vert X\vert)^{\vert Y\vert}$), we want to build a bijection between $(A^B)^C$ and $(A^C)^B$ for any sets $A,B,C$.

Now to each $f\in (A^B)^C$ - that is, each function $C\rightarrow A^B$ - we can associate a function $\hat{f}\in (A^C)^B$ as follows: $$\hat{f}(b)=\lambda x\in C. f(x,b).$$

It's easy to check that the assignment $f\mapsto\hat{f}$ defines a bijection as desired. Note that this is all really just Currying and permuting inputs: Currying identifies $(A^B)^C$ and $A^{B\times C}$, and there's an obvious bijection between $A^{B\times C}$ and $A^{C\times B}$.

Answer 2

Yes.

Let $A^B$ denote the set of all functions from $B$ to $A$. Thus, $2^i$ is the set of all functions mapping $i:=\{0,1,2,\ldots,i-1\}$ to $2:=\{0,1\}$. (Easily identifiable with all the subsets of $i$.) Similarly, $(2^i)^j$ is the set of all functions mapping $j$ to $2^i$ (easily identifiable with $j$-tuplets of elements in $2^i$) etc.

In general, there is a canonical map of $(A^B)^C$ to $(A^C)^B$, which you can apply to your special case of $A=2, B=i, C=j$. It maps any given element (function) $f:C\to A^B$ to a function $g:B\to A^C$ such that $$g(b)(c)=f(c)(b)$$ for all $b\in B, c\in C$.

In your case, this mapping may be interpreted as follows: it maps a $j$-tuple $(A_0,A_1,\ldots,A_{j-1})$ of subsets of $\{0,1,2,\ldots,i-1\}$ into an $i$-tuple $(B_0,B_1,\ldots,B_{i-1})$ of subsets of $\{0,1,2,\ldots,j-1\}$ so that $$n\in B_m\iff m\in A_n$$ for all $0\le m\le i-1, 0\le n\le j-1$.

In the above, all the indices start from $0$. If you want, you can rewrite all of it using the indices starting from $1$.

Answer 3

$(2^i)^j$ corresponds to subsets of an $i\times j$ grid. Given a tuple $(S_1,\dots,S_j)$, where $S_k\subseteq\{1,\dots,i\}$ for each $k\in \{1,\dots,j\}$, the $k^\text{th}$ tuple entry determines the which cells in the $k^\text{th}$ column are included, for each $k\in \{1,\dots,j\}$.

On the other hand, $(2^j)^i$ also determines a subset of the $i\times j$ grid, where each tuple entry instead determines the subset of cells in the $\ell^\text{th}$ row for each $\ell\in \{1,\dots,i\}$.

Since the two are in bijection with the same thing, they are in bijection with each other.