Question 3 on infinity - the axiom of choice

Factual Questions
1

I quote:
For every set A there is a choice function, f, such that for any non-empty subset B of A, f(B) is a member of B.

Let’s see if I am understanding this correctly.
In constructing a subset of A, let’s call it B, I must go through the elements in A and choose whether they will belong in B.

Going one step further, if n is the cardinality of A, then the number of possible subsets is 2^n.
One step further again. If the cardinality of A is aleph0, then the number of possible Bs must be 2^aleph0, i.e., the cardinality of the continuium.

This is pretty similar to some of the other trains of thought raised in my other two threads. http://boards.straightdope.com/sdmb/showthread.php?p=8864359 and http://boards.straightdope.com/sdmb/showthread.php?p=8864356
In the context of things, this seems fairly straightforward. I don’t understand why the infinitude of B’s should be an obstacle to proving that c=aleph1

2

I’m honestly not sure why you think it wouldn’t be an obstacle. On one hand, you have an infinite set A; on the other hand, you’re talking about all of the infinitely many subsets B of A. I see no reason why the cardinality of the latter couldn’t be much much larger than the cardinality of the former.

3

I’m not sure what this has to do with the Axiom of Choice. AC says that given any nonempty subset B of A, you can choose an element of B.

The Axiom of Choice seems intuitively obvious, especially if you don’t think about it too hard. After all, all it says is that you can pull an element out of any nonempty set: surely this is the easiest thing in the world!

But intuition mostly relates to finite, or at least countable, sets. And for these sets AC can actually be proved inductively. The real power of AC, the part that’s an axiom, is the part talking about uncountable sets. When you start proving things using AC, you get some results that are not so intuitively obvious.

… The problem is that these three postulates are all equivalent, but mathematical intuition (at least for many mathematicians) does not provide a clear idea of whether they are true.

4

I’m not sure that you’ve got the axiom right. The axiom of choice asserts that for any set A, there is a function f from 2[sup]A[/sup] - Ø to A with f(B) [symbol]Î[/symbol] B for any subset B of A. It has nothing to do with constructing an arbitrary subset of A, which is what it sounds like you’re trying to do.

5

As others have said, it’s not clear why you mention the Axiom of Choice at all. However, why don’t we jump right to your question: you ask why there would be any obstacle to proving that c = aleph_1. Well, why don’t you tell us what potential method of proof you see for showing that c = aleph_1.

6

(so that we can point out the obstacles, I mean)

7

AC takes various equivalent forms. One says that, given any indexed family of non-empy sets, there is a function on the index set that chooses one element from each one. There is a version that says that given any pairwise disjoint collection of non-empty sets, there is a set that intersects each of the given sets in exactly one point. Another version says that the cartesian product of non-empty sets is non-empty (each element is a choice function). And then various other statements that are provably equivalent, but this gets further from the question. The real question is what does any of this have to do with the continuum hypothesis. Answer: nothing at all. CH is independent with or without AC.

8

Well, there is one small connection in this vein which one might mention. Although the Continuum Hypothesis is independent of both the Axiom of Choice and its negation, it can be shown that the Generalized Continuum Hypothesis implies the Axiom of Choice.

(All in the context of ZF, of course)

9

(Well, board timeouts prevented me from fixing it, but, of course, the phrase “independent of both _ and its negation” is redundant)

10

Wait, no it isn’t.

I blame the delirium which the emotional distress of temporarily losing SDMB access would naturally inflict upon anyone. :slight_smile:

11

Nothing that elaborate. I am merely trying to make some sense of what I have read. When I finished the book I realised on reflection that I still hadn’t comprehended the crux of what was being argued. A couple of weeks later it was still bugging me and so I thought it a good time to ask the dope.

Thanks to everyone who contributed to my minor enlightenment. I won’t pretend to fully understand, but at least I know what I was reading about.

12

I researched this a couple of months ago when I was first introduced to the concept.

