Bijection rule
The bijection rule states that if a bijection exists from one
set to another, then they have the same cardinality. This is because, in a bijection between two sets, each element of one set uniquely corresponds to exactly one element of the other
set, and vice versa.
For finite sets \(A\) and \(B\), if there is a bijection from \(A\) to \(B\):
$$|A| = |B|$$
⚠ If the elements in a set are tricky to count, a good approach is to come up with a bijection between
it and a set whose elements are easier to count. That way, you'll lower the difficulty of the counting
process.
⚠ Coming up with a bijection involves showing a way to map each element in one set to a unique element
in the other set, and each element in the other set to a unique element in the first set.
The bijection rule can be used to obtain the formula for the cardinality of the power
set of a set:
Consider a finite set, \(A\), such that \(|A| = n.\) We want to connect its power set \(\mathcal{P}(A)\)
to \(B^n\), the set of all \(n\)-bit binary strings, through a bijection. It's already known through the
rule of product that the cardinality of \(B^n\) is \(2^n.\) Let's look
at these sets:
$$A = \set{a_1, a_2, ... a_n}$$
$$\mathcal{P}(A) = \set{\emptyset, \set{a_1}, ... \set{a_1, a_2, ... a_n}}$$
$$B^n = \set{b_1 b_2 ... b_n : b_1 \in \set{0, 1}, b_2 \in \set{0, 1}, ... b_n \in \set{0, 1}}$$
Hopefully, the notation for \(B^n\) isn't too confusing, it is simply the set of all strings of length
\(n\) whose characters are drawn from the alphabet \(\set{0, 1}.\) Now, list out all the elements of
\(A\) in a particular order \(a_1, a_2, ... a_n\) and stick with it for this next part. Let's define a
function, \(f\), that maps each subset \(S \subseteq A\) to an \(n\)-bit binary string, \(b_1 b_2 ...
b_n\), such that, for \(1 \leq i \leq n\), if \(a_i \in S\), \(b_i = 1\), and if \(a_i \notin S\), \(b_i
= 0.\) Basically, if a subset contains the \(i\)th element in \(a_1, a_2, ... a_n\), the \(i\)th digit
of its corresponding binary string will be \(1\), otherwise, it'll be \(0.\) Since every subset of \(A\)
either contains a particular element of \(A\) or it does not, there will always be exactly one \(n\)-bit
binary string to represent it, so \(f\) is a function from \(\mathcal{P}(A)\) to \(B^n.\) Its inverse,
\(f^{-1}\), is also well-defined, as it will map every \(n\)-bit binary string, \(b_1 b_2 ... b_n\),
back to exactly one subset \(S \subseteq A\), such that, for \(1 \leq i \leq n\), if \(b_i = 1\), \(a_i
\in S\), and if \(b_i = 0\), \(a_i \notin S.\) For every subset \(S \subseteq A\) and every \(n\)-bit
binary string \(s\):
$$f(S) = s \leftrightarrow f^{-1}(s) = S$$
Therefore, \(f\) is a bijection from \(\mathcal{P}(A)\) to \(B^n\), and by the bijection rule:
$$|\mathcal{P}(A)| = |B^n| = 2^n$$
Recall that \(|A| = n.\) Thus, \(|\mathcal{P}(A)| = 2^{|A|}.\)
⚠ If \(|A| = 3\), then for the function \(f\) defined above, with the elements of \(A\) ordered as
\(a_1, a_2, a_3\):
$$f(\emptyset) = 000 \leftrightarrow f^{-1}(000) = \emptyset$$
$$f(\set{a_1}) = 100 \leftrightarrow f^{-1}(100) = \set{a_1}$$
$$f(\set{a_2}) = 010 \leftrightarrow f^{-1}(010) = \set{a_2}$$
$$f(\set{a_3}) = 001 \leftrightarrow f^{-1}(001) = \set{a_3}$$
$$f(\set{a_1, a_2}) = 110 \leftrightarrow f^{-1}(110) = \set{a_1, a_2}$$
$$f(\set{a_1, a_3}) = 101 \leftrightarrow f^{-1}(101) = \set{a_1, a_3}$$
$$f(\set{a_2, a_3}) = 011 \leftrightarrow f^{-1}(011) = \set{a_2, a_3}$$
$$f(\set{a_1, a_2, a_3}) = 111 \leftrightarrow f^{-1}(111) = \set{a_1, a_2, a_3}$$
There would be \(2^3 = 8\) subsets of \(A\), each corresponding to the \(8\) binary strings of length
\(n.\) Each subset of \(A\) can be converted into only one \(n\)-bit binary string and each \(n\)-bit
binary string can be converted into only one subset of \(A.\) This is important, as having an inverse is
exactly what distinguishes bijections from other functions.
\(k\)-to-\(1\) correspondence
Occasionally, the cardinality of a set is an integer multiple of the cardinality of another set. While
it's impossible for a bijection, a \(1\)-to-\(1\) correspondence, to exist between the two sets,
something else known as a \(k\)-to-\(1\) correspondence may exist between them, which can make
counting easier:
For finite sets \(X\) and \(Y\), the function \(f : X \rightarrow Y\) is a \(k\)-to-\(1\) correspondence
if for every \(y \in Y\), there are exactly \(k\) different \(x \in X\) such that \(f(x) = y.\)
Furthermore, the \(k\)-to-\(1\) rule states that if \(f : X \rightarrow Y\) is a \(k\)-to-\(1\)
correspondence:
$$|Y| = \frac{|X|}{k}$$
If a farm buys \(x\) new horseshoes for its horses, such that every horse gets all their horseshoes
replaced, and the farm doesn't buy any extras, how many horses are on the farm? Chances are, you said
\(\frac{x}{4}\) because horses have \(4\) hooves, making this a \(4\)-to-\(1\) correspondence from the
set of horseshoes to the set of horses.