- #1

- 13

- 0

If so, why? (I'm assuming this depends on the Axiom of Choice).

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

In summary: You can't make the choices because ZF simply doesn't have the power to show that it's possible. But ZFC does have the power.If c : P(X) --> X is a choice function, let x be an element of X, and define A_n recursively: A_(n+1) = A_n U c(X-A_n) and A_1 = {x}. The size of A_n is n, so the union will be countable. I don't think this is provable in ZF.

- #1

- 13

- 0

If so, why? (I'm assuming this depends on the Axiom of Choice).

Physics news on Phys.org

- #2

Science Advisor

- 8,140

- 572

- #3

- 2,199

- 81

divergentgrad said:

If so, why? (I'm assuming this depends on the Axiom of Choice).

Under the Continuum Hypothesis, an infinite set which has a one to one mapping into real numbers would contain the countable set of rational numbers. I believe the AC is necessary to define exactly what is meant by a one-to-one mapping into the real numbers and to prove that such a mapping exists. There are others in this forum that know more about Set Theory than I do who I'm sure will weigh in.

Note: I did not see mathman's post since I started mine before he posted.

Last edited:

- #4

- 13

- 0

mathman said:

It seems so obvious now. Thanks.

- #5

- 22,183

- 3,321

- #6

Science Advisor

- 8,140

- 572

micromass said:

Why do you need the axiom of choice?

- #7

- 22,183

- 3,321

- #8

Science Advisor

- 8,140

- 572

micromass said:

I believe you are not completely familiar with the axiom of choice.

Specifically it says: given an infinite collection of non-empty sets, there exists a set (the choice set) which has an element in common with each set of the collection.

In the problem at hand we are dealing with only one infinite set, so you don't need the axiom of choice to select an element.

- #9

- 22,183

- 3,321

mathman said:I believe you are not completely familiar with the axiom of choice.

I did my thesis on the axiom of choice. But that's besides the point.

What we do here is to select an element xSpecifically it says: given an infinite collection of non-empty sets, there exists a set (the choice set) which has an element in common with each set of the collection.

In the problem at hand we are dealing with only one infinite set, so you don't need the axiom of choice to select an element.

Sets which have a countable subset are called Dedekind-infinite. So without the axiom of choice, there might exist infinite Dedekind-finite sets.

However, what we're doing here does not require the full axiom of choice! It is even weaker than the axiom of countable choice. But it is not derivable from ZF that every set has a countable subset. Some kind of choice is needed here (although a very light kind of choice!)

See http://en.wikipedia.org/wiki/Dedekind_infinite for more information, or check out the excellent book "Axiom of choice" by Horst Herrlich.

- #10

- 22,183

- 3,321

Here is a proof that the axiom of countable choice implies that every set has a countable subset.

Take an infinite set X. Consider for each n

[tex]X_n=\{(x_1,...,x_n)~\vert~x_i\neq x_j~\text{forall i,j}\}[/tex]

By countable choice, there exists an element [itex](y_n)_n\in \prod{X_n}[/itex]

Concatenation of the y

- #11

Staff Emeritus

Science Advisor

Gold Member

- 14,981

- 26

How do you plan on making the infinitely many choices?mathman said:In the problem at hand we are dealing with only one infinite set, so you don't need the axiom of choice to select an element.

The axiom of choice tells you things you

You cannot make the choices because ZF simply doesn't have the power to show that it's possible. But ZFC does have the power.

- #12

Science Advisor

- 1,866

- 34

If c : P(X) --> X is a choice function, let x be an element of X, and define A_n recursively: A_(n+1) = A_n U c(X-A_n) and A_1 = {x}. The size of A_n is n, so the union will be countable. I don't think this is provable in ZF.

Hurkyl, could you answer me this, it has been bothering me for a while: How do you choose one element from a set X in the set theoretical formal language? For example, if I want to define a singleton subset from X, how do we do this by set construction?

We know that [tex]\exists x : x \in X[/tex]. But how do we "draw" one element from X so that we can define a singleton subset Y? Or is this even possible? Maybe we can't do more that say [tex]\exists x : x \subseteq X[/tex] and the cardinality of x is 1.

Hurkyl, could you answer me this, it has been bothering me for a while: How do you choose one element from a set X in the set theoretical formal language? For example, if I want to define a singleton subset from X, how do we do this by set construction?

We know that [tex]\exists x : x \in X[/tex]. But how do we "draw" one element from X so that we can define a singleton subset Y? Or is this even possible? Maybe we can't do more that say [tex]\exists x : x \subseteq X[/tex] and the cardinality of x is 1.

Last edited:

- #13

- 2,199

- 81

- #14

Staff Emeritus

Science Advisor

Gold Member

- 14,981

- 26

I think your analysis is correct. In ZF, if all we know is that "X is a set", then that is more or less the best we can do.disregardthat said:How do you choose one element from a set X in the set theoretical formal language?

Maybe we can't do more that say [tex]\exists x : x \subseteq X[/tex] and the cardinality of x is 1.

- #15

Science Advisor

- 1,866

- 34

Hurkyl said:I think your analysis is correct. In ZF, if all we know is that "X is a set", then that is more or less the best we can do.

This kind of changes the semantics for these kinds of proofs. If we take the example of the choice function above, A_n isn't really a defined set. It isn't set theoretically correct (that is, there is no corresponding argument in ZFC) to say: "let x be an element of X. Define A = {x}." We have to be able to know more of X, to such a degree that we can specify an element x for us to be able to define a singleton set. By "define" I mean as in comparison to e.g. the trivial example "Define Y = X".

So I believe that if we work with general sets, it should be put more appropriately. If I take my example again, we would have to argue that "there exists a sequence of subsets [itex]A_1,A_2,...,A_n[/itex] such that [itex]A_1 \subseteq A_2 \subseteq ... \subseteq A_n[/itex] and the cardinality of A_k is k", and from that argue that "there exists a countable subset of X" which doesn't involve defining anything, but only using the mechanics of the existence quantifier. This could alternatively be seen as 'what our argument actually mean' (if we insist on it being expressible in ZFC). Or would someone disagree with that?

Last edited:

- #16

Staff Emeritus

Science Advisor

Gold Member

- 14,981

- 26

Once you've introduced the variable

A := {x}

is a perfectly good way to define a new variable A. (and makes Then the challenge of the proof is to ensure that your generalized elements are drawn from non-empty sets.

For finitely many such variables, it is enough to show that each individual variable varies over a non-empty domain.

For infinitely such variables, we still need only ensure each individual variable ranges over a non-empty domain. Some variant of the notion of choice function ensures that the entire collection of variables jointly varies over a non-empty domain.

Without the axiom of choice, we are no longer guaranteed that the collection of all our variables varies over a non-empty domain even if each individual one does on its own. It becomes more difficult to make arguments of this form.

- #17

Science Advisor

- 8,140

- 572

As far as the etc. part (going from one at a time to countably infinite). Is this any different from the standard proof that the rationals are countable?

- #18

Science Advisor

- 1,866

- 34

You don't just need one element, you will have to pick each element in the countable subset.

- #19

- 22,183

- 3,321

Showing that [itex]\mathbb{N}[/itex] and [itex]\mathbb{N}^2[/itex] have the same cardinality can be done without choice since an explicit bijection can be found (otherwise, choice was necessary). But not all sets are as well-behaved as the naturals!

Let's say I give you an infinite set X. Try to write down an explicit countable subset of X. Explicit in the sense that you can use unions, products (which can be empty), intersections, etc. What would that explicit subset look like? Can you write it down?

- #20

- 799

- 7

mathman said:As far as the etc. part (going from one at a time to countably infinite). Is this any different from the standard proof that the rationals are countable?

Yes. Say you have a countable collection of arbitrary countable sets. You want to do the "diagonal snake" trick by laying out each countable set horizontally, one above the other, to form an infinite matrix.

For each of the countable sets, there is a bijection with N, so we can certainly write down its elements in a list a1, a2, a3, ...

But what we need to do is choose a particular bijection for each of the countably many countable sets. For that we need choice.

In other words each countable set has a bijection with N. But you need Choice to simultaneously choose a particular bijection for each set.

I know that won't convince an AC disbeliever (or agnostic, as the case may be), but that's the explanation as I understand it.

Last edited:

- #21

Staff Emeritus

Science Advisor

Gold Member

- 14,981

- 26

It's not what you're choosing from -- it's how many choices you have to make. You can still have a problem even if every set you're choosing from has only two members.mathman said:Maybe I'm being naive, but I don't see the need for the axiom of choice if we want to choose a member of a set which has an infinite number of members.

- #22

Science Advisor

- 8,140

- 572

I don't understand the objection. I am choosing one element from one non-empty set. Next, since the set had an infinite number of elements, I then can choose another element, etc. I am not trying to choose an infinite number of elements from an infinite number of sets (axiom of choice - as far as I understand it).Hurkyl said:It's not what you're choosing from -- it's how many choices you have to make. You can still have a problem even if every set you're choosing from has only two members.

- #23

Staff Emeritus

Science Advisor

Gold Member

- 14,981

- 26

That "etc." only gets you up to "I can make N choices from this set, where N is a natural number". It does not get you up to "I can make infinitely many choices from this set".mathman said:I don't understand the objection. I am choosing one element from one non-empty set. Next, since the set had an infinite number of elements, I then can choose another element, etc.

- #24

- 22,183

- 3,321

mathman said:I don't understand the objection. I am choosing one element from one non-empty set. Next, since the set had an infinite number of elements, I then can choose another element, etc. I am not trying to choose an infinite number of elements from an infinite number of sets (axiom of choice - as far as I understand it).

You can choose a finite number of elements. And that finite number can be made as large as you want. But it can't be made infinite.

- #25

- 799

- 7

mathman said:I don't understand the objection. I am choosing one element from one non-empty set. Next, since the set had an infinite number of elements, I then can choose another element, etc. I am not trying to choose an infinite number of elements from an infinite number of sets (axiom of choice - as far as I understand it).

Here's how I understand that. You have an infinite set X. X is certainly nonempty. So I can pick one element; call it x1.

Now X\{x2} is certainly nonempty, so I can pick x2.

Now X\{x1,x2} is certainly nonempty, so I can pic x3.

Dot dot dot ... but that's where the AC is needed. Because to complete this construction, I have to choose one element from each of an infinite collection of nonempty sets.

- #26

Science Advisor

- 8,140

- 572

A set is infinite if it contains an unlimited number of elements. This means that no matter how many elements are counted, there will always be more to count.

A countable subset is a subset of a set that can be put into a one-to-one correspondence with the set of natural numbers. This means that the elements in the subset can be counted and labeled with unique natural numbers.

To prove this statement, we can use the axiom of choice and the Cantor-Schröder-Bernstein theorem. This theorem states that if there exists an injection from one set to another and an injection from the other set to the first, then there exists a bijection between the two sets. By using this theorem, we can show that every infinite set can be put into a one-to-one correspondence with the set of natural numbers, thus proving the existence of an infinite, countable subset.

Yes, an infinite set can have multiple infinite, countable subsets. For example, the set of even numbers and the set of odd numbers are both infinite, countable subsets of the set of integers.

Yes, an infinite set can have subsets that are not countable. For example, the set of real numbers is infinite but is not countable. This is because there is no way to put the real numbers into a one-to-one correspondence with the natural numbers.

Share:

- Replies
- 22

- Views
- 2K

- Replies
- 5

- Views
- 1K

- Replies
- 22

- Views
- 2K

- Replies
- 5

- Views
- 900

- Replies
- 1

- Views
- 995

- Replies
- 1

- Views
- 658

- Replies
- 33

- Views
- 2K

- Replies
- 1

- Views
- 1K

- Replies
- 13

- Views
- 1K

- Replies
- 6

- Views
- 886