avewright/proofwiki-math huggingface dataset:
Theorem: Rank is Ordinal

Let $S$ be a small class
The rank of $S$ is an ordinal.

Proof:
{{NotZFC}}
The rank of $S$ is an intersection of a set of ordinals $B$.
$B$ is non-empty by the fact that Set has Rank.
Thus, $B$ has a minimal element, which is the rank of $S$ plus $1$.
Therefore, the rank is itself an ordinal.
{{qed}}
Theorem: Ordinal Equal to Rank

Let $x$ be an ordinal.
Let $S$ be a small class.
Let $\map V x$ denote the von Neumann hierarchy on the ordinal $x$.
Then $x$ equals the rank of $S$ {{iff}} $S \in \map V {x + 1} \land S \notin \map V x$.

Proof:
{{NotZFC}}
Theorem: Group Direct Product of Cyclic Groups/Corollary

Let $n_1, n_2, \ldots, n_s$ be a finite sequence of integers, all greater than $1$, such that for any pair of them $n_i$ and $n_j$, $n_i \perp n_j$.
Let $G_i$ be a cyclic group of order $n_i$ for each $i: 1 \le i \le s$.
Then $G_1 \times G_2 \times \cdots \times G_s$ is cyclic of order $n_1 n_2 \ldots n_s$.

Proof:
When $s = 1$ the result is trivial.
Assume the result holds for $s = k$.
Then $H = G_1 \times G_2 \times \ldots \times G_k$ is cyclic of order $n_1 n_2 \ldots n_k$.
Applying the main result to $H \times G_{k + 1}$ gives us the result for $s = k + 1$.
The result follows by induction.
{{qed}}
Theorem: Divisor Count Function of Prime Number

Let $p \in \Z_{> 0}$.
Then $p$ is a prime number {{iff}}:
:$\map {\sigma_0} p = 2$
where $\map {\sigma_0} p$ denotes the divisor count function of $p$.

Proof:
=== Necessary Condition ===
Let $p$ be a prime number.
Then, by definition, the only positive divisors of $p$ are $1$ and $p$.
Hence by definition of the divisor count function:
:$\map {\sigma_0} p = 2$
{{qed|lemma}}
=== Sufficient Condition ===
Suppose $\map {\sigma_0} p = 2$.
Then by One Divides all Integers we have:
:$1 \divides p$
Also, by Integer Divides Itself we have:
:$p \divides p$
So if $p > 1$ it follows that $\map {\sigma_0} p \ge 2$.
Now for $\map {\sigma_0} p = 2$ it must follow that the only divisors of $p$ are $1$ and $p$.
That is, that $p$ is a prime number.
{{qed}}
Theorem: Join is Commutative

Let $\struct {S, \vee, \preceq}$ be a join semilattice.
Then $\vee$ is commutative.

Proof:
Let $a, b \in S$ be arbitrary.
Then:
{{begin-eqn}}
{{eqn | l = a \vee b
      | r = \sup \set {a, b}
      | c = {{Defof|Join (Order Theory)}}
}}
{{eqn | r = \sup \set {b, a}
      | c = {{Defof|Set Equality}}
}}
{{eqn | r = b \vee a
      | c = {{Defof|Join (Order Theory)}}
}}
{{end-eqn}}
Hence the result.
{{qed}}
Theorem: Meet is Commutative

Let $\struct {S, \wedge, \preceq}$ be a meet semilattice.
Then $\wedge$ is commutative.

Proof:
Let $a, b \in S$ be arbitrary.
Then:
{{begin-eqn}}
{{eqn | l = a \wedge b
      | r = \inf \set {a, b}
      | c = {{Defof|Meet (Order Theory)|Meet}}
}}
{{eqn | r = \inf \set {b, a}
      | c = {{Defof|Set Equality}}
}}
{{eqn | r = b \wedge a
      | c = {{Defof|Meet (Order Theory)|Meet}}
}}
{{end-eqn}}
Hence the result.
{{qed}}
Theorem: Join Succeeds Operands

