Injective, Surjective, Bijective FunctionsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/