4

I'm doing some practice problems and am having trouble answering these problems:

Prove or disprove each statement.

(a) If $f : A \rightarrow A$ is one-to-one, then $f$ is onto.

(b) If $A$ is finite and $f : A \rightarrow A$ is one-to-one, then f is onto.

(c) If $f : A \rightarrow A$ is $f$ is onto, then $f$ is one-to-one.

(d) If $A$ is finite and $f : A \rightarrow A$ is $f$ is onto, then $f$ is one-to-one

I know that for a function to be one-to-one there can't be two distinct elements in the domain that map to the same element in the codomain. Also that a function is onto if every element in the codomain has a pre-image in the domain (or in other words every element in the codomain must be mapped to an element in the domain).

Pictorially what I mean is this: enter image description here

So for my problem: In part a) I believe that just because a function is one-to-one it does not necessarily have to be onto as can be seen from the diagram.

But then I feel like you can use the same logic to disprove all of them, which I'm not sure it correct. (maybe the finite ones are true?)

Any help with these problems would be appreciated.

TheDifficultyOfAlgortihms
  • 125
  • 2
  • 11
  • 1
    It will be important to notice that in the pictures, the map goes from $X$ to $Y$; i.e. they are different sets, and in particular, they have a different number of elements. Your questions, on the other hand, regard a function from $A$ to $A$ (i.e. the same set in both cases). – BaronVT Nov 13 '13 at 20:02
  • Note that in your exercise, the functions map a set $A$ to itself, so the pictures are a bit misleading. – Sammy Black Nov 13 '13 at 20:02
  • Hint: Part (b) only differs from (a) in that you may assume that the set $A$ is finite. Therefore, you might consider an infinite set in order to find a counterexample in (a). – Sammy Black Nov 13 '13 at 20:04
  • 1
    I was just simply showing what I meant by ono-to-one and onto through the pictures. I see what you mean. Sorry if I caused confusion. – TheDifficultyOfAlgortihms Nov 13 '13 at 20:04
  • Also, the hint applies mutatis mutandis to parts (c) and (d). – Sammy Black Nov 13 '13 at 20:05
  • @user98289 Nothing to be sorry about! In fact, quite the contrary; you explained your thinking well enough that several of us were able to quickly determine the source of your confusion. Good work. – BaronVT Nov 13 '13 at 20:08
  • You are doing fine. Just continue. – Mhenni Benghorbal Nov 13 '13 at 20:08

1 Answers1

2

In the infinite case, part a can be false: For example, the map $f:\mathbb{N} \rightarrow \mathbb{N}$ defined by $f(n) = 2n$ is injective, but not onto.

But, in the finite case, we cannot do this. This is the pigeon hole principle.

parts c and d are of a similar concept.

(Think perhaps of mapping 1 and 2 to the same thing, then everything else to a natural number one less than it.)

Vladhagen
  • 4,878
  • My examples are all over the natural numbers by the way. – Vladhagen Nov 13 '13 at 20:09
  • That's fine I'm using natural numbers as well. So would the finite case be true? I'm trying to consider the pigeon hole principle, however wouldn't that make at least part d false since that would mean at least one element from the codomain would map to an element of the domain which has already been mapped to by another element from the codomain and therefore it cannot possibly be one-to-one or am I thinking about this wrong? – TheDifficultyOfAlgortihms Nov 13 '13 at 20:18
  • In the finite case, say we have 10 things in our set (or however many finite elements you want.) Each thing in the codomain can be mapped to by at most one thing. Well, all ten things in our domain must map to something. This leaves us with no option but to map each thing in the domain to exactly one thing in the codomain. This gives us that our function is onto. – Vladhagen Nov 13 '13 at 20:23
  • for part d, if our function is onto, then all (ten say) things in our finite codomain are mapped to. We only have ten elements in the domain, so each element in the domain needed to map to a unique thing. If two things in the domain went to the same thing, then we left something in the codomain out. – Vladhagen Nov 13 '13 at 20:27
  • Oh, ok so both finite cases would be true then. – TheDifficultyOfAlgortihms Nov 13 '13 at 20:29