What is meant by a “diagonalization argument”?












9












$begingroup$


From Wikipedia:




A variety of diagonal arguments are used in mathematics.




  • Cantor's diagonal argument

  • Cantor's theorem

  • Halting problem

  • Diagonal lemma




Besides the above four examples, there is another one I found in a blog. When proving that "if a sequence of measurable mappings converges in measure, then there is a subsequence converging a.e.", the construction of the subsequence is also called diagonalization:




The method for establishing this result is fairly typical of such
arguments: we rely on diagonalization along with the control that
Borel-Cantelli gives us. Let $f_n$ be a sequence that converges in
measure to $f$. This means that for any n we have a $f_{m_n}$ with
$mu(|f_{m_n} - f| > 1/n) < 2^{-n} $. Applying Borel-Cantelli to the
sequence of sets $A_n = {x | |f_{m_n}(x) - f(x)| > 1/n}$ yields
$mu(limsup_m cup_{n=m}^infty A_n) = 0$. But this is simply saying
that the set of points on which $f_{m_n}$ doesn’t converge to $f$ has
measure $0$.




As someone who has not been very much exposed to "diagonalization arguments", I wonder if the examples above have something in common, so that we may answer what "diagonalization argument" is and what kinds of problems it may help to solve?










share|cite|improve this question











