Axiom of Choice- a layman’s explanation.

Say you’re given the set \{1,2,3,\dots,n\}, and asked to choose a number. Any number. You may choose 1,2, or anything that you feel like from the set. Now suppose you’re given a set S, and you have absolutely no idea about what points S contains. In this case, you can’t visualize the points in S and pick any you feel like. You might say “pick the lowest upper bound of S“. However, what if S is not ordered? What if it does not even contain numbers? How do you select a point from a set when you can’t even describe any of the points in that set?

Here, the Axiom of Choice comes in. It states that if \mathfrak{B} is a set of disjoint subsets of S, then a function c: \mathfrak{B}\to \bigcup\limits_{B\in\mathfrak{B}}B such that one point from every disjoint set is selected. You can divide S into disjoint sets in any manner whatsoever, and get one point from each set. In fact, the disjoint sets don’t necessarily have to cover S. The condition is \bigcup\limits_{B\in\mathfrak{B}}\subseteq S.

Going by the above explanation, you may take each point in S to be a disjoint interval, and hence select the whole of S.

What is so special about this seemingly obvious remark? Selecting points from a set has always been defined by a knowledge of the set and its points. For example, if I say f:\Bbb{R}\to\Bbb{R} such that f(x)=f(x^2), I have selected the points with the information that points in \Bbb{R} can be squared, and lie inside \Bbb{R}, etc. If we had f:A\to \Bbb{R} where A is a set of teddy bears, then f(x)=x^2 would not be defined. With the Axiom of Choice, regardless of whether A contains real numbers or teddy bears, we can select a bunch of points from it.

What if B\in\mathfrak{B} are not all pair-wise disjoint? We can still select points from each B. Proof: Take the cross product \mathfrak{B}\times S. You will get points of the form (B,x), where B\in\mathfrak{B} and x\in S. Now create disjoint sets in \mathfrak{B}\times S by taking sets of the form B_i=\{(B_i,x)|x\in B\}; in essence you’re isolating individual sets of \mathfrak{B}. These are disjoint, as if x is the same, then B is different. The main purpose of taking this cross product was to create disjointed sets as compared to overlapping sets in S, so that we could apply the Axiom of Choice. Now we use the choice function to collect one point from each disjoint interval. Each of thee points will be of the form (B,x). Now we define a function g:\mathfrak{B}\times S\to S as g((B,x))=x. Hence, we have collected one point from each B\in\mathfrak{B}. Note that these points may well be overlapping. We found the cross-product just to be able to apply the Axiom of Choice. If the Axiom of Choice was defined for overlapping sets, then we wouldn’t have to find the cross product at all.

Now we come to the reason why this article was written: defining an injective function f:\Bbb{Z}_+\to B, where A is an infinite set and B is a subset of it. We don’t know if A is countable or not.

OK first I’d like to give you the following proof, and you should tell me the flaw in it. We use Proof by Induction. Say f(1)=a_1\in S. We find A-\{a_1\}, and determine a_2\in A-\{a_1\}. We assume f(a_n) equals a point in A-\{a_1,a_2,\dots,a_{n-1}\}, and then find f(a_{n+1}) in A-\{a_1,a_2,\dots,a_n\}. Why can we not do this? Because we know nothing about the points f(a_1),f(a_2),\dots! How can we possibly map 1 to any points without knowing what point we’re mapping it to?

The bad news is we might never know the properties of S. The good news is we can still work around it. Select \mathfrak{B} to be the set of all subsets of S. As one might know, there are \mathfrak{B}=2^{|S|}. The elements of \mathfrak{B} are not pairwise disjoint. However, we can still select a point from every set, as has been proven above (by taking the cross product to create disjoint sets, etc). The most brilliant part of the proof is this: take c(S). We know S\in \mathfrak{B}. This will give you one element from the whole of s. You need to know nothing about S to select an element from S. Let f(1)=c(S). Now take S-f(1). We know S-f(1)\in \mathfrak{B}. Let f(2)=c(S-f(1)). Continuing this pattern, we have f(n)=c(S-\bigcup\limits_{i}f(i)), where i\in \{1,2,3,\dots,n-1\}. By induction, we have that the whole of \Bbb{Z}_+ is mapped to a subset of S.

Published by -

Graduate student

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: