problem 2 1 Give an example of a function f Q N that is surj

problem 2

1. Give an example of a function f Q N that is surjective. (Note: Q 12la, b E z, b 0) 2. Let X e such that there exists a surjective function f X Z. Prove that X is infinite. 3. Let P represent the set of all polynomials with integer coefficients. Prove that P is countable. 4. Let I 0,1] and J 0.21 losed intervals of the real line). Show that III J lJl.

Solution

A surjective function is called a surjection.

Example: f(x)=x

(2). If X is a countable set, then we refer to an onto function f : N X as an enumeration of X, and write X = {xn : n N}, where x_n = f(n).

(3).

P(n) = {n is an element of the integers| axⁿ + bx^n-1 + ... where a,b... are integers.}
P(1) = {ax¹}. There is one element in this set therefore this set is countable.
Assume P(k) is true, i.e.
P(k) = {k is an element of the integers| ax^k + bx^k-1 + ... where a,b... are integers.} is a countable set.
Show P(K+1) is true i.e. that
P(k+1) = {k+1 is an element of the integers| ax^(k+1) + bx^k + cx^(k-1) ... where a,b,c... are integers.} is a countable set.

By our assumptpn we are trying to show that {k+1 is an element of integers | ax^(k+1) + a countable set) is a countable set.

(4)

Two sets I, J have equal cardinality, written I J , if there is a one-to-one, onto map f : I J

A surjective function is called a surjection.

Example:f(x)=x

(2). If X is a countable set, then we refer to an onto function f : N X as an enumeration of X, and write X = {xn : n N}, where xn = f(n).

(3).

P(n) = {n is an element of the integers| ax^n + bx^n-1 + ... where a,b... are integers.}
P(1) = {ax^1}. There is one element in this set therefore this set is countable.
Assume P(k) is true, i.e.
P(k) = {k is an element of the integers| ax^k + bx^k-1 + ... where a,b... are integers.} is a countable set.
Show P(K+1) is true i.e. that
P(k+1) = {k+1 is an element of the integers| ax^(k+1) + bx^k + cx^(k-1) ... where a,b,c... are integers.} is a countable set.

By our assumptpn we are trying to show that {k+1 is an element of integers | ax^(k+1) + a countable set) is a countable set.

(4)

Two sets I, J have equal cardinality, written I J , if there is a one-to-one, onto map f : I J