$endgroup$

















    9












    $begingroup$


    From Wikipedia:




    A variety of diagonal arguments are used in mathematics.




    • Cantor's diagonal argument

    • Cantor's theorem

    • Halting problem

    • Diagonal lemma




    Besides the above four examples, there is another one I found in a blog. When proving that "if a sequence of measurable mappings converges in measure, then there is a subsequence converging a.e.", the construction of the subsequence is also called diagonalization:




    The method for establishing this result is fairly typical of such
    arguments: we rely on diagonalization along with the control that
    Borel-Cantelli gives us. Let $f_n$ be a sequence that converges in
    measure to $f$. This means that for any n we have a $f_{m_n}$ with
    $mu(|f_{m_n} - f| > 1/n) < 2^{-n} $. Applying Borel-Cantelli to the
    sequence of sets $A_n = {x | |f_{m_n}(x) - f(x)| > 1/n}$ yields
    $mu(limsup_m cup_{n=m}^infty A_n) = 0$. But this is simply saying
    that the set of points on which $f_{m_n}$ doesn’t converge to $f$ has
    measure $0$.




    As someone who has not been very much exposed to "diagonalization arguments", I wonder if the examples above have something in common, so that we may answer what "diagonalization argument" is and what kinds of problems it may help to solve?










    share|cite|improve this question











    $endgroup$















      9












      9








      9


      2



      $begingroup$


      From Wikipedia:




      A variety of diagonal arguments are used in mathematics.




      • Cantor's diagonal argument

      • Cantor's theorem

      • Halting problem

      • Diagonal lemma




      Besides the above four examples, there is another one I found in a blog. When proving that "if a sequence of measurable mappings converges in measure, then there is a subsequence converging a.e.", the construction of the subsequence is also called diagonalization:




      The method for establishing this result is fairly typical of such
      arguments: we rely on diagonalization along with the control that
      Borel-Cantelli gives us. Let $f_n$ be a sequence that converges in
      measure to $f$. This means that for any n we have a $f_{m_n}$ with
      $mu(|f_{m_n} - f| > 1/n) < 2^{-n} $. Applying Borel-Cantelli to the
      sequence of sets $A_n = {x | |f_{m_n}(x) - f(x)| > 1/n}$ yields
      $mu(limsup_m cup_{n=m}^infty A_n) = 0$. But this is simply saying
      that the set of points on which $f_{m_n}$ doesn’t converge to $f$ has
      measure $0$.




      As someone who has not been very much exposed to "diagonalization arguments", I wonder if the examples above have something in common, so that we may answer what "diagonalization argument" is and what kinds of problems it may help to solve?










      share|cite|improve this question











      $endgroup$




      From Wikipedia:




      A variety of diagonal arguments are used in mathematics.




      • Cantor's diagonal argument

      • Cantor's theorem

      • Halting problem

      • Diagonal lemma




      Besides the above four examples, there is another one I found in a blog. When proving that "if a sequence of measurable mappings converges in measure, then there is a subsequence converging a.e.", the construction of the subsequence is also called diagonalization:




      The method for establishing this result is fairly typical of such
      arguments: we rely on diagonalization along with the control that
      Borel-Cantelli gives us. Let $f_n$ be a sequence that converges in
      measure to $f$. This means that for any n we have a $f_{m_n}$ with
      $mu(|f_{m_n} - f| > 1/n) < 2^{-n} $. Applying Borel-Cantelli to the
      sequence of sets $A_n = {x | |f_{m_n}(x) - f(x)| > 1/n}$ yields
      $mu(limsup_m cup_{n=m}^infty A_n) = 0$. But this is simply saying
      that the set of points on which $f_{m_n}$ doesn’t converge to $f$ has
      measure $0$.




      As someone who has not been very much exposed to "diagonalization arguments", I wonder if the examples above have something in common, so that we may answer what "diagonalization argument" is and what kinds of problems it may help to solve?







      soft-question






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited Dec 19 '18 at 8:36









      Morgan Sinclaire

      706




      706










      asked Mar 12 '12 at 1:44









      TimTim

      16.6k21123330




      16.6k21123330






















          3 Answers
          3






          active

          oldest

          votes


















          5












          $begingroup$

          Someone with more experience might be better equipped to address this question, but here's my perspective. "Diagonal arguments" are often invoked when dealings with functions or maps. In order to show the existence or non-existence of a certain sort of map, we create a large array of all the possible inputs and outputs. Moving along the diagonal, we use a self-referential construction to introduce an object that cannot possibly be on the list, and the desired object is obtained.



          Cantor's Diagonal Argument: The maps are elements in $mathbb{N}^{mathbb{N}} = mathbb{R}$. The diagonalization is done by changing an element in every diagonal entry.



          Halting Problem: The maps are partial recursive functions. The killer $K$ program encodes the diagonalization.



          Diagonal Lemma / Fixed Point Lemma: The maps are formulas, with input being the codes of sentences. The diagonalization is accomplished by a somewhat confusing self-referential construction.



          Cantor's Theorem ($|A| < |P(A)|$) : The maps are the correspondences between elements of $A$ and elements in $P(A)$. Diagonalization is accomplished by considering a self-referential subset in $P(A)$ that nothing can map to.






          share|cite|improve this answer









          $endgroup$









          • 1




            $begingroup$
            +1 Thanks! (1) Do "inputs and outputs" mean domain and codomain values of a map? (2) What does "self-referential" mean in "self-referential construction"? (3) In "to introduce an object that cannot possibly be on the list", does an "object" mean a map, and does the "list" mean the certain sort of maps?
            $endgroup$
            – Tim
            Mar 12 '12 at 2:31












          • $begingroup$
            (1) Generally, yes. I say "generally" because the notion of a "diagonalization" argument is a broad one that I find hard to pin down. (2) In the Halting Problem, you try to plug a function into itself. In Cantor's theorem, you consider the subset of $P(A)$ of all elements that do not map to sets containing themselves. Any element that maps to this strange set says something very peculiar about itself. (3) Yep. By an object, I mean a list. By a list, I mean an enumeration of all possible "domains" and "codomains".
            $endgroup$
            – Elchanan Solomon
            Mar 12 '12 at 2:46



















          4












          $begingroup$

          Yes, I would consider the "diagonal argument" a general proof-construction technique, similar to, say, the pigeonhole principle or other combinatorial principles.



          Perhaps the most general form of the diagonal argument is the following:




          Theorem: Let $X$ be a set with more than one member, let $I$ be an arbitrary set, and let $X^I$ denote the set of functions from $I$ to $X$. Then there exists no surjection from $I$ to $X^I$.




          Proof: Let $f$ be a function from $I$ to $X^I$, and let $a$ and $b$ be distinct members of $X$. For notational convenience, let $f_i$ denote the function $f(i)$. We construct a function $g in X^I$ as follows:



          $$g(i) = begin{cases} a & text{if }f_i(i) ne a \ b & text{if }f_i(i) = a end{cases}$$



          By construction, for every $i in I$, $g(i) ne f_i(i)$, and thus $g ne f_i$. Therefore $g$ is not in the image of $f$, and thus $f$ is not a surjection. $square$



          (Correction: Contrary to what I originally wrote, the proof above does work also for $I = emptyset$. In that case, the only function $f: I to X^I$ is the empty function, which is indeed not surjective, and the construction above vacuously but correctly yields a counterexample $g in X^I$, where $g$ is itself the empty function from $I$ to $X$.)



          By setting up a bijection between the powerset $mathcal P(I)$ and the set ${0,1}^I$ (sometimes written as $2^I$), we also obtain the following corollary:




          Corollary: There exists no surjection from $I$ to $mathcal P(I)$.




          A nice feature of this particular form of the diagonal argument is that it makes very few logical or set-theoretical assumptions: for instance, it doesn't use proof by contradiction or make any reference to cardinalities. Thus, it works even in many oddball versions of logic and set theory than some people occasionally consider. However, in standard set theory, the theorem above can be given a more succint form:




          Corollary: If $X$ has more than one member, then $X^I$ has strictly greater cardinality than $I$. Also, $mathcal P(I)$ has strictly greater cardinality than $I$.







          share|cite|improve this answer











          $endgroup$





















            2












            $begingroup$

            The Arzelà Ascoli theorem is an instance of this. See http://en.wikipedia.org/wiki/Arzel%C3%A0%E2%80%93Ascoli_theorem. What is interesting about this example is that this theorem has applications in differential equations. One example of an application is the theorem that in a hyperbolic surface, every free homotopy class of loops has a unique geodesic in that class.






            share|cite|improve this answer









            $endgroup$














              Your Answer





              StackExchange.ifUsing("editor", function () {
              return StackExchange.using("mathjaxEditing", function () {
              StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
              StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
              });
              });
              }, "mathjax-editing");

              StackExchange.ready(function() {
              var channelOptions = {
              tags: "".split(" "),
              id: "69"
              };
              initTagRenderer("".split(" "), "".split(" "), channelOptions);

              StackExchange.using("externalEditor", function() {
              // Have to fire editor after snippets, if snippets enabled
              if (StackExchange.settings.snippets.snippetsEnabled) {
              StackExchange.using("snippets", function() {
              createEditor();
              });
              }
              else {
              createEditor();
              }
              });

              function createEditor() {
              StackExchange.prepareEditor({
              heartbeatType: 'answer',
              autoActivateHeartbeat: false,
              convertImagesToLinks: true,
              noModals: true,
              showLowRepImageUploadWarning: true,
              reputationToPostImages: 10,
              bindNavPrevention: true,
              postfix: "",
              imageUploader: {
              brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
              contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
              allowUrls: true
              },
              noCode: true, onDemand: true,
              discardSelector: ".discard-answer"
              ,immediatelyShowMarkdownHelp:true
              });


              }
              });














              draft saved

              draft discarded


















              StackExchange.ready(
              function () {
              StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f119089%2fwhat-is-meant-by-a-diagonalization-argument%23new-answer', 'question_page');
              }
              );

              Post as a guest















              Required, but never shown

























              3 Answers
              3






              active

              oldest

              votes








              3 Answers
              3






              active

              oldest

              votes









              active

              oldest

              votes






              active

              oldest

              votes









              5












              $begingroup$

              Someone with more experience might be better equipped to address this question, but here's my perspective. "Diagonal arguments" are often invoked when dealings with functions or maps. In order to show the existence or non-existence of a certain sort of map, we create a large array of all the possible inputs and outputs. Moving along the diagonal, we use a self-referential construction to introduce an object that cannot possibly be on the list, and the desired object is obtained.



              Cantor's Diagonal Argument: The maps are elements in $mathbb{N}^{mathbb{N}} = mathbb{R}$. The diagonalization is done by changing an element in every diagonal entry.



              Halting Problem: The maps are partial recursive functions. The killer $K$ program encodes the diagonalization.



              Diagonal Lemma / Fixed Point Lemma: The maps are formulas, with input being the codes of sentences. The diagonalization is accomplished by a somewhat confusing self-referential construction.



              Cantor's Theorem ($|A| < |P(A)|$) : The maps are the correspondences between elements of $A$ and elements in $P(A)$. Diagonalization is accomplished by considering a self-referential subset in $P(A)$ that nothing can map to.






              share|cite|improve this answer









              $endgroup$









              • 1




                $begingroup$
                +1 Thanks! (1) Do "inputs and outputs" mean domain and codomain values of a map? (2) What does "self-referential" mean in "self-referential construction"? (3) In "to introduce an object that cannot possibly be on the list", does an "object" mean a map, and does the "list" mean the certain sort of maps?
                $endgroup$
                – Tim
                Mar 12 '12 at 2:31












              • $begingroup$
                (1) Generally, yes. I say "generally" because the notion of a "diagonalization" argument is a broad one that I find hard to pin down. (2) In the Halting Problem, you try to plug a function into itself. In Cantor's theorem, you consider the subset of $P(A)$ of all elements that do not map to sets containing themselves. Any element that maps to this strange set says something very peculiar about itself. (3) Yep. By an object, I mean a list. By a list, I mean an enumeration of all possible "domains" and "codomains".
                $endgroup$
                – Elchanan Solomon
                Mar 12 '12 at 2:46
















              5












              $begingroup$

              Someone with more experience might be better equipped to address this question, but here's my perspective. "Diagonal arguments" are often invoked when dealings with functions or maps. In order to show the existence or non-existence of a certain sort of map, we create a large array of all the possible inputs and outputs. Moving along the diagonal, we use a self-referential construction to introduce an object that cannot possibly be on the list, and the desired object is obtained.



              Cantor's Diagonal Argument: The maps are elements in $mathbb{N}^{mathbb{N}} = mathbb{R}$. The diagonalization is done by changing an element in every diagonal entry.



              Halting Problem: The maps are partial recursive functions. The killer $K$ program encodes the diagonalization.



              Diagonal Lemma / Fixed Point Lemma: The maps are formulas, with input being the codes of sentences. The diagonalization is accomplished by a somewhat confusing self-referential construction.



              Cantor's Theorem ($|A| < |P(A)|$) : The maps are the correspondences between elements of $A$ and elements in $P(A)$. Diagonalization is accomplished by considering a self-referential subset in $P(A)$ that nothing can map to.






              share|cite|improve this answer









              $endgroup$









              • 1




                $begingroup$
                +1 Thanks! (1) Do "inputs and outputs" mean domain and codomain values of a map? (2) What does "self-referential" mean in "self-referential construction"? (3) In "to introduce an object that cannot possibly be on the list", does an "object" mean a map, and does the "list" mean the certain sort of maps?
                $endgroup$
                – Tim
                Mar 12 '12 at 2:31












              • $begingroup$
                (1) Generally, yes. I say "generally" because the notion of a "diagonalization" argument is a broad one that I find hard to pin down. (2) In the Halting Problem, you try to plug a function into itself. In Cantor's theorem, you consider the subset of $P(A)$ of all elements that do not map to sets containing themselves. Any element that maps to this strange set says something very peculiar about itself. (3) Yep. By an object, I mean a list. By a list, I mean an enumeration of all possible "domains" and "codomains".
                $endgroup$
                – Elchanan Solomon
                Mar 12 '12 at 2:46














              5












              5








              5





              $begingroup$

              Someone with more experience might be better equipped to address this question, but here's my perspective. "Diagonal arguments" are often invoked when dealings with functions or maps. In order to show the existence or non-existence of a certain sort of map, we create a large array of all the possible inputs and outputs. Moving along the diagonal, we use a self-referential construction to introduce an object that cannot possibly be on the list, and the desired object is obtained.



              Cantor's Diagonal Argument: The maps are elements in $mathbb{N}^{mathbb{N}} = mathbb{R}$. The diagonalization is done by changing an element in every diagonal entry.



              Halting Problem: The maps are partial recursive functions. The killer $K$ program encodes the diagonalization.



              Diagonal Lemma / Fixed Point Lemma: The maps are formulas, with input being the codes of sentences. The diagonalization is accomplished by a somewhat confusing self-referential construction.



              Cantor's Theorem ($|A| < |P(A)|$) : The maps are the correspondences between elements of $A$ and elements in $P(A)$. Diagonalization is accomplished by considering a self-referential subset in $P(A)$ that nothing can map to.






              share|cite|improve this answer









              $endgroup$



              Someone with more experience might be better equipped to address this question, but here's my perspective. "Diagonal arguments" are often invoked when dealings with functions or maps. In order to show the existence or non-existence of a certain sort of map, we create a large array of all the possible inputs and outputs. Moving along the diagonal, we use a self-referential construction to introduce an object that cannot possibly be on the list, and the desired object is obtained.



              Cantor's Diagonal Argument: The maps are elements in $mathbb{N}^{mathbb{N}} = mathbb{R}$. The diagonalization is done by changing an element in every diagonal entry.



              Halting Problem: The maps are partial recursive functions. The killer $K$ program encodes the diagonalization.



              Diagonal Lemma / Fixed Point Lemma: The maps are formulas, with input being the codes of sentences. The diagonalization is accomplished by a somewhat confusing self-referential construction.



              Cantor's Theorem ($|A| < |P(A)|$) : The maps are the correspondences between elements of $A$ and elements in $P(A)$. Diagonalization is accomplished by considering a self-referential subset in $P(A)$ that nothing can map to.







              share|cite|improve this answer












              share|cite|improve this answer



              share|cite|improve this answer










              answered Mar 12 '12 at 2:03









              Elchanan SolomonElchanan Solomon

              22k54277




              22k54277








              • 1




                $begingroup$
                +1 Thanks! (1) Do "inputs and outputs" mean domain and codomain values of a map? (2) What does "self-referential" mean in "self-referential construction"? (3) In "to introduce an object that cannot possibly be on the list", does an "object" mean a map, and does the "list" mean the certain sort of maps?
                $endgroup$
                – Tim
                Mar 12 '12 at 2:31












              • $begingroup$
                (1) Generally, yes. I say "generally" because the notion of a "diagonalization" argument is a broad one that I find hard to pin down. (2) In the Halting Problem, you try to plug a function into itself. In Cantor's theorem, you consider the subset of $P(A)$ of all elements that do not map to sets containing themselves. Any element that maps to this strange set says something very peculiar about itself. (3) Yep. By an object, I mean a list. By a list, I mean an enumeration of all possible "domains" and "codomains".
                $endgroup$
                – Elchanan Solomon
                Mar 12 '12 at 2:46














              • 1




                $begingroup$
                +1 Thanks! (1) Do "inputs and outputs" mean domain and codomain values of a map? (2) What does "self-referential" mean in "self-referential construction"? (3) In "to introduce an object that cannot possibly be on the list", does an "object" mean a map, and does the "list" mean the certain sort of maps?
                $endgroup$
                – Tim
                Mar 12 '12 at 2:31












              • $begingroup$
                (1) Generally, yes. I say "generally" because the notion of a "diagonalization" argument is a broad one that I find hard to pin down. (2) In the Halting Problem, you try to plug a function into itself. In Cantor's theorem, you consider the subset of $P(A)$ of all elements that do not map to sets containing themselves. Any element that maps to this strange set says something very peculiar about itself. (3) Yep. By an object, I mean a list. By a list, I mean an enumeration of all possible "domains" and "codomains".
                $endgroup$
                – Elchanan Solomon
                Mar 12 '12 at 2:46








              1




              1




              $begingroup$
              +1 Thanks! (1) Do "inputs and outputs" mean domain and codomain values of a map? (2) What does "self-referential" mean in "self-referential construction"? (3) In "to introduce an object that cannot possibly be on the list", does an "object" mean a map, and does the "list" mean the certain sort of maps?
              $endgroup$
              – Tim
              Mar 12 '12 at 2:31






              $begingroup$
              +1 Thanks! (1) Do "inputs and outputs" mean domain and codomain values of a map? (2) What does "self-referential" mean in "self-referential construction"? (3) In "to introduce an object that cannot possibly be on the list", does an "object" mean a map, and does the "list" mean the certain sort of maps?
              $endgroup$
              – Tim
              Mar 12 '12 at 2:31














              $begingroup$
              (1) Generally, yes. I say "generally" because the notion of a "diagonalization" argument is a broad one that I find hard to pin down. (2) In the Halting Problem, you try to plug a function into itself. In Cantor's theorem, you consider the subset of $P(A)$ of all elements that do not map to sets containing themselves. Any element that maps to this strange set says something very peculiar about itself. (3) Yep. By an object, I mean a list. By a list, I mean an enumeration of all possible "domains" and "codomains".
              $endgroup$
              – Elchanan Solomon
              Mar 12 '12 at 2:46




              $begingroup$
              (1) Generally, yes. I say "generally" because the notion of a "diagonalization" argument is a broad one that I find hard to pin down. (2) In the Halting Problem, you try to plug a function into itself. In Cantor's theorem, you consider the subset of $P(A)$ of all elements that do not map to sets containing themselves. Any element that maps to this strange set says something very peculiar about itself. (3) Yep. By an object, I mean a list. By a list, I mean an enumeration of all possible "domains" and "codomains".
              $endgroup$
              – Elchanan Solomon
              Mar 12 '12 at 2:46











              4












              $begingroup$

              Yes, I would consider the "diagonal argument" a general proof-construction technique, similar to, say, the pigeonhole principle or other combinatorial principles.



              Perhaps the most general form of the diagonal argument is the following:




              Theorem: Let $X$ be a set with more than one member, let $I$ be an arbitrary set, and let $X^I$ denote the set of functions from $I$ to $X$. Then there exists no surjection from $I$ to $X^I$.




              Proof: Let $f$ be a function from $I$ to $X^I$, and let $a$ and $b$ be distinct members of $X$. For notational convenience, let $f_i$ denote the function $f(i)$. We construct a function $g in X^I$ as follows:



              $$g(i) = begin{cases} a & text{if }f_i(i) ne a \ b & text{if }f_i(i) = a end{cases}$$



              By construction, for every $i in I$, $g(i) ne f_i(i)$, and thus $g ne f_i$. Therefore $g$ is not in the image of $f$, and thus $f$ is not a surjection. $square$



              (Correction: Contrary to what I originally wrote, the proof above does work also for $I = emptyset$. In that case, the only function $f: I to X^I$ is the empty function, which is indeed not surjective, and the construction above vacuously but correctly yields a counterexample $g in X^I$, where $g$ is itself the empty function from $I$ to $X$.)



              By setting up a bijection between the powerset $mathcal P(I)$ and the set ${0,1}^I$ (sometimes written as $2^I$), we also obtain the following corollary:




              Corollary: There exists no surjection from $I$ to $mathcal P(I)$.




              A nice feature of this particular form of the diagonal argument is that it makes very few logical or set-theoretical assumptions: for instance, it doesn't use proof by contradiction or make any reference to cardinalities. Thus, it works even in many oddball versions of logic and set theory than some people occasionally consider. However, in standard set theory, the theorem above can be given a more succint form:




              Corollary: If $X$ has more than one member, then $X^I$ has strictly greater cardinality than $I$. Also, $mathcal P(I)$ has strictly greater cardinality than $I$.







              share|cite|improve this answer











              $endgroup$


















                4












                $begingroup$

                Yes, I would consider the "diagonal argument" a general proof-construction technique, similar to, say, the pigeonhole principle or other combinatorial principles.



                Perhaps the most general form of the diagonal argument is the following:




                Theorem: Let $X$ be a set with more than one member, let $I$ be an arbitrary set, and let $X^I$ denote the set of functions from $I$ to $X$. Then there exists no surjection from $I$ to $X^I$.




                Proof: Let $f$ be a function from $I$ to $X^I$, and let $a$ and $b$ be distinct members of $X$. For notational convenience, let $f_i$ denote the function $f(i)$. We construct a function $g in X^I$ as follows:



                $$g(i) = begin{cases} a & text{if }f_i(i) ne a \ b & text{if }f_i(i) = a end{cases}$$



                By construction, for every $i in I$, $g(i) ne f_i(i)$, and thus $g ne f_i$. Therefore $g$ is not in the image of $f$, and thus $f$ is not a surjection. $square$



                (Correction: Contrary to what I originally wrote, the proof above does work also for $I = emptyset$. In that case, the only function $f: I to X^I$ is the empty function, which is indeed not surjective, and the construction above vacuously but correctly yields a counterexample $g in X^I$, where $g$ is itself the empty function from $I$ to $X$.)



                By setting up a bijection between the powerset $mathcal P(I)$ and the set ${0,1}^I$ (sometimes written as $2^I$), we also obtain the following corollary:




                Corollary: There exists no surjection from $I$ to $mathcal P(I)$.




                A nice feature of this particular form of the diagonal argument is that it makes very few logical or set-theoretical assumptions: for instance, it doesn't use proof by contradiction or make any reference to cardinalities. Thus, it works even in many oddball versions of logic and set theory than some people occasionally consider. However, in standard set theory, the theorem above can be given a more succint form:




                Corollary: If $X$ has more than one member, then $X^I$ has strictly greater cardinality than $I$. Also, $mathcal P(I)$ has strictly greater cardinality than $I$.







                share|cite|improve this answer











                $endgroup$
















                  4












                  4








                  4





                  $begingroup$

                  Yes, I would consider the "diagonal argument" a general proof-construction technique, similar to, say, the pigeonhole principle or other combinatorial principles.



                  Perhaps the most general form of the diagonal argument is the following:




                  Theorem: Let $X$ be a set with more than one member, let $I$ be an arbitrary set, and let $X^I$ denote the set of functions from $I$ to $X$. Then there exists no surjection from $I$ to $X^I$.




                  Proof: Let $f$ be a function from $I$ to $X^I$, and let $a$ and $b$ be distinct members of $X$. For notational convenience, let $f_i$ denote the function $f(i)$. We construct a function $g in X^I$ as follows:



                  $$g(i) = begin{cases} a & text{if }f_i(i) ne a \ b & text{if }f_i(i) = a end{cases}$$



                  By construction, for every $i in I$, $g(i) ne f_i(i)$, and thus $g ne f_i$. Therefore $g$ is not in the image of $f$, and thus $f$ is not a surjection. $square$



                  (Correction: Contrary to what I originally wrote, the proof above does work also for $I = emptyset$. In that case, the only function $f: I to X^I$ is the empty function, which is indeed not surjective, and the construction above vacuously but correctly yields a counterexample $g in X^I$, where $g$ is itself the empty function from $I$ to $X$.)



                  By setting up a bijection between the powerset $mathcal P(I)$ and the set ${0,1}^I$ (sometimes written as $2^I$), we also obtain the following corollary:




                  Corollary: There exists no surjection from $I$ to $mathcal P(I)$.




                  A nice feature of this particular form of the diagonal argument is that it makes very few logical or set-theoretical assumptions: for instance, it doesn't use proof by contradiction or make any reference to cardinalities. Thus, it works even in many oddball versions of logic and set theory than some people occasionally consider. However, in standard set theory, the theorem above can be given a more succint form:




                  Corollary: If $X$ has more than one member, then $X^I$ has strictly greater cardinality than $I$. Also, $mathcal P(I)$ has strictly greater cardinality than $I$.







                  share|cite|improve this answer











                  $endgroup$



                  Yes, I would consider the "diagonal argument" a general proof-construction technique, similar to, say, the pigeonhole principle or other combinatorial principles.



                  Perhaps the most general form of the diagonal argument is the following:




                  Theorem: Let $X$ be a set with more than one member, let $I$ be an arbitrary set, and let $X^I$ denote the set of functions from $I$ to $X$. Then there exists no surjection from $I$ to $X^I$.




                  Proof: Let $f$ be a function from $I$ to $X^I$, and let $a$ and $b$ be distinct members of $X$. For notational convenience, let $f_i$ denote the function $f(i)$. We construct a function $g in X^I$ as follows:



                  $$g(i) = begin{cases} a & text{if }f_i(i) ne a \ b & text{if }f_i(i) = a end{cases}$$



                  By construction, for every $i in I$, $g(i) ne f_i(i)$, and thus $g ne f_i$. Therefore $g$ is not in the image of $f$, and thus $f$ is not a surjection. $square$



                  (Correction: Contrary to what I originally wrote, the proof above does work also for $I = emptyset$. In that case, the only function $f: I to X^I$ is the empty function, which is indeed not surjective, and the construction above vacuously but correctly yields a counterexample $g in X^I$, where $g$ is itself the empty function from $I$ to $X$.)



                  By setting up a bijection between the powerset $mathcal P(I)$ and the set ${0,1}^I$ (sometimes written as $2^I$), we also obtain the following corollary:




                  Corollary: There exists no surjection from $I$ to $mathcal P(I)$.




                  A nice feature of this particular form of the diagonal argument is that it makes very few logical or set-theoretical assumptions: for instance, it doesn't use proof by contradiction or make any reference to cardinalities. Thus, it works even in many oddball versions of logic and set theory than some people occasionally consider. However, in standard set theory, the theorem above can be given a more succint form:




                  Corollary: If $X$ has more than one member, then $X^I$ has strictly greater cardinality than $I$. Also, $mathcal P(I)$ has strictly greater cardinality than $I$.








                  share|cite|improve this answer














                  share|cite|improve this answer



                  share|cite|improve this answer








                  edited Apr 13 '17 at 12:19









                  Community

                  1




                  1










                  answered Mar 16 '12 at 1:27









                  Ilmari KaronenIlmari Karonen

                  20.1k25186




                  20.1k25186























                      2












                      $begingroup$

                      The Arzelà Ascoli theorem is an instance of this. See http://en.wikipedia.org/wiki/Arzel%C3%A0%E2%80%93Ascoli_theorem. What is interesting about this example is that this theorem has applications in differential equations. One example of an application is the theorem that in a hyperbolic surface, every free homotopy class of loops has a unique geodesic in that class.






                      share|cite|improve this answer









                      $endgroup$


















                        2












                        $begingroup$

                        The Arzelà Ascoli theorem is an instance of this. See http://en.wikipedia.org/wiki/Arzel%C3%A0%E2%80%93Ascoli_theorem. What is interesting about this example is that this theorem has applications in differential equations. One example of an application is the theorem that in a hyperbolic surface, every free homotopy class of loops has a unique geodesic in that class.






                        share|cite|improve this answer









                        $endgroup$
















                          2












                          2








                          2





                          $begingroup$

                          The Arzelà Ascoli theorem is an instance of this. See http://en.wikipedia.org/wiki/Arzel%C3%A0%E2%80%93Ascoli_theorem. What is interesting about this example is that this theorem has applications in differential equations. One example of an application is the theorem that in a hyperbolic surface, every free homotopy class of loops has a unique geodesic in that class.






                          share|cite|improve this answer









                          $endgroup$



                          The Arzelà Ascoli theorem is an instance of this. See http://en.wikipedia.org/wiki/Arzel%C3%A0%E2%80%93Ascoli_theorem. What is interesting about this example is that this theorem has applications in differential equations. One example of an application is the theorem that in a hyperbolic surface, every free homotopy class of loops has a unique geodesic in that class.







                          share|cite|improve this answer












                          share|cite|improve this answer



                          share|cite|improve this answer










                          answered Jun 21 '12 at 2:16









                          Baby DragonBaby Dragon

                          2,1671526




                          2,1671526






























                              draft saved

                              draft discarded




















































                              Thanks for contributing an answer to Mathematics Stack Exchange!


                              • Please be sure to answer the question. Provide details and share your research!

                              But avoid



                              • Asking for help, clarification, or responding to other answers.

                              • Making statements based on opinion; back them up with references or personal experience.


                              Use MathJax to format equations. MathJax reference.


                              To learn more, see our tips on writing great answers.




                              draft saved


                              draft discarded














                              StackExchange.ready(
                              function () {
                              StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f119089%2fwhat-is-meant-by-a-diagonalization-argument%23new-answer', 'question_page');
                              }
                              );

                              Post as a guest















                              Required, but never shown





















































                              Required, but never shown














                              Required, but never shown












                              Required, but never shown







                              Required, but never shown

































                              Required, but never shown














                              Required, but never shown












                              Required, but never shown







                              Required, but never shown







                              Popular posts from this blog

                              Plaza Victoria

                              Puebla de Zaragoza

                              Musa