nyuuzyou/wikis huggingface dataset:
Count of Commutative Binary Operations on Set

== Theorem ==
Let $S$ be a set whose cardinality is $n$.
The number $N$ of possible different commutative binary operations that can be applied to $S$ is given by:
:$N = n^{\frac {n \paren {n + 1} } 2}$
=== Sequence of Values of $N$ ===
== Proof ==
Let $\struct {S, \circ}$ be a magma.
From Cardinality of Cartesian Product of Finite Sets, there are $n^2$ elements in $S \times S$.
The binary operations $\circ$ is commutative :
:$\forall x, y \in S: x \circ y = y \circ x$
Thus for every pair of elements $\tuple {x, y} \in S \times S$, it is required that $\tuple {y, x} \in S \times S$.
So the question boils down to establishing how many different unordered pairs there are in $S$.
That is, how many doubleton subsets there are in $S$.
From Cardinality of Set of Subsets, this is given by:
:$\dbinom n 2 = \dfrac {n \paren {n - 1} } 2$
To that set of doubleton subsets, we also need to add those ordered pairs where $x = y$.
There are clearly $n$ of these.
So the total number of pairs in question is:
:$\dfrac {n \paren {n - 1} } 2 + n = \dfrac {n \paren {n + 1} } 2$
The result follows from Cardinality of Set of All Mappings.
== Examples ==
== Sources ==
* : Chapter $\text I$: Algebraic Structures: $\S 2$: Compositions: Exercise $2.3$
Category:Combinatorics
Category:Abstract Algebra
Category:Commutativity
Category:Count of Commutative Binary Operations on Set
Count of Commutative Binary Operations on Set/Examples/Order 2

== Example of Use of Count of Binary Operations on Set ==
The Cayley tables for the complete set of commutative magmas of order $2$ are listed below.
The underlying set in all cases is $\set {a, b}$.
:$\begin{array}{r|rr}
 & a & b \\
\hline
a & a & a \\
b & a & a \\
\end{array}
\qquad
\begin{array}{r|rr}
 & a & b \\
\hline
a & a & a \\
b & a & b \\
\end{array}$
:$\begin{array}{r|rr}
 & a & b \\
\hline
a & a & b \\
b & b & a \\
\end{array}
\qquad
\begin{array}{r|rr}
 & a & b \\
\hline
a & a & b \\
b & b & b \\
\end{array}$
:$\begin{array}{r|rr}
 & a & b \\
\hline
a & b & a \\
b & a & a \\
\end{array}
\qquad
\begin{array}{r|rr}
 & a & b \\
\hline
a & b & a \\
b & a & b \\
\end{array}$
:$\begin{array}{r|rr}
 & a & b \\
\hline
a & b & b \\
b & b & a \\
\end{array}
\qquad \begin{array}{r|rr}
 & a & b \\
\hline
a & b & b \\
b & b & b \\
\end{array}$
== Sources ==
* : Chapter $4$. Groups: Exercise $1 \ \text{(i)}$
Category:Count of Commutative Binary Operations on Set/Examples
Count of Commutative Binary Operations on Set/Sequence

== Theorem ==
Let $S$ be a set whose cardinality is $n$.
Let $N$ denote the number of different commutative binary operations that can be applied to $S$:
:$N = n^{\frac {n \paren {n + 1} } 2}$
The sequence of $N$ for each $n$ begins:
$\begin{array} {c|cr}
n & \dfrac {n \paren {n + 1} }2 & n^{\frac {n \paren {n + 1} } 2} \\
\hline
1 & 1 & 1 \\
2 & 3 & 8 \\
3 & 6 & 729 \\
4 & 10 & 1 \ 048 \ 576 \\
\end{array}$
and so on.
Category:Count of Commutative Binary Operations on Set
Count of Commutative Binary Operations with Fixed Identity

