Question

Discrete math

Which of the following functions f : {0, 1, 2, 3} ! {0, 1, 2, 3} are onto?
1) f(x) = x
2) f(x) = x^2 mod 4
3) f(x) = x^2 - x mod 4

4) f(0) = 3, f(1) = 2, f(2) = 1, f(3) = 0
5) f(0) = 1, f(1) = 2, f(2) = 1, f(3) = 2

Answer 1

1) yes

2) No

3) No

4) yes

5) No

Explanation:

1) f(0)=0, f(1)=1, f(2)=2, f(3)=3, then
`f[\{0, 1, 2, 3\}]=\{0, 1, 2, 3\}`

2) f(0)=0,
`1^2=1\equiv 1 \text{mod 4}`, then f(1)=1;
`2^2=4\equiv 0 \text{ mod 4}`, then f(2)=0;
`3^2=9\equiv 1 \text{mod 4}`, then f(3)=1

Then
`f[\{0, 1, 2, 3\}]=\{0, 1, 3\}`, this means that f isn't onto.

3.

• f(0)=0;

• 
  `1^1-1=0`, then f(1)=0
• 
  `2^2-2=2`, then f(2)=2
• 
  `3^2-3=6\equiv 2 \text{ mod 4}`, then f(3)=2

Then
`f[\{0, 1, 2, 3\}]=\{0, 2\}`, this means that f isn't onto.

4.
`f[\{0, 1, 2, 3\}]=\{0, 1, 2,3\}`, then f is onto.

5.
`f[\{0, 1, 2, 3\}]=\{1, 2\}`, this means that f isn't onto.