Show that is countable by showing that the polynomial function with is one-to-one and onto.
A set is countable if it is finite or countably infinite.
A set is finite if it contains a limited number of elements (thus it is possible to list every single element in the set).
A set is countably infinite if the set contains an unlimited number of elements and if there is a one-to-one correspondence with the positive integers.
The function f is one-to-one if and only if implies that for all a and b in the domain.
There is one-to-one function A to B if only if .
To proof: is countable.
Let definite the function f as:
Note: Since an odd number is always follows by an even number and an even number is always followed by an odd number, or is even (but not both) and the other element is then odd. The even term is then divisible by and thus,
is an integer, which means that .
Let us first evaluate the formula at a few pairs mentioned in the diagram.
Then note that represents the position of (m,n) in the path created by the diagram below, with (1,1) the position, (1,2) the position, (2,1) the position, etc.
Let assume that and such that a and b have the same image.
By definition of the function f, the image of f then represents the same element in the path created in the diagram. However, each value is unique along the path and thus the corresponding values need to be in the same location.
Then note that implies role="math" localid="1668423647696" and for all . By the definition of one-to-one, f is then one-to-one.
Let role="math" localid="1668423698801" .
Let (a,b) be the ordered pair in the path.
By definition of f:
Then note that for every , there exists an element such that . By the definition of onto, f is then onto.
Showed that f is onto and one-to-one, which implies that f is a one-to-one correspondence between and role="math" localid="1668423836805" . This then also means that is countable as is countable.
94% of StudySmarter users get better grades.Sign up for free