Some of you have been confused by the proof of Proposition 2 in Week 3 notes; I wrote the following e-mail to explain parts of it, and thought it might be worth posting here.
---
It is easiest to illustrate how this argument works
with an example. Suppose that X is the set
X = {2, 4, 6, 8, 10, 12, ...}
then we create the sets A_0, A_1, A_2, ... and numbers a_0,
a_1, a_2, ... as follows.
* We define A_0 to equal X, thus
A_0 = {2, 4, 6, 8, 10, 12, ...}
* We define a_0 to be the minimum of A_0, thus
a_0 = min(A_0) = 2
* We define A_1 to equal A_0 - {a_0}, thus
A_1 = A_0 - {2} = {4, 6, 8, 10, 12, ...}
* We define a_1 to be the minimum of A_1, thus
a_1 = min(A_1) = 4
* We define A_2 to equal A_1 - {a_1}, thus
A_2 = A_1 - {4} = {6, 8, 10, ...}
etc.
In this way we create a sequence a_0, a_1, a_2, a_3... which can
be used to create a bijection between N and X. The sets A_0, A_1, A_2, ... are used to generate the sequence a_0, a_1, ... but are otherwise not used very much in the
rest of the proof.
> Also, what does it mean for a set to be well-defined?
This means that the recipe used to define the set is well-defined - it has a definite
value. For instance, if we have two real numbers a and b and we define a new number x by
x := a/b, then x will be well-defined as long as b is non-zero, but if b is zero then x is
ill-defined because we are not allowed to divide by 0. Of course as soon as something is ill-defined,
you have to stop whatever argument you are doing because you are working with objects that do not
make sense, so whenever there is a possibility of being ill-defined (e.g. by denominators being zero),
then one has to first check that this does not occur before one can proceed.
In this case, the potential problem in the above construction is that the sets A_n may become empty, in which
case min(A_n) becomes undefined (There is no such thing as the minimum element of the empty set; the well-ordering
principle only works for non-empty sets). For instance, if X = {2,4}, then the above recipe will set
A_0 equal to {2, 4}, a_0 equal to 2, A_1 equal to {4}, a_1, equal to 4, A_2 equal to the empty set, but then
a_2 is undefined. However, if we start with the assumption that X is infinite then one can show that one never
runs into this problem.
Terry