• Support PF! Buy your school textbooks, materials and every day products Here!

Finite Sets

  • Thread starter moo5003
  • Start date
  • #1
207
0
1. Homework Statement

Assume that A is finite and f: A->A. If f is onto then f is one-to-one

2. The attempt at a solution

f[A] = A
Card(A) = n a natural number.

I assume I need to use the axiom of choice since this equivalence only holds if you use it (correct?).

My proof so far is supposing that its not injective, then there would exist a_1, a_2, a_3..., a_k such that f(a_1)=f(a_2)...=f(a_k) = C in A.

Thus, f[A\{a_2, a_3, a_4.., a_k}] = A

I want to somehow keep reducing this until f is known to be injective and then show that there is a bijection between a proper subset of A and A itself thus leading to a contradiction. My only concern is that I'm not sure how to show with rigor these steps. Most notably how to construct a proper subset A such that f is one to one and onto A.
 

Answers and Replies

  • #2
morphism
Science Advisor
Homework Helper
2,013
4
You don't need the axiom of choice. The fundamental property here is the finiteness of A.
 
  • #3
207
0
Suppose f is onto.

Suppose by contradiction f is not injective.

Let g be a proper subset of f such that g is one-to-one and onto A. Since f was not injective this implies g is a proper subset of f and the domain of g = B is a proper subset of A.

Thus:
f[A]=A onto not injective
g=A bijection

This implies card(B) = card(A) which is a contradiction since A is finite and B is a proper subset of A implying card(B) < card(A)

Is there anything wrong with this?
 
Last edited:

Related Threads for: Finite Sets

  • Last Post
Replies
7
Views
1K
  • Last Post
Replies
3
Views
3K
Replies
1
Views
338
Replies
8
Views
3K
  • Last Post
Replies
3
Views
1K
Replies
17
Views
6K
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
15
Views
3K
Top