It makes 1/aleph_x sense. (Same as my lottery odds)

I’ve always wondered where that tangent graph went after it left the page at the top and showed back up on the bottom. Was it the same one in the evil Spock universe that showed back up in our good Spock universe? How many aleph’s did it hit if it did? Did it have an aleph_gotee when it was gone?

13

If you’re talking about the graph of 1/x as a function from nonzero reals to nonzero reals, it didn’t go anywhere. It happens to climb up without stop as it approaches 0 from above, to be undefined at 0, and to climb down without stop as it approaches 0 from below, all without there being any “connection” or what have you along the way. There’s nothing wrong with this, it’s a perfectly good function all the same.

But, if that answer doesn’t satisfy you, then you may find it worthwhile to investigate the real projective line and the Riemann sphere, which extend the real line/complex numbers (respectively) with a single point, Infinity, which is the limit of 1/x (as a function from the real projective line/Riemann sphere to itself) as x approaches 0 from any direction.

14

I’ll explain my intuition of the difference between c and aleph1. Understand, of course, this is only my intuition; none of the crux of it can be traced back to any ZFC axioms.

I explained in this thread (post 4) how to define aleph1 in terms of the order-structure distinct ways of well ordering a countable set (by the way, my definition of a “well ordering” in that thread should include the fact that the set must also be linearly ordered).

c, on the other hand, can be defined as the number of different permutations of the natural numbers. What I mean is: Look at all the ways of ordering the natural numbers by the ordinal omega:

0,1,2,3,4,…

is one way, of course.

Also:

1,0,3,2,5,4,…

is a completely different one. Notice that this is distinct from post 4 in the previously mentioned thread; here, the different labelings make the different permutations distinct.

We also have:

1,2,3,6,5,4,7,8,9,12,11,10,…

as another example.

(To be clear, by “permutation” or “well ordering by omega”, I simply mean all the different labelings of the natural numbers that are still order isomorphic to the standard ordering of the natural numbers, just with different labelings).

Anyway, this is where the non-axiomatic intuition comes into it for me. A well ordering of a set appeals to me as being a very structurally precise ordering. There are “relatively few” of these, to my intuition

On the other hand, permutations seem to me to be a much “less structured” ordering than a well ordering. In particular, the orderings

0,1,2,3,4,5,6,…

and 1,0,3,2,6,5,…

are order isomorphically the same, but different permutations. Not to mention all the uncountably many other examples that are still order isomorphic to these, yet permutationally distinct.

Based on this idea, it tends to be my intuition that there are many more distinct permutations of a countable set than there are distinct well orderings.

15

I don’t know, Cabbage, it’s hard for me to make that intuition work. On the one hand, c is “pushed” towards being larger than aleph_1, because different labellings count as distinct for your c-sized-set but not for your aleph_1-sized-set. But, on the other hand, aleph_1 is “pushed” towards being larger than c, since lots of order types are allowed for your aleph_1-sized-set and only one fixed order type is allowed for your c-sized-set. The conflicting “pushes” cancel out any intuition I might have about how to compare the two.

Although, since choice tells us that c = c*aleph_1, I suppose there’s no need to restrict the c-sized-set to just the one order type; i.e., the c-sized-set can consist of every labelling of every member of the aleph_1-sized-set. That could perhaps work better for one’s intuition, there no longer being contrary “pushes”, though it still doesn’t work for me.

16

AH HAH!!
I knew this had something to do with strings and branes.
Now I have (sort of) a practical application to get a hold of.

This concept does indeed deal with the nature of our universe and the evils Spocks.

As I read on into the nature of the universe, the most curius of all problems are that of scale. Scaling a problem is by no means it’s analog. We can see a star that is roughly 2 billion years old (a baby), but we can’t see the flag on the moon? At the other end of scale, physics and intuition as we understand it is totaly disrupted. AKA 1/x. It’s a perfectly good function, just don’t ask about that one – or two points.