Countably Infinite Set, Axiom of Choice

[divergentgrad]

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 $A$ is countably infinite, but we don't know anything else about set $A$. So we know there are bijections $A \to \mathbb{N}$. I ask you to give me a concrete, example bijection $\phi : A \to \mathbb{N}$.

To construct one such $\phi$... 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 $x \in A$ to an $i \in \mathbb{N}$.

Put another way...
Ordinarily I feel completely comfortable listing the elements of an arbitrary countable set $A$ as $A = \{x_1, x_2, ...\}$ 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 $\{x_1, x_2, ...\}$, 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.

 

[Eynstone]

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.

 

[disregardthat]

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.