Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Injective, Surjective, Bijective Functions


Date: 01/23/2001 at 00:19:58
From: David H.
Subject: Definitions of injective, surjective, bijective functions

Hi there, you fine math folks!

I would be most obliged if perhaps you could provide me with the 
definitions of the terms injective, surjective, and bijective as they 
apply to functions in set theory.  

I have tried looking them up, but all definitions I have seen seem to 
contradict one another.  For example, in an archived question, (see 

Sets, Injection, and Surjections
http://mathforum.org/dr.math/problems/mcsweeney12.4.98.html    ) 

someone stated the following:

"If we have a non-empty set S, an injective function F from S to S is 
defined such that no element of S appears more than once as the 
second component of an ordered pair.

A surjective function on the same set S (ie from S to S) is one where 
each element appears as the second component of at most one ordered 
pair."

It seems to me that "no element appears more than once" is the exact 
same statement as "each element appears at most once."  Where is the 
difference?  

As for bijectivity, I know not what to think.  The Internet isn't 
being too helpful with this one.

Any enlightenment would be most welcome.
Many thanks again for your time.

Dave


Date: 01/23/2001 at 10:57:17
From: Doctor Rob
Subject: Re: Definitions of injective, surjective, bijective functions

Thanks for writing to Ask Dr. Math, Dave.

Perhaps it would be clearer in terms of the f(x) notation.  Let S
and T be nonempty sets.

f:S -> T is an injective function if f(s1) = f(s2) implies s1 = s2.
(This is often called a "one-to-one" function.)

f is a surjective function if for all t in T, there is an s in S
such that f(s) = t.  (This is often called an "onto" function.)

f is a bijective function if it is both injective and surjective.
(This is often called a "one-to-one correspondence".)

The difference between the definitions you found is not in the two
phrases you picked out, which are, indeed, synonymous.  It is,
instead, in the parts immediately preceding them.  Let me rephrase
them to see what I mean.

A function f:S -> T can be thought of as the set of all ordered
pairs F = {(s,f[s]): s in S}, which is a subset of S x T.  (This
set F is often called the graph of f.)  It is a function if and
only if each element s in S appears exactly once as the first
component of an ordered pair in F.

An injective function f is one such that every element of T
appears at most once as the second component of an ordered pair
in F.

A surjective function f is one such that every element of T
appears at least once as the second component of an ordered pair
in F.

A bijective function f is one such that every element of T
appears exactly once as the second component of an ordered pair
in F.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/   
    
Associated Topics:
High School Sets

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/