General results

Theorem 31 (Klein): If X and Y are different sets, and Y is a subset of X, then there is a function from Y into X whose range is X.

Proof:

Let X={1,2,3} and Y={1,3}
X and Y are both different sets and Y is a subset of X.

The Cartesian Product of X and Y is X x Y={1,3}x{1,2,3}={(1,1),(1,2),(1,3),(3,1),(3,2),(3,3)}

From the Cartesian Product and the Function definition, there are 9 possible functions. They are:

f={(1,1),(3,1)} or {(1,1),(3,2)} or {(1,1),(3,3)} or {(1,2),(3,1)} or {(1,2),(3,2)} or {(1,2),(3,3)} or {(1,3),(3,1)} or {(1,3),(3,2)} or {(1,3),(3,3)}

By inspection we see that the ranges of these functions are: {1} or {1,2} or {1,3} or {2} or {2,3} or {3}

None of these ranges equals the set X, therefore the theorem is false.

QED

"Instead of having "answers" on a math test, they should just call
them "impressions," and if you got a different "impression," so what,
can't we all be brothers?"

Theorem 35 (Paul): If X is a set, then X is the same size as X.

Proof:
Let X be a set.
For this statement to be true, there must be a one-to-one function from X onto X. I propose that the function f = {(x,x):x is an element of X} satisfies this requirement. I must first show that f satisifes the three parts of the definition of a function:
a) f must be a subset of X x X
b) if x is an element of X, there must be a coordinate pair in f such that the first coordinate is x
and
c) if (a,b) is in f and (a,c) is in f then b=c.

X x X = {(x,y):x is in X and y is in X, but x does not have to equal y}. By definition, f is a subset of X x X because every element of f is in X x X because the first coordinate of every element of f is in X and the second coordinate of every element of f is also in X.
Let x be an element of X. There is a coordinate pair (x,x) in f. Because this is true for every element x in X, f satisfies the second part of the definition of a function.
Let (a,b) and (a,c) be elements of f. By the definition of f, a=b and a=c. Therefore, by the transitive property, b=c.

Now that I've proven f is a function I must prove that it is one-to-one and onto.
To prove that f is one-to-one, I must show that if (a,c) is an element of f and (b,c) is an element of f, then a=b. To prove that f is onto, I must show that the range of f is X.

Let (a,c) and (b,c) be elements of f. By the definition of f, a=c and b=c. By the transitive property, a=b. Therefore, f is one-to-one.
The range of f is defined as {p:there is an element of f whose second coordinate is p}. By the definition of f, the range of f is {x:x is an element of X}, which is equal to X. Therefore, f is onto.

Because f(x)=x is a one-to-one function from X onto X, X is the same size as X.

QED

Problem #28 (Brennan Baffer)
If X and Y are sets and f is a function from X into Y, then the range of f is a subset of the codomain of f.

True

Proof:
If there exists an element p in the range of f and p is also in the codomain of f, then the range of f is a subset of the codomain of f.

Let X be a set and Y be a set.
Let f be a function from X into Y.
Let p be the element of the range of f.

Then the cartesian product of X with Y is the set {(p,q):p is an element of X and q is an element of Y}.
Since f must be a subset of the cartesian product of X with Y, the second coordinate of an ordered pair in f is an element of Y which is the codomain of f. Since p is in the range of f and p is in the codomain of f, the range of f is a subset of the codomain of f.

QED

page revision: 9, last edited: 29 Mar 2010 02:54