Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Countably Infinite Set, Axiom of Choice

  1. Aug 10, 2011 #1
    I'm not sure if this question has any sense. Either way, hopefully someone can help me see either the right question or the right way of thinking about this. I don't have any special background in set theory, myself.

    A set is countably infinite if there is a bijection between it and the natural numbers. Right?

    Suppose I tell you set [itex]A[/itex] is countably infinite, but we don't know anything else about set [itex]A[/itex]. So we know there are bijections [itex]A \to \mathbb{N}[/itex]. I ask you to give me a concrete, example bijection [itex]\phi : A \to \mathbb{N}[/itex].

    To construct one such [itex]\phi[/itex]... do you have to use AC? I ask because it seems like you'll have to make an infinite number of choices, arbitrarily choosing and then mapping each [itex]x \in A[/itex] to an [itex]i \in \mathbb{N}[/itex].

    Put another way...
    Ordinarily I feel completely comfortable listing the elements of an arbitrary countable set [itex]A[/itex] as [itex]A = \{x_1, x_2, ...\}[/itex] when I need to use the elements. But given a concrete countable set with no possible, "natural" decision rule to assign each element to a natural number... if I then want to list the elements of the set as [itex]\{x_1, x_2, ...\}[/itex], am I not implicitly using AC?

    Moreover--and this might be closer to the heart of the question, but I don't know--to dream up a countably infinite set that has no "natural" decision rule to assign each element to a natural number, do I need to invoke AC?

    Sorry again if this is inane or just silly.
  2. jcsd
  3. Aug 10, 2011 #2
    As I see it, one can infer the countability of a set only a fortiori , i.e., after one has a bijection with N in hand.
    I'm not an expert in set theory, but Axiom of Choice usually refers to its uncountable version.
  4. Aug 10, 2011 #3


    User Avatar
    Science Advisor

    I can't even give you a single concrete element of A if all I know is that it's a set and it's countably infinite. The axiom of choice of course does not produce any concrete bijection.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook