Sets, Injection, and Surjections

Date: 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/