Countably Infinite Set, Axiom of Choice

  • #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.
 

Answers and Replies

  • #2
336
0
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.
 
  • #3
disregardthat
Science Advisor
1,861
34
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.
 

Related Threads on Countably Infinite Set, Axiom of Choice

Replies
11
Views
5K
  • Last Post
2
Replies
49
Views
3K
Replies
10
Views
1K
  • Last Post
Replies
5
Views
3K
Replies
1
Views
1K
  • Last Post
Replies
17
Views
5K
  • Last Post
Replies
3
Views
2K
Replies
7
Views
3K
Replies
2
Views
2K
  • Last Post
Replies
8
Views
2K
Top