nyuuzyou/wikis huggingface dataset:
Cardinality of Finite Vector Space

== Theorem ==
Let $K$ be a Galois field.
Let $V$ be a $K$-vector space.
Let the dimension of $V$ be finite.
Then:
:$\size V = \size K^{\map \dim V}$
== Proof ==
By Isomorphism from $\R^n$ via $n$-Term Sequence, $V$ is isomorphic to the $K$-vector space $K^{\map \dim V}$.
Thus:
:$\size V = \size {K^{\map \dim V} }$
By Cardinality of Finite Cartesian Space:
:$\size {K^{\map \dim V} } = \size K^{\map \dim V}$
Thus:
:$\size V = \size K^{\map \dim V}$
Category:Vector Spaces
Cardinality of Generator of Vector Space is not Less than Dimension

== Theorem ==
Let $V$ be a vector space over a field $F$.
Let $\BB$ be a generator for $V$ containing $m$ elements.
Then:
:$\map {\dim_F} V \le m$
where $\map {\dim_F} V$ is the dimension of $V$.
== Proof 1 ==
== Proof 2 ==
Category:Generators of Vector Spaces
Category:Dimension of Vector Space
Category:Cardinality of Generator of Vector Space is not Less than Dimension
Cardinality of Generator of Vector Space is not Less than Dimension/Proof 1

== Theorem ==
== Proof ==
Let $\BB = \set {x_1, x_2, \ldots, x_m}$ be a generator for $G$.
Let $\set {y_1, y_2, \ldots, y_n}$ be a subset of $G$ such that $n > m$.
As $\BB$ generates $G$, there exist $\alpha_{i j} \in F$ where $1 \le i \le m, 1 \le j \le n$ such that:
:$\ds \forall j: 1 \le j \le n: y_j = \sum_{i \mathop = 1}^m \alpha_{i j} x_i$
Now let $\beta_1, \ldots, \beta_n$ be elements of $F$.
Then:
:$\ds \sum_{j \mathop = 1}^n \beta_j y_j = \sum_{i \mathop = 1}^m \sum_{j \mathop = 1}^n \paren {\alpha_{i j} \beta_j} x_i$
As $n > m$ the result Homogeneous Linear Equations with More Unknowns than Equations can be applied.
That is, there exist $\beta_1, \ldots, \beta_n \in F$ which are not all zero such that:
:$\ds \forall i: 1 \le i \le m: y_j = \sum_{j \mathop = 1}^n \alpha_{i j} \beta_j = 0$
That is, such that:
:$\ds \sum_{j \mathop = 1}^n \beta_j y_j = 0$
So $\set {y_1, y_2, \ldots, y_n}$ is linearly dependent.
The result follows by definition of dimension.
== Sources ==
* : Chapter $\text {I}$: Elementary Definitions: $\S 4$. Vector Spaces: Theorem $4.2$
Category:Cardinality of Generator of Vector Space is not Less than Dimension
Cardinality of Generator of Vector Space is not Less than Dimension/Proof 2

== Theorem ==
== Proof ==
From Generator of Vector Space Contains Basis there exists a basis $B$ of $E$ such that $B \subseteq G$.
From Cardinality of Basis of Vector Space, $\card B = n$.
The result follows.
== Sources ==
* : Chapter $\text {V}$: Vector Spaces: $\S 27$. Subspaces and Bases: Theorem $27.14$
* : Chapter $7$: Vector Spaces: $\S 34$. Dimension: Theorem $67 \ \text{(iii)}$
* : $\text{A}.2$: Linear algebra and determinants: Theorem $\text{A}.7$
Category:Cardinality of Generator of Vector Space is not Less than Dimension
Cardinality of Image of Injection

== Theorem ==
Let $f: S \rightarrowtail T$ be an injection.
Let $A \subseteq S$ be a finite subset of $S$.
Then:
:$\card {f \paren A} = \card A$
where $\card A$ denotes the cardinality of $A$.
== Proof ==
Proof by induction:
For all $n \in \N_{>0}$, let $P_n$ be the proposition:
:$\card {f \paren A} = \card A$ when $\card A = n$
Suppose $\card A = 0$.
So $P_0$ holds.
=== Basis for the Induction ===
Suppose $\card A = 1$.
Then let $A = \set a$.
So:
:$f \paren A = \set {f \paren a}$
and so:
:$\card {f \paren A} = 1$
So $P_1$ is true.
This is our basis for the induction.
=== Induction Hypothesis ===
Now we need to show that, if $P_k$ is true, where $k \ge 1$, then it logically follows that $P_{k + 1}$ is true.
So this is our induction hypothesis:
:$\card {f \paren A} = \card A$ when $\card A = k$
Then we need to show:
:$\card {f \paren A} = \card A$ when $\card A = k + 1$
=== Induction Step ===
This is our induction step:
Consider $A$ where $\card A = k+1$.
Let $s \in A$ and consider $A' = A \setminus \set s$.
Let $f {\restriction_{A'} }$ be the restriction of $f$ to $A'$.
By Restriction of Injection is Injection we have that $f {\restriction_{A'} }$ is also an injection.
Then by the induction hypothesis:
:$\card {f {\restriction_{A'} } \paren {A'} } = \card {A'}$
because $\card {A'} = k$.
Now consider $f \paren s$.
Suppose $f \paren s \in f {\restriction_{A'} } \paren {A'}$.
Then:
:$\exists t \in A': f \paren t = f \paren s$
and so $f$ would not be an injection.
So:
:$f \paren s \notin f {\restriction_{A'} } \paren {A'}$ and so:
So $P_k \implies P_{k + 1}$ and the result follows by the Principle of Mathematical Induction.
== Sources ==
* : $\S 22.2$: Injections; bijections; inverse of a bijection
Category:Injections
Category:Cardinality
Cardinality of Image of Mapping not greater than Cardinality of Domain

== Theorem ==
Let $S$ and $T$ be sets.
Let $f: S \to T$ be a mapping.
Let $\card S$ denote the cardinal number of $S$.
Then:
:$\card {\Img f} \le \card S$
== Proof ==
By Restriction of Mapping to Image is Surjection, the mapping:
:$f: S \to \Img f$
is a surjection.
Let $h$ be a mapping such that:
:$h: \card S \to S$
is a bijection.
By Composite of Surjections is Surjection:
:$f \circ h: \card S \to \Img f$
is a surjection.
Construct a set $R$ such that:
:$R = \set {x \in \card S: \forall y \in x: \map f {\map h x} \ne \map f {\map h y} }$
It follows that:
:$R \subseteq \card S$
By Subset of Ordinal implies Cardinal Inequality:
:$\card R \le \card S$
Suppose:
:$x \in R$
:$y \in R$
:$\map f {\map h x} = \map f {\map h y}$
Then, $x$ and $y$ are ordinals and by Ordinal Membership is Trichotomy:
:$x < y \lor x = y \lor y < x$
If $x < y$, then:
:$\map f {\map h x} \ne \map f {\map h y}$ by the definition of $R$.
Similarly, $y < x$ implies that:
:$\map f {\map h x} \ne \map f {\map h y}$
Therefore, $x = y$.
It follows that the restriction $f \circ h \restriction_R : R \to \Img f$ is an injection.
Finally, by the definition of surjection, for all $x \in \Img f$, there is some $y \in \card S$ such that:
:$\map f {\map h y} = x$
But since this is true for some $y$, the set:
:$\set {\map y \in \card S: \map f {\map h y} = x}$
has a minimal element.
For this minimal element $y$, it follows that:
:$\forall z \in y: \map f {\map h z} \ne \map f {\map h y}$
since if it were equal, this would contradict the fact that $y$ is a $\in$-minimal element.
It follows that the restriction $f \circ h \restriction_R : R \to \Img f$ is a bijection.
By the definition of set equivalence, $R \sim \Img f$.
So:
== Sources ==
* : $\S 10.26$
Category:Images
Category:Cardinality
Cardinality of Image of Mapping of Intersections is not greater than Weight of Space

== Theorem ==
Let $T = \struct {X, \tau}$ be a topological space.
Let $f: X \to \tau$ be a mapping such that:
:$\forall x \in X: \paren {x \in \map f x \land \forall U \in \tau: x \in U \implies \map f x \subseteq U}$
Then the cardinality of the image of $f$ is no greater than the weight of $T$:
:$\card {\Img f} \le \map w T$
== Proof ==
By definition of weight, there exists a basis $\BB$ of $T$ such that:
:$\card \BB = \map w T$
By Image of Mapping of Intersections is Smallest Basis:
:$\Img f \subseteq \BB$
Thus by Subset implies Cardinal Inequality:
:$\card {\Img f} \le \card \BB = \map w T$
== Sources ==
* 
* 
Category:Topology
Category:Cardinals
Cardinality of Image of Set not greater than Cardinality of Set

== Theorem ==
Let $X, Y$ be sets.
Let $f: X \to Y$ be a mapping.
Let $A$ be a subset of $X$.
Then:
:$\card {\map {f^\to} A} \le \card A$
where $\card A$ denotes the cardinality of $A$.
== Proof ==
By definitions of surjection and restriction of mapping:
:$F \restriction_A: A \to \map {f^\to} A$ is a surjection
Thus by Surjection iff Cardinal Inequality:
:$\card {\map {f^\to} A} \le \card A$
== Sources ==
* 
Category:Cardinals
Category:Images
Cardinality of Infinite Sigma-Algebra is at Least Cardinality of Continuum

== Theorem ==
Let $\MM$ be an infinite $\sigma$-algebra on a set $X$.
Then $\MM$ is has cardinality at least that of the cardinality of the continuum $\mathfrak c$:
:$\map \Card \MM \ge \mathfrak c$
=== Corollary ===
== Proof ==
Let:
:$\mathbb M_\infty := \set {A \in \MM : \map \Card {\MM_A} = \infty}$
where:
:$\MM_A$ denotes the trace $\sigma$-algebra of $A$ in $\MM$
Let $A \in \mathbb M_\infty$.
Observe:
Thus:
:$\forall B \in \MM_A : B \in {\mathbb M}_\infty \lor A \setminus B \in {\mathbb M}_\infty$
In particular:
:$\forall A \in {\mathbb M}_\infty : \exists B \in {\mathbb M}_\infty : B \subsetneq A$
That is:
:$\O \not \in \mathbb S$
where:
:$\mathbb S := \set {\set {\tuple {A, B} : B \in \mathbb M_\infty, B \subsetneq A} : A \in \mathbb M_\infty}$
By Axiom of Choice, there is a choice function:
:$\tilde f : \mathbb S \to \bigcup \mathbb S$
In particular, it satisfies:
:$\forall A \in \mathbb M_\infty : \map {\tilde f} {\set {\tuple {A, B} : B \in \mathbb M_\infty, B \subsetneq A} } \in \set {\tuple {A, B} : B \in \mathbb M_\infty, B \subsetneq A}$
Hence there exists a mapping:
:$f : \mathbb M_\infty \to \mathbb M_\infty$
such that:
:$\forall A \in \mathbb M_\infty : \map f A \subsetneq A$
More specifically, we can define:
:$\map f A := \map {\pr_2} {\map {\tilde f} {\set {\tuple {A, B} : B \in \mathbb M_\infty, B \subsetneq A} } }$
where $\pr_2$ denotes the second projection of $\paren {\mathbb M_\infty}^2$.
Let:
:$F_i := \map {f^i} X \setminus \map {f^{i + 1} } X$
for $i \in \N$.
Then $\sequence {F_i}_{i \mathop \in \N}$ are non-empty pairwise disjoint sets in $\MM$.
We can define an injection $\powerset \N \to \MM$ by:
:$\ds N \mapsto \bigsqcup_{i \mathop \in N} F_i$
That is:
:$\map \Card \MM \ge \map \Card {\powerset \N}$
But by Power Set of Natural Numbers has Cardinality of Continuum:
:$\map \Card {\powerset \N} = \mathfrak c$
Hence the result.
== Sources ==
* : Exercise $1.3$
Category:Cardinality of Infinite Sigma-Algebra is at Least Cardinality of Continuum
Category:Cardinality of Continuum
Category:Sigma-Algebras
Cardinality of Infinite Sigma-Algebra is at Least Cardinality of Continuum/Corollary

== Corollary to Cardinality of Infinite Sigma-Algebra is at Least Cardinality of Continuum ==
Let $\MM$ be an infinite $\sigma$-algebra on a set $X$.
Then $\MM$ is uncountable.
== Proof ==
From Cardinality of Infinite Sigma-Algebra is at Least Cardinality of Continuum, $\MM$ has at least the cardinality of the set of real numbers $\R$.
The result follows from Real Numbers are Uncountable.
== Sources ==
* : Exercise $1.3$
Category:Cardinality of Infinite Sigma-Algebra is at Least Cardinality of Continuum
Cardinality of Integer Interval

== Theorem ==
Let $a, b \in \Z$ be integers.
Let $\left[{a \,.\,.\, b}\right]$ denote the integer interval between $a$ and $b$.
Then $\left[{a \,.\,.\, b}\right]$ is finite and its cardinality equals:
:$\begin{cases} 
b - a + 1 & : b \ge a - 1 \\ 
0 & : b \le a - 1 
\end{cases}$
== Proof ==
Let $b < a$.
Then $\left[{a \,.\,.\, b}\right]$ is empty.
By Empty Set is Finite, $\left[{a \,.\,.\, b}\right]$ is finite.
By Cardinality of Empty Set, $\left[{a \,.\,.\, b}\right]$ has cardinality $0$.
Let $b \ge a$.
By Translation of Integer Interval is Bijection, there exists a bijection between $\left[{a \,.\,.\, b}\right]$ and $\left[{0 \,.\,.\, b - a}\right]$.
Thus $\left[{a \,.\,.\, b}\right]$ is finite of cardinality $b - a + 1$.
Category:Set Theory
Cardinality of Linearly Independent Set is No Greater than Dimension

== Theorem ==
Let $E$ be a vector space of $n$ dimensions.
Let $H$ be a linearly independent subset of $E$.
Then:
:$H$ has at most $n$ elements.
== Proof ==
Let $H$ be a linearly independent subset of $E$.
By definition of dimension of vector space, $E$ has a basis with exactly $n$ elements.
By Sufficient Conditions for Basis of Finite Dimensional Vector Space, $B$ is a generator for $E$.
Then by Size of Linearly Independent Subset is at Most Size of Finite Generator, $H$ has at most $n$ elements.
== Sources ==
* : Chapter $\text {V}$: Vector Spaces: $\S 27$. Subspaces and Bases: Theorem $27.14$
* : Chapter $7$: Vector Spaces: $\S 34$. Dimension: Theorem $67 \ \text{(ii)}$
* : $\text{A}.2$: Linear algebra and determinants: Theorem $\text{A}.7$
Category:Linear Independence
Cardinality of Mapping

== Theorem ==
Let $S$ be a finite set whose cardinality is $n$:
:$\card S = n$
Let $T$ be a non-empty set
Let $f: S \to T$ be a mapping.
Then:
:$\card f = n$
== Proof ==
First suppose $T = \O$ there are no elements in $f$
From Null Relation is Mapping iff Domain is Empty Set, there are no elements in $f$.
Hence in this case $\card f = 0$, whatever $\card S$ may be,
By definition of mapping, $f$ is a set of ordered pairs $\tuple {s, t}$ where $s \in S$ and $t \in T$, such that:
:$(1): \quad \forall s \in S: \exists \tuple {s, t} \in f$
and:
:$(2): \quad \forall x \in S: \tuple {s, t_1} \in f \land \tuple {s, t_2} \in f \implies t_1 = t_2$
From $(1)$ it follows that $\card f \ge n$.
 that $\card f > n$.
Then by the Pigeonhole Principle:
:$\exists x \in f: \exists y_1, y_2 \in T, y_1 \ne y_2: \tuple {x, y_1} \in f \land \tuple {x, y_2} \in f$
and so $f$ is not a mapping.
From this contradiction it follows that $\card f = n$.
== Sources ==
* : Appendix $\text{A}.4$: Functions
Category:Mapping Theory
Category:Cardinality
Cardinality of Master Code

== Theorem ==
Let $\map V {n, p}$ be a master code of length $n$ modulo $p$.
Then there are $p^n$ elements of $\map V {n, p}$.
== Proof ==
For each term of a sequence in $\map V {n, p}$ there are $p$ possible values.
There are $n$ such terms.
Hence there are $\underbrace {p \times p \times \cdots \times p}_{n \text { times} } = p^n$ different possible sequences in $\map V {n, p}$.
== Sources ==
* : Chapter $6$: Error-correcting codes
Category:Linear Codes
Cardinality of Maximal Independent Subset Equals Rank of Set

== Theorem ==
Let $M = \struct{S, \mathscr I}$ be a matroid.
Let $A \subseteq S$.
Let $X$ be a maximal independent subset of $A$.
Then:
:$\card X = \map \rho A$
where $\rho$ is the rank function on $M$.
== Proof ==
From Independent Subset is Contained in Maximal Independent Subset:
:$\exists Y \in \mathscr I : X \subseteq Y \subseteq A : \card Y = \map \rho A$
By definition of a maximal independent Subset of $A$:
:$X = Y$
The result follows.
Category:Matroid Independent Subsets
Category:Matroid Rank Functions
Cardinality of Power Set is Invariant

== Theorem ==
Let $X, Y$ be sets.
Let $\card X = \card Y$
where $\card X$ denotes the cardinality of $X$.
Then:
:$\card {\powerset X} = \card {\powerset Y}$
where $\powerset X$ denotes the power set of $X$.
== Proof ==
By definition of cardinality:
:$X \sim Y$
where $\sim$ denotes the set equivalence.
Then by definition of set equivalence:
: there exists a bijection $f: X \to Y$
By definition of bijection
:$f$ is an injection and a surjection.
By Mapping is Injection iff Direct Image Mapping is Injection:
:the direct image mapping $\map {f^\to}: \powerset X \to \powerset Y$ is an injection.
By Direct Image Mapping of Surjection is Surjection:
:$f^\to$ is a surjection.
Then by definition of bijection:
:$f^\to: \powerset X \to \powerset Y$ is a bijection.
Hence by definition of set equivalence:
:$\powerset X \sim \powerset Y$
Thus the result by definition of cardinality:
:$\card {\powerset X} = \card {\powerset Y}$
== Sources ==
* 
Category:Cardinals
Category:Power Set
Cardinality of Power Set of Finite Set

== Theorem ==
Let $S$ be a set such that:
:$\card S = n$
where $\card S$ denotes the cardinality of $S$,
Then:
:$\card {\powerset S} = 2^n$
where $\powerset S$ denotes the power set of $S$.
Thus it can be seen that the power set's alternative notation $2^S$ is indeed appropriate.
However, because of possible confusion over the conventional meaning of $2^n$, its use is deprecated.
== Proof 1 ==
== Proof 2 ==
== Proof 3 ==
== Informal Proof ==
== Sources ==
* : $\S 5$: Complements and Powers
* : $\S 13$: Arithmetic
* : $\S 1$: Sets and Set Inclusion: Problem $3 \ \text {(d)}$
* : Chapter $1$. Sets: Exercise $13$
* : Chapter $\text I$: Algebraic Structures: $\S 1$: The Language of Set Theory: Exercise $1.8$
* : $\text {3-1}$ Permutations and Combinations: Exercise $1$
* : Chapter $1$: Mappings: $\S 15 \alpha$
* : $\S 10.49$
* : Chapter $1$: Theory of Sets: $\S 6$: Functions: Exercise $8$
* : Appendix $\text{A}.6$: Mathematical Induction: Problem Set $\text{A}.6$: $41$
* : Chapter $1$: Preliminaries: $1.4$ Set Notation: Example $1.2$
* : Chapter $1$: Sets and mappings: $\S 1.2$: Sets: Exercise $4$
* : Appendix $\text{A}.6$: Cardinality (in passing)
* 
* 
* : Appendix $\text{A}.5$: Theorem $\text{A}.30$
Category:Power Set
Category:Combinatorics
Category:Cardinality
Category:Cardinality of Power Set
Cardinality of Power Set of Finite Set/Informal Proof

== Theorem ==
== Proof ==
Given an element $x$ of $S$, each subset of $S$ either includes $x$ or does not include $x$ (this follows directly from the definition of a set), which gives us two possibilities.
The same reasoning holds for any element of $S$.
One can intuitively see that this means that there are $\ds \underbrace {2 \times 2 \times \ldots \times 2}_{\card S} = 2^{\card S}$ total possible combinations of elements of $S$.
This is exactly $\card {\powerset S}$.
=== Motivation ===
The formal mathematical backing for the intuitive leap made in this "proof" is non-trivial, so while this it serves as an excellent demonstration of why this result holds true, it does not constitute a fully rigorous proof of this theorem.
== Sources ==
* : $\text I$. Algebra: Permutations and Combinations: The number of selections from $n$ things if any number may be taken
* : Chapter $1$: Rings - Definitions and Examples: $2$: Some examples of rings: Ring Example $6$
* : $\S 6.8$: Subsets
Category:Cardinality of Power Set
Cardinality of Power Set of Finite Set/Proof 1

== Theorem ==
== Proof ==
Let $T = \set {0, 1}$.
For each $A \in \powerset S$, we consider the characteristic function $\chi_A: S \to T$ defined as:
:$\forall x \in S: \map {\chi_A} x = \begin{cases}
1 & : x \in A \\
0 & : x \notin A
\end{cases}$
Now consider the mapping $f: \powerset S \to T^S$:
:$\forall A \in \powerset S: \map f A = \chi_A$
where $T^S$ is the set of all mappings from $S$ to $T$.
Also, consider the mapping $g: T^S \to \powerset S$:
:$\forall \phi \in T^S: \map g \phi = \phi^{-1} \sqbrk {\set 1}$
where $\phi^{-1} \sqbrk {\set 1}$ is the preimage of $\set 1$ under $\phi$.
Consider the characteristic function of $\phi^{-1} \sqbrk {\set 1}$, denoted $\chi_{\phi^{-1} \sqbrk {\set 1} }$.
We have:
So:
So $f \circ g = I_{T^S}$, that is, the identity mapping on $T^S$.
So far so good. Now we consider the preimage of $\set 1$ under $\chi_A$:
: $\chi_A^{-1} \sqbrk {\set 1} = A$
from the definition of the characteristic function $\chi_A$ above.
Thus:
So $g \circ f = I_{\powerset S}$, that is, the identity mapping on $\powerset S$.
It follows from Bijection iff Left and Right Inverse that $f$ and $g$ are bijections.
Thus by Cardinality of Set of All Mappings the result follows.
== Sources ==
* : $\S 8$: Functions
* : $\S 3.7$. Similar sets: Example $57$
* : Chapter $\text {III}$: The Natural Numbers: $\S 19$: Combinatorial Analysis: Theorem $19.5$
* : $\S 2$: Sets and functions: Graphs and functions
* : $\S 8$: Theorem $8.1$
* : Chapter $1$: Sets and mappings: Further exercises: $3$
Category:Cardinality of Power Set
Cardinality of Power Set of Finite Set/Proof 2

== Theorem ==
== Proof ==
Enumerating the subsets of $S$ is equivalent to counting all of the ways of selecting $k$ out of the $n$ elements of $S$ with $k = 0, 1, \ldots, n$.
So, from Cardinality of Set of Subsets, the number we are looking for is:
:$\ds \card {\powerset S} = \sum_{k \mathop = 0}^n \binom n k$
But from the binomial theorem:
:$\ds \paren {x + y}^n = \sum_{k \mathop = 0}^n \binom n k x^{n - k} y^k$
It follows that:
:$2^n = \ds \paren {1 + 1}^n = \sum_{k \mathop = 0}^n \binom n k \paren 1^{n - k} \paren 1^k = \sum_{k \mathop = 0}^n \binom n k = \card {\powerset S}$
== Sources ==
* : Introduction $\S 1$: Operations on Sets
* : $\S 2.3$. Partitions: Example $35$
Category:Cardinality of Power Set
Cardinality of Power Set of Finite Set/Proof 3

== Theorem ==
== Proof ==
Proof by induction:
For all $n \in \N$, let $\map P n$ be the proposition:
:$\card S = n \implies \card {\powerset S} = 2^n$
Do not confuse $\map P n$, which is a propositional function on $\N$, with $\powerset S$, the power set of $S$.
=== Basis for the Induction ===
From Cardinality of Empty Set:
: $S = \O \iff \card S = 0$
Then:
: $\powerset \O = \set \O$
has one element, that is, $\O$.
So:
: $\card {\powerset \O} = \card {\set \O} = 1 = 2^0$
thus confirming that $\map P 0$ holds.
This is our basis for the induction.
=== Induction Hypothesis ===
Now we need to show that, if $\map P k$ is true, where $k \ge 2$, then it logically follows that $\map P {k + 1}$ is true.
So this is our induction hypothesis:
:$\card S = k \implies \card {\powerset S} = 2^k$
Then we need to show:
:$\card S = k + 1 \implies \card {\powerset S} = 2^{k + 1}$
=== Induction Step ===
This is our induction step:
Let $\card S = k + 1$.
Let $x \in S$.
Consider the set $S' = S \setminus \set x$ where $x$ is any element of $S$.
We see that $\card {S'} = k$.
Now adjoin $x$ to all the subsets of $S'$.
Counting the subsets of $S$, we have:
: all the subsets of $S'$
and:
: all the subsets of $S'$ with $x$ adjoined to them.
From the induction hypothesis, there are $2^k$ subsets of $S'$.
Adding $x$ to each of these does not change their number, so there are another $2^k$ subsets of $S$ consisting of all the subsets of $S'$ with $x$ adjoined to them.
In total that makes $2^k + 2^k = 2 \times 2^k = 2^{k + 1}$ subsets of $S$.
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
:$\forall n \in \N: \card S = n \implies \card {\powerset S} = 2^n$
== Sources ==
* : $\S 0.6$: Theorem $8: \ 1$
Category:Cardinality of Power Set
Cardinality of Power Set of Natural Numbers Equals Cardinality of Real Numbers

== Theorem ==
The cardinality of the power set of the natural numbers is equal to the cardinality of the real numbers.
== Proof ==
This is a direct corollary of Power Set of Natural Numbers has Cardinality of Continuum.
Category:Cardinality
Category:Power Set
Category:Natural Numbers
Category:Infinite Sets
Category:Cardinals
Cardinality of Proper Subset of Finite Set

== Theorem ==
Let $A$ and $B$ be finite sets such that $A \subsetneqq B$.
Let $\card B = n$, where $\card {\, \cdot \,}$ denotes cardinality.
Then $\card A < n$.
== Proof ==
The proof proceeds by the Principle of Mathematical Induction on $n$, the cardinality of $B$.
Let $S$ be the set of $n \in \N$ such that every proper subset of any set with $m$ elements is finite and has (strictly) fewer than $n$ elements.
=== Basis for the Induction ===
The case $n = 0$ is verified as follows:
Suppose $\card B = 0$.
From Cardinality of Empty Set, $B = \O$. 
There are no sets $A$ such that $A \subsetneq \O$.
Therefore $0 \in S$ by vacuous truth.
This is the basis for the induction.
=== Induction Hypothesis ===
Fix $k \in \N$ with $k \ge 0$.
Suppose that $k \in S$.
That is:
:every proper subset of any set with $k$ elements is finite and has (strictly) fewer than $k$ elements.
This is our induction hypothesis.
It remains to be proved that $k + 1 \in S$:
:every proper subset of any set with $k + 1$ elements is finite and has (strictly) fewer than $k + 1$ elements.
=== Induction Step ===
This is our induction step:
Suppose we have any set $B$ such that $\card B = k + 1$.
Let $A \subsetneqq B$.
From the definition of $\subsetneqq$:
:$\exists b \in B: b \notin A$
Therefore:
:$A \subseteq B \setminus \set b$
From Cardinality Less One:
:$\card {B - \set b} = k$
Suppose $A = B - \set b$.
Then $\card A = k < k + 1$ and so has fewer than $k + 1$ elements and is finite by definition.
Otherwise:
:$A \subsetneqq B - \set b$
So by the induction hypothesis:
:$A$ is finite and has fewer than $k$ elements.
But as $k < k + 1$ it also follows that $A$ is finite and has fewer than $k + 1$ elements.
Thus $A \in S$.
The result follows by the Principle of Mathematical Induction.
== Sources ==
* : $\S 13$: Arithmetic
* : $\S 3.7$. Similar sets: Example $56$
* : Chapter $\text {III}$: The Natural Numbers: $\S 17$: Finite Sets: Theorem $17.5$
* : $1$: Set Theory and Logic: $\S 6$: Finite Sets: Theorem $6.2$
* : $1$: Set Theory and Logic: $\S 6$: Finite Sets: Corollary $6.6$
Category:Proper Subsets
Category:Cardinality
Category:Proofs by Induction