Skip to main content
Logo image

Elementary Foundations: An introduction to topics in discrete mathematics

Jeremy Sylvestre

πŸ”—

Exercises 10.7 Exercises

πŸ”—

1.

πŸ”—
Use predicate logic to write formal definitions of surjective function, injective function, and bijective function. Be sure to state the domains of your free variables.
πŸ”—

2.

πŸ”—
πŸ”—
Let A represent the set of all university students and let C be the set of all university courses. Does the rule f:A→C given by
f(a)=c if student is registered in course 
πŸ”—
define a function? Justify your answer.
πŸ”—

Testing bijectivity and determining inverses.

πŸ”—
πŸ”—
In each of Exercises 3–7, determine whether or not the described function is a bijection. For those functions that are bijective, describe the inverse function; that is, specify the inverse function’s
πŸ”—

3.

πŸ”—
Ξ›={T,F}, n:Ξ›β†’Ξ› is the logical negation function n(p)=Β¬p.
πŸ”—

4.

πŸ”—
L represents the set of all possible logical statements, N:L→L is the logical negation function N(A)=¬A for A a logical statement.
πŸ”—
(Note: You may treat equivalent statements as being the same statement.)
πŸ”—

5.

πŸ”—
N:Zβ†’Z is the numerical negation function N(n)=βˆ’n.
πŸ”—

6.

πŸ”—
Ξ£={0,1}, Ξ£βˆ— represents the set of all binary words, c:Ξ£βˆ—β†’Ξ£βˆ— is the bitwise complement function defined by: if w is a binary word, let c(w) be a binary word of the same length but with a 0 at every position that w has a 1, and a 1 at every position that w has a 0. For example, c(010)=101 and c(0000)=1111.
πŸ”—

7.

πŸ”—
U represents a universal set, C:P(U)β†’P(U) is the complement function C(A)=Ac, for AβŠ†U.
πŸ”—

8.

πŸ”—
Let EβŠ†Z represent the set of even integers, and consider the function f:Zβ†’E, f(n)=2n.
πŸ”—

(b)

πŸ”—
Describe the inverse function fβˆ’1:Eβ†’Z. That is, describe the rule to determine fβˆ’1(n), given even number n.
πŸ”—

9.

πŸ”—
As usual, Rm=RΓ—RΓ—β‹―Γ—R represents the Cartesian product of m copies of R, where m is a positive integer. Consider the function D:Rβ†’Rm defined by D(x)=(x,x,…,x).
πŸ”—

(d)

πŸ”—
Can you come up with other β€œnatural” embeddings Rβ†ͺRm?
πŸ”—

10.

πŸ”—
Let A={0,1,2,3,4,5,6,7,8,9} and let PβŠ†P(A) represent the set of all subsets of A which contain an odd number of elements. Define Ξ½:Pβ†’A by setting Ξ½(X) to be the β€œmiddle” element of X when the elements of X are listed in order by size. For example, Ξ½({0,8,9})=8.
πŸ”—
Is Ξ½ injective? Surjective? Bijective?
πŸ”—

11.

πŸ”—
Let Ξ£={0,1}. Recall that for n∈N, Ξ£nβˆ— is the subset of Ξ£βˆ— consisting of all binary words of length n.
πŸ”—
Suppose A={a1,a2,…,an} is a set with n (distinct) elements. Construct a bijection P(A)β†’Ξ£nβˆ—.
πŸ”—

12.

πŸ”—
Call a function with domain βˆ… an empty function.
πŸ”—

(b)

πŸ”—
Verify that an empty function with empty codomain is bijective.
Hint.
You have already verified injectivity of an empty function more generally in Task a. For surjectivity in this more specific setting, use your formal expression of surjective from Exercise 10.7.1, along with what you learned in Section 4.3.
πŸ”—

13.

πŸ”—

(a)

πŸ”—
Prove that if f and g are both surjective, then g∘f is surjective.
πŸ”—

(b)

πŸ”—
If g∘f is surjective, must either or both of f,g necessarily be surjective? Justify your answers.
πŸ”—

(c)

πŸ”—
Prove that if f and g are both injective, then g∘f is injective.
πŸ”—

(d)

πŸ”—
If g∘f is injective, must either or both of f,g necessarily be injective? Justify your answers.
πŸ”—

Function image sets and inverse image sets.

πŸ”—
In each of Exercises 15–18, consider abstract function f:Aβ†’B and subsets A1,A2βŠ†A, B1,B2βŠ†B.
πŸ”—

19.

πŸ”—
Suppose f:Aβ†’B is an injection. Use f to devise an injection F:P(A)β†ͺP(B). Be sure to verify that your proposed function F is injective. If f is bijective, will F also be bijective?
<Prev^TopNext>