1. Let f : Z to Z and g : Z to Z be functions de�fined by f (x) = 3x + 1 and g(x) = [x/2]

.
(a) Is fog one-to-one? Prove your answer.
(b) Is fog onto? Prove your answer.
(c) Is gof one-to-one? Prove your answer.
(d) Is gof onto? Prove your answer.

one-to-one (injection):

every element in the codomain is mapped by at most one element of the domain.

onto (surjection):
every element in the codomain is mapped by at least one element of the domain.

We can see that f(x) is both one-to-one but not onto, since
f(1)=4, f(2)=7, so codomain (Z) contains "holes" such as 5 and 6 which are not mapped.
On the other hand, g(x) is onto, but not one-to-one, since
g(2)=g(3)=1 (assuming [x/2] is the greatest integer function of x/2).

(a)
fog(x)=f(g(x)) is not one-to-one since
fog(2)=f(g(2))=f(1)=3(1)+1=4
fog(3)=f(g(3))=f(1)=3(1)+1=4
gives a counter-example.
(b)
fog(x)=f(g(x)) is not onto since the codomain (Z) still contain holes (such as 5 and 6 which are not mapped.

I will leave (c) and (d) for you as exercise.

To determine if the functions fog and gof are one-to-one (injective) and onto (surjective), we need to analyze the properties of the functions f and g.

Let's begin by understanding the given functions f(x) = 3x + 1 and g(x) = [x/2], defined on the set of integers Z.

(a) To prove whether fog is one-to-one, we need to show that for any distinct elements a and b in the domain of fog, f(g(a)) is distinct from f(g(b)).

To do this, we'll evaluate f(g(x)) = f([x/2]) for distinct integers a and b:

f(g(a)) = f([a/2]) = 3([a/2]) + 1 = (3a/2) + 1
f(g(b)) = f([b/2]) = 3([b/2]) + 1 = (3b/2) + 1

Now, let's assume that f(g(a)) = f(g(b)), meaning (3a/2) + 1 = (3b/2) + 1. By subtracting 1 from both sides and multiplying by 2, we get 3a = 3b. Dividing by 3 yields a = b. This shows that if f(g(a)) = f(g(b)), then a = b, ensuring that fog is one-to-one.

(b) To prove whether fog is onto, we need to show that for any element y in the codomain of fog (set Z), there exists an element x in the domain of fog such that f(g(x)) = y.

For fog to be onto, every integer in the codomain should have a corresponding element in the domain. Let y be an arbitrary integer in Z. We want to find x such that f(g(x)) = y.

Consider the equation (3x/2) + 1 = y, where x is an integer. Solving for x, we obtain x = (2(y - 1))/3. Since y is an integer, (y - 1)/3 is an integer as well. Therefore, x = (2(y - 1))/3 is an integer solution. This demonstrates that for any y in Z, there exists an x in Z such that f(g(x)) = y, ensuring that fog is onto.

(c) To prove whether gof is one-to-one, we need to show that for any distinct elements a and b in the domain of gof, g(f(a)) is distinct from g(f(b)).

Let's evaluate g(f(x)) = g(3x + 1) for distinct integers a and b:

g((3a + 1) = [(3a + 1)/2]
g(f(b)) = g(3b + 1) = [(3b + 1)/2]

Assume g((f(b)), which implies (3a + 1)/2 = (3b + 1)/2. By cross-multiplying, we obtain 3a + 1 = 3b + 1. Subtracting 1 from both sides and dividing by 3, we find that a = b. This demonstrates that if g((f(b)), then a = b, thus proving that gof is one-to-one.

(d) To prove whether gof is onto, we need to show that for any element y in the codomain of gof (set Z), there exists an element x in the domain of gof such that g(f(x)) = y.

Again, let y be an arbitrary integer in Z. We want to find x such that g(f(x)) = y.

Consider the equation [(3x + 1)/2] = y, where x is an integer. Solving for x, we obtain x = (2y - 1)/3. Since y is an integer, (2y - 1)/3 is an integer as well. Thus, x = (2y - 1)/3 is an integer solution, proving that for any y in Z, there exists an x in Z such that g(f(x)) = y. This ensures that gof is onto.