== Theorem ==
Let $S$ be a set whose cardinality is $n$.
Let $x \in S$.
The number $N$ of possible different commutative binary operations such that $x$ is an identity element that can be applied to $S$ is given by:
:$N = n^{\frac {n \paren {n - 1} } 2}$
=== Sequence of Values of $N$ ===
== Proof ==
This follows by the arguments of Count of Binary Operations with Fixed Identity and Count of Commutative Binary Operations on Set.
From Count of Binary Operations on Set, there are $n^{\paren {n^2} }$ binary operations in total.
We also know that:
:$a \in S \implies a \circ x = a = x \circ a$
so all binary operations on $x$ are already specified.
It remains to count all possible combinations of the remaining $n-1$ elements.
This is effectively counting the mappings:
:$\paren {S \setminus \set x} \times \paren {S \setminus \set x} \to S$
So the question boils down to establishing how many different unordered pairs there are in $\paren {S \setminus \set x}$.
That is, how many doubleton subsets there are in $\paren {S \setminus \set x}$.
From Cardinality of Set of Subsets, this is given by:
:$\dbinom {n - 1} 2 = \dfrac {\paren {n - 1} \paren {n - 2} } 2$
To that set of doubleton subsets, we also need to add those ordered pairs where $x = y$.
There are clearly $n - 1$ of these.
So the total number of pairs in question is:
:$\dfrac {\paren {n - 1} \paren {n - 2} } 2 + n - 1 = \dfrac {n \paren {n - 1} } 2$
The result follows from Cardinality of Set of All Mappings.
== Sources ==
* : Chapter $\text I$: Algebraic Structures: $\S 4$: Neutral Elements and Inverses: Exercise $4.2$
Category:Combinatorics
Category:Abstract Algebra
Category:Commutativity
Category:Count of Commutative Binary Operations with Fixed Identity
Count of Commutative Binary Operations with Fixed Identity/Sequence

== Theorem ==
Let $S$ be a set whose cardinality is $n$.
Let $x \in S$.
Let $N$ denote the number of different commutative binary operations such that $x$ is an identity element that can be applied to $S$:
:$N = n^{\frac {n \paren {n - 1} } 2}$
The sequence of $N$ for each $n$ begins:
$\begin {array} {c|cr}
n & \dfrac {n \paren {n - 1} } 2 & n^{\frac {n \paren {n - 1} } 2} \\
\hline
1 & 0 & 1 \\
2 & 1 & 2 \\
3 & 3 & 27 \\
4 & 6 & 4 \ 096 \\
5 & 10 & 9 \ 765 \ 625 \\
\end {array}$
Category:Count of Commutative Binary Operations with Fixed Identity
Count of Commutative Binary Operations with Identity

== Theorem ==
Let $S$ be a set whose cardinality is $n$.
The number $N$ of possible different commutative binary operations that can be applied to $S$ which have an identity element is given by:
:$N = n^{\frac {n \paren {n - 1} } 2 + 1}$
=== Sequence of Values of $N$ ===
== Proof ==
From Count of Commutative Binary Operations with Fixed Identity, there are $n^{\frac {n \paren {n - 1} } 2}$ such binary operations for each individual element of $S$.
As Identity is Unique, if $x$ is the identity, no other element can also be an identity.
As there are $n$ different ways of choosing such an identity, there are $n \times n^{\frac {n \paren {n - 1} } 2}$ different algebraic structures with an identity.
These are guaranteed not to overlap by the uniqueness of the identity.
Hence the result.
== Sources ==
* : Chapter $\text I$: Algebraic Structures: $\S 4$: Neutral Elements and Inverses: Exercise $4.2$
Category:Combinatorics
Category:Abstract Algebra
Category:Commutativity
Category:Count of Commutative Binary Operations with Identity
Count of Commutative Binary Operations with Identity/Sequence

