description/proof of that 'positive natural number'-th power of cardinality of set is that times multiplication of cardinality
Topics
About: set
The table of contents of this article
Starting Context
- The reader knows a definition of set.
- The reader knows a definition of cardinality of set.
Target Context
- The reader will have a description and a proof of the proposition that for the cardinality of any set, any 'positive natural number'-th power of the cardinality is the natural number times multiplication of the cardinality.
Orientation
There is a list of definitions discussed so far in this site.
There is a list of propositions discussed so far in this site.
Main Body
1: Structured Description
Here is the rules of Structured Description.
Entities:
\(S\): \(\in \{\text{ the sets }\}\)
\(n\): \(\in \mathbb{N} \setminus \{0\}\)
//
Statements:
\((Card (S))^n = Card (S) ... Card (S)\), which is the \(n\) times multiplication
//
2: Note
The proposition is not so obvious, because \((Card (S))^n\) is not defined as the \(n\) times multiplication, but as the cardinality of \(\{f \in Pow (n \times S) \vert f: n \to S\}\).
Only because of this proposition, \((Card (S))^n\) can be regarded to be the \(n\) times multiplication.
3: Proof
Whole Strategy: prove it inductively; Step 1: see that it holds for \(n = 1\); Step 2: suppose that it holds for \(n = n'\) where \(1 \le n'\), and see that it holds for \(n = n' + 1\); Step 3: conclude the proposition.
Step 1:
For \(n = 1\), \((Card (S))^n = Card (S)\), because it is the cardinality of the set of the functions, \(F:= \{f \in Pow (1 \times S) \vert f: 1 \to S\}\) where \(1 = \{0\}\).
Step 2:
Let us suppose that for \(n = n'\) where \(n' \in \mathbb{N} \setminus \{0\}\) such that \(1 \le n'\) is any, \((Card (S))^n = Card (S) ... Card (S)\), which is the \(n\) times multiplication.
\((Card (S))^{n + 1}\) is the cardinality of the set of the functions, \(F:= \{f \in Pow ((n + 1) \times S) \vert f: (n + 1) \to S\}\).
Any \(f \in F\) is \(f = f' \cup \{\langle n + 1, s \rangle\}\) where \(f'\) is any \(f' \in F':= \{f' \in Pow (n \times S) \vert f': n \to S\}\) and \(s\) is any \(s \in S\).
On the other hand, \((Card (S))^n Card (S) = Card (F') Card (S) = Card (F' \times S)\) by the definition of arithmetic of cardinalities.
Any element of \(F' \times S\) is \(\langle f', s \rangle\) where \(f'\) is any \(f' \in F'\) and \(s\) is any \(s \in S\).
There is the bijection, \(g: F \to F' \times S, f' \cup \{\langle n + 1, s \rangle\} \mapsto \langle f', s \rangle\), so, \((Card (S))^{n + 1} = Card (F) = Card (F' \times S) = Card (F') Card (S) = Card (S) ... Card (S)\), which is the \(n + 1\) times multiplication.
Step 3:
So, by the induction principle, for any natural number, \(n\), \((Card (S))^n = Card (S) ... Card (S)\), which is the \(n\) times multiplication.
