# Thread: Disjoint sets and Axiom of choice.

1. ## Disjoint sets and Axiom of choice.

"Axiom of choice: Let A = {A1, A2, ...} be a collection of disjoint sets. Then there exists a set A such that A $\subseteq$ UiAi......"

How can the union of disjoint sets (no element in common, intersection empty) exist?

2. ## Re: Disjoint sets and Axiom of choice.

Originally Posted by Hartlw
"Axiom of choice: Let A = {A1, A2, ...} be a collection of disjoint sets. Then there exists a set A such that A $\subseteq$ UiAi......"
How can the union of disjoint sets (no element in common, intersection empty) exist?
You really need to spend some time studying this website.

3. ## Re: Disjoint sets and Axiom of choice.

Originally Posted by Plato
You really need to spend some time studying this website.
Thanks for reference. I looked at it. I think I'll pass.

4. ## Re: Disjoint sets and Axiom of choice.

Originally Posted by Hartlw
Thanks for reference. I looked at it. I think I'll pass.

5. ## Re: Disjoint sets and Axiom of choice.

Originally Posted by Plato
That does not follow logically from what I wrote, as any reader of this thread will discover if they go to your reference.

6. ## Re: Disjoint sets and Axiom of choice.

Originally Posted by Hartlw
That does not follow logically from what I wrote, as any reader of this thread will discover if they go to your reference.
You missed the point: You have no idea what the axiom of choice is about.

7. ## Re: Disjoint sets and Axiom of choice.

Originally Posted by Plato
You missed the point: You have no idea what the axiom of choice is about.

You are absoluteley correct. And after looking over the link I concluded I would'nt know if I studied it all night.

And yet, you did answer my question in a certain sense, for which, please note, I thanked you and am still appreciative. I think the shot was unnecessary.

8. ## Re: Disjoint sets and Axiom of choice.

Originally Posted by Hartlw
"Axiom of choice: Let A = {A1, A2, ...} be a collection of disjoint sets. Then there exists a set A such that A $\subseteq$ UiAi......"

How can the union of disjoint sets (no element in common, intersection empty) exist?
It appears the quoted statement above is incorrect.

I found the following:

"Given any set S of mutually disjoint nonempty sets, there is a set C containing a single member from each element of S. C can thus be thought of as the result of "choosing" a representative from each set in S. Hence the name."

That makes perfectly good sense as the statement of a principle. For finite sets, there is a set consisting of one member from each of the given disjoint sets. If the disjoint sets are {1,2,3}, {4,5,6}, and {8,9,10}, then a choice for C is {1,4,8}. Another is {3,5,10}. I imagine the difficulty arises with infinite sets.

9. ## Re: Disjoint sets and Axiom of choice.

Originally Posted by Hartlw
It appears the quoted statement above is incorrect.

I found the following:

"Given any set S of mutually disjoint nonempty sets, there is a set C containing a single member from each element of S. C can thus be thought of as the result of "choosing" a representative from each set in S. Hence the name."

That makes perfectly good sense as the statement of a principle. For finite sets, there is a set consisting of one member from each of the given disjoint sets. If the disjoint sets are {1,2,3}, {4,5,6}, and {8,9,10}, then a choice for C is {1,4,8}. Another is {3,5,10}. I imagine the difficulty arises with infinite sets.
yes, it does. the problem isn't with the "choosing" per se, it's how to explicitly come up with the "choice" function: if we have infinite sets to choose from (say each set is a copy of the real numbers) and an infinite number of sets to choose from (say a different copy of the real numbers for each different real number) we're hard-pressed to say our function is well-defined. we have "too many choices" to be able to say "which" choice we chose (there's no hope of even naming the possible choice functions).

of course, if we could create a well-ordering for each set, then we could easily specify a choice function, by picking the least element of every set. so it seems plausible that the well-ordering theorem, and the axiom of choice might amount to the same thing (which they do).

on the other hand, it seems obvious that we can come up with a choice function: since each set is non-empty, just pick one element from each! which works just fine, as long as we don't ask: "how?"

and here is a big fork in the road for the budding mathematician: when you say: "there exists..." do you mean "there is (and i can exhibit)...",

or do you mean "there is (in principle, but i have no idea how to find it)..."?

**********

to answer the question you actually asked, it is perfectly possible to have a union of disjoint sets. {a,b} and {c,d} have no element in common,

but {a,b} U {c,d} is no trouble at all to whip out, it is: {a,b,c,d}. disjoint sets are nice to work with, because "union" acts like "adding" (we don't have to

watch out for double-counting the "overlap" that is, the intersection).

