Math 440, Fall 2014, Assignment 1

The beginner ... should not be discouraged if ... he finds that he does not have the prerequisites for reading the prerequisites.

- P. Halmos

Carefully define the following terms, then give one example and one non-example of each:

1. Cartesian product (of two sets).
2. Power set (of a set).
3. Equinumerous (sets).
4. Countable set.
5. Uncountable set.
6. Cardinality of the continuum.
7. Partial order.
8. Maximal element (of a partially ordered set).
9. Largest element (of a partially ordered set).
10. Chain (in a partially ordered set).

Carefully state the following theorems (you need not prove them):

1. Cantor-Bernstein Theorem.
2. Cantor's Theorem.
3. Continuum Hypothesis (of course this is not a theorem, though it is sometimes taken as an axiom).
4. Axiom of Choice (see above).
5. Zorn's Lemma.

Solve the following problems:

1. Prove Cantor's Theorem (exercise 1I.1 contains many hints).
2. Problems 1E and 1H (you will use the results of 1H incessantly for the rest of the semester).

--------------------End of assignment--------------------

Solutions:

1. Cartesian Product of Two Sets:

   Let \(A\) and \(B\) be sets. The cartesian product of \(A\) and \(B\), \(A \times B\), is the set:$$ A \times B = \{(a,b)| a\in A , b \in B\} $$

   Example:

   The cartesian product of \(\{1,2\}\) and \(\{a,b\}\) is \(\{(1,a), (1,b), (2,a), (2,b)\}\)

   Non-Example:

   Remember that the Cartesian product is a set of tuples. Don't confuse it with the union of two sets, which would be \(\{1,2,a,b\}\) for the above example.

1. Power Set of a Set:

   Let \(A\) be a set. The power set of \(A\) is the set of all subsets of \(A\): $$ \mathscr{P}(A) = \{B | B \subseteq A\} $$

   Example:

   The power set of \(\{1,2\}\) is \(\{\emptyset,\{1\}, \{2\}, \{1,2\}\}\)

   Non-Example:

2. Equinumerous Sets:

   Two sets \(A\) and \(B\) are equinumerous if there is a bijection between the two sets.

   Example:

   \(\mathbb{Z}\) and \(\mathbb{Q}\) are equinumerous.

   Non-Example:

   \(\mathbb{Z}\) and \(\mathbb{R}\) are not equinumerous.

3. Countable Set:

   A set \(S\) is countable if there is an injection from \(S\) to \(\mathbb{Z}\) (or any other countable set.)

   Example:

   \(\{a,b,c\}\) is countable - it can easily be injected to \(\mathbb{Z}\).

   Non-Example:

   \(\mathbb{R}\)

4. Uncountable Set:

   A set is uncountable if there is no injection from it to \(\mathbb{Z}\).

   Example:

   \(\mathbb{R}\).

   Non-Example:

5. Cardinality of the Continuum:

   The cardinality of the continuum, \(\mathbb{c}\), is the cardinality of the real numbers.

   Example:

   \(\mathbb{R}\).

   Non-Example:

   \(\mathbb{Z}\)

6. Partial Order:

   A partial ordering on a set \(A\) is a relation that is reflexive, transitive, and anti-symmetric. A set with a partial order is also called a poset.

   Example:

   \((\mathbb{R},\leq)\) is a partial ordering of the reals.

   Non-Example:

   \((\mathbb{R},\lt)\) is not a partial ordering - it is not reflexive.

7. Maximal Element of a Poset:

   If \((A,\leq)\) is a poset, then an element \(b \in A\) is maximal if there is no \(c \in A\) such that \(b \leq c\).

   Example:

   a is maximal in the alphabet, by alphabetical order.

   Non-Example:

   There is no maximal natural number.

8. Largest Element of a Poset:

   If \((A,\leq)\) is a poset, then an element \(b \in A\) is the largest element of \(A\) if for all \(c\in A\) \(b \geq c\).

   Example:

   3 is the largest element of the set \(\{1,2,3\}\).

   Non-Example:

   The set \((0,1)\) has no largest element (within itself).

9. Chain in a Poset:

   Given a poset \((A,\leq)\), a chain in \(A\) is a totally ordered subset \(B\). Meaning for every two elements \(a,b \in B\), either \((a,b) \in \leq\) or \((b,a) \in \leq\).

   Example:

   The integers are a chain in the real numbers with respect to \(\leq\).

   Non-Example:

Theorems:

1. Cantor-Bernstein Theorem

   Let \(A\) and \(B\) be sets. If there are injections \(f:A \rightarrow B\) and \(g:B \rightarrow A\), then \(|A| = |B|\). (Does not require the axiom of choice).

2. Cantor's Theorem

   For all sets \(A\), \(\mathscr{P}(A)\) has strictly greater cardinality than \(A\).

3. Continuum Hypothesis

   There does not exist a set \(A\) such that \(|\mathbb{Z}| \lt |A| \lt \mathbb{c}\).

4. Axiom of Choice

   Let \(X\) be a set of sets. Then there exists a function \(f\) such that \(f(x) \in x\) for all \(x \in X\). Less formally, if we have a collection of sets, we have a way to choose one element from each of those sets.

5. Zorn's Lemma

   Let \(A\) be a poset. If every chain in \(A\) has a maximal element, then \(A\) has a maximal element.