Register

Kenneth Rosen, exercise: 6.2, question: 8

279 views
0 votes
0 votes
Show that if f is a function from S to T , where S and T are finite sets with |S| > |T |, then there are elements s1 and s2 in S such that f (s1) = f (s2), or in other words, f is not one-to-one.

How can I prove it by using “proof by contradiction”?

Is it possible to prove the same by using “proof by contraposition”? If yes, how?
User Avatar

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
0 answers
2
admin asked Apr 29, 2020
320 views
Kenneth Rosen Edition 7 Exercise 6.2 Question 47 (Page No. 407)
An alternative proof of Theorem $3$ ... there is no increasing subsequence of length $n + 1,$ then there must be a decreasing subsequence of this length.
An alternative proof of Theorem $3$ based on the generalized pigeonhole principle is outlined in this exercise. The notation used is the same as that used in the proof in...
User Avatar
0 votes
0 votes
0 answers
3
admin asked Apr 29, 2020
276 views
Kenneth Rosen Edition 7 Exercise 6.2 Question 46 (Page No. 407)
Let $n_{1}, n_{2},\dots,n_{t}$ be positive integers. Show that if $n_{1} + n_{2} +\dots + n_{t} − t + 1$ objects are placed into $t$ boxes, then for some $i, i = 1, 2,\dots,t,$ the $i^{\text{th}}$ box contains at least $n_{i}$ objects.
Let $n_{1}, n_{2},\dots,n_{t}$ be positive integers. Show that if $n_{1} + n_{2} +\dots + n_{t} − t + 1$ objects are placed into $t$ boxes, then for some $i, i = 1, 2,\...
User Avatar
0 votes
0 votes
1 answer
4
admin asked Apr 29, 2020
430 views
Kenneth Rosen Edition 7 Exercise 6.2 Question 45 (Page No. 407)
Let $x$ be an irrational number. Show that for some positive integer $j$ not exceeding the positive integer $n,$ the absolute value of the difference between $j x$ and the nearest integer to $j x$ is less than $1/n.$
Let $x$ be an irrational number. Show that for some positive integer $j$ not exceeding the positive integer $n,$ the absolute value of the difference between $j x$ and th...
User Avatar
Link Copied!