{"id":4883,"date":"2020-08-23T18:40:06","date_gmt":"2020-08-23T09:40:06","guid":{"rendered":"https:\/\/sasamath.com\/blog\/?p=4883"},"modified":"2020-08-25T22:35:19","modified_gmt":"2020-08-25T13:35:19","slug":"exercises-sets-and-functions","status":"publish","type":"post","link":"https:\/\/sasamath.com\/blog\/articles\/exercises-sets-and-functions\/","title":{"rendered":"Exercises: Sets and Functions"},"content":{"rendered":"
\n

This set of exercises is retrieved from the second chapter of Linear Algebra by Robert J. Valenza. Note that these solutions are not fully elaborated; You have to fill the descriptions by yourself.\n<\/p>\n<\/div>\n

Problem 1.1<\/span>
\nFind the sets \\(S,\\) \\(T\\) and \\(U\\) and functions \\(f: S \\rightarrow T\\) and \\(g: T \\rightarrow U\\) such that \\(g \\circ f\\) is injective, but \\(g\\) is not injective.<\/p>\n

\n

Solution.<\/span>
\nTake
\n\\(S = U = \\left\\{ 1 \\right\\} ,\\,\\, T = \\left\\{ 0,\\,1 \\right\\},\\)
\nand
\n\\(f(s) = 1 ,\\,\\, g(t) = 1\\)
\nfor all \\(s\\in S\\) and \\(t \\in T.\\)\n<\/p>\n<\/div>\n

<\/p>\n

Problem 1.2<\/span>
\nFind sets \\(S,\\) \\(T\\) and \\(U\\) and functions \\(f : S \\rightarrow T\\) and \\(g: T \\rightarrow U\\) such that \\(g \\circ f\\) is surjective, but \\(f\\) is not surjective.\n<\/p>\n

\n

Solution.<\/span>
\nSame as Problem 1.1.\n<\/p>\n<\/div>\n

<\/p>\n

Problem 1.3<\/span>
\nFind a non-identity function \\(\\mathbb{R} \\rightarrow \\mathbb{R}\\) which is its own inverse function. That is, \\(f \\circ f = 1_\\mathbb{R}\\) or, equivalently, \\(f(f(x)) = x\\) for all real \\(x.\\)\n<\/p>\n

\n

Solution.<\/span>
\nTake \\(f(x) = -x.\\)\n<\/p>\n<\/div>\n

<\/p>\n

Problem 1.4<\/span>
\nAssess the injectivity and surjectivity of each of the following functions from \\(\\mathbb{R}\\) to \\(\\mathbb{R}.\\) Be sure to defend your responses rigorously. For example, to show that a function is bijective, you might exhibit the inverse function. You might also deduce valuable information by sketching the graph as you did in calculus.\n<\/p>\n

    \n
  1. \\(f(x) = 2x+1\\)<\/li>\n
  2. \\(f(x)=x^3 – 3x\\)<\/li>\n
  3. \\(f(x)=e^x\\)<\/li>\n
  4. \\(f(x)=x^4 -2x^2\\)<\/li>\n
  5. \\(f(x)=e^{-x^2}\\)<\/li>\n<\/ol>\n
    \n

    Solution.<\/span>(Defending is skipped.)<\/p>\n

      \n
    1. Bijective.<\/li>\n
    2. Surjective, but not injective.<\/li>\n
    3. Injective, but not surjective.<\/li>\n
    4. Not injective nor surjective.<\/li>\n
    5. Not injective nor surjective.<\/li>\n<\/ol>\n<\/div>\n

      <\/p>\n

      Problem 1.5<\/span>
      \nFind the bijective map from the open interval \\((-\\pi \/2 ,\\, + \\pi \/2 )\\) to the set \\(\\mathbb{R}\\) of real numbers. This shows, by the way, that both sets have the same cardinality.\n<\/p>\n

      \n

      Solution.<\/span>
      \nTake \\(f(x) = \\tan x .\\)\n<\/p>\n<\/div>\n

      <\/p>\n

      Problem 1.6<\/span>
      \nExplicitly construct a bijective function from the set of integers \\(\\mathbb{Z}\\) to the set of even integers \\(2\\mathbb{Z}.\\) Despite your naive intuition to the contrary, this shows that \\(\\operatorname{Card}(\\mathbb{Z}) = \\operatorname{Card}(2\\mathbb{Z}).\\)\n<\/p>\n

      \n

      Solution.<\/span>
      \nTake \\(f(x) =2x.\\)\n<\/p>\n<\/div>\n

      <\/p>\n

      Problem 1.7<\/span>
      \nProve that if \\(\\operatorname{Card}(S) = \\operatorname{Card}(T)\\) and \\(\\operatorname{Card}(T) = \\operatorname{Card}(U),\\) then \\(\\operatorname{Card}(S) = \\operatorname{Card}(U).\\)\n<\/p>\n

      \n

      Solution.<\/span>
      \nThe composition of two bijective functions is a bijective function.\n<\/p>\n<\/div>\n

      <\/p>\n

      Problem 1.8<\/span>
      \nLet \\(\\mathbb{N} \\times \\mathbb{N}\\) denote the set of all ordered pairs \\((m,\\,n)\\) of natural numbers. Show that \\(\\operatorname{Card}(\\mathbb{N} \\times \\mathbb{N}) = \\operatorname{Card}(\\mathbb{N})\\) by explicitly constructing a bijection \\(\\mathbb{N} \\times \\mathbb{N} \\rightarrow \\mathbb{N}.\\)\n<\/p>\n

      \n

      Solution.<\/span>
      \nTake the function \\(f : \\mathbb{N} \\times \\mathbb{N} \\rightarrow \\mathbb{N}\\) as
      \n\\[f(m,\\,n) = \\frac{(m+n-2)(m+n-1)}{2} +n,\\]
      \nprovided that \\(\\mathbb{N} = \\left\\{ 1,\\,2,\\,3,\\,\\cdots \\right\\}.\\)\n<\/p>\n<\/div>\n

      <\/p>\n

      Problem 1.9<\/span>
      \nExpress the following composition of cycles in matrix notation.
      \n\\[\\left( 1\\quad 4\\quad 7\\quad 6 \\right) \\circ \\left( 2 \\quad 7 \\quad 5 \\right)\\]
      \nBe sure to work from right to left.\n<\/p>\n

      \n

      Solution.<\/span>
      \n\\[\\left(
      \n\\begin{matrix}
      \n1 & 2 & 3 & 4 & 5 & 6 & 7 \\\\
      \n4 & 6 & 3 & 7 & 2 & 1 & 5
      \n\\end{matrix}
      \n\\right).
      \n\\]\n<\/p>\n<\/div>\n

      <\/p>\n

      Problem 1.10<\/span>
      \nDecompose the following permutation into the product of disjoint cycles.
      \n\\[\\pi = \\left(
      \n\\begin{matrix}
      \n1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\\\
      \n6 & 5 & 9 & 1 & 4 & 3 & 8 & 7 & 2
      \n\\end{matrix}
      \n\\right)
      \n\\]\n<\/p>\n

      \n

      Solution.<\/span>
      \n\\[\\pi =
      \n\\left( 1 \\quad 6 \\quad 3 \\quad 9 \\quad 2 \\quad 5 \\quad 4 \\right) \\circ \\left(7 \\quad 8\\right).
      \n\\]\n<\/p>\n<\/div>\n

      <\/p>\n

      Problem 1.11<\/span>
      \nHow many reversals does the permutation \\(\\pi\\) in the previous problem manifest? What is its sign? Factor \\(\\pi\\) into the product of transpositions.\n<\/p>\n

      \n

      Solution.<\/span>
      \nThe number of reversals is \\[5+4+6+0+2+1+2+1=21.\\] Its sign is \\(-1,\\) that is, the parity of \\(\\pi\\) is odd. \\(\\pi\\) is factorized as
      \n\\[\\pi =
      \n\\left ( 4 \\quad 5 \\right) \\circ
      \n\\left ( 4 \\quad 2 \\right) \\circ
      \n\\left ( 4 \\quad 9 \\right) \\circ
      \n\\left ( 4 \\quad 3 \\right) \\circ
      \n\\left ( 4 \\quad 6 \\right) \\circ
      \n\\left ( 4 \\quad 1 \\right) \\circ
      \n\\left ( 7 \\quad 8 \\right)
      \n,\\]
      \nthe composition of SEVEN transpositions.\n<\/p>\n<\/div>\n

      <\/p>\n

      Problem 1.12<\/span>
      \nReferring to the permutation,
      \n\\[\\pi = \\left(
      \n\\begin{matrix}
      \n1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\\\
      \n8 & 1 & 3 & 6 & 4 & 5 & 7 & 2
      \n\\end{matrix}
      \n\\right).
      \n\\]\n<\/p>\n

        \n
      1. Express \\(\\pi\\) as the product of disjoint cycles.<\/li>\n
      2. Express \\(\\pi\\) as the product of transpositions.<\/li>\n
      3. Compute the sign of \\(\\pi.\\)<\/li>\n<\/ol>\n
        \n

        Solution.<\/span>
        \n\\[\\begin{align}
        \n\\pi &=
        \n\\left( 1 \\quad 8 \\quad 2 \\right) \\circ
        \n\\left( 4 \\quad 6 \\quad 5 \\right) \\\\[7pt]
        \n&=
        \n\\left( 1 \\quad 2 \\right) \\circ
        \n\\left( 1 \\quad 8 \\right) \\circ
        \n\\left( 4 \\quad 5 \\right) \\circ
        \n\\left( 4 \\quad 6 \\right) .
        \n\\end{align}\\]
        \nThe sign of \\(\\pi\\) is \\(1,\\) that is, \\(\\pi\\) is an even permutation.\n<\/p>\n<\/div>\n

        <\/p>\n

        Problem 1.13<\/span>
        \nLet \\(\\pi \\in S_n\\) be a \\(k\\)-cycle. For which positive integers \\(m\\) is \\(\\pi ^m\\) equal to the identity map? Here \\(\\pi^m\\) means \\(\\pi\\) composed with itself \\(m\\) times.\n<\/p>\n

        \n

        Solution.<\/span>
        \n\\(m\\) has to be a multiple of \\(k.\\)\n<\/p>\n<\/div>\n

        <\/p>\n

        Problem 1.14<\/span>
        \nSuppose that for permutations \\(\\pi\\) and \\(\\tau\\) in \\(S_n ,\\) \\(\\pi \\circ \\tau = \\tau \\circ \\pi .\\) (Recall that this is not in general true.) Show that for all positive integer \\(n,\\) \\((\\pi \\circ \\tau )^n = \\pi^n \\circ \\tau^n .\\)\n<\/p>\n

        \n

        Solution.<\/span>
        \nUse mathematical induction for \\(n.\\)\n<\/p>\n<\/div>\n

        <\/p>\n

        Problem 1.15<\/span>
        \nShow that disjoint cycles commute; that is, if \\(\\pi\\) and \\(\\tau\\) are cycles with no elements in common, then \\(\\pi \\circ \\tau = \\tau \\circ \\pi .\\)\n<\/p>\n

        \n

        Solution.<\/span>
        \nFirst prove commutativity for two disjoint transpositions. Next, express \\(\\pi\\) and \\(\\tau\\) as transpositions and prove commutativity. In the process, you can use mathematical induction.\n<\/p>\n<\/div>\n

        <\/p>\n

        Problem 1.16<\/span>
        \nRecall that every permutation may be written as the product of disjoint cycles. Using this fact and the previous three exercises, show that \\(\\pi ^{n!}\\) is the identity map for any permutation \\(\\pi\\) in \\(S_n .\\)\n<\/p>\n

        \n

        Solution.<\/span>
        \nLet \\(\\pi\\) be the product of disjoint \\(m\\) cycles
        \n\\[\\pi = \\pi_1 \\circ \\pi_2 \\circ \\cdots \\circ \\pi_m ,\\]
        \nwhere each \\(\\pi_i\\) is a \\(k_i\\)-cycle. Because each \\(k_i\\) divides \\(n! ,\\) \\({\\pi_i}^{n!}\\) is the identity map.<\/p>\n

        As a consequence, we have
        \n\\[\\pi ^{n!} = {\\pi_1}^{n!} \\circ {\\pi_2}^{n!} \\circ \\cdots \\circ {\\pi_m}^{n!} ,\\]
        \nthat is, \\(\\pi^{n!}\\) is a composition of the identity maps, thus it is the identity map.\n<\/p>\n<\/div>\n

        <\/p>\n

        Problem 1.17<\/span>
        \nWe showed above that for transpositions \\(\\tau_1 ,\\) \\(\\tau_2 ,\\) \\(\\cdots ,\\) \\(\\tau_m \\)
        \n\\[\\sigma \\left( \\tau_1 \\circ \\tau_2 \\circ \\cdots \\circ \\tau_m \\right) = (-1)^m\\]
        \nand also that every permutation is the product of transpositions. Use this two facts to prove that for all permutations \\(\\pi_1\\) and \\(\\pi_2 ,\\)
        \n\\[\\sigma \\left( \\pi_1 \\circ \\pi_2 \\right) = \\sigma \\left( \\pi_1 \\right) \\sigma \\left( \\pi_2 \\right).\\]\n<\/p>\n

        \n

        Solution.<\/span>
        \nExpress \\(\\pi_2\\) as a product of transpositions
        \n\\[\\pi_2 = \\tau_1 \\circ \\tau_2 \\circ \\cdots \\circ \\tau_m ,\\]
        \nand use mathematical induction for \\(m.\\)\n<\/p>\n<\/div>\n

        <\/p>\n

        Problem 1.18<\/span>
        \nShow that if \\(S\\) and \\(T\\) are nonempty sets, then \\(\\operatorname{Card}(S \\times T) = \\operatorname{Card}(T \\times S).\\)\n<\/p>\n

        \n

        Solution.<\/span>
        \nDefine \\(f : S \\times T \\rightarrow T \\times S\\) by
        \n\\(f(s,\\,t) = (t,\\,s)\\)
        \nthen \\(f\\) is a bijective function.\n<\/p>\n<\/div>\n

        <\/p>\n

        Problem 1.19<\/span>
        \nLet \\(S,\\) \\(S ‘ ,\\) \\(T ,\\) \\(T ‘ \\) be sets such that \\(S\\) and \\(T\\) are disjoint, as are \\(S ‘ \\) and \\(T ‘ .\\) Assume further that
        \n\\[\\operatorname{Card}(S) = \\operatorname{Card}(S ‘ ) \\quad\\text{and}\\quad\\operatorname{Card}(T) = \\operatorname{Card}(T ‘ ).\\]
        \nShow that \\[\\operatorname{Card}(S\\cup T) = \\operatorname{Card}(S ‘ \\cup T ‘ ).\\] Note that this result extends easily to arbitrary disjoint unions (possibly involving an infinite family of disjoint sets.)\n<\/p>\n

        \n

        Solution.<\/span>
        \nBy the definition, there are two bijective functions \\(f : S \\rightarrow S ‘ \\) and \\(g : T \\rightarrow T ‘ .\\)<\/p>\n

        Define \\(\\phi : S \\cup T \\rightarrow S ‘ \\cup T ‘ \\) by
        \n\\[\\phi(x) = \\begin{cases}
        \nf(x) \\quad &\\text{if} \\,\\, x \\in S \\\\[7pt]
        \ng(x) \\quad &\\text{if} \\,\\, x \\in T.
        \n\\end{cases}\\]\n<\/p>\n

        Then \\(\\phi\\) is a bijective function from \\(S \\cup T\\) to \\(S ‘ \\cup T ‘ .\\)\n<\/p><\/div>\n

        <\/p>\n

        Problem 1.20<\/span>
        \nLet \\(S\\) and \\(T\\) be nonempty sets. Show that there exist sets \\(S ‘ \\) and \\(T ‘ \\) such that
        \n\\[\\operatorname{Card}(S) = \\operatorname{Card}(S ‘ ) \\quad\\text{and}\\quad \\operatorname{Card}(T) = \\operatorname{Card}(T ‘ )\\]
        \nwith \\(S ‘ \\) and \\(T ‘ \\) disjoint.\n<\/p>\n

        \n

        Solution.<\/span>
        \nTake \\(S ‘ = S \\times \\left\\{ 0 \\right\\}\\) and \\(T ‘ = T \\times \\left\\{ 1 \\right\\}.\\)\n<\/p>\n<\/div>\n

        <\/p>\n

        Problem 1.21<\/span>
        \nProve Schr\u00f6der\u2013Bernstein theorem, that is, if \\(X\\) and \\(Y\\) are sets and both
        \n\\[\\operatorname{Card}(X) \\le \\operatorname{Card}(Y) \\quad\\text{and}\\quad \\operatorname{Card}(X) \\ge \\operatorname{Card}(Y)\\]
        \nhold, then \\(\\operatorname{Card}(X) = \\operatorname{Card}(Y).\\)\n<\/p>\n

        \n

        Solution.<\/span>
        \nSee a kind and nice explanation: Click here<\/a>.\n<\/p>\n<\/div>\n

        <\/p>\n","protected":false},"excerpt":{"rendered":"

        This set of exercises is retrieved from the second chapter of Linear Algebra by Robert J. Valenza. Note that these solutions are not fully elaborated; You have to fill the descriptions by yourself. Problem 1.1 Find the sets \\(S,\\) \\(T\\) and \\(U\\) and functions \\(f: S \\rightarrow T\\) and \\(g: T \\rightarrow U\\) such that \\(g \\circ f\\) is injective, but \\(g\\) is not…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_lmt_disableupdate":"","_lmt_disable":"","footnotes":""},"categories":[57,45],"tags":[409,402,400,401,404,403],"class_list":["post-4883","post","type-post","status-publish","format-standard","hentry","category-linear-algebra","category-sets-and-logic","tag-cardinality","tag-exercises","tag-linear-algebra","tag-sets-and-functions","tag-solution","tag-tip"],"_links":{"self":[{"href":"https:\/\/sasamath.com\/blog\/wp-json\/wp\/v2\/posts\/4883","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sasamath.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sasamath.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sasamath.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/sasamath.com\/blog\/wp-json\/wp\/v2\/comments?post=4883"}],"version-history":[{"count":49,"href":"https:\/\/sasamath.com\/blog\/wp-json\/wp\/v2\/posts\/4883\/revisions"}],"predecessor-version":[{"id":5090,"href":"https:\/\/sasamath.com\/blog\/wp-json\/wp\/v2\/posts\/4883\/revisions\/5090"}],"wp:attachment":[{"href":"https:\/\/sasamath.com\/blog\/wp-json\/wp\/v2\/media?parent=4883"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sasamath.com\/blog\/wp-json\/wp\/v2\/categories?post=4883"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sasamath.com\/blog\/wp-json\/wp\/v2\/tags?post=4883"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}