== Theorem ==
Let $S$ be a set whose cardinality is $n$.
Let $N$ denote the number of different commutative binary operations which have an identity element that can be applied to $S$:
:$N = n^{\frac {n \paren {n - 1} } 2 + 1}$
The sequence of $N$ for each $n$ begins:
$\begin{array} {c|cr}
n & \dfrac {n \paren {n - 1} } 2 + 1 & n^{\frac {n \paren {n - 1} } 2 + 1} \\
\hline
1 & 1 & 1 \\
2 & 2 & 4 \\
3 & 4 & 81 \\
4 & 7 & 16 \ 384 \\
5 & 11 & 48 \ 828 \ 125 \\
\end{array}$
Category:Count of Commutative Binary Operations with Identity
Count of Commutative Operations on Finite Set which are Closed on Every Subset

== Theorem ==
Let $S$ be a finite set with $n$ elements.
There are $2^{n \paren {n - 1} / 2}$ commutative binary operations on $S$ which are closed on all subsets of $S$.
== Proof ==
From Count of Operations on Finite Set which are Closed on Every Subset, there are $2^{n \paren {n - 1} }$ binary operations on $S$ which are closed on all subsets of $S$.
For each $a, b \in S$, we have that
:there are $2$ possible products for $a \circ b$
:there are $2$ possible products for $b \circ a$
and so on the set $\set {a, b}$ there are $4$ binary operations which are closed on all subsets of $\set {a, b}$.
Let $\circ$ be commutative.
Then:
:$a \circ b = b \circ a$
and so now there are only $2$ possible such products.
Hence the number of commutative binary operations on $S$ which are closed on all subsets of $S$ equals the number of distinct doubleton subsets of $S$.
There are half as many of these as there are ordered pairs.
That is, there are $\dfrac {n^2 - n} 2 = \dfrac {n \paren {n - 1} } 2$ doubletons $\set {x, y} \subseteq S$, such that $x \ne y$.
The result follows.
== Sources ==
* : Chapter $\text {II}$: New Structures from Old: $\S 8$: Compositions Induced on Subsets: Exercise $8.2$
Category:Closed Algebraic Structures
Category:Commutativity
Count of Commutative Quasigroups on Set given Count of Commutative Algebra Loops

== Theorem ==
Let $S$ be a finite set of cardinality $n$.
Let $e \in S$.
Let there be $m$ commutative operations $\oplus$ on $S$ such that $\struct {S, \oplus}$ is an algebra loop whose identity is $e$.
Then there are $n! m$ commutative binary operations $\otimes$ on $S$ such that $\struct {S, \otimes}$ is a quasigroup.
== Proof ==
Consider a commutative algebra loop $\struct {S, \oplus}$ whose identity is $e$.
Consider the row of the Cayley table of $S$ which is headed by $e$.
There are $n!$ permutations of the elements of this row.
Each of these corresponds to a different commutative operation on $S$, as the corresponding column headed by $e$ is constrained to be the same as the row.
The result follows by the Product Rule for Counting.
== Examples ==
== Sources ==
* : Chapter $\text I$: Algebraic Structures: $\S 7$: Semigroups and Groups: Exercise $7.9 \ \text {(c)}$
Category:Algebra Loops
Category:Quasigroups
Category:Count of Commutative Quasigroups on Set given Count of Commutative Algebra Loops
Count of Commutative Quasigroups on Set given Count of Commutative Algebra Loops/Examples

== Examples of Use of Count of Commutative Quasigroups on Set given Count of Commutative Algebra Loops ==
=== Order 3 ===
=== Order 4 ===
Category:Count of Commutative Quasigroups on Set given Count of Commutative Algebra Loops
Count of Commutative Quasigroups on Set given Count of Commutative Algebra Loops/Examples/Order 3