10. ## Re: Disjoint sets and Axiom of choice.

Originally Posted by Deveno
yes, it does. the problem isn't with the "choosing" per se, it's how to explicitly come up with the "choice" function: if we have infinite sets to choose from (say each set is a copy of the real numbers) and an infinite number of sets to choose from (say a different copy of the real numbers for each different real number) we're hard-pressed to say our function is well-defined. we have "too many choices" to be able to say "which" choice we chose (there's no hope of even naming the possible choice functions).

of course, if we could create a well-ordering for each set, then we could easily specify a choice function, by picking the least element of every set. so it seems plausible that the well-ordering theorem, and the axiom of choice might amount to the same thing (which they do).

on the other hand, it seems obvious that we can come up with a choice function: since each set is non-empty, just pick one element from each! which works just fine, as long as we don't ask: "how?"

and here is a big fork in the road for the budding mathematician: when you say: "there exists..." do you mean "there is (and i can exhibit)...",

or do you mean "there is (in principle, but i have no idea how to find it)..."?

**********

to answer the question you actually asked, it is perfectly possible to have a union of disjoint sets. {a,b} and {c,d} have no element in common,

but {a,b} U {c,d} is no trouble at all to whip out, it is: {a,b,c,d}. disjoint sets are nice to work with, because "union" acts like "adding" (we don't have to

watch out for double-counting the "overlap" that is, the intersection).
Many thanks Deveno. The quoted statement in my first post went on to specify A intersection Ai consisted of one element of Ai. I just blanked out on the union.

If I have an infinite number of disjoint infinite sets, what's wrong with one element from each set? Doesn't that satisfy the axiom of choice? Hmmmm. If you have an infinite set, how do you specify a member of the set if, say, for example, they aren't subscripted variables. If an infinite set exists, it would seem whether or not you could pick out a member would depend on the definition. You can always specify points on a line or in space by a coordinate system. An infinite number of unspecified "things" doesn't sound too interesting to an enginer (purposeley misspelled to amuse the mathematicians). BTW, I am not a budding mathematician. I have no memory whatsoever, which is why I can't learn a language. I could repeat the def of a word 50 times and not remember it. And even if I could remember a sequence of definitions, I wouldn't believe them unless they made some sense to me other than a sequence of definitions.

EDIT In retrospect I see I just said what you said. I don't think you can count the real numbers but you can id them with a cut. Doesn't that work for any space of real numbers?

11. ## Re: Disjoint sets and Axiom of choice.

there's nothing wrong with picking just one. just one is all we need for a choice function. the question is: how do we decide "which one's the one"? in other words, what is our decision algorithm?

given certain sets, there is sometimes an algorithm that is obvious. the axiom of choice is true (without the need for an axiom) for certain sets (such as finite sets). but proving there is an algorithm for every single set you can imagine....well, that's a taller order. there are a lot of sets out there, and some sets are just plain weird.

the axiom of choice essentially says...well, even if we can't find an algorithm, there still ought to be one. and we'll let this "magical" algorithm, which exists because we say it does, do our choosing for us. problem solved! if you find that a little bit suspicious, you're not alone.

but let's take another statement, which seems a bit more innocuous. let's say i have an onto function f:A-->B, so every element b has a pre-image a in A, such that f(a) = b (every b in B is the target under f of some a in A). it seems pretty clear that we ought to be able to define a right-inverse for f, that is a function g:B--->A with f(g(b)) = b in the following way:

for every b in B, define g(b) = a, where a is an element such that f(a) = b.

then f(g(b)) = f(a) = b, nifty!

for example, f:R--->R+U{0} could be the function f(x) = x^2. f isn't 1-1, because -x and x both get mapped to x^2, but it is onto the set of non-negative reals.

and, indeed we can define g(y)= √y, and we see that f(g(y)) = f(√(y)) = (√y)^2 = y (since y is non-negative). so hey! it works! no problemo!

