15.5. Cardinality of a Set

Next we define the cardinality of a set. So, we say that cardinality of a set S is n and for that we use this notation. We use this to vertical bar symbols ( | | ) within S to denote its cardinality and we write it is equal to n provided there are n elements in S where n is some non-negative integer.

Cardinality refers to the number of elements in a set, denoted by vertical bars around the set's symbol, e.g., |S|. If a set S has n elements (which can be any non-negative integer: 0, 1, 2,...), we say its cardinality is n. For example, if S = {1, 2, 3}, then |S| = 3 because there are three elements.

Think of cardinality as counting the number of apples in a basket. If there are 4 apples, we say the cardinality of the apple set is 4.

So, n could be 0 or 1 or it should be some value belonging to the set of natural numbers or it should be a non-negative integer. So, if the cardinality is some n where n is a non-negative integer then we say that S is a finite set else we say it is an infinite set.

If you can count the number of elements in a set using a non-negative integer, the set is considered finite. For example, the set A = {1, 2, 3} is finite with cardinality 3. Conversely, if a set has elements that cannot be fully counted using integers (like all integers or all real numbers), we categorize it as an infinite set.

Imagine a classroom with a known number of students – that's a finite set. Now picture a crowd at a concert where people keep arriving. You can't count all of them easily – that's an infinite set.

We next define what we call as the power set of a set and we use this notation P(S). So, you are given a set S. And if I take the collection of all subsets of this set S, then that itself is a set because I am just listing down the subsets of S and the elements here the elements of P(S) are the subsets of S.

The power set P(S) of a set S contains all possible subsets of S, including the empty set and S itself. For example, if S = {1, 2}, then P(S) = {{}, {1}, {2}, {1, 2}}, which means P(S) has four subsets including the empty set.

Consider a bag with two colored balls: red and blue. All combinations of taking these balls out (including taking none) create the power set: no balls, just red, just blue, or both red and blue!

Now a very fundamental fact here is that, if the cardinality of your set is n where n is some non-negative integer, then the cardinality of the power set will be 2n.

A striking property of power sets is that if a set has n elements, its power set will have 2^n subsets. For example, if a set S has 3 elements (like {a, b, c}), then the power set will have 2^3 = 8 subsets. Each subset can be viewed as a combination of including or excluding each element.

Imagine deciding which clothes to pack for a trip. If you have three items, you can either pack each item or not, leading to a variety of combinations, resulting in 2^3 = 8 ways to pack them!

We will try to prove the statement by induction on the value of n.

To demonstrate the rule of power set cardinality, we can use mathematical induction. Start with a base case where n=0 (the empty set) has a power set containing just itself. Assuming it holds for n=k allows us to generalize to n=k+1, thereby proving it holds for all non-negative integers.

Think of building blocks. If you build a tower with 0 blocks, you have 1 way (doing nothing). Then if you add 1 block, you can either keep it or not, doubling the ways you can arrange things each time you add another block.

--