Question

1. Prove or give a counterexample for the following statements: a) If ff: AA → BB is an injective function and bb ∈ BB, then |ff−1({bb})| = 1. b) If ff: AA → BB is a bijection and AA is countable, then BB is countable. c) If ff: AA → BB is a surjective function and AA is finite, then BB is finite. d) If ff: AA → BB is a surjective function and BB is finite, then AA is finite.

Answer 1

Answer:

a) False. A = {1}, B = {1,2} f: A ⇒ B, f(1) = 1

b) True

c) True

d) B = {1}, A = N, f: N ⇒ {1}, f(x) = 1

Step-by-step explanation:

a) lets use A = {1}, B = {1,2} f: A ⇒ B, f(1) = 1. Here f is injective but 2 is an element of b and |f−¹({b})| = 0., not 1. This statement is False.

b) This is True. If  A were finite, then it can only be bijective with another finite set with equal cardinal, therefore, B should be finite (and with equal cardinal). If A were not finite but countable, then there should exist a bijection g: N ⇒ A, where N is the set of natural numbers. Note that f o g : N ⇒ B is a bijection because it is composition of bijections. This, B should be countable. This statement is True.

c) This is true, if f were surjective, then for every element of B there should exist an element a in A such that f(a) = b. This means that  f−¹({b}) has positive cardinal for each element b from B. since f⁻¹(b) ∩ f⁻¹(b') = ∅ for different elements b and b' (because an element of A cant return two different values with f). Therefore, each element of B can be assigned to a subset of A (f⁻¹(b)), with cardinal at least 1, this means that |B| ≤ |A|, and as a consequence, B is finite.

b) This is false, B = {1} is finite, A = N is infinite, however if f: N ⇒ {1}, f(x) = 1 for any natural number x, then f is surjective despite A not being finite.