2.Suppose that f is a function from A to B, where a and B are finite sets with |A| = |B|. Show that f is one-to –one if and only if it is onto.

lilyba(Sunshine)

Let n = |A|. Thus A = {x1,x2,x3, ¼,xn}, where all elements are distinct.

Assume that f is a one-to-one function. Then for any integer j we have f(xi) ¹ f(xj) whenever 0 £ i < j. This implies that |{f(x1),f(x2),f(x3), ¼,f(xn)}| = n. Since {f(x1),f(x2),f(x3), ¼,f(xn)} Í B and |{f(x1),f(x2),f(x3), ¼,f(xn)}| = |B|, we can conclude that the range of f is B. Therefore, f is an onto function. Assume now that f is onto but it is not a one-to-one function. Then there exist integers i ¹ j such that f(xi) = f(xj). Thus, |{f(x1),f(x2),f(x3), ¼,f(xn)}| < n and since |B| = n, there must be an element of B so that no element of A is mapped on it by f. Thus, f is not onto, a contradiction.

(#779124@0)
Last Updated: 2002-10-3
This post has been archived. It cannot be replied.

要在上学期我就能帮你做了，现在书都卖了，也忘的差不多了。什么时候交？晚几天倒是能做出来。帮你UP吧。 -heian(黑暗®-谢幕中); 2002-10-2 (#778950@0)

明天早上:(( -rainrain(雨雨秋风何故乱翻书); 2002-10-3 (#778960@0)

真同情..... :-D -lazycod(飞鹰战士); 2002-10-3 (#778963@0)

虽然知道自己学过但肯定不会做了，但还是忍不住进来看看，不看不知道 -oceandeep(北极熊® Zzz Zzz); 2002-10-3 {58} (#778965@0)

一看才知道，自己题目也看不懂，咳，我这英文该回去还给老师了

不管怎么说，谢谢好心肠的MM~~~ -rainrain(雨雨秋风何故乱翻书); 2002-10-3 (#778970@0)

你不能这么害我啊，我不能帮你，你也不能把我变性了：（（（（（（（（ -oceandeep(北极熊® Zzz Zzz); 2002-10-3 (#779049@0)

what's the meaning of "f o g" in 1st question ? -mildkiller(M.K.); 2002-10-3 (#778977@0)

复合函数 f（g(x)) -rainrain(雨雨秋风何故乱翻书); 2002-10-3 (#778981@0)

可惜俺E文不行，不知道怎么讲～～～给你一个中文参考。§8 部分 -mildkiller(M.K.); 2002-10-3 (#779030@0)

俺对概念还是有点明白的。就是俺对函数从小就怕，尤其是证明这个那个，长大了学完了以为再也不要了，结果现在还是要学，命真苦呀:((( -rainrain(雨雨秋风何故乱翻书); 2002-10-3 (#779042@0)

套用一下定义定理就好呀 -mildkiller(M.K.); 2002-10-3 (#779045@0)

大学时就离散数学枯燥无味难学，考试时有十几个人booking俺周围的位子，其中包括几位恐龙mm。俺掂量再三，小心地选择了6个mm(锉子里头拔高个),2个gg(因为他们是我打勾级时的联邦)，结果，kao -andy2060(胖胖猴-香水boy); 2002-10-3 {163} (#778993@0)

有一个mm的成绩比我还高。原来，她收集了3份答案，少数服从多数，择优选择。
不过，现在那点底都丢到爪哇国了，连题都看不懂了，惨！
>
>
>
>
>
>
我是说雨雨mm好惨！

想起了那个笑话，说一个学生用掷骰子/硬币的办法做选择题，每一题都多掷好几遍，老师问他为什么，他回答是 -hzgxy(edonkey使用ing); 2002-10-3 {16} (#779019@0)
我总得验算一次啊

You owe me big time -jeffrey815(Smartiecat); 2002-10-3 {747} (#779006@0)

1.
The following makes assumption that f and g are both linear......

f o g (v) = f(g(v))

if f(g(v)) is one to one
>> f(g(v)) = 0 if g(v) = 0 and there is only 1 v such that g(v) = 0
>> v = 0 only.
Therefore, g is one-to-one because g(v) = 0 iff v=0

2.
This is actually a corollary. Again, the assumption is f is liinear.

if f is one-to-one
>> ker(f) = {0}
>> Nullity(f) + Rank(f) = dim(A)
>> Rank(f) = dim(A) = dim(B)
>> Range(f) is a subset of A with the same dimension.
>> Range(f) = B
>> we prove if it's one-to-one, then it's onto

if f is onto
>>Range(f) = B
>>Rank(f) = dim(B)
>>Nullity(f) + dim(B) = dim(A) = dim(B)
>>Nullity(f) = 0. ie. ker(f) = {0}
>>f is one-to-one

Hence, this prove if and only if.

"f(g(v)) = 0 if g(v) = 0" ? -heian(黑暗®-谢幕中); 2002-10-3 (#779024@0)

Did you even read the question? It's given f is one to one. -jeffrey815(Smartiecat); 2002-10-3 (#779032@0)

"function such that each element of the range has a unique preimage are called one-to-one" this is df. of one-to-one. It's impossible to get "f(g(v)) = 0 if g(v) = 0 " by assume "v=0". -heian(黑暗®-谢幕中); 2002-10-3 (#779055@0)
c/m:f(x) = x + 1, g(x)=x, x=0 g(x)=0, f(g(0))=1 -heian(黑暗®-谢幕中); 2002-10-3 (#779058@0)

yo....just to refresh your memory....we are talking about vector spaces...1 could be 0 vector under a vector space... ok?? -jeffrey815(Smartiecat); 2002-10-3 (#779059@0)

....right....but still think your pf. has problem...sigh, forget almost of math, don't like those courses. -heian(黑暗®-谢幕中); 2002-10-3 (#779065@0)

I took them 2 terms ago and forgot all of them as well.. copied straight out from my notes. -jeffrey815(Smartiecat); 2002-10-3 (#779071@0)

suggest rainrain directly uses your ans, let's wait and see if it's right :P...if it's same question as your notes, maybe I am wrong...but I think there should be another way to proof that..... -heian(黑暗®-谢幕中); 2002-10-3 (#779078@0)

I made a comment below...... My proof is about map and transformation of vector spaces. But her questions are about discrete mathematics, maybe it's the same. -jeffrey815(Smartiecat); 2002-10-3 (#779081@0)
The whole thing is like this if you are not convinced this is right under linear algebra. -jeffrey815(Smartiecat); 2002-10-3 {369} (#779084@0)
Suppose L: V --> W is a linear map and V and W are vector spaces.

Because it's linear, then there exists.
L(0v) = 0w where 0v is the zero vector under vector space V
0w is the zero vector under vector space W
This is a property of linear map....

We are given L is one to one....

Therefore, 0v is the only solution.....

I got rainrain's questions from my friend's discrete math textbook, it doesn't use such algebra way to solve...just few sentense... -heian(黑暗®-谢幕中); 2002-10-3 (#779096@0)

okee.. -jeffrey815(Smartiecat); 2002-10-3 (#779101@0)

Isn't this called Linear Algebra? 线性代数？Instead of 离散数学? -jeffrey815(Smartiecat); 2002-10-3 (#779008@0)

should be linear algebra -heian(黑暗®-谢幕中); 2002-10-3 (#779027@0)
thanks, many thanks, it's discrete math. -rainrain(雨雨秋风何故乱翻书); 2002-10-3 {199} (#779037@0)
还有一个f is a function from A to B, let S and T be the subsets of B. Show that f -1(S U T) = f -1(S) U f-1 (T)
f-1是说的逆函数，俺不会打那个小-1 :(

俺无以为报，俺只能在任何话题上无条件支持你:(

Sorry. can't find it in my note. -jeffrey815(Smartiecat); 2002-10-3 (#779073@0)

我真同情你. 实在不行,找个同学问问吧. -fox69(fox); 2002-10-3 (#779012@0)

Ok... I have to remind you that proof I gave you is valid under Linear Algebra where we are dealing vector spaces and different type of maps. I'm not sure whether it's the same under discrete mathematics. -jeffrey815(Smartiecat); 2002-10-3 (#779064@0)

1.If f and f o g are one-to-one, does it follow that g is one-to-one? Justify your answer. -lilyba(Sunshine); 2002-10-3 {468} (#779105@0)

Here, we assume that G is a function from some set A to another set B, while F is a function from B to some set C. Consider two distinct points, a,a' of A. Since F o G is one-to-one, we know that c= F(G(a)) is distinct from c' = F(G(a')). Of course the only way that this could happen is if G(a) is distinct from G(a'), i.e. just think about it if they were the same. Since a and a' is an arbitrary pair of distinct elements of A, this shows that G is one-to-one.

Long time no see...How's the weather in Edmonton? We have a record high in southern Ontario...28 degree yesterday and today... crazy!!! -jeffrey815(Smartiecat); 2002-10-3 (#779111@0)

嘿嘿，看看我的答案对不对。题目反正是对的。我们这里现在早晨只有3度。不过屋里很暖和。 -lilyba(Sunshine); 2002-10-3 (#779114@0)

I don't know ar... I thought her question is about linear algebra since I didn't know 离散数学 is discrete math....... I haven't and won't be taking any discrete math in my life.... -jeffrey815(Smartiecat); 2002-10-3 (#779131@0)

2.Suppose that f is a function from A to B, where a and B are finite sets with |A| = |B|. Show that f is one-to –one if and only if it is onto. -lilyba(Sunshine); 2002-10-3 {744} (#779124@0)
Let n = |A|. Thus A = {x1,x2,x3, ¼,xn}, where all elements are distinct.

Assume that f is a one-to-one function. Then for any integer j we have f(xi) ¹ f(xj) whenever 0 £ i < j. This implies that |{f(x1),f(x2),f(x3), ¼,f(xn)}| = n. Since {f(x1),f(x2),f(x3), ¼,f(xn)} Í B and |{f(x1),f(x2),f(x3), ¼,f(xn)}| = |B|, we can conclude that the range of f is B. Therefore, f is an onto function. Assume now that f is onto but it is not a one-to-one function. Then there exist integers i ¹ j such that f(xi) = f(xj). Thus, |{f(x1),f(x2),f(x3), ¼,f(xn)}| < n and since |B| = n, there must be an element of B so that no element of A is mapped on it by f. Thus, f is not onto, a contradiction.

@Calgary

2.Suppose that f is a function from A to B, where a and B are finite sets with |A| = |B|. Show that f is one-to –one if and only if it is onto.

Replies, comments and Discussions:

More Topics