Question

Assume that the domain A and codomain B for function f are both finite sets and that f is an onto function. What is the necessary relationship between the cardinality of A and the cardinality of B? Explain.

Answer 1

Answer:

• Cardinality of B ≤ cardinality of A

• # B ≤ # A

Explanation:

The domain is the set of input elements of the function.

The codomain is the set of output elements of the function.

Cardinality is the number of elements of a set.

As per the definition of function one input cannot have more than one output. Thus, every element of the domain is related to one element of the codomain and no more.

An onto function, also knwon as surjection, is one in which any element of the codomain is related with at least one element of the domain. But it could happen that the same element of the domain is related with several elements of the domain. Hence, the number of elements in the codomain may be less than or equal to the number of elements of the domain, but never greater.

Conclusion:

The cardinality of B is less than or equal to the cardinality of A. Using the symbol # for cardinality that is: #B ≤ #A.