Prove constructively that $log_2 3$ is irrational.
$begingroup$
The usual proof that $log_2 3$ is irrational is by contradiction. For instance:
Assume the negation: that $log_2 3 = m/n$ for some integers $m$ and $n$. Then, by the property of logarithms, $2^{m/n} = 3$, which implies that $2^m = 3^n$. However, $2^m$ is even and $3^n$ is odd and an even number cannot be equal to an odd number. Therefore the assumption that $log_2 3$ is rational is wrong.
My understanding is that this form of proof by contradiction (assume the negation and arrive at a contradiction) is using the law of excluded middle (that proving $lnot lnot A$ is the same as proving $A$) and is therefore not a valid constructive proof.
So that leads to my two-part question:
- Is the proof actually okay as a constructive proof (i.e., is my understanding wrong) and if so, why is it okay?
- If it is not valid, what is a constructive proof that $log_2 3$ is irrational?
alternative-proof irrational-numbers constructive-mathematics intuitionistic-logic
asked Dec 21 '18 at 18:38
Ted HoppTed Hopp
1628
$endgroup$
add a comment |
$begingroup$
The usual proof that $log_2 3$ is irrational is by contradiction. For instance:
Assume the negation: that $log_2 3 = m/n$ for some integers $m$ and $n$. Then, by the property of logarithms, $2^{m/n} = 3$, which implies that $2^m = 3^n$. However, $2^m$ is even and $3^n$ is odd and an even number cannot be equal to an odd number. Therefore the assumption that $log_2 3$ is rational is wrong.
My understanding is that this form of proof by contradiction (assume the negation and arrive at a contradiction) is using the law of excluded middle (that proving $lnot lnot A$ is the same as proving $A$) and is therefore not a valid constructive proof.
So that leads to my two-part question:
- Is the proof actually okay as a constructive proof (i.e., is my understanding wrong) and if so, why is it okay?
- If it is not valid, what is a constructive proof that $log_2 3$ is irrational?
alternative-proof irrational-numbers constructive-mathematics intuitionistic-logic
asked Dec 21 '18 at 18:38
Ted HoppTed Hopp
1628
$endgroup$
1
$begingroup$
What exactly do you mean by "constructively"?
$endgroup$
– Frpzzd
Dec 21 '18 at 18:42
$begingroup$
@Frpzzd - See en.wikipedia.org/wiki/Constructive_proof
$endgroup$
– Ted Hopp
Dec 21 '18 at 18:43
add a comment |
$begingroup$
The usual proof that $log_2 3$ is irrational is by contradiction. For instance:
Assume the negation: that $log_2 3 = m/n$ for some integers $m$ and $n$. Then, by the property of logarithms, $2^{m/n} = 3$, which implies that $2^m = 3^n$. However, $2^m$ is even and $3^n$ is odd and an even number cannot be equal to an odd number. Therefore the assumption that $log_2 3$ is rational is wrong.
My understanding is that this form of proof by contradiction (assume the negation and arrive at a contradiction) is using the law of excluded middle (that proving $lnot lnot A$ is the same as proving $A$) and is therefore not a valid constructive proof.
So that leads to my two-part question:
- Is the proof actually okay as a constructive proof (i.e., is my understanding wrong) and if so, why is it okay?
- If it is not valid, what is a constructive proof that $log_2 3$ is irrational?
alternative-proof irrational-numbers constructive-mathematics intuitionistic-logic
asked Dec 21 '18 at 18:38
Ted HoppTed Hopp
1628
$endgroup$
The usual proof that $log_2 3$ is irrational is by contradiction. For instance:
Assume the negation: that $log_2 3 = m/n$ for some integers $m$ and $n$. Then, by the property of logarithms, $2^{m/n} = 3$, which implies that $2^m = 3^n$. However, $2^m$ is even and $3^n$ is odd and an even number cannot be equal to an odd number. Therefore the assumption that $log_2 3$ is rational is wrong.
My understanding is that this form of proof by contradiction (assume the negation and arrive at a contradiction) is using the law of excluded middle (that proving $lnot lnot A$ is the same as proving $A$) and is therefore not a valid constructive proof.
So that leads to my two-part question:
- Is the proof actually okay as a constructive proof (i.e., is my understanding wrong) and if so, why is it okay?
- If it is not valid, what is a constructive proof that $log_2 3$ is irrational?
alternative-proof irrational-numbers constructive-mathematics intuitionistic-logic
alternative-proof irrational-numbers constructive-mathematics intuitionistic-logic
asked Dec 21 '18 at 18:38
Ted HoppTed Hopp
1628
asked Dec 21 '18 at 18:38
Ted HoppTed Hopp
1628
asked Dec 21 '18 at 18:38
Ted HoppTed Hopp
1628
asked Dec 21 '18 at 18:38
Ted HoppTed Hopp
1628
asked Dec 21 '18 at 18:38
Ted HoppTed Hopp
1628
1628
1
$begingroup$
What exactly do you mean by "constructively"?
$endgroup$
– Frpzzd
Dec 21 '18 at 18:42
$begingroup$
@Frpzzd - See en.wikipedia.org/wiki/Constructive_proof
$endgroup$
– Ted Hopp
Dec 21 '18 at 18:43
add a comment |
1
$begingroup$
What exactly do you mean by "constructively"?
$endgroup$
– Frpzzd
Dec 21 '18 at 18:42
$begingroup$
@Frpzzd - See en.wikipedia.org/wiki/Constructive_proof
$endgroup$
– Ted Hopp
Dec 21 '18 at 18:43
1
1
$begingroup$
What exactly do you mean by "constructively"?
$endgroup$
– Frpzzd
Dec 21 '18 at 18:42
$begingroup$
What exactly do you mean by "constructively"?
$endgroup$
– Frpzzd
Dec 21 '18 at 18:42
$begingroup$
@Frpzzd - See en.wikipedia.org/wiki/Constructive_proof
$endgroup$
– Ted Hopp
Dec 21 '18 at 18:43
$begingroup$
@Frpzzd - See en.wikipedia.org/wiki/Constructive_proof
$endgroup$
– Ted Hopp
Dec 21 '18 at 18:43
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
$x$ is irrational is defined as "$x$ is not rational", so a proof that shows that from the assumption that $x$ is rational we derive a contradiction is a valid constructive proof for
"$x$ is not rational", in fact it's the usual proof for such negative statements in e.g. intuitionistic logic.
answered Dec 21 '18 at 18:43
Henno BrandsmaHenno Brandsma
114k348123
$endgroup$
1
$begingroup$
In fact, it's not at all unusual to define $lnot phi$ as being "synactic sugar" for $phi rightarrow bot$; and in that case, a proof of this form would be a special case of the standard ${rightarrow} I$ rule.
$endgroup$
– Daniel Schepler
Dec 21 '18 at 18:45
$begingroup$
So let's see if I understand this. By definition, "$log_2 3$ is irrational" is by definition shorthand for "$log_2 3$ is not rational" and we're proving a negative. Furthermore, in constructivism, any theorem of the form "$lnot A$" can be validly proven by showing that $Avdashbot$? So even though the structure of the proof looks like we're proving $lnot lnot Avdashbot$, that's not what's going on?
$endgroup$
– Ted Hopp
Dec 21 '18 at 20:29
1
$begingroup$
@TedHopp indeed. A negative is proven by contradiction. How else could one prove a negative. But $lnotlnotphi$ does not show $phi$. The linked proof here that there are $a,b$ irrational such that $a^b$ is rational shows this by assuming 'tertium non datur' which is not allowed constructively.
$endgroup$
– Henno Brandsma
Dec 21 '18 at 22:41
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%2f3048782%2fprove-constructively-that-log-2-3-is-irrational%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
$x$ is irrational is defined as "$x$ is not rational", so a proof that shows that from the assumption that $x$ is rational we derive a contradiction is a valid constructive proof for
"$x$ is not rational", in fact it's the usual proof for such negative statements in e.g. intuitionistic logic.
answered Dec 21 '18 at 18:43
Henno BrandsmaHenno Brandsma
114k348123
$endgroup$
1
$begingroup$
In fact, it's not at all unusual to define $lnot phi$ as being "synactic sugar" for $phi rightarrow bot$; and in that case, a proof of this form would be a special case of the standard ${rightarrow} I$ rule.
$endgroup$
– Daniel Schepler
Dec 21 '18 at 18:45
$begingroup$
So let's see if I understand this. By definition, "$log_2 3$ is irrational" is by definition shorthand for "$log_2 3$ is not rational" and we're proving a negative. Furthermore, in constructivism, any theorem of the form "$lnot A$" can be validly proven by showing that $Avdashbot$? So even though the structure of the proof looks like we're proving $lnot lnot Avdashbot$, that's not what's going on?
$endgroup$
– Ted Hopp
Dec 21 '18 at 20:29
1
$begingroup$
@TedHopp indeed. A negative is proven by contradiction. How else could one prove a negative. But $lnotlnotphi$ does not show $phi$. The linked proof here that there are $a,b$ irrational such that $a^b$ is rational shows this by assuming 'tertium non datur' which is not allowed constructively.
$endgroup$
– Henno Brandsma
Dec 21 '18 at 22:41
add a comment |
$begingroup$
$x$ is irrational is defined as "$x$ is not rational", so a proof that shows that from the assumption that $x$ is rational we derive a contradiction is a valid constructive proof for
"$x$ is not rational", in fact it's the usual proof for such negative statements in e.g. intuitionistic logic.
answered Dec 21 '18 at 18:43
Henno BrandsmaHenno Brandsma
114k348123
$endgroup$
1
$begingroup$
In fact, it's not at all unusual to define $lnot phi$ as being "synactic sugar" for $phi rightarrow bot$; and in that case, a proof of this form would be a special case of the standard ${rightarrow} I$ rule.
$endgroup$
– Daniel Schepler
Dec 21 '18 at 18:45
$begingroup$
So let's see if I understand this. By definition, "$log_2 3$ is irrational" is by definition shorthand for "$log_2 3$ is not rational" and we're proving a negative. Furthermore, in constructivism, any theorem of the form "$lnot A$" can be validly proven by showing that $Avdashbot$? So even though the structure of the proof looks like we're proving $lnot lnot Avdashbot$, that's not what's going on?
$endgroup$
– Ted Hopp
Dec 21 '18 at 20:29
1
$begingroup$
@TedHopp indeed. A negative is proven by contradiction. How else could one prove a negative. But $lnotlnotphi$ does not show $phi$. The linked proof here that there are $a,b$ irrational such that $a^b$ is rational shows this by assuming 'tertium non datur' which is not allowed constructively.
$endgroup$
– Henno Brandsma
Dec 21 '18 at 22:41
add a comment |
$begingroup$
$x$ is irrational is defined as "$x$ is not rational", so a proof that shows that from the assumption that $x$ is rational we derive a contradiction is a valid constructive proof for
"$x$ is not rational", in fact it's the usual proof for such negative statements in e.g. intuitionistic logic.
answered Dec 21 '18 at 18:43
Henno BrandsmaHenno Brandsma
114k348123
$endgroup$
$x$ is irrational is defined as "$x$ is not rational", so a proof that shows that from the assumption that $x$ is rational we derive a contradiction is a valid constructive proof for
"$x$ is not rational", in fact it's the usual proof for such negative statements in e.g. intuitionistic logic.
answered Dec 21 '18 at 18:43
Henno BrandsmaHenno Brandsma
114k348123
answered Dec 21 '18 at 18:43
Henno BrandsmaHenno Brandsma
114k348123
answered Dec 21 '18 at 18:43
Henno BrandsmaHenno Brandsma
114k348123
answered Dec 21 '18 at 18:43
Henno BrandsmaHenno Brandsma
114k348123
114k348123
1
$begingroup$
In fact, it's not at all unusual to define $lnot phi$ as being "synactic sugar" for $phi rightarrow bot$; and in that case, a proof of this form would be a special case of the standard ${rightarrow} I$ rule.
$endgroup$
– Daniel Schepler
Dec 21 '18 at 18:45
$begingroup$
So let's see if I understand this. By definition, "$log_2 3$ is irrational" is by definition shorthand for "$log_2 3$ is not rational" and we're proving a negative. Furthermore, in constructivism, any theorem of the form "$lnot A$" can be validly proven by showing that $Avdashbot$? So even though the structure of the proof looks like we're proving $lnot lnot Avdashbot$, that's not what's going on?
$endgroup$
– Ted Hopp
Dec 21 '18 at 20:29
1
$begingroup$
@TedHopp indeed. A negative is proven by contradiction. How else could one prove a negative. But $lnotlnotphi$ does not show $phi$. The linked proof here that there are $a,b$ irrational such that $a^b$ is rational shows this by assuming 'tertium non datur' which is not allowed constructively.
$endgroup$
– Henno Brandsma
Dec 21 '18 at 22:41
add a comment |
1
$begingroup$
In fact, it's not at all unusual to define $lnot phi$ as being "synactic sugar" for $phi rightarrow bot$; and in that case, a proof of this form would be a special case of the standard ${rightarrow} I$ rule.
$endgroup$
– Daniel Schepler
Dec 21 '18 at 18:45
$begingroup$
So let's see if I understand this. By definition, "$log_2 3$ is irrational" is by definition shorthand for "$log_2 3$ is not rational" and we're proving a negative. Furthermore, in constructivism, any theorem of the form "$lnot A$" can be validly proven by showing that $Avdashbot$? So even though the structure of the proof looks like we're proving $lnot lnot Avdashbot$, that's not what's going on?
$endgroup$
– Ted Hopp
Dec 21 '18 at 20:29
1
$begingroup$
@TedHopp indeed. A negative is proven by contradiction. How else could one prove a negative. But $lnotlnotphi$ does not show $phi$. The linked proof here that there are $a,b$ irrational such that $a^b$ is rational shows this by assuming 'tertium non datur' which is not allowed constructively.
$endgroup$
– Henno Brandsma
Dec 21 '18 at 22:41
1
1
$begingroup$
In fact, it's not at all unusual to define $lnot phi$ as being "synactic sugar" for $phi rightarrow bot$; and in that case, a proof of this form would be a special case of the standard ${rightarrow} I$ rule.
$endgroup$
– Daniel Schepler
Dec 21 '18 at 18:45
$begingroup$
In fact, it's not at all unusual to define $lnot phi$ as being "synactic sugar" for $phi rightarrow bot$; and in that case, a proof of this form would be a special case of the standard ${rightarrow} I$ rule.
$endgroup$
– Daniel Schepler
Dec 21 '18 at 18:45
$begingroup$
So let's see if I understand this. By definition, "$log_2 3$ is irrational" is by definition shorthand for "$log_2 3$ is not rational" and we're proving a negative. Furthermore, in constructivism, any theorem of the form "$lnot A$" can be validly proven by showing that $Avdashbot$? So even though the structure of the proof looks like we're proving $lnot lnot Avdashbot$, that's not what's going on?
$endgroup$
– Ted Hopp
Dec 21 '18 at 20:29
$begingroup$
So let's see if I understand this. By definition, "$log_2 3$ is irrational" is by definition shorthand for "$log_2 3$ is not rational" and we're proving a negative. Furthermore, in constructivism, any theorem of the form "$lnot A$" can be validly proven by showing that $Avdashbot$? So even though the structure of the proof looks like we're proving $lnot lnot Avdashbot$, that's not what's going on?
$endgroup$
– Ted Hopp
Dec 21 '18 at 20:29
1
1
$begingroup$
@TedHopp indeed. A negative is proven by contradiction. How else could one prove a negative. But $lnotlnotphi$ does not show $phi$. The linked proof here that there are $a,b$ irrational such that $a^b$ is rational shows this by assuming 'tertium non datur' which is not allowed constructively.
$endgroup$
– Henno Brandsma
Dec 21 '18 at 22:41
$begingroup$
@TedHopp indeed. A negative is proven by contradiction. How else could one prove a negative. But $lnotlnotphi$ does not show $phi$. The linked proof here that there are $a,b$ irrational such that $a^b$ is rational shows this by assuming 'tertium non datur' which is not allowed constructively.
$endgroup$
– Henno Brandsma
Dec 21 '18 at 22:41
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%2f3048782%2fprove-constructively-that-log-2-3-is-irrational%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
1
$begingroup$
What exactly do you mean by "constructively"?
$endgroup$
– Frpzzd
Dec 21 '18 at 18:42
$begingroup$
@Frpzzd - See en.wikipedia.org/wiki/Constructive_proof
$endgroup$
– Ted Hopp
Dec 21 '18 at 18:43