Questions on the use of axiom of choice

Question

So I must prove that "Every infinite set has a countably infinite subset." with following definition of the axiom of choice

Let $\{A_\alpha\}_{\alpha \in \lambda}$ be a collection of non-empty sets. Then there is a function $f:\lambda \rightarrow \cup_{\alpha \in \lambda} A_\alpha$ such that for each $\alpha$ in $\lambda$, $f(\alpha)$ is an element of $A_\alpha$.

Can I state "Let $A$ be an infinite set. Consider the collection of subsets of $A$ $\{A_\alpha\}_{\alpha \in \mathbb{N}}$," without violating the axiom of choice?

Answer 1

It's not a matter of violating the axiom of choice but rather of making sense. It doesn't make sense to say "Consider the collection of subsets of $A$ $\{A_\alpha\}_{\alpha \in \mathbb{N}}$" because you haven't specified which collection of subsets you are talking about. The word "the" implies you have some specific collection in mind, so you need to define what your collection is: given a natural number $\alpha\in\mathbb{N}$, what is the definition of $A_\alpha$?

I think you are getting a bit thrown off by the index set $\lambda$ here. Really, you should think of $\{A_\alpha\}_{\alpha\in\lambda}$ as just any set of sets; you don't have to pick some particular index set. If $S$ is any set of nonempty sets, then you can take $\lambda=S$ and $A_\alpha=\alpha$ for each $\alpha\in S$, and the collection $\{A_\alpha\}_{\alpha\in\lambda}$ is just a really fancy way of saying "$S$". So the axiom of choice says that if you have any set $S$ whose elements are nonempty sets, there exists a function on $S$ which takes each $\alpha\in S$ to an element of $\alpha$.

In this problem, in fact, you probably want to let the set $S$ be the collection of all nonempty subsets of $A$. Think about how you might then use a function $f$ provided by the axiom of choice to recursively pick an infinite sequence of distinct elements of $A$.

Answer 2

Let A be infinite. Use AxC to well order A. The order cannot
stop at any finite ordinal. Select the first omega_0 elements.

A more formal way is by well ordering A, prove dependent choice
and from dependent choice, prove countable choice and from
countable choice an denumberable subset.

Answer 3

Let $A$ be infinite. For $n\in \Bbb N$ let $[A]^n$ be the set of all $n$-member subsets of $A.$ (This is standard notation.)

Let $E:\Bbb N\to \cup_{n\in \Bbb N}[A]^n$ such that $\forall n\in \Bbb N\;(E(n)\in [A]^n).$

For $n\in \Bbb N$ let $L(n)$ be the set of all linear orderings of $E(n).$ Let $F:\Bbb N\to \cup_{n\in \Bbb N}L(n)$ such that $\forall n\in \Bbb N\;(F(n)\in L(n)).$

For clarity write $<_n$ for $F(n).$ For brevity let $E'=\cup_{n\in \Bbb N}E(n).$

For $x\in E'$ define $r(x)$ as the least $n\in \Bbb N$ such that $x\in E(n).$

Define $<^*$ on $E'$ by

(i) if $r(x)<r(y)$ then $x<^*y$ and $\neg (y<^*x)$

(ii) if $r(x)=r(y)=n$ then $(x<^*y \iff x<_ny).$

For $x\in E'$ and $r(x)=n$ we have $\{y: y<^*x\}= (\cup_{m<n}E(m))\cup \{y\in E(n):y<_n x\}.$

Let $G(x)$ be the number of members of $\{x\}\cup \{y:y<^*x\}.$ Then $G:E'\to \Bbb N$ is a bijection.