Question

For each of the functions below, indicate whether the function is onto, one-to-one, neither or both. If the function is not onto or not one-to- one, give an example showing why.

(a) f: {0, 1}{0, 1}3. The output of f is obtained by taking the input string and dropping the first bit. For example f(1011) = 011.
(b) f: {0, 1}-{0, 1}3. The output of f is obtained by taking the input string and replacing the first bit by 1, regardless of whether the first bit is a 0 or 1. For example, f(001) = 101 and f(110) = 110.
(c) f: (0, 1)3(0, 1)3. The output off is obtained by taking the input string and reversing the bits. For example f(011) = 110.
(d) f: {0, 1}{0, 1}4. The output of f is obtained by taking the input string and adding an extra copy of the first bit to the end of the string. For example, f(100) = 1001.
(e) Let A be defined to be the set {1, 2, 3, 4, 5, 6, 7, 8). f: P(A) (0, 1, 2, 3, 4, 5, 6, 7, 8). For X A, f(X) = IXI. Recall that for a finite set A, P(A) denotes the power set of A which is the set of all subsets of A.
(f) Let A be defined to be the set {1, 2, 3, 4, 5, 6, 7, 8). f: P(A) → P(A). For X ≤ A, f(X) = X. Recall that for a finite set A, P(A) denotes the power set of A which is the set of all subsets of A.
(g) Let A be defined to be the set {1, 2, 3, 4, 5, 6, 7, 8) and let B = {1}. f: P(A) → P(A). For X = A, f(x) = X - B. Recall that for a finite set A, P(A) denotes the power set of A which is the set of all subsets of A.

Answer 1

In function (a), f is one-to-one but not onto. In function (b), f is neither one-to-one nor onto. In function (c), f is both one-to-one and onto.

Step-by-step explanation:

For function (a), f: {0, 1}³ → {0, 1}³, the function is one-to-one but not onto. An example is f(001) = 001 and f(101) = 001, which shows that two different inputs have the same output.

For function (b), f: {0, 1}-³ → {0, 1}³, the function is neither one-to-one nor onto. An example is f(001) = 101 and f(110) = 110, which shows that two different inputs have the same output.

For function (c), f: (0, 1)³ → (0, 1)³, the function is both one-to-one and onto. An example is f(011) = 110, which has a unique output for every input.

For function (d), f: {0, 1}²⁰⁰³ → {0, 1}²⁰⁰⁴, the function is onto but not one-to-one. An example is f(100) = 1001 and f(1100) = 1001, which shows that two different inputs have the same output.

For function (e), f: P(A) → (0, 1, 2, 3, 4, 5, 6, 7, 8), where A = {1, 2, 3, 4, 5, 6, 7, 8}, the function is both one-to-one and onto. The output of f is obtained by taking the cardinality of the input set. For example, f({1, 2}) = 2 and f({3, 4, 5}) = 3.

For function (f), f: P(A) → P(A), where A = {1, 2, 3, 4, 5, 6, 7, 8}, the function is both one-to-one and onto. The output of f is the input set itself. For example, f({1, 2, 3}) = {1, 2, 3}.

For function (g), f: P(A) → P(A), where A = {1, 2, 3, 4, 5, 6, 7, 8} and B = {1}, the function is neither one-to-one nor onto. An example is f({1, 2, 3, 4}) = {2, 3, 4} and f({2, 3, 4}) = {3, 4}, which shows that two different inputs have the same output.