Let $\struct {S, \preceq}$ be an ordered set.
Let $a, b \in S$ admit a join $a \vee b \in S$.
Then:
:$a \preceq a \vee b$
:$b \preceq a \vee b$
That is, $a \vee b$ succeeds its operands $a$ and $b$.

Proof:
By definition of join:
:$a \vee b = \sup \set {a, b}$
where $\sup$ denotes supremum.
Since a supremum is {{afortiori}} an upper bound:
:$a \preceq \sup \set {a, b}$
:$b \preceq \sup \set {a, b}$
as desired.
{{qed}}
Theorem: Meet Precedes Operands

Let $\struct {S, \preceq}$ be an ordered set.
Let $a, b \in S$ admit a meet $a \wedge b \in S$.
Then:
:$a \wedge b \preceq a$
:$a \wedge b \preceq b$
That is, $a \wedge b$ precedes its operands $a$ and $b$.

Proof:
By definition of meet:
:$a \wedge b = \inf \set {a, b}$
where $\inf$ denotes infimum.
Since an infimum is {{afortiori}} a lower bound:
:$\inf \set {a, b} \preceq a$
:$\inf \set {a, b} \preceq b$
as desired.
{{qed}}
Category:Meet Operation
qzj9efw5t71pagp8isyhwlqpnr9eccw
Theorem: Meet is Associative

Let $\struct {S, \wedge, \preceq}$ be a meet semilattice.
Then $\wedge$ is associative.

Proof:
Let $a, b, c \in S$ be arbitrary.
Then:
{{begin-eqn}}
{{eqn | l = a \wedge \paren {b \wedge c}
      | r = \inf \set {a, b \wedge c}
      | c = {{Defof|Meet (Order Theory)|Meet}}
}}
{{eqn | r = \inf \set {\inf \set a, \inf \set {b, c} }
      | c = Infimum of Singleton
}}
{{eqn | r = \inf \set {a, b, c}
      | c = Infimum of Infima
}}
{{eqn | r = \inf \set {\inf \set {a, b}, \inf \set c}
      | c = Infimum of Infima
}}
{{eqn | r = \inf \set {a, b} \wedge c
      | c = Infimum of Singleton
}}
{{eqn | r = \paren {a \wedge b} \wedge c
      | c = {{Defof|Meet (Order Theory)|Meet}}
}}
{{end-eqn}}
Hence the result.
{{qed}}
Theorem: Poset Elements Equal iff Equal Weak Lower Closure

Let $\left({S, \preccurlyeq}\right)$ be an ordered set.
Let $s, t \in S$.
Then $s = t$ {{iff}}:
:$s^\preccurlyeq = t^\preccurlyeq$
where $s^\preccurlyeq$ denotes weak lower closure of $s$.
That is, {{iff}}, for all $r \in S$:
:$r \preccurlyeq s \iff r \preccurlyeq t$

Proof:
=== Necessary Condition ===
If $s = t$, then trivially also:
:$s^\preccurlyeq = t^\preccurlyeq$
{{qed|lemma}}
Theorem: Poset Elements Equal iff Equal Weak Upper Closure

Let $\left({S, \preccurlyeq}\right)$ be an ordered set.
Let $s, t \in S$.
Then $s = t$ {{iff}}:
:$s^\succcurlyeq = t^\succcurlyeq$
where $s^\succcurlyeq$ denotes weak upper closure of $s$.
That is, {{iff}}, for all $r \in S$:
:$s \preccurlyeq r \iff t \preccurlyeq r$

Proof:
=== Necessary Condition ===
If $s = t$, then trivially also:
:$s^\succcurlyeq = t^\succcurlyeq$
{{qed|lemma}}
Theorem: Join is Associative

Let $\struct {S, \vee, \preceq}$ be a join semilattice.
Then $\vee$ is associative.

