Thread: How can you proof this?

Okey hi!
I have a question. I have to prove that:
g has bijectivity <-> g has injectivity <-> g has surjetivity.

I know that the map is g: X -> Y. X and Y are both finite sets, and you know that the cardinality of X is the same as the cardinality of Y.

How do you proof this statement?
I don't know how to start, what to do, what to use...

Thanks for any help!
Mary

Originally Posted by MaryB

Okey hi!
I have a question. I have to prove that:
g has bijectivity <-> g has injectivity <-> g has surjetivity.

I know that the map is g: X -> Y. X and Y are both finite sets, and you know that the cardinality of X is the same as the cardinality of Y.

How do you proof this statement?
I don't know how to start, what to do, what to use...

Actually I have no idea what you are asking.
A mapping is a bijection if and only if it is both injective and surjective.

Now what is the exact statement of the question you have been given?

Originally Posted by Plato

Actually I have no idea what you are asking.
A mapping is a bijection if and only if it is both injective and surjective.

Now what is the exact statement of the question you have been given?

I think the question is the following: If X and Y are both finite and have the same cardinality, i.e. |X|=|Y|, then g:X->Y is bijective if and only if it is injective (and if and only if it is surjective).
So, under these particular assumptions (X,Y finite and of the same cardinality) being bijective, being injective, and being surjective are all equivalent. It sounds true, doesn't it?
Now to prove this I suggest showing, first, that from g:X->Y being injective it follows that g is also surjective, and, second, that from g being surjective it follows that g ia also injective. (Under the given assumptions, the first statement follows, because the image of X under g is a subset of the finite set Y, is contained in Y, and has the same number of elements as Y. The second statement follows, because if g is surjective and X and Y have the same cardinality, it is not possible that the inverse image of some element of Y contains more than one element of X, because otherwise the cardinality of the image of X under g would be less than the cardinality of Y, contradicting the assumed surjectivity of g.)

Originally Posted by MaryB

Okey hi!
I have a question. I have to prove that:
g has bijectivity <-> g has injectivity <-> g has surjetivity.

I know that the map is g: X -> Y. X and Y are both finite sets, and you know that the cardinality of X is the same as the cardinality of Y.

How do you proof this statement?
I don't know how to start, what to do, what to use...

Thanks for any help!
Mary

If X and Y have both finite cardinality and |X|=|Y| this is true. Note that the way you stated your questions is backwards, you should of said, let g be a map g:X->Y where X and Y have finite (and same) cardinality, then ....


But anyhow, the standard trick to proving this is based on the pigeon hole principle.

I'm going to label the statements in your proof:

1<=> 2<=> 3
g has bijectivity <=> g has injectivity <=> g has surjetivity.


It suffices to show 2 => 3 and 3=>2 because by definition (2 and 3) <=> 1

Let

So suppose that g is injective. Now in order to come to a contradiction suppose that g is not surjective. Then there exists a such that . This means that which means by the pigeon hole principle there exist such that and which contradicts injectivity.


For the other direction, suppose that g is surjective. Then and furthermore . Suppose that g is not injective. Then a contradiction.

I have questions for both Failure & gmatt.
The original question is so garbled, how do you read it?
It is clearly about finite sets.
But you don’t which of the two standard definitions of finite is being used.
Some texts say that a set is finite if it bijects with for some positive integer .
If that is the case then this is a trivial question.

On the other hand, the second way to define finite set is to say that ‘A set is finite if it is not infinite’.
This is often called Dedekind finite. A set is Dedekind infinite if it bijects with a proper subset of itself.

Now unless you know the setting of the question, I think it is hard to give a correct answer.

Originally Posted by Plato

I have questions for both Failure & gmatt.
The original question is so garbled, how do you read it?

Call it "instinct", or rather "searching for a charitable interpretation of the question". Also, you get plenty of exercise decoding garbled language in everyday life (outside the context of studying and discussing mathematics).

It is clearly about finite sets.
But you don’t which of the two standard definitions of finite is being used.
Some texts say that a set is finite if it bijects with for some positive integer .
If that is the case then this is a trivial question.

On the other hand, the second way to define finite set is to say that ‘A set is finite if it is not infinite’.
This is often called Dedekind finite. A set is Dedekind infinite if it bijects with a proper subset of itself.

If you know for a certainty (preferably with a proof) that these two definitions of "finite" are equivalent, then using Dedekind's definition of "finite" would not be any more problematic. - If, on the other hand, you don't know whether these two definitions are equivalent, then you have a problem at hand that is perhaps more difficult to solve than the exercise itself (after you have solved the primary problem of showing the two definitions to be equivalent).

