ECS 20 Discrete Math: Discussion 6 Mon 11/11/2013 Injective, Surjective, and Bijective functions
A function is one-to-one or injective if no two distinct elements in the domain maps to the same element in the codomain.
A function is onto or surjective if every element in the codomain has a pre-image in the domain.
one-to-one (injective), but not onto
A function is bijective if it is both injective and surjective.
onto (surjective), but not one-to-one
The identity function ( ) maps an element to itself (from the domain to the codomain). It is useful for many questions in PS6.
1
ECS 20 Discrete Math: Discussion 6 Mon 11/11/2013
PS6 Hints & Notes
2) Consider an infinite set such as for counter-examples. 3)Recallthat ( )isavalue suchthat ( ) .
4a) Consider defining different maps for different pre-image values (piecewise mapping). To have [0,1] map to (0,1], we have to map 0 to some non-zero image, which forces us to make room for other domain elements. Consider the identity function for certain domain elements.
4b) Consider the identity function. This is a much simpler problem compared to 4a.
5) Recall that the composition of injective maps is injective, and the composition of surjective maps is surjective. (Note that although satisfies the three properties of an equivalence relation, we do not say it is an equivalence relation because there does not exist a set such that .)
6) Consider using contradiction to prove that BIG – Little is uncountable. Consider the fact that a subset of a countable set is still countable.
7) Consider merging two sequences to make one sequence. There are multiple encoding schemes for this question.
8b) Recall that for a set to form a group under an operator
it must be associative: ( ) ( )
there exists an identity such that
there is always an inverse such that
2