Proof:
Let $a, b, c \in S$ be arbitrary.
Then:
{{begin-eqn}}
{{eqn | l = a \vee \paren {b \vee c}
      | r = a \vee \sup \set {b, c}
      | c = {{Defof|Join (Order Theory)}}
}}
{{eqn | r = \sup \set {\sup \set a, \sup \set {b, c} }
      | c = Supremum of Singleton
}}
{{eqn | r = \sup \set {a, b, c}
      | c = Supremum of Suprema
}}
{{eqn | r = \sup \set {\sup \set {a, b}, \sup \set c}
      | c = Supremum of Suprema
}}
{{eqn | r = \sup \set {a, b} \vee c
      | c = Supremum of Singleton
}}
{{eqn | r = \paren {a \vee b} \vee c
      | c = {{Defof|Join (Order Theory)}}
}}
{{end-eqn}}
Hence the result.
{{qed}}
Theorem: Prime iff Equal to Product

Let $p \in \Z$ be an integer such that $p \ne 0$ and $p \ne \pm 1$.
Then $p$ is prime {{iff}}:
:$\forall a, b \in \Z: p = ab \implies p = \pm a \lor p = \pm b$

Proof:
=== Necessary Condition ===
Let $p$ be a prime number.
Then by definition, the only divisors of $p$ are $\pm 1$ and $\pm p$.
Thus, if $p = a b$ then either $a = \pm 1$ and $b = \pm p$ or $a = \pm p$ and $b = \pm 1$.
{{qed|lemma}}
Theorem: Multiple of Divisor Divides Multiple

Let $a, b, c \in \Z$.
Let:
:$a \divides b$
where $\divides$ denotes divisibility.
Then:
:$a c \divides b c$

Proof:
We have that Integers form Integral Domain.
The result then follows from Multiple of Divisor in Integral Domain Divides Multiple.
{{qed}}
Theorem: Multiple of Divisor Divides Multiple

Let $a, b, c \in \Z$.
Let:
:$a \divides b$
where $\divides$ denotes divisibility.
Then:
:$a c \divides b c$

Proof:
By definition, if $a \divides b$ then $\exists d \in \Z: a d = b$.
Then:
:$\paren {a d} c = b c$
that is:
:$\paren {a c} d = b c$
which follows because Integer Multiplication is Commutative and Integer Multiplication is Associative.
Hence the result.
{{qed}}
Theorem: Divisor Relation is Transitive

The divisibility relation is a transitive relation on $\Z$, the set of integers.
That is:
:$\forall x, y, z \in \Z: x \divides y \land y \divides z \implies x \divides z$

Proof:
We have that Integers form Integral Domain.
The result then follows directly from Divisor Relation in Integral Domain is Transitive.
{{qed}}
Theorem: Divisor Relation is Transitive

The divisibility relation is a transitive relation on $\Z$, the set of integers.
That is:
:$\forall x, y, z \in \Z: x \divides y \land y \divides z \implies x \divides z$

Proof:
{{begin-eqn}}
{{eqn | l = x
      | o = \divides
      | r = y
      | c = 
}}
{{eqn | ll= \leadsto
      | q = \exists q_1 \in \Z
      | l = q_1 x
      | r = y
      | c = {{Defof|Divisor of Integer}}
}}
{{eqn | l = y
      | o = \divides
      | r = z
      | c = 
}}
{{eqn | ll= \leadsto
      | q = \exists q_2 \in \Z
      | l = q_2 y
      | r = z
      | c = {{Defof|Divisor of Integer}}
}}
{{eqn | ll= \leadsto
      | l = q_2 \paren {q_1 x}
      | r = z
      | c = substituting for $y$
}}
{{eqn | ll= \leadsto
      | l = \paren {q_2 q_1} x
      | r = z
      | c = Integer Multiplication is Associative
}}
{{eqn | ll= \leadsto
      | q = \exists q \in \Z
      | l = q x
      | r = z
      | c = where $q = q_1 q_2$
}}
{{eqn | ll= \leadsto
      | l = x
      | o = \divides
      | r = z
      | c = {{Defof|Divisor of Integer}}
}}
{{end-eqn}}
{{Qed}}
Theorem: Polynomial Forms over Field form Integral Domain/Formulation 1

Let $\struct {F, +, \circ}$ be a field whose zero is $0_F$ and whose unity is $1_F$.
Let $X$ be transcendental in $F$.
Let $F \sqbrk X$ be the ring of polynomial forms in $X$ over $F$.
Then $F \sqbrk X$ is an integral domain.