Now unless you know the setting of the question, I think it is hard to give a correct answer.

I tend to follow Yogi Berra's advice: "When you come to a fork in the road, take it."
So if I have the option of choosing a (quite common) definition of finite (originally given by Bertrand Russell, I believe), that makes the exercise trivial to solve: I'll choose that definition, of course.

Sorry to read that I caused so much troubles!
But I can´t help it, the assignments I get are like this, I can´t make it any easier or better to read.

`Proof the following: a map g has bijectivity iff g has injectivity iff g has surjectivity. Map g is defined g: X -> Y.
X and Y are both finite sets, and you know that X and Y have the same cardinality.'

This is what it says...

Mary

Originally Posted by Plato

On the other hand, the second way to define finite set is to say that ‘A set is finite if it is not infinite’.
This is often called Dedekind finite. A set is Dedekind infinite if it bijects with a proper subset of itself.

To show that a proof of the statement is not any less "trivial" for Dedekind's definition of "finite", let me show that g injective implies g surjective, and that g surjective implies g injective (assuming the axiom of choice).

Since we are told that X and Y have the same cardinality, we are allowed to assume that a bijective mapping b:X->Y of X onto Y exists.

Proof of g injective g surjective: (indirect) assume g were not surjective, then the inverse of g restricted to the image of X under g, combined with b would give a bijective mapping of Y onto a proper subset of itself, contradicting the (Dedekind) finiteness of Y.

Proof of g surjective g injective: (indirect) if g is surjective then, by the axiom of choice, there exists a mapping g* that maps every y of Y to a single x of the inverse image of y under g. If g were not injective, then the combination of g with g* would yield a bijective mapping of a proper subset of X onto X, contradicting the (Dedekind) finiteness of X.

Edit: Come to think of it: talk of the axiom of choice, in the context of finite sets, is a bit of overkill here. However, if you are not shy about the axiom of choice, there is no problem. - I suppose, someone using Dedekind's definition of finiteness is likely not to be shy about the axiom of choice.

Originally Posted by Failure

To show that a proof of the statement is not any less "trivial" for Dedekind's definition of "finite", let me show that g injective implies g surjective, and that g surjective implies g injective (assuming the axiom of choice).

Since we are told that X and Y have the same cardinality, we are allowed to assume that a bijective mapping b:X->Y of X onto Y exists.

Proof of g injective g surjective: (indirect) assume g were not surjective, then the inverse of g restricted to the image of X under g, combined with b would give a bijective mapping of Y onto a proper subset of itself, contradicting the (Dedekind) finiteness of Y.

Proof of g surjective g injective: (indirect) if g is surjective then, by the axiom of choice, there exists a mapping g* that maps every y of Y to a single x of the inverse image of y under g. If g were not injective, then the combination of g with g* would yield a bijective mapping of a proper subset of X onto X, contradicting the (Dedekind) finiteness of X.

Edit: Come to think of it: talk of the axiom of choice, in the context of finite sets, is a bit of overkill here. However, if you are not shy about the axiom of choice, there is no problem. - I suppose, someone using Dedekind's definition of finiteness is likely not to be shy about the axiom of choice.

Please be kind to the old dog trying to learn new tricks!?

I find this fascinating, and we've just covered similar material in my class.

I follow everything up to where you combine the inverse of g with b to get a bijective map of Y to a proper subset of itself. Since g is not necessarily a bijective map, how does it follow that you get a bijective map of Y to a proper subset of itself?

Thanks

Originally Posted by oldguynewstudent

Please be kind to the old dog trying to learn new tricks!?

I find this fascinating, and we've just covered similar material in my class.

I follow everything up to where you combine the inverse of g with b to get a bijective map of Y to a proper subset of itself. Since g is not necessarily a bijective map, how does it follow that you get a bijective map of Y to a proper subset of itself?

Thanks

Well, assuming g: X->Y is injective, then g: X->g(X) is a bijective mapping of X onto the subset g(X) of Y, where g(X) is the image of X under g. If g were not surjective, then g(X) would be a proper subset of Y. Now you can use the inverse of g to map g(X) bijectively onto X and then map X bijectively onto Y, using the bijective mapping b: X->Y that we are allowed to assume exists, because we are told that |X|=|Y| holds. Thus, the bijective map h:g(X)->Y, defined as would do the job of mapping a proper subset of Y, namely g(X), onto Y. But since we are told that Y is (Dedekind) finite, this is a contradiction.