Sets, Injection, and SurjectionsDate: 12/04/98 at 12:01:57 From: Philip McSweeney Subject: Definition of an infinite set using functions Hi, I have a question regarding the definition of an infinite set. It uses the definition of two types of functions - an injective function and a surjective function. Definitions: 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. A set S is an infinite set if there exists a function A from S to S which is an injection but not a surjection. Now I have no problems with any of these definitions or their applications in general, but I have been wondering about some of their implications. Recently I asked myself "If S is an infinite set, does there exist a surjective function from S to S which is not an injection?" I have answered this question in the affirmative but it has led me to a much more intractable problem: "If S is a set, such that every injection A from S to S is also a surjection, does S have the property that every surjection A from S to S is also an injection?" This is a really puzzling question, and I must admit that it is one in which I have no idea of how to proceed. Any help on the matter would be greatly appreciated. Thanks. Date: 12/04/98 at 14:55:21 From: Doctor Rob Subject: Re: definition of an infinite set using functions Your conjecture is true. First, the set S must be finite. Let its size be n = #S. Then a function from S to S is an injection if and only if it is a surjection. Proof: Let f be a surjection. Then the domain and range of f are all of S. Let x be in S, and y be such that f(y) = x. Suppose that there was a z in S different than y with f(z) = f(y) = x. Then the number of elements in the range of f would be at most n-1, a contradiction. Thus f is an injection. Now let f be an injection. Since there are n elements in the domain, and each goes to a unique element of the range, the range also contains n elements. But the range is contained in S, which contains n elements, so it must be the whole of S. Thus f is a surjection. - 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/