#choice function

The first problem is a write off. It's basically an application of the subset theorem. It might be something like "given A is a set, prove A x A is a set". And then you would notice that an element of A x A is of the form {{a}, {a, a'}}, which is a subset of the power set of A, PA. Then a set of these things, e.g. A x A, would be a subset of PPA. By the subset axiom, A x A is a set. Easy.

(Time out: I haven't actually defined ordered pairs yet for you guys. The concept of an ordered pair is pretty simple: it's something of the form <a, b>, where knowing a, knowing b, and knowing the order they go in completely determines the ordered pair. There were several propositions on how to go about formally defining this idea, but the one that stuck is to let <a, b> = {{a}, {a, b}}. Then, the set {a, b} completely determines the elements of the ordered pair, and the element in the singleton, i.e. {a}, is the first element in the ordered pair. Like I said, there have been other equally valid formulations that work, and it might be interesting to look them up. This method is popular because it is convenient and easy to work with.

Then, given two sets A and B, A x B is defined to be the set of all ordered pairs <a, b> where a comes from A and b comes from B. This set is the cross product of A and B.)

The second question is of the form "given a set A, show there is a smallest subset B satisfying conditions xyz". The trick here is to create a set, T, containing all subsets that satisfy the desired conditions. T is a subset of PA, so it's a set. Then, you show the intersection over all the elements in T is still in T, i.e. ∩T satisfies xyz. Then, ∩T is the smallest subset satisfying conditions xyz. It's the smallest because it's contained in all other subsets that satisfy the conditions, since it's the intersection over all of the subsets that satify the conditions. If there were a set contained in ∩T that satisfied the conditions, then it would be in T and therefore ∩T would have to be a subset of it.

The third question is an application of Zorn's Lemma. Oh yeah! Zorn's Lemma is some new material for this blog. Let's do a quick refresher on the axiom of choice. At this point in the class, we've got several alternate formulations of the axiom of choice:

For any function R, there is a function f contained in R, with the same domain as R.

If H is a function defined on I, and H(i) is nonempty for every i ∈ I, then there is a function with domain I and f(i) ∈ H(i). In other words, the cross product of nonempty sets is nonempty.

For any set A, there is a function f whose domain is the set of nonempty sets of A, and f(B) ∈ B for all nonempty B ⊆ A. In this case, f is called the choice function on A.

For sets C, D, either there is a one to one function from C into D, or there is a one to one function from D into C. We say C is dominated by D if there is a one to one function from C into D. This formulation says that, given a pair of sets, one must be dominated by another.

If A is a set so that for every chain B ⊆ A, we have that the union over B is an element of A, i.e. ∪B ∈ A, then A has a maximal element. This statement is Zorn's Lemma. There's quite a few new terms in this one, so let's go through it slowly. B is a chain iff for any C, D in B, either C ⊆ D or D ⊆ C. An element M ∈ A is maximal if M is not a subset of any other set in A.

So the third question on the qual is simply an application of Zorn's Lemma: "given a set A with some qualities, show that A contains a maximal element". You must show that A satisfies the conditions for Zorn's Lemma, i.e. for every chain in A, the union over the chain is an element of A (has whatever qualities qualify a set to be in A).

The last question is just an identification of the axiom of choice within a proof or statement. This question is generally pretty easy: you just look for some statement "for every A, there is a B, so let BA be this B". This statement evokes the axiom of choice if there are an infinite amount of As. In general, you are looking for some sort of choice or specification of one element out of a group of similar elements--and this choice is made for an infinite number of groups.