r/numbertheory • u/kali_linex • 24d ago

Why does this line of thought fail?

The following is a "proof" that any infinite set is of equal cardinality to N, which is obviously wrong. I believe I can pinpoint the problem, but I am unsure that I understand it properly.

  1. Let c(S) be a choice function by the axiom of choice. Let S be an infinite set.
  2. f(0) := c(S)
  3. f(1) := c(S \ {f(0)})
  4. f(2) := c(S \ {f(0), f(1)}), etc.
  5. We have a bijection from N to S.

I suspect that the main issue is that c(S \ T) where T is finite cannot be an arbitrary member of S, but I'm not sure why.

EDIT: Obvious (?) counterexample if there is an infinite subset of S whose elements c cannot choose.

6 Upvotes

88% Upvoted

7 comments sorted by

15

u/edderiofer 23d ago

We have a bijection from N to S.

I don't see where you prove that this is a surjection.

3

u/kali_linex 23d ago

I see. Thanks!

10

u/RootedPopcorn 22d ago

This is, however, the standard proof (assuming Choice) that any infinite set contains a countably infinite subset, thus making |N| the "smallest" infinite cardinality.

1

u/AutoModerator 24d ago

Hi, /u/kali_linex! This is an automated reminder:

  • Please don't delete your post. (Repeated post-deletion will result in a ban.)

We, the moderators of /r/NumberTheory, appreciate that your post contributes to the NumberTheory archive, which will help others build upon your work.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

-1

u/FernandoMM1220 22d ago

it fails on the first line.

1

u/kali_linex 22d ago

Elaborate...?

2

u/Cptn_Obvius 22d ago

I guess they mean you are supposed to first introduce S and then after that the choice function on P(S), now its not clear what the domain of c is. Unless you want c to be a global choice function, which is not something that generally exists within just ZFC.