Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search