Thursday 17 November class

Topics:

• Some set notation that we need
  See the Set post from Math is Fun
  Also: cardinality of a set
The cardinality of a set A is the size of that set: we use the notation |A| for the cardinality of the set A.
For a finite set A, the cardinality is just the number of elements in A:
if A has n elements, then |A|=n.
For an infinite set, we have to define different cardinalities, according to which sets are in one-to-one correspondence with each other.
We define the cardinality of the set of natural numbers  (or any countable set) to be aleph-null (or aleph-nought), designated by the symbol  ℵ₀ - this kind of infinite size number is called a transfinite number).

• Power sets
  See the Power Set post from Math is Fun, and also in Wikipedia: the power set of A is the set whose elements are all the subsets of A.
  The important thing we need from Power Sets is that the power set of a set A has size greater than the size of A: If |A|=n, then the power set of A has 2ⁿ elements. We prove that by making a one-to-one correspondence between the elements of the power set and the binary numbers with n digits: we then need to know that there are exactly 2ⁿ binary numbers with n digits.
So in fact, the size of the power set is exponentially greater than the size of A.
This will continue to be true even for infinite sets, as we will discuss more next time.

Homework:
• Make sure that you review the notation for sets and cardinalities of sets given and linked above.
• Problems:
1) Write down all of the 4-digit binary numbers in a list (as is done in the Power Set post from Math is Fun, under "It's Binary!", for 3-digit numbers)
2) For the set {red, yellow, green, blue}, give the power set by listing the subset that corresponds to each binary number in the list from problem #1. How many elements does the power set have?

For next time: We'll look at power sets of infinite sets, how we can prove that the power set of an infinite set has larger cardinality than the original set, and how to show that there is an infinite number of sizes of infinity!

Preliminary Reading: Ask Dr. Math on finding the power set of a power set

P.S. no journals due yet: you'll submit them Tuesday, since there is no class on Thursday next week!