0
$\begingroup$

In the book of "Introduction_to_the_Theory_of_Computation_by_Michael_Sipser_Third_Edition_Course_Technology", Page 7, last sentence is "A function that use all the elements of the range is said to be noto the range." What doe it mean by "use"? How can a function uses its element of its range? Can you please give an example ? Thank you so much in advance!

"In the case of the function abs, if we are working with integers, the domain and the range are Z, so we write abs : Z−!Z. In the case of the addition function for integers, the domain is the set of pairs of integers Z × Z and the range is Z, so we write add : Z × Z−!Z. Note that a function may not necessarily use all the elements of the specified range. The function abs never takes on the value −1 even though −1 2 Z. A function that does use all the elements of the range is said to be onto the range."

$\endgroup$
1
  • $\begingroup$ I'd say that phrasing is unusual, but all it means is that every element of the range is a value of the function. For any set $S$ the identity function is an example of a function that maps onto it's range. $\endgroup$
    – lulu
    Jan 10 '18 at 0:14
1
$\begingroup$

It just means that for every $y$ in the range, there is some $x$ in the domain such that $f(x) = y$, i.e. every element of the range is mapped onto.

Note that in modern usage it is more common to use the term "codomain" to refer to what Sipser calls the "range", and "range" to actually mean the image of $f$. $f$ is then called "onto" if its range is equal to its codomain.

$\endgroup$
0
$\begingroup$

As stated by @lulu, the last sentence is trying to express that a function f is called onto when every value v in the range is f(x) for some x in the domain.

So, to take the quoted example, the integer absolute value function is onto exactly when its range is the non-negative integers (assuming its domain is the integers).

To see this, observe that if we define a function f by $f:Z\to Z^{nonneg}$ such that $f(x) = |x|$ for all integers x, then we can pick any element b in the range ($Z^{nonneg}$) and find an element a of the domain (in this case, either b or -b would work) such that f(a) = b, so f is onto.

On the other hand, if the range were any superset of $Z^{nonneg}$ (such as Z), it would be easy to find an element (such as -1) which is never the output of f, so f would not be onto.

$\endgroup$
0
$\begingroup$

A function $f:A\to B$ is onto if for every $y$ in$ B$ we can find an $x$ in $A$ such that $f(x)=y.$

That is, all of $ B$ must be covered by $f$. Consider a class-room with $25$ chairs and $20$ students. Let us define a function $f:S\to C$ where$ S$ is the set of students and $C$ is the set of chairs by $f(s)=c$ where $s$ represents any student and $c$ is the chair that is taken by that student. Then this function is not onto because there are some chairs that are not "used". To make it onto we may remove five chairs from the class-room or bring five more students to the class-room.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.