Let X be the set {a, b, c, d, e}. Give answers to each of the following questions, justifying your answer in each case.(a) How many functions are there which map from X to X?(b) How many distinct total orders can be defined on X?(c) For each function f in the set of functions from X to X, consider the relation that is the symmetric closure ofthe function f . Let us call the set of these symmetric closures Y . List at least two elements of Y .(d) Suppose R is some partial order on X. What is the smallest possible cardinality R could have? What is thelargest?
Question
Let X be the set {a, b, c, d, e}. Give answers to each of the following questions, justifying your answer in each case.(a) How many functions are there which map from X to X?(b) How many distinct total orders can be defined on X?(c) For each function f in the set of functions from X to X, consider the relation that is the symmetric closure ofthe function f . Let us call the set of these symmetric closures Y . List at least two elements of Y .(d) Suppose R is some partial order on X. What is the smallest possible cardinality R could have? What is thelargest?
Solution
(a) The number of functions from a set to itself is given by n^n, where n is the number of elements in the set. In this case, n=5 (a, b, c, d, e). So, there are 5^5 = 3125 functions which map from X to X.
(b) A total order on a set is a way of arranging the elements in a sequence. For a set with n elements, there are n! (n factorial) distinct total orders. In this case, n=5, so there are 5! = 120 distinct total orders that can be defined on X.
(c) The symmetric closure of a function f from X to X is a relation that includes both the function and its inverse. For example, if f(a)=b, then the symmetric closure includes both (a, b) and (b, a). Two possible elements of Y could be the symmetric closures of the functions f(a)=b, f(b)=a, f(c)=d, f(d)=e, f(e)=c and f(a)=a, f(b)=b, f(c)=c, f(d)=d, f(e)=e.
(d) A partial order on a set is a binary relation that is reflexive, antisymmetric, and transitive. The smallest possible cardinality R could have is n, because each element must at least be related to itself (reflexivity). The largest possible cardinality is n^2, because in the most extreme case, every element is related to every other element and itself. In this case, n=5, so the smallest possible cardinality is 5 and the largest possible cardinality is 25.
Similar Questions
Which ordered pairs need to be added to the relationp = {(a,a),(a,b),(b,a),(c,c),(c,d),(d,c),(d,d)}on the set X = {a,b,c,d} to create the symmetric closure p^s of p? A (a,a) B (a,b) C (a,c) D (a,d) E (b,a) F (b,b) G (b,c) H (b,d) I (c,a) J (c,b) K (c,c) L (c,d) M (d,a) N (d,b) O (d,c) P (d,d) Q None of them
Which set of ordered pairs is a function fromA = {a, b, c, d} to B = {1, 2, 3, 4, 5, 6}? R4 = {(a, 2), (b, 2), (c, 6), (d, 2), (c, 5)} R3 = {(a, 3), (b, 2), (a, 4),(c, 5), (d, 4)} R1 = {(a, 3), (b, 3), (c, 4), (d, 1)} R2 = {(a, 1), (a, 4), (b, 1), (c, 5), (d, 4)}
4. Determine whether each of these functions from {a, b, c, d} to itself is one-to-one (onto)a) f (a) = b, f (b) = a, f (c) = c, f (d) = db) f (a) = b, f (b) = b, f (c) = d, f (d) = cc) f (a) = d, f (b) = b, f (c) = c, f (d) = d
Given the sets of ordered pairs, determine if they represent a relation or a function. If it is a function,specify the domain and range. (Criteria A)a) {(1,2),(2,3),(1,5),(4,6)}{(1,2),(2,3),(1,5),(4,6)}b) {(3,4),(2,7),(5,2),(3,1)}{(3,4),(2,7),(5,2),(3,1)}c) {(2,3),(5,6),(2,7),(8,1)}{(2,3),(5,6),(2,7),(8,1)}d) {(1,3),(2,5),(3,7),(4,9)}{(1,3),(2,5),(3,7),(4,9)}
How many functions are there form the set {A, B, C, D} to the set {1, 2, 3}?Select one:a.43b.0c.None of the othersd.34e.12
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.