# Computer science: Functions help

• Jan 26th 2009, 05:41 PM
AlexH
Computer science: Functions help
Hi, I hope I can get some help with this problem. The class is called "Formal models of computation". It's a computer science course where we talk about models of how computers work, Turing machines, automatons, etc. It's kind of like Discrete Math for computer science (which I hated).

Give functions f: E -> E (where E is the set of even integers) that fulfill the following properties

a. f is one-to-one, but not onto or total
b. f is total, but not one-to-one or onto
c. f is total, one-to-one and onto, but is not the identity function (f(x) = x)
d. f is not total or one-to-one, but is onto.

I have part c figured out but can't come up with anything for the other 3. Everytime I come up with a function for one property it doesn't meet the other ones. The professor wants the functions to be in the form f(x) = something. We are not allowed to create subsets of set E either. The functions have to work over the entire set E.

Thanks for any help.
• Jan 26th 2009, 09:50 PM
wil
(b) and (c)
Quote:

Originally Posted by AlexH
Give functions f: E -> E (where E is the set of even integers) that fulfill the following properties

a. f is one-to-one, but not onto or total
b. f is total, but not one-to-one or onto
c. f is total, one-to-one and onto, but is not the identity function (f(x) = x)
d. f is not total or one-to-one, but is onto.

I can't help you with all of them, but for (b), try the absolute value function or $\displaystyle f(x)=x^2$. For (c) try $\displaystyle f(x)=x+2$.
• Jan 26th 2009, 10:31 PM
Functions
Hello AlexH
Quote:

Originally Posted by AlexH
Give functions f: E -> E (where E is the set of even integers) that fulfill the following properties

a. f is one-to-one, but not onto or total
b. f is total, but not one-to-one or onto
c. f is total, one-to-one and onto, but is not the identity function (f(x) = x)
d. f is not total or one-to-one, but is onto.

I have part c figured out but can't come up with anything for the other 3. Everytime I come up with a function for one property it doesn't meet the other ones. The professor wants the functions to be in the form f(x) = something. We are not allowed to create subsets of set E either. The functions have to work over the entire set E.

(a) $\displaystyle f(x) = \sqrt{x}$ works OK. It's not total - only perfect squares, 0, 4, 16, ... work as input values; it's not onto - we're just taking the positive square root; but it is one-to-one.

wil's suggestions for (b) seem to work OK.

I'm still thinking about (d) ...

• Jan 27th 2009, 12:59 AM
Functions
Hello AlexH
Quote:

Originally Posted by AlexH
d. f is not total or one-to-one, but is onto.

I have got an answer for (d), but it's pretty obscure. I reasoned as follows:

$\displaystyle f$ is not total, so we must exclude at least one even integer from being a valid input to $\displaystyle f$. The square root function permits only positive numbers as inputs, so that looks a likely candidate.

$\displaystyle f$ is onto, so we have to find some way of generating negative as well as positive outputs. So I thought of $\displaystyle (-1)^n$ as a candidate, because, as $\displaystyle n$ goes alternately odd and even, $\displaystyle (-1)^n$ has values -1, 1, -1, 1, ...

$\displaystyle f$ is not one-one, so there must be at least two different input values that generate the same output value.

So I played around with these ideas and came up with (wait for it!)

$\displaystyle f(x) = \tfrac{1}{2}(-1)^{\frac{1}{2}\sqrt{x}}(\sqrt{x} - 1 + (-1)^{\frac{1}{2}\sqrt{x}})$

So: $\displaystyle x$ can only take (positive) even perfect squares as values: 0, 4, 16, 36, 64, 100, ... Therefore $\displaystyle f$ is not total.

For these values of $\displaystyle x$, then:

$\displaystyle \sqrt{x} = 0, 2, 4, 6, 8, 10, ...$

$\displaystyle (-1)^{\frac{1}{2}\sqrt{x}} = 1, -1, 1, -1, 1, -1, ...$

$\displaystyle \sqrt{x} - 1 + (-1)^{\frac{1}{2}\sqrt{x}} = 0, 0, 4, 4, 8, 8, ...$

and finally:

$\displaystyle \tfrac{1}{2}(-1)^{\frac{1}{2}\sqrt{x}}(\sqrt{x} - 1 + (-1)^{\frac{1}{2}\sqrt{x}}) = 0, 0, 2, -2, 4, -4, ...$

Note that $\displaystyle f(0) = 0 = f(4)$. So $\displaystyle f$ is not one-one, but it is total, because any even integer (positive or negative) can be generated using a suitable value of $\displaystyle x$.

I think you need a twisted mind for this sort of thing!