What is meant by a “diagonalization argument”?
$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?
soft-question
$endgroup$
add a comment |
$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?
soft-question
$endgroup$
add a comment |
$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?
soft-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
soft-question
edited Dec 19 '18 at 8:36
Morgan Sinclaire
706
706
asked Mar 12 '12 at 1:44
TimTim
16.6k21123330
16.6k21123330
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$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.
$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
add a comment |
$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$.
$endgroup$
add a comment |
$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.
$endgroup$
add a comment |
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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
$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.
$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
add a comment |
$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.
$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
add a comment |
$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.
$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.
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
add a comment |
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
add a comment |
$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$.
$endgroup$
add a comment |
$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$.
$endgroup$
add a comment |
$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$.
$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$.
edited Apr 13 '17 at 12:19
Community♦
1
1
answered Mar 16 '12 at 1:27
Ilmari KaronenIlmari Karonen
20.1k25186
20.1k25186
add a comment |
add a comment |
$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.
$endgroup$
add a comment |
$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.
$endgroup$
add a comment |
$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.
$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.
answered Jun 21 '12 at 2:16
Baby DragonBaby Dragon
2,1671526
2,1671526
add a comment |
add a comment |
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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