Math Is Fun Forum

TheMathsDude

Member

Registered: 2008-01-16

Posts: 3

Bijection

Completely stuck with this one. Don't know where to start. Could anybdoy provide an explanation and perhaps some examples as to how to tackle this problem please.

Many Thanks,
TheMathsDude

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Bijection

To show that something is a bijection, you must show it is an injection (1 to 1) and a surjection (onto).  This may be done by the following:

A map is an injection means that if f(x) = f(y), then x = y.
A map is a surjection means that for all y in the range, there exists an x such that f(x) = y.

For example, prove that f: Z->Z defined by f(x) = x^2 is neither an injection nor a surjection.

Proof: Let y = -1.  Then there is certainly no x in Z such that f(x) = x^2 = -1.  Thus, f can't be a surjection.  To see that f is not an injection, consider f(2) and f(-2).  f(2) = 2^2 = 4 and f(-2) = (-2)^2 = 4.  Thus, f(2) = f(-2), but 2 does not equal -2.

Prove that f : R->R defined by f(x) = ax + b for some fixed a (nonzero) and b is a bijection.

Proof: Let f(x) = f(y).  We will show x = y.  Since f(x) = f(y), it must be that ax + b = ay + b.  Thus, ax = ay, and hence, x = y.  Now we shall show that it is surjective.  Let y be any real number.  Certainly (y-b) / a is a real number, and thus, in the domain of f.  Also, f((y-b)/a) = a((y-b)/a) + b = (y-b) + b = y.  Thus, for all y in the range, there exists an x in the domain such that f(x) = y.  So f is surjective.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Bijection

Ricky, do you realize that the conventional textbook method of proving bijection doesn’t quite work out for this particular problem?

Last edited by JaneFairfax (2008-01-16 12:29:37)

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Bijection

Given any

, we have

.

Notice that

is the sum of all the integers from 0 to

. Thus

represents the sequence of triangular numbers

. (Note that this is a strictly increasing sequence.)

Note also that

. Hence all the integers in the gap between two successive triangular numbers

and

(exclusive of the former but inclusive of the latter) can be obtained from

by letting i range from 1 to k−1.

So, given any natural number n, take k such that T[sub]k[/sub] is the maximum triangular number (strictly) less than n. Such a T[sub]k[/sub] always exist, for

(i)

(ii) if

, then (a) if

,

, and (b) if

,

Furthermore, suppose

and

(where k ≥ k′). Then

and

and

. Thus we must have

for if

, the difference

would have to be at least

.

And so we end up with this: given any natural number n we have a unique representation of it as

where, since

, we have

.

This seems a rather strange way of showing that a function is a bijection – but this is normally what to expect when you’re dealing with bijections between a countable set and a Cartesian product of countable sets.

Last edited by JaneFairfax (2008-01-16 12:18:36)