except....remember when we defined g(b) to be an a such that f(a) = b? that means "choosing" some a from the non-empty set in A that maps to b. for the function f(x) = x^2, we "rigged the question", because for each non-negative y, we only have two choices for x (two x's such that x^2 = y), so it's easy to give an explicit algorithm: pick the positive one. for a general function, we might not have such a clear choice, in fact, we could probably invent a function so strange, that it would be very hard to decide which "pre-image" element to choose.

and yet, it seems intuitively OBVIOUS we can define g. you can imagine how surprised mathematicians were, when it was shown that assuming the axiom of choice was false, was just as logically sound as assuming it was true. i mean, something is either true, or it isnt, right? well, it would seem, not exactly....

12. ## Re: Disjoint sets and Axiom of choice.

Thanks Deveno. I see the difficulty of specifying an element of the set in a general case.

I thought Russel's analogy about choice given sets of pairs of socks and pairs of shoes silly.

Whether or not you can make a choice for given sets depends on how the sets are defined.

For an infinite number of disjoint infinite sets of real numbers, if the sets are defined there should be some algorithm to pick a number.

Now from Plato's link, all possible disjoint sets of real numbers is a stumper. If you don't know which one to pick, pick any ONE since you know the set isn't empty. Does the axiom of choice say you need an algorithm (f(S) or does it just say you can pick one? If you need an algorithm, the question becomes, from an arbitrary set of real numbers what do you want to pick? As you say, smallest one is easy, (lub?), but other than that, since the set is arbitrary, there is no basis for picking a number since all you know is it contains any where from 1 to infinity real numbers. You can't define f(S) if you can't define S. S is the set of all possible sets (including S?)?. All possible sets between [0,1]? It seems you are getting into word games.

13. ## Re: Disjoint sets and Axiom of choice.

you are correct. at the "deeper" levels of logics, semantics become important. the question of how to make unabiguous definitions proves to be a dificult one. the task of coming of up with systems that "follow the rules" but "act bizzare" is a field of active research (called non-standard model theory). fortunately for us of lesser mental capacity, the "usual" way of looking at things seems to be "ok" (that is, we haven't found any "logical holes" so far).

the analogy of socks shows that even when you can create "an" algorithm (just pick one!), you may not be able to communicate that algorithm to anyone else. if someone wanted to duplicate your choice, exactly, they'd have a hard task. especially if you had as many socks as there are real numbers (not technically possible, but you get the idea). and "duplicating the choice" is what we mean by function: same input gives same output.

so what the axiom of choice says, is: it's hypothetically possible to make such a choice, even if S is "non-contructively defined" (and an arbitrary set of real numbers fits the bill pretty well). if you are someone who believes that existence of mathematical entities is logically dependent on "basic mathematical atomic structures" (the natural numbers is an example of such a structure), there's no way to convince you the axiom of choice should be true.

if, however, you believe that mathematical structures' existence is purely hypothetical, based on a set of properties we find desirable, then the axiom of choice seems a prefectly good way of saying "i can choose an arbitrary element of a set, if i need to." in other words, it's true because that is a property we wish sets to have (none of the other properties of sets by themselves, or combined imply this property).

and you are quite correct, in a sense the whole question comes down to a problem of definitions. nobody has an issue with explicitly defined sets, like "words that start with t", or "even integers". the problem comes with implicitly defined sets: "the set of all subsets of a complicated set of functions on some other complicated set". and the problem comes into sharp focus whenever we have an equivalence relation (which automatically defines a partition of disjoint sets, the equivalence classes).

we'd like to treat "equivalence classes" as elements of a set, in their own right. and we'd like the equivalence classes to preserve some (but not all) of the properties of the parent set. well often the properties of the parent set are defined "element-wise". so, to treat the equivalence classes element-wise we need to choose a "representative member". and that, involes invoking the axiom of....

14. ## Re: Disjoint sets and Axiom of choice.

Deveno. Thanks. Your previous post was very enlightening. Especially the notion of communicating your choice.

So where I am now is that the axiom of choice is a postulate that "identical" things can be uniqueley identified (number, color, smell, weight, geometry, etc).

If f(S) is an object from each set, it only makes sense if you can identify the set and the object.

For example: I have five buckets of different colored sand. I define f(S) by taking a grain from each bucket and putting it in a bowl.

First problem: By taking the grain of sand from each bucket I change each bucket of sand and I can no longer ID the grain in the bucket because it is no longer there.

f(S) is the bowl of sand only if I can pick a grain from a bucket, duplicate it, and put one back in the bucket and one in the bowl. Now someone can take a grain from the bowl and get it from the bucket by comparison.

Duplication and comparison is one way to define f(S), The other way is to take a grain of sand, describe it uniqueley, and put it back in the bucket. So to tell someone to get a particular grain of sand I have to ID the bucket and the grain of sand. Objects identical by comparison or description have the same ID.

EDIT: Or is there some deeper meaning to the axiom of choice that even if you can identify individual "things" you might not be able to choose them.