== Examples of Use of Count of Commutative Quasigroups on Set given Count of Commutative Algebra Loops ==
Let $S$ have exactly $3$ elements.
There are $6$ quasigroups $\struct {S, \otimes}$ on $S$ such that $\otimes$ is a commutative operation.
== Proof ==
Let $e \in S$ be a distinguished element of $S$.
Let $N$ be the number of quasigroups $\struct {S, \otimes}$ on $S$ such that $\otimes$ is a commutative operation.
From Count of Commutative Quasigroups on Set given Count of Commutative Algebra Loops we have that:
:$N = n! m$
where:
:$n$ is the cardinality of $S$
:$m$ is the number of commutative operations $\oplus$ on $S$ such that $\struct {S, \oplus}$ is an algebra loop whose identity is $e$.
In this case, we have:
:$n = 3$ 
:$m = 1$ from Algebra Loops of Order 3
Hence:
:$N = 3! \times 1 = 6$
== Sources ==
* : Chapter $\text I$: Algebraic Structures: $\S 7$: Semigroups and Groups: Exercise $7.9 \ \text {(c)}$
Category:Count of Commutative Quasigroups on Set given Count of Commutative Algebra Loops
Count of Commutative Quasigroups on Set given Count of Commutative Algebra Loops/Examples/Order 4

== Examples of Use of Count of Commutative Quasigroups on Set given Count of Commutative Algebra Loops ==
Let $S$ have exactly $4$ elements.
There are $96$ quasigroups $\struct {S, \otimes}$ on $S$ such that $\otimes$ is a commutative operation.
== Proof ==
Let $e \in S$ be a distinguished element of $S$.
Let $N$ be the number of quasigroups $\struct {S, \otimes}$ on $S$ such that $\otimes$ is a commutative operation.
From Count of Commutative Quasigroups on Set given Count of Commutative Algebra Loops we have that:
:$N = n! m$
where:
:$n$ is the cardinality of $S$
:$m$ is the number of commutative operations $\oplus$ on $S$ such that $\struct {S, \oplus}$ is an algebra loop whose identity is $e$.
In this case, we have:
:$n = 4$ 
:$m = 4$ from Algebra Loops of Order 4
Hence:
:$N = 4! \times 4 = 96$
== Sources ==
* : Chapter $\text I$: Algebraic Structures: $\S 7$: Semigroups and Groups: Exercise $7.9 \ \text {(c)}$
Category:Count of Commutative Quasigroups on Set given Count of Commutative Algebra Loops
Count of Distinct Homomorphisms between Additive Groups of Integers Modulo m

== Theorem ==
Let $m, n \in \Z_{>0}$ be (strictly) positive integers.
Let $\struct {\Z_m, +}$ denote the additive group of integers modulo $m$.
The number of distinct homomorphisms $\phi: \struct {\Z_m, +} \to \struct {\Z_n, +}$ is $\gcd \set {m, n}$.
== Proof ==
$\Z_m$ is isomorphic to the quotient group $\Z / m\Z$.
By Universal Property of Quotient Group, to give a group homomorphism from $\Z_m$ to $\Z_n$ is equivalent to give a homomorphism $\varphi$ from $\Z$ to $\Z_n$ with kernel including the subgroup $m\Z \subset \Z$.
$\Z$ is generated by the element $1$.
By Homomorphism of Generated Group, $\varphi$ is determined by $\map \varphi 1$.
The kernel condition means $\map \varphi m = m \map \varphi 1 = 0 \in \Z_n$.
Number of possible such $\map \varphi 1$ is exactly $\gcd \set {m, n}$.
== Sources ==
* : Chapter $2$: Group Homomorphism and Isomorphism: $\S 60 \zeta$
Category:Additive Groups of Integers Modulo m
Count of Operations on Finite Set which are Closed on Every Subset

== Theorem ==
Let $S$ be a finite set with $n$ elements.
There are $2^{n \paren {n - 1} }$ binary operations on $S$ which are closed on all subsets of $S$.
== Proof ==
Suppose $\circ$ is a binary operation on $S$ such that $a \circ b = c$ for $a \ne b \ne c \ne a$.
Then $\circ$ is not closed on $\set {a, b} \subseteq S$.
Similarly, suppose $\circ$ is a binary operation on $S$ such that $a \circ a = b$ for $a \ne b$.
Then $\circ$ is not closed on $\set a \subseteq S$.
Hence for $\circ$ to be closed on all subsets of $S$:
:$\forall a \in S: a \circ a = a$
and:
:$\forall a, b \in S: \paren {a \circ b = a} \lor \paren {a \circ b = b}$.
So for every ordered pair $\tuple {x, y}$ of elements of $S$ such that $a \ne b$ there are two possible products: $x$ or $y$.
For an algebraic structure of order $n$, there are $n^2$ such ordered pairs.
However, of these $n^2$ such ordered pairs $\tuple {x, y}$, $n$ of these are such that $x = y$.
There remain $n^2 - n = n \paren {n - 1}$ ordered pairs $\tuple {x, y}$, such that $x \ne y$.
Each one contributes $2$ different products
It follows by the Product Rule for Counting that there are $2^{n \paren {n - 1} }$ binary operations on $S$ which are closed on all subsets of $S$.
== Sources ==
* : Chapter $\text {II}$: New Structures from Old: $\S 8$: Compositions Induced on Subsets: Exercise $8.2$
Category:Closed Algebraic Structures
Count of Rows of Truth Table

== Theorem ==
Let $P$ be a WFF of propositional logic.
Suppose $\PP$ is of finite size such that it contains $n$ different letters.
Then a truth table constructed to express $P$ will contain $2^n$ rows.
== Proof ==
In a truth table, one row is needed for each boolean interpretation of $P$.
Let $S$ be the set of different letters used in $P$.
The result then follows from applying Number of Boolean Interpretations for Finite Set of Variables to $S$.
== Sources ==
* : $\S 3.1$: The Truth-Table Method of Testing the Validity of Arguments
* : $\S \text{II}.13$: Symbolism of sentential calculus
* : $2$ Arguments Containing Compound Statements: $2.3$: Argument Forms and Truth Tables
* : $\S 1.4.1$: The meaning of logical connectives
Category:Truth Tables
Count of Subsets with Even Cardinality/Proof 1

== Theorem ==
== 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}$
Category:Count of Subsets with Even Cardinality
Count of Subsets with Even Cardinality/Proof 2

== Theorem ==
== 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$.
== Sources ==
* : $\S 0.6$: Theorem $8: \ 2$
Category:Count of Subsets with Even Cardinality
Count of Subsets with Odd Cardinality/Proof 1

== Theorem ==
== 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}$
Category:Count of Subsets with Odd Cardinality
Count of Subsets with Odd Cardinality/Proof 2

== Theorem ==
== 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 odd 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 = 2$ 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 odd, and that is $S$.
This is our basis for the induction.
=== Induction Hypothesis ===
Now we need to show that, if $\map P k$ is true, where $k \ge 1$, 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 odd is $2^{k - 1}$, where $\card S = k$.
Then we need to show:
:The number of subsets of $S$ whose cardinality is odd 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 odd 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 odd number of elements is:
:$K$ subsets of $S$ that have an odd 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 odd 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 odd 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 odd is $2^{n - 1}$, where $\card S = n$.
== Sources ==
* : $\S 0.6$: Theorem $8: \ 2$
Category:Count of Subsets with Odd Cardinality
Count of Truth Functions

== Theorem ==
There are $2^{\paren {2^k} }$ distinct truth functions on $k$ variables.
== Proof ==
Let $f: \mathbb B^k \to \mathbb B$ be a truth function.
The domain of $f$ has $2^k$ elements, from Cardinality of Cartesian Product of Finite Sets.
The result follows from Cardinality of Set of All Mappings.
== Sources ==
* : $\S 3.8$: The Total Number of Truth-Functional Expressions
* : Chapter $2$: The Propositional Calculus $2$: $3$ Truth-Tables: Exercise $6 \ \text{(ii)}$
* : $\S 1$: Informal statement calculus: $\S 1.2$: Truth functions and truth tables
* : Chapter $2$: Propositional Calculus: $\S 2.1$: Boolean operators
* : $\S 2.4.1$
Category:Combinatorics
Category:Truth Functions