Proof:
We already have from Ring of Polynomial Forms is Commutative Ring with Unity that $F \sqbrk X$ is a ring.
Suppose $f$ and $g$ are polynomials in $F \sqbrk X$ such that $f \ne 0_F, g \ne 0_F$.
If $\map \deg f = \map \deg g = 0$ then $f$ and $g$ are elements of $F$.
As $F$ is a field and a field is an integral domain, $f g \ne 0_f$.
Otherwise from Degree of Product of Polynomials over Integral Domain:
:$\map \deg {f g} = \map \deg f + \map \deg g$
and so:
:$\map \deg {f g} > 0$
which means:
:$f g \ne 0_F$
Hence the result, by definition of integral domain.
{{qed}}
Theorem: Polynomial Forms over Field form Integral Domain/Formulation 1

Let $\struct {F, +, \circ}$ be a field whose zero is $0_F$ and whose unity is $1_F$.
Let $X$ be transcendental in $F$.
Let $F \sqbrk X$ be the ring of polynomial forms in $X$ over $F$.
Then $F \sqbrk X$ is an integral domain.

Proof:
We have from Ring of Polynomial Forms is Commutative Ring with Unity that $F \sqbrk X$ is a commutative ring with unity.
The result follows from Ring of Polynomial Forms is Integral Domain.
{{qed}}
Theorem: Sum of Indices of Real Number/Positive Integers

Let $n, m \in \Z_{\ge 0}$ be positive integers.
Let $r^n$ be defined as $r$ to the power of $n$.
Then:
: $r^{n + m} = r^n \times r^m$

Proof:
Proof by induction on $m$:
For all $m \in \Z_{\ge 0}$, let $\map P m$ be the proposition:
:$\forall n \in \Z_{\ge 0}: r^{n + m} = r^n \times r^m$
$\map P 0$ is true, as this just says:
:$r^{n + 0} = r^n = r^n \times 1 = r^n \times r^0$
Theorem: Product of Indices of Real Number/Positive Integers

Let $n, m \in \Z_{\ge 0}$ be positive integers.
Let $r^n$ be defined as $r$ to the power of $n$.
Then:
:$\paren {r^n}^m = r^{n m}$

Proof:
Proof by induction on $m$:
For all $m \in \Z_{\ge 0}$, let $\map P m$ be the proposition:
:$\forall n \in \Z_{\ge 0}: \paren {r^n}^m = r^{n m}$
$\map P 0$ is true, as this just says:
:$\paren {r^n}^0 = 1 = r^0 = r^{n \times 0}$
Theorem: Equivalence of Formulations of Axiom of Empty Set

The following formulations of the '''{{axiom-link|the Empty Set|Set Theory}}''' are equivalent:

Proof:
=== Formulation 1 implies Formulation 2 ===
{{begin-eqn}}
{{eqn | n = 1
      | o = 
      | r = \forall y: y = y
      | c = Equality is Reflexive
}}
{{eqn | n = 2
      | o = 
      | r = \neg \exists y: y \ne y
      | c = From $(1)$: Assertion of Universality
}}
{{eqn | n = 3
      | o = 
      | r = x := \set { {y: y \ne y} }
      | c = 
}}
{{eqn | n = 4
      | o = 
      | r = \neg \exists y: y \in x
      | c = From $(2)$ and $(3)$
}}
{{end-eqn}}
{{qed|lemma}}
Theorem: Smallest Element is Initial Object

Let $\mathbf P$ be an order category.
Suppose the objects $\mathbf P_0$ of $\mathbf P$, considered as an ordered set, have a smallest element $p$.
Then $p$ is an initial object of $\mathbf P$.

Proof:
Since $p$ is the smallest element of $\mathbf P_0$, we have:
:$\forall q \in \mathbf P_0: p \le q$
that is, for every object $q$ of $\mathbf P$ there is a unique morphism $p \to q$.
That is, $p$ is initial.
{{qed}}
Theorem: Ordinal is Subset of Rank of Small Class iff Not in Von Neumann Hierarchy

Let $x$ be an ordinal.
Let $S$ be a small class.
Let $\map V x$ denote the von Neumann hierarchy on the ordinal $x$.
Then $x$ is a subset of the rank of $S$ {{iff}} $S \notin \map V x$.

