Finite Axiom of Choice

  • Thread starter jacobrhcp
  • Start date
  • #1
169
0

Homework Statement



Prove, without using the Axiom of Choice:

if f: X->Y is surjective and Y is finite, there exists a 'section', a function s:Y->X such that f(s(y))=y for all y in Y

Hint: perform induction over the cardinality of Y

The Attempt at a Solution



Induction over the cardinality of Y? I don't even know what they mean. I'd say this would require the AC because we need to pick one of the elements of f^-1 (y) for all y in Y. since X is infinite, one of these f^-1 (y) has to be infinite as well, and I don't know how to pick a specific element of this if I can't just say 'I pick some'.

And I also don't understand the hint. Some help would be appreciated.
 

Answers and Replies

  • #2
HallsofIvy
Science Advisor
Homework Helper
41,847
966
You don't know "proof by induction"? Surely you are just misunderstanding. Since Y is finite, its cardinality is some positive integer, say n. Prove this statement by induction on n.

If n= 1, that means that Y contains exactly one member, call it "y". There exist some function from X such that f(x)= y for all x in X. Can you find a function from Y to X, s(y) such that f(s(y))= y? That should be pretty easy.

Now, suppose that statement is true when y contains n members and prove that it is true and prove it is true when Y contains n+1 members. (Hint: remove a specific one of the members of Y.)
 
Last edited by a moderator:
  • #3
169
0
Ah, thank you, yes I was misunderstanding. I do know proof by induction yes, but 'over the cardinality of Y' was a weird statement to me. This clears things up, I should be fine now.
 

Related Threads on Finite Axiom of Choice

  • Last Post
Replies
3
Views
2K
Replies
0
Views
1K
  • Last Post
Replies
5
Views
808
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
24
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
8
Views
1K
  • Last Post
Replies
8
Views
1K
Top