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

Show there exists a one to one function from N to S iff function f exists

  • Thread starter h.shin
  • Start date
  • #1
7
0

Homework Statement


Show that for a set S, there exists an injective function [itex]\Phi[/itex] :
N [itex]\rightarrow[/itex] S if and only if there exists an injective, but non-surjective
function f : S [itex]\rightarrow[/itex] S. (Sets S satisfying this condition are called
in nite sets.)


Homework Equations





The Attempt at a Solution


Since this is a if and only if (biconditional) statement.
I can prove this statement if i can prove the two conditional statements:
i) If [itex]\Phi: N \rightarrow S[/itex] is injective then f: S [itex]\rightarrow[/itex] S is injective but not surjective
ii)If f: S [itex]\rightarrow[/itex] S is injective but not surjective then [itex]\Phi: N \rightarrow S[/itex] is injective.

I realize that this is the step that i should take, but i just don't know how to prove these two statements..
Any help?
 

Answers and Replies

  • #2
Dick
Science Advisor
Homework Helper
26,258
618
Take them one at a time. If you have phi:N->S is injective, you want to prove there is a function f:S->S that's injective but not surjective. You probably want to define f in terms of phi. Can you think of a function from N->N that's injective but not surjective?
 
  • #3
7
0
Take them one at a time. If you have phi:N->S is injective, you want to prove there is a function f:S->S that's injective but not surjective. You probably want to define f in terms of phi. Can you think of a function from N->N that's injective but not surjective?
yes, well
n--->2n is injective but not surjective
 
  • #4
Dick
Science Advisor
Homework Helper
26,258
618
yes, well
n--->2n is injective but not surjective
Ok, so phi(n) is an element of S for all n in N. Define f(s)=phi(2n) for all of those elements of S. What's an easy way to define f(s) if s isn't in phi(N)?
 

Related Threads on Show there exists a one to one function from N to S iff function f exists

Replies
0
Views
2K
Replies
11
Views
1K
Replies
25
Views
2K
  • Last Post
Replies
5
Views
2K
Replies
5
Views
2K
  • Last Post
Replies
3
Views
1K
Replies
7
Views
1K
Replies
2
Views
2K
Replies
7
Views
4K
Top