Proof:
{{NotZFC}}
Theorem: Membership Rank Inequality

Let $S$ and $T$ be sets.
Let $\map {\operatorname{rank} } S$ denote the rank of $S$.
Then:
:$S \in T \implies \map {\operatorname{rank} } S < \map {\operatorname{rank} } T$

Proof:
{{NotZFC}}
By Ordinal Equal to Rank:
:$T \in \map V {\map {\operatorname{rank} } T + 1}$
By the definition of rank:
:$T \subseteq \map V {\map {\operatorname{rank} } T}$
Since $S \in T$:
:$S \in \map V {\map {\operatorname{rank} } T}$
By Ordinal is Subset of Rank of Small Class iff Not in Von Neumann Hierarchy:
:$\map {\operatorname{rank} } T \nsubseteq \map {\operatorname{rank} } S$
Therefore by Ordinal Membership is Trichotomy and Transitive Set is Proper Subset of Ordinal iff Element of Ordinal:
:$\map {\operatorname{rank} } S < \map {\operatorname{rank} } T$
{{qed}}
Theorem: Greatest Element is Terminal Object

Let $\mathbf P$ be an order category.
Let $p$ be the greatest element of the objects $\mathbf P_0$ of $\mathbf P$, considered as a ordered set.
Then $p$ is a terminal object of $\mathbf P$.

Proof:
Since $p$ is the greatest element of $\mathbf P_0$, we have:
:$\forall q \in \mathbf P_0: q \le p$
that is, for every object $q$ of $\mathbf P$ there is a unique morphism $q \to p$.
That is, $p$ is terminal.
{{qed}}
Theorem: Identity Morphism is Terminal Object in Slice Category

Let $\mathbf C$ be a metacategory, and let $C \in \mathbf C_0$ be an object of $\mathbf C$.
Let $\operatorname{id}_C: C \to C$ be the identity morphism for $C$.
Then $\operatorname{id}_C$ is a terminal object in the slice category $\mathbf C \mathop / C$.

Proof:
Let $f: B \to C$ be an object of $\mathbf C \mathop / C$.
Then there is a morphism $a: f \to \operatorname{id}_C$ {{iff}}:
:$f = \operatorname{id}_C \circ a = a$
Thus, $f$ itself defines the unique morphism $f \to \operatorname{id}_C$ in $\mathbf C \mathop / C$.
We therefore have the following commutative diagram in $\mathbf C$:
$\quad\quad \begin{xy}
<-3em,0em>*+{B} = "X",
<3em,0em>*+{C} = "X2",
<0em,-4em>*+{C} = "C",
"X";"X2" **@{--} ?>*@{>} ?*!/_1em/{f},
"X";"C" **@{-} ?>*@{>} ?<>(.3)*!/^1em/{f},
"X2";"C" **@{-} ?>*@{>} ?<>(.3)*!/_1em/{\operatorname{id}_C},
\end{xy}$
Hence the result, by definition of terminal object.
{{qed}}
Theorem: Identity Morphism is Initial Object in Coslice Category

Let $\mathbf C$ be a metacategory, and let $C \in \mathbf C_0$ be an object of $\mathbf C$.
Let $\operatorname{id}_C: C \to C$ be the identity morphism for $C$.
Then $\operatorname{id}_C$ is an initial object in the coslice category $C / \mathbf C$.

Proof:
Let $f: C \to D$ be an object of $C / \mathbf C$.
Then there is a morphism $a: \operatorname{id}_C \to f$ {{iff}}:
:$f = a \circ \operatorname{id}_C = a$
Thus, $f$ itself defines the unique morphism $\operatorname{id}_C \to f$ in $C \mathop / \mathbf C$.
We therefore have the following commutative diagram in $\mathbf C$:
$\quad\quad \begin{xy}
<-3em,0em>*+{C} = "X",
<3em,0em>*+{D} = "X2",
<0em,4em>*+{C} = "C",
"X";"X2" **@{--} ?>*@{>} ?*!/^1em/{f},
"C";"X" **@{-} ?>*@{>} ?*!/^.6em/{\operatorname{id}_C},
"C";"X2" **@{-} ?>*@{>} ?<>(.6)*!/_1em/{f'},
\end{xy}$
Hence the result, by definition of initial object.
{{qed}}
Theorem: Rank of Set Determined by Members

Let $S$ be a set.
Let $\map {\operatorname{rank} } S$ denote the rank of $S$.
Then:
:$\map {\operatorname{rank} } S = \bigcap \set {x \in \On: \forall y \in S: \map {\operatorname{rank} } y < x}$

Proof:
{{NotZFC}}
Let:
:$T = \bigcap \set {x \in \On: \forall y \in S: \map {\operatorname{rank} } y < x}$
Let $y \in S$.
Then by Membership Rank Inequality:
:$\map {\operatorname{rank} } x < \map {\operatorname{rank} } S$
{{explain|$x$ or $y$?}}
Therefore:
:$T \subseteq \map {\operatorname{rank} } S$
Conversely, take any $x \in T$.
By the definition of $T$:
:$\forall y \in S: \map {\operatorname{rank} } y < x$
From Ordinal is Subset of Rank of Small Class iff Not in Von Neumann Hierarchy:
:$\forall y \in S: y \in \map V x$
where $\map V x$ denotes the von Neumann hierarchy.
Therefore by the definition of subset:
:$S \subseteq \map V x$
By the definition of rank.
:$\map {\operatorname{rank} } S \le x$
Therefore:
:$\map {\operatorname{rank} } S = T$
{{qed}}
Theorem: Rank of Ordinal

Let $x$ be an ordinal.
Let $\map {\operatorname {rank} } x$ denote the rank of $x$.
Then:
:$\map {\operatorname {rank} } x = x$

Proof:
{{NotZFC}}
The proof shall proceed by Transfinite Induction (Strong Induction) on $x$.
Suppose $\forall y \in x: \map {\operatorname {rank} } y = y$.
Then:
{{begin-eqn}}
{{eqn | l = \map {\operatorname {rank} } x
      | r = \bigcap \set {z \in \On: \forall y \in x: y < z}
      | c = Rank of Set Determined by Members
}}
{{eqn | r = \bigcap \set {z \in \On: x \subseteq z}
      | c = {{Defof|Subset}}
}}
{{eqn | r = x
      | c = 
}}
{{end-eqn}}
{{qed}}
Theorem: Bounded Rank implies Small Class

Let $S$ be a class.
Suppose the rank, denoted $\map {\operatorname{rank} } x$, of each $x \in S$ is bounded above by some ordinal $y$.
{{MissingLinks|rank}}
Then $S$ is a small class.

Proof:
{{NotZFC}}
Let $V$ denote the von Neumann hierarchy.
Then:
{{begin-eqn}}
{{eqn | q = \forall x \in S
      | l = \map {\operatorname{rank} } x
      | o = \le
      | r = y
      | c = {{hypothesis}}
}}
{{eqn | ll= \leadsto
      | l = x
      | o = \in
      | r = \map V {y + 1}
      | c = Ordinal is Subset of Rank of Small Class iff Not in Von Neumann Hierarchy and Ordinal Equal to Rank
}}
{{eqn | ll= \leadsto
      | l = S
      | o = \subseteq
      | r = \map V {y + 1}
      | c = {{Defof|Subset}}
}}
{{end-eqn}}
Therefore, by Axiom of Subsets Equivalents, it follows that $S$ is a small class.
{{qed}}
Theorem: Count of Subsets with Even Cardinality

Let $S$ be a set whose cardinality is $n$.
Then the number of subsets of $S$ whose cardinality is even is $2^{n-1}$.

Proof:
Let $E$ be the total number of subsets of $S$ whose cardinality is even.
From Cardinality of Set of Subsets, the number of subsets of $S$ with $m$ elements is $\dbinom n m$:
:$\dbinom n m = \dfrac {n!} {m! \paren {n - m} }$
where $\dbinom n m$ is a binomial coefficient.
Thus the total number of subsets of $S$ whose cardinality is even is given by:
:$\ds E = \dbinom n 0 + \dbinom n 2 + \dbinom n 4 + \cdots = \sum_{j \mathop \in \Z} \dbinom n {2 j}$
Note the loose limits of the summation sign: the expression truly ranges over all $\Z$.
This is because, when $2 j < 0$ and $2 j > n$, $\dbinom n {2 j} = 0$ by definition of binomial coefficient.
The result then follows from Sum of Even Index Binomial Coefficients:
:$\ds \sum_{j \mathop \ge 0} \dbinom n {2 j} = 2^{n - 1}$
{{qed}}
Theorem: Count of Subsets with Even Cardinality

Let $S$ be a set whose cardinality is $n$.
Then the number of subsets of $S$ whose cardinality is even is $2^{n-1}$.

Proof:
Proof by induction:
For all $n \in \N$, let $\map P n$ be the proposition:
:The number of subsets of $S$ whose cardinality is even is $2^{n - 1}$, where $\card S = n$.
=== Basis for the Induction ===
When $n = 1$ we have from Cardinality of Power Set of Finite Set that $S$ has $2^1 = 1$ subsets: $\O$ and $S$ itself.
We have that $\card S = 1$ and $\card \O = 0$.
So there is indeed $2^{1 - 1} = 2^0 = 1$ subset of $S$ whose cardinality is even, that is $\O$.
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:
:The number of subsets of $S$ whose cardinality is even is $2^{k - 1}$, where $\card S = k$.
Then we need to show:
:The number of subsets of $S$ whose cardinality is even is $2^k$, where $\card S = 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$.
We see that $\card {S'} = k$.
Let $A \subseteq S$.
If $x \notin A$ then $A \subseteq S'$.
If $x \in A$ then there exists a unique $A' \subseteq S'$ such that $A' \cup \set x = A$.
In fact, $A' = A \setminus \set x$.
Let $K$ be the number of subsets of $S'$ with an even number of elements.
From the induction hypothesis we have that $K = 2^{k - 1}$.
Now adjoin $x$ to all the subsets of $S'$.
Suppose $E' \subseteq S'$, where $E'$ has an even number of elements.
Then $E' \cup \set x$ has an odd number of elements.
Similarly, $O' \subseteq S'$, where $O'$ has an odd number of elements.
Then $O' \cup \set x$ has an even number of elements.
So the number of subsets of $S$ with an even number of elements is:
:$K$ subsets of $S$ that have an even number of elements and are subsets of $S'$
and:
:$K$ subsets of $S$ of the form $O' \cup \set x$
We have that subset $A$ of $S$ has a unique expression of the form $A'$ or $A' \cup \set x$ with $A' \subseteq S'$.
Thus there are exactly $2 K$ subsets of $S$ with an even number of elements.
But as $K = 2^{k - 1}$ it follows that $2 K = 2^k$.
That is, there are $2^k$ subsets of $S$ with an even number of elements.
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
::The number of subsets of $S$ whose cardinality is even is $2^{n - 1}$, where $\card S = n$.
{{qed}}
Theorem: Count of Subsets with Odd Cardinality

Let $S$ be a set whose cardinality is $n$.
Then the number of subsets of $S$ whose cardinality is odd is $2^{n-1}$.

Proof:
Let $F$ be the total number of subsets of $S$ whose cardinality is odd.
From Cardinality of Set of Subsets, the number of subsets of $S$ with $m$ elements is $\dbinom n m$:
:$\dbinom n m = \dfrac {n!} {m! \paren {n - m} }$
where $\dbinom n m$ is a binomial coefficient.
Thus the total number of subsets of $S$ whose cardinality is Odd is given by:
:$\ds E = \dbinom n 1 + \dbinom n 3 + \dbinom n 5 + \cdots = \sum_{j \mathop \in \Z} \dbinom n {2 j + 1}$
Note the loose limits of the summation sign: the expression truly ranges over all $\Z$.
This is because, when $2 j + 1 < 0$ and $2 j + 1 > n$, $\dbinom n {2 j + 1} = 0$ by definition of binomial coefficient.
The result then follows from Sum of Odd Index Binomial Coefficients:
:$\ds \sum_{j \mathop \ge 0} \binom n {2 j + 1} = 2^{n - 1}$
{{qed}}