A statement following from the law of excluded middle
$begingroup$
Does the statement ~~$Aequiv A$ follow from the law of excluded middle?
According to my book which is not on logic it does, but I do not know how to use the law of excluded middle for this simple tautology.
logic propositional-calculus
asked Aug 26 '18 at 16:14
User12239User12239
453216
$endgroup$
add a comment |
$begingroup$
Does the statement ~~$Aequiv A$ follow from the law of excluded middle?
According to my book which is not on logic it does, but I do not know how to use the law of excluded middle for this simple tautology.
logic propositional-calculus
asked Aug 26 '18 at 16:14
User12239User12239
453216
$endgroup$
add a comment |
$begingroup$
Does the statement ~~$Aequiv A$ follow from the law of excluded middle?
According to my book which is not on logic it does, but I do not know how to use the law of excluded middle for this simple tautology.
logic propositional-calculus
asked Aug 26 '18 at 16:14
User12239User12239
453216
$endgroup$
Does the statement ~~$Aequiv A$ follow from the law of excluded middle?
According to my book which is not on logic it does, but I do not know how to use the law of excluded middle for this simple tautology.
logic propositional-calculus
logic propositional-calculus
asked Aug 26 '18 at 16:14
User12239User12239
453216
asked Aug 26 '18 at 16:14
User12239User12239
453216
asked Aug 26 '18 at 16:14
User12239User12239
453216
asked Aug 26 '18 at 16:14
User12239User12239
453216
asked Aug 26 '18 at 16:14
User12239User12239
453216
453216
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
Assume $A$ and $neg A$. Then $Aland neg A$, which is absurd, hence $negneg A$. So $Aimplies negneg A$: this holds without the law of excluded middle.
Now assume $negneg A$. If $A$, then $A$.
If $neg A$, then $neg Aland negneg A$ which is absurd, hence $A$.
So whether $A$ holds or $neg A$ holds, we always get that $A$ holds : thus [it's this "thus" that uses the law of excluded middle] $negneg Aimplies A$
answered Aug 26 '18 at 17:17
MaxMax
14.3k11142
$endgroup$
$begingroup$
Thanks for your complete illustration
$endgroup$
– User12239
Aug 26 '18 at 18:23
$begingroup$
You should probably add that you are using the principle of explosion, if not it is not explicit how you go from "which is absurd" to "hence A". It turns out that you cannot get DNE (double-negation elimination) from LEM without EX (explosion), even though we can get both LEM and EX from DNE over the other standard rules.
$endgroup$
– user21820
Sep 21 '18 at 5:43
$begingroup$
@user21820 : explosion is a standard rule, isn't it ?
$endgroup$
– Max
Sep 21 '18 at 5:53
$begingroup$
Well... it is of course standard in classical logic, but here we are obviously talking about weaker systems than classical, so that you can investigate the relation between DNE and LEM over those weaker systems. If you look at a Fitch-style system, you see that the rules for $land,to$ are like definitions of one-line/expanded forms, rather than assumptions. And the rules for $lor$ are quite natural if you treat $lor$ as meaning branching (such as via game semantics). $neg,bot$ are different though, so I think it is better to explicitly state the rules for them that are involved here. =)
$endgroup$
– user21820
Sep 21 '18 at 6:03
$begingroup$
@user21820 : surely for weaker systems it is useful to state that; but it is standard in intuitionistic logic as well for instance, which is (it seems to me - but I get your point) what the question seemed to be aiming at
$endgroup$
– Max
Sep 21 '18 at 8:02
|
show 2 more comments
$begingroup$
An informal argument showing that $lnot lnot A equiv A$ follows from the law of excluded middle is the following: by the law of excluded middle, either $A$ or $lnot A$ holds, there is no third option. So, $lnot lnot A$ (whose truth value is determined by the truth value of $A$) should be equivalent to either $A$ or $lnot A$. Since $lnot lnot A$ is the negation of $lnot A$, it is impossible that $lnot lnot A$ and $lnot A$ hold at the same time and hence they are not equivalent. Therefore, $lnot lnot A$ is equivalent to $A$.
answered Aug 26 '18 at 17:00
TaroccoesbroccoTaroccoesbrocco
5,32871839
$endgroup$
$begingroup$
Why talk about "equivalent" ?
$endgroup$
– Max
Aug 26 '18 at 17:14
$begingroup$
@Max - What is wrong with the word "equivalent"?
$endgroup$
– Taroccoesbrocco
Aug 26 '18 at 17:27
$begingroup$
Well, I agree that it's true in classical logic, but a priori why should the LEM imply that $negneg A$ is equivalent to $A$ or $neg A$ ? Moreover, it's not really what matters: it's not important that $negneg A$ is equivalent to $A$ or to $neg A$
$endgroup$
– Max
Aug 26 '18 at 17:39
2
$begingroup$
@Max: The question asks whether $lnot lnot A$ is equivalent to $A$. Depending on how you state it, one formulation of the law of the excluded middle says that each statement is either true or false - there is no "middle". This is why the rule is called "tertium non datur" after all. So, in any model, $A$ and $lnot A$ have opposite truth values, and the question is whether $lnot lnot$ has the same truth value as $A$ or as $lnot A$. Since $lnot A$ and $lnot (lnot A)$ have opposite truth values, $A$ and $lnot lnot A$ must have the same truth value.
$endgroup$
– Carl Mummert
Aug 26 '18 at 19:11
3
$begingroup$
The interesting thing to me is that the two answers use different viewpoints. They could be looked at as syntactic and semantic. It also strikes me that the first answer could be viewed as looking at LEM as the ability to assume $A lor lnot A$, which is a useful way to look at LEM in the context of constructive mathematics (where we might know LEM holds for some particular statement, and want to use that). The second answer could be viewed as looking at LEM in terms of two-valued semantics, where LEM says that negation is an involution on truth values.
$endgroup$
– Carl Mummert
Aug 26 '18 at 19:15
|
show 3 more comments
$begingroup$
This question isn't clear. Is the question "Can (~~A≡A) follow from the law of the excluded middle" the answer is 'yes'. That follows immediately from every single tautology implying every other tautology. Or equivalently, "all tautologies imply every other tautology."
However, if the question is "does the law of the excluded middle necessarily imply (~~A≡A)", where "imply" gets understood to mean that the law of the excluded middle will appear in any proof of (~~A≡A) where (~~A≡A) is not an axiom, then the answer is 'no'. As a simple example, (~~A -> A) and (A -> ~~A) along with modus ponens and ((A -> B) -> ((B -> A) -> (A ≡ B))) will imply that (~~A ≡ A). There is no law of the excluded middle there, and (~~A≡A) is not an axiom.
answered Aug 27 '18 at 7:25
Doug SpoonwoodDoug Spoonwood
8,00112144
$endgroup$
1
$begingroup$
I got reminded of the proverb of the centipede who forgot how to walk when asked to explain exactly how it dealt with so many legs (a remark in the same book where my question arose from)
$endgroup$
– User12239
Aug 27 '18 at 8:46
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%2f2895192%2fa-statement-following-from-the-law-of-excluded-middle%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$
Assume $A$ and $neg A$. Then $Aland neg A$, which is absurd, hence $negneg A$. So $Aimplies negneg A$: this holds without the law of excluded middle.
Now assume $negneg A$. If $A$, then $A$.
If $neg A$, then $neg Aland negneg A$ which is absurd, hence $A$.
So whether $A$ holds or $neg A$ holds, we always get that $A$ holds : thus [it's this "thus" that uses the law of excluded middle] $negneg Aimplies A$
answered Aug 26 '18 at 17:17
MaxMax
14.3k11142
$endgroup$
$begingroup$
Thanks for your complete illustration
$endgroup$
– User12239
Aug 26 '18 at 18:23
$begingroup$
You should probably add that you are using the principle of explosion, if not it is not explicit how you go from "which is absurd" to "hence A". It turns out that you cannot get DNE (double-negation elimination) from LEM without EX (explosion), even though we can get both LEM and EX from DNE over the other standard rules.
$endgroup$
– user21820
Sep 21 '18 at 5:43
$begingroup$
@user21820 : explosion is a standard rule, isn't it ?
$endgroup$
– Max
Sep 21 '18 at 5:53
$begingroup$
Well... it is of course standard in classical logic, but here we are obviously talking about weaker systems than classical, so that you can investigate the relation between DNE and LEM over those weaker systems. If you look at a Fitch-style system, you see that the rules for $land,to$ are like definitions of one-line/expanded forms, rather than assumptions. And the rules for $lor$ are quite natural if you treat $lor$ as meaning branching (such as via game semantics). $neg,bot$ are different though, so I think it is better to explicitly state the rules for them that are involved here. =)
$endgroup$
– user21820
Sep 21 '18 at 6:03
$begingroup$
@user21820 : surely for weaker systems it is useful to state that; but it is standard in intuitionistic logic as well for instance, which is (it seems to me - but I get your point) what the question seemed to be aiming at
$endgroup$
– Max
Sep 21 '18 at 8:02
|
show 2 more comments
$begingroup$
Assume $A$ and $neg A$. Then $Aland neg A$, which is absurd, hence $negneg A$. So $Aimplies negneg A$: this holds without the law of excluded middle.
Now assume $negneg A$. If $A$, then $A$.
If $neg A$, then $neg Aland negneg A$ which is absurd, hence $A$.
So whether $A$ holds or $neg A$ holds, we always get that $A$ holds : thus [it's this "thus" that uses the law of excluded middle] $negneg Aimplies A$
answered Aug 26 '18 at 17:17
MaxMax
14.3k11142
$endgroup$
$begingroup$
Thanks for your complete illustration
$endgroup$
– User12239
Aug 26 '18 at 18:23
$begingroup$
You should probably add that you are using the principle of explosion, if not it is not explicit how you go from "which is absurd" to "hence A". It turns out that you cannot get DNE (double-negation elimination) from LEM without EX (explosion), even though we can get both LEM and EX from DNE over the other standard rules.
$endgroup$
– user21820
Sep 21 '18 at 5:43
$begingroup$
@user21820 : explosion is a standard rule, isn't it ?
$endgroup$
– Max
Sep 21 '18 at 5:53
$begingroup$
Well... it is of course standard in classical logic, but here we are obviously talking about weaker systems than classical, so that you can investigate the relation between DNE and LEM over those weaker systems. If you look at a Fitch-style system, you see that the rules for $land,to$ are like definitions of one-line/expanded forms, rather than assumptions. And the rules for $lor$ are quite natural if you treat $lor$ as meaning branching (such as via game semantics). $neg,bot$ are different though, so I think it is better to explicitly state the rules for them that are involved here. =)
$endgroup$
– user21820
Sep 21 '18 at 6:03
$begingroup$
@user21820 : surely for weaker systems it is useful to state that; but it is standard in intuitionistic logic as well for instance, which is (it seems to me - but I get your point) what the question seemed to be aiming at
$endgroup$
– Max
Sep 21 '18 at 8:02
|
show 2 more comments
$begingroup$
Assume $A$ and $neg A$. Then $Aland neg A$, which is absurd, hence $negneg A$. So $Aimplies negneg A$: this holds without the law of excluded middle.
Now assume $negneg A$. If $A$, then $A$.
If $neg A$, then $neg Aland negneg A$ which is absurd, hence $A$.
So whether $A$ holds or $neg A$ holds, we always get that $A$ holds : thus [it's this "thus" that uses the law of excluded middle] $negneg Aimplies A$
answered Aug 26 '18 at 17:17
MaxMax
14.3k11142
$endgroup$
Assume $A$ and $neg A$. Then $Aland neg A$, which is absurd, hence $negneg A$. So $Aimplies negneg A$: this holds without the law of excluded middle.
Now assume $negneg A$. If $A$, then $A$.
If $neg A$, then $neg Aland negneg A$ which is absurd, hence $A$.
So whether $A$ holds or $neg A$ holds, we always get that $A$ holds : thus [it's this "thus" that uses the law of excluded middle] $negneg Aimplies A$
answered Aug 26 '18 at 17:17
MaxMax
14.3k11142
answered Aug 26 '18 at 17:17
MaxMax
14.3k11142
answered Aug 26 '18 at 17:17
MaxMax
14.3k11142
answered Aug 26 '18 at 17:17
MaxMax
14.3k11142
14.3k11142
$begingroup$
Thanks for your complete illustration
$endgroup$
– User12239
Aug 26 '18 at 18:23
$begingroup$
You should probably add that you are using the principle of explosion, if not it is not explicit how you go from "which is absurd" to "hence A". It turns out that you cannot get DNE (double-negation elimination) from LEM without EX (explosion), even though we can get both LEM and EX from DNE over the other standard rules.
$endgroup$
– user21820
Sep 21 '18 at 5:43
$begingroup$
@user21820 : explosion is a standard rule, isn't it ?
$endgroup$
– Max
Sep 21 '18 at 5:53
$begingroup$
Well... it is of course standard in classical logic, but here we are obviously talking about weaker systems than classical, so that you can investigate the relation between DNE and LEM over those weaker systems. If you look at a Fitch-style system, you see that the rules for $land,to$ are like definitions of one-line/expanded forms, rather than assumptions. And the rules for $lor$ are quite natural if you treat $lor$ as meaning branching (such as via game semantics). $neg,bot$ are different though, so I think it is better to explicitly state the rules for them that are involved here. =)
$endgroup$
– user21820
Sep 21 '18 at 6:03
$begingroup$
@user21820 : surely for weaker systems it is useful to state that; but it is standard in intuitionistic logic as well for instance, which is (it seems to me - but I get your point) what the question seemed to be aiming at
$endgroup$
– Max
Sep 21 '18 at 8:02
|
show 2 more comments
$begingroup$
Thanks for your complete illustration
$endgroup$
– User12239
Aug 26 '18 at 18:23
$begingroup$
You should probably add that you are using the principle of explosion, if not it is not explicit how you go from "which is absurd" to "hence A". It turns out that you cannot get DNE (double-negation elimination) from LEM without EX (explosion), even though we can get both LEM and EX from DNE over the other standard rules.
$endgroup$
– user21820
Sep 21 '18 at 5:43
$begingroup$
@user21820 : explosion is a standard rule, isn't it ?
$endgroup$
– Max
Sep 21 '18 at 5:53
$begingroup$
Well... it is of course standard in classical logic, but here we are obviously talking about weaker systems than classical, so that you can investigate the relation between DNE and LEM over those weaker systems. If you look at a Fitch-style system, you see that the rules for $land,to$ are like definitions of one-line/expanded forms, rather than assumptions. And the rules for $lor$ are quite natural if you treat $lor$ as meaning branching (such as via game semantics). $neg,bot$ are different though, so I think it is better to explicitly state the rules for them that are involved here. =)
$endgroup$
– user21820
Sep 21 '18 at 6:03
$begingroup$
@user21820 : surely for weaker systems it is useful to state that; but it is standard in intuitionistic logic as well for instance, which is (it seems to me - but I get your point) what the question seemed to be aiming at
$endgroup$
– Max
Sep 21 '18 at 8:02
$begingroup$
Thanks for your complete illustration
$endgroup$
– User12239
Aug 26 '18 at 18:23
$begingroup$
Thanks for your complete illustration
$endgroup$
– User12239
Aug 26 '18 at 18:23
$begingroup$
You should probably add that you are using the principle of explosion, if not it is not explicit how you go from "which is absurd" to "hence A". It turns out that you cannot get DNE (double-negation elimination) from LEM without EX (explosion), even though we can get both LEM and EX from DNE over the other standard rules.
$endgroup$
– user21820
Sep 21 '18 at 5:43
$begingroup$
You should probably add that you are using the principle of explosion, if not it is not explicit how you go from "which is absurd" to "hence A". It turns out that you cannot get DNE (double-negation elimination) from LEM without EX (explosion), even though we can get both LEM and EX from DNE over the other standard rules.
$endgroup$
– user21820
Sep 21 '18 at 5:43
$begingroup$
@user21820 : explosion is a standard rule, isn't it ?
$endgroup$
– Max
Sep 21 '18 at 5:53
$begingroup$
@user21820 : explosion is a standard rule, isn't it ?
$endgroup$
– Max
Sep 21 '18 at 5:53
$begingroup$
Well... it is of course standard in classical logic, but here we are obviously talking about weaker systems than classical, so that you can investigate the relation between DNE and LEM over those weaker systems. If you look at a Fitch-style system, you see that the rules for $land,to$ are like definitions of one-line/expanded forms, rather than assumptions. And the rules for $lor$ are quite natural if you treat $lor$ as meaning branching (such as via game semantics). $neg,bot$ are different though, so I think it is better to explicitly state the rules for them that are involved here. =)
$endgroup$
– user21820
Sep 21 '18 at 6:03
$begingroup$
Well... it is of course standard in classical logic, but here we are obviously talking about weaker systems than classical, so that you can investigate the relation between DNE and LEM over those weaker systems. If you look at a Fitch-style system, you see that the rules for $land,to$ are like definitions of one-line/expanded forms, rather than assumptions. And the rules for $lor$ are quite natural if you treat $lor$ as meaning branching (such as via game semantics). $neg,bot$ are different though, so I think it is better to explicitly state the rules for them that are involved here. =)
$endgroup$
– user21820
Sep 21 '18 at 6:03
$begingroup$
@user21820 : surely for weaker systems it is useful to state that; but it is standard in intuitionistic logic as well for instance, which is (it seems to me - but I get your point) what the question seemed to be aiming at
$endgroup$
– Max
Sep 21 '18 at 8:02
$begingroup$
@user21820 : surely for weaker systems it is useful to state that; but it is standard in intuitionistic logic as well for instance, which is (it seems to me - but I get your point) what the question seemed to be aiming at
$endgroup$
– Max
Sep 21 '18 at 8:02
|
show 2 more comments
$begingroup$
An informal argument showing that $lnot lnot A equiv A$ follows from the law of excluded middle is the following: by the law of excluded middle, either $A$ or $lnot A$ holds, there is no third option. So, $lnot lnot A$ (whose truth value is determined by the truth value of $A$) should be equivalent to either $A$ or $lnot A$. Since $lnot lnot A$ is the negation of $lnot A$, it is impossible that $lnot lnot A$ and $lnot A$ hold at the same time and hence they are not equivalent. Therefore, $lnot lnot A$ is equivalent to $A$.
answered Aug 26 '18 at 17:00
TaroccoesbroccoTaroccoesbrocco
5,32871839
$endgroup$
$begingroup$
Why talk about "equivalent" ?
$endgroup$
– Max
Aug 26 '18 at 17:14
$begingroup$
@Max - What is wrong with the word "equivalent"?
$endgroup$
– Taroccoesbrocco
Aug 26 '18 at 17:27
$begingroup$
Well, I agree that it's true in classical logic, but a priori why should the LEM imply that $negneg A$ is equivalent to $A$ or $neg A$ ? Moreover, it's not really what matters: it's not important that $negneg A$ is equivalent to $A$ or to $neg A$
$endgroup$
– Max
Aug 26 '18 at 17:39
2
$begingroup$
@Max: The question asks whether $lnot lnot A$ is equivalent to $A$. Depending on how you state it, one formulation of the law of the excluded middle says that each statement is either true or false - there is no "middle". This is why the rule is called "tertium non datur" after all. So, in any model, $A$ and $lnot A$ have opposite truth values, and the question is whether $lnot lnot$ has the same truth value as $A$ or as $lnot A$. Since $lnot A$ and $lnot (lnot A)$ have opposite truth values, $A$ and $lnot lnot A$ must have the same truth value.
$endgroup$
– Carl Mummert
Aug 26 '18 at 19:11
3
$begingroup$
The interesting thing to me is that the two answers use different viewpoints. They could be looked at as syntactic and semantic. It also strikes me that the first answer could be viewed as looking at LEM as the ability to assume $A lor lnot A$, which is a useful way to look at LEM in the context of constructive mathematics (where we might know LEM holds for some particular statement, and want to use that). The second answer could be viewed as looking at LEM in terms of two-valued semantics, where LEM says that negation is an involution on truth values.
$endgroup$
– Carl Mummert
Aug 26 '18 at 19:15
|
show 3 more comments
$begingroup$
An informal argument showing that $lnot lnot A equiv A$ follows from the law of excluded middle is the following: by the law of excluded middle, either $A$ or $lnot A$ holds, there is no third option. So, $lnot lnot A$ (whose truth value is determined by the truth value of $A$) should be equivalent to either $A$ or $lnot A$. Since $lnot lnot A$ is the negation of $lnot A$, it is impossible that $lnot lnot A$ and $lnot A$ hold at the same time and hence they are not equivalent. Therefore, $lnot lnot A$ is equivalent to $A$.
answered Aug 26 '18 at 17:00
TaroccoesbroccoTaroccoesbrocco
5,32871839
$endgroup$
$begingroup$
Why talk about "equivalent" ?
$endgroup$
– Max
Aug 26 '18 at 17:14
$begingroup$
@Max - What is wrong with the word "equivalent"?
$endgroup$
– Taroccoesbrocco
Aug 26 '18 at 17:27
$begingroup$
Well, I agree that it's true in classical logic, but a priori why should the LEM imply that $negneg A$ is equivalent to $A$ or $neg A$ ? Moreover, it's not really what matters: it's not important that $negneg A$ is equivalent to $A$ or to $neg A$
$endgroup$
– Max
Aug 26 '18 at 17:39
2
$begingroup$
@Max: The question asks whether $lnot lnot A$ is equivalent to $A$. Depending on how you state it, one formulation of the law of the excluded middle says that each statement is either true or false - there is no "middle". This is why the rule is called "tertium non datur" after all. So, in any model, $A$ and $lnot A$ have opposite truth values, and the question is whether $lnot lnot$ has the same truth value as $A$ or as $lnot A$. Since $lnot A$ and $lnot (lnot A)$ have opposite truth values, $A$ and $lnot lnot A$ must have the same truth value.
$endgroup$
– Carl Mummert
Aug 26 '18 at 19:11
3
$begingroup$
The interesting thing to me is that the two answers use different viewpoints. They could be looked at as syntactic and semantic. It also strikes me that the first answer could be viewed as looking at LEM as the ability to assume $A lor lnot A$, which is a useful way to look at LEM in the context of constructive mathematics (where we might know LEM holds for some particular statement, and want to use that). The second answer could be viewed as looking at LEM in terms of two-valued semantics, where LEM says that negation is an involution on truth values.
$endgroup$
– Carl Mummert
Aug 26 '18 at 19:15
|
show 3 more comments
$begingroup$
An informal argument showing that $lnot lnot A equiv A$ follows from the law of excluded middle is the following: by the law of excluded middle, either $A$ or $lnot A$ holds, there is no third option. So, $lnot lnot A$ (whose truth value is determined by the truth value of $A$) should be equivalent to either $A$ or $lnot A$. Since $lnot lnot A$ is the negation of $lnot A$, it is impossible that $lnot lnot A$ and $lnot A$ hold at the same time and hence they are not equivalent. Therefore, $lnot lnot A$ is equivalent to $A$.
answered Aug 26 '18 at 17:00
TaroccoesbroccoTaroccoesbrocco
5,32871839
$endgroup$
An informal argument showing that $lnot lnot A equiv A$ follows from the law of excluded middle is the following: by the law of excluded middle, either $A$ or $lnot A$ holds, there is no third option. So, $lnot lnot A$ (whose truth value is determined by the truth value of $A$) should be equivalent to either $A$ or $lnot A$. Since $lnot lnot A$ is the negation of $lnot A$, it is impossible that $lnot lnot A$ and $lnot A$ hold at the same time and hence they are not equivalent. Therefore, $lnot lnot A$ is equivalent to $A$.
answered Aug 26 '18 at 17:00
TaroccoesbroccoTaroccoesbrocco
5,32871839
edited Aug 26 '18 at 17:36
answered Aug 26 '18 at 17:00
TaroccoesbroccoTaroccoesbrocco
5,32871839
answered Aug 26 '18 at 17:00
TaroccoesbroccoTaroccoesbrocco
5,32871839
answered Aug 26 '18 at 17:00
TaroccoesbroccoTaroccoesbrocco
5,32871839
5,32871839
$begingroup$
Why talk about "equivalent" ?
$endgroup$
– Max
Aug 26 '18 at 17:14
$begingroup$
@Max - What is wrong with the word "equivalent"?
$endgroup$
– Taroccoesbrocco
Aug 26 '18 at 17:27
$begingroup$
Well, I agree that it's true in classical logic, but a priori why should the LEM imply that $negneg A$ is equivalent to $A$ or $neg A$ ? Moreover, it's not really what matters: it's not important that $negneg A$ is equivalent to $A$ or to $neg A$
$endgroup$
– Max
Aug 26 '18 at 17:39
2
$begingroup$
@Max: The question asks whether $lnot lnot A$ is equivalent to $A$. Depending on how you state it, one formulation of the law of the excluded middle says that each statement is either true or false - there is no "middle". This is why the rule is called "tertium non datur" after all. So, in any model, $A$ and $lnot A$ have opposite truth values, and the question is whether $lnot lnot$ has the same truth value as $A$ or as $lnot A$. Since $lnot A$ and $lnot (lnot A)$ have opposite truth values, $A$ and $lnot lnot A$ must have the same truth value.
$endgroup$
– Carl Mummert
Aug 26 '18 at 19:11
3
$begingroup$
The interesting thing to me is that the two answers use different viewpoints. They could be looked at as syntactic and semantic. It also strikes me that the first answer could be viewed as looking at LEM as the ability to assume $A lor lnot A$, which is a useful way to look at LEM in the context of constructive mathematics (where we might know LEM holds for some particular statement, and want to use that). The second answer could be viewed as looking at LEM in terms of two-valued semantics, where LEM says that negation is an involution on truth values.
$endgroup$
– Carl Mummert
Aug 26 '18 at 19:15
|
show 3 more comments
$begingroup$
Why talk about "equivalent" ?
$endgroup$
– Max
Aug 26 '18 at 17:14
$begingroup$
@Max - What is wrong with the word "equivalent"?
$endgroup$
– Taroccoesbrocco
Aug 26 '18 at 17:27
$begingroup$
Well, I agree that it's true in classical logic, but a priori why should the LEM imply that $negneg A$ is equivalent to $A$ or $neg A$ ? Moreover, it's not really what matters: it's not important that $negneg A$ is equivalent to $A$ or to $neg A$
$endgroup$
– Max
Aug 26 '18 at 17:39
2
$begingroup$
@Max: The question asks whether $lnot lnot A$ is equivalent to $A$. Depending on how you state it, one formulation of the law of the excluded middle says that each statement is either true or false - there is no "middle". This is why the rule is called "tertium non datur" after all. So, in any model, $A$ and $lnot A$ have opposite truth values, and the question is whether $lnot lnot$ has the same truth value as $A$ or as $lnot A$. Since $lnot A$ and $lnot (lnot A)$ have opposite truth values, $A$ and $lnot lnot A$ must have the same truth value.
$endgroup$
– Carl Mummert
Aug 26 '18 at 19:11
3
$begingroup$
The interesting thing to me is that the two answers use different viewpoints. They could be looked at as syntactic and semantic. It also strikes me that the first answer could be viewed as looking at LEM as the ability to assume $A lor lnot A$, which is a useful way to look at LEM in the context of constructive mathematics (where we might know LEM holds for some particular statement, and want to use that). The second answer could be viewed as looking at LEM in terms of two-valued semantics, where LEM says that negation is an involution on truth values.
$endgroup$
– Carl Mummert
Aug 26 '18 at 19:15
$begingroup$
Why talk about "equivalent" ?
$endgroup$
– Max
Aug 26 '18 at 17:14
$begingroup$
Why talk about "equivalent" ?
$endgroup$
– Max
Aug 26 '18 at 17:14
$begingroup$
@Max - What is wrong with the word "equivalent"?
$endgroup$
– Taroccoesbrocco
Aug 26 '18 at 17:27
$begingroup$
@Max - What is wrong with the word "equivalent"?
$endgroup$
– Taroccoesbrocco
Aug 26 '18 at 17:27
$begingroup$
Well, I agree that it's true in classical logic, but a priori why should the LEM imply that $negneg A$ is equivalent to $A$ or $neg A$ ? Moreover, it's not really what matters: it's not important that $negneg A$ is equivalent to $A$ or to $neg A$
$endgroup$
– Max
Aug 26 '18 at 17:39
$begingroup$
Well, I agree that it's true in classical logic, but a priori why should the LEM imply that $negneg A$ is equivalent to $A$ or $neg A$ ? Moreover, it's not really what matters: it's not important that $negneg A$ is equivalent to $A$ or to $neg A$
$endgroup$
– Max
Aug 26 '18 at 17:39
2
2
$begingroup$
@Max: The question asks whether $lnot lnot A$ is equivalent to $A$. Depending on how you state it, one formulation of the law of the excluded middle says that each statement is either true or false - there is no "middle". This is why the rule is called "tertium non datur" after all. So, in any model, $A$ and $lnot A$ have opposite truth values, and the question is whether $lnot lnot$ has the same truth value as $A$ or as $lnot A$. Since $lnot A$ and $lnot (lnot A)$ have opposite truth values, $A$ and $lnot lnot A$ must have the same truth value.
$endgroup$
– Carl Mummert
Aug 26 '18 at 19:11
$begingroup$
@Max: The question asks whether $lnot lnot A$ is equivalent to $A$. Depending on how you state it, one formulation of the law of the excluded middle says that each statement is either true or false - there is no "middle". This is why the rule is called "tertium non datur" after all. So, in any model, $A$ and $lnot A$ have opposite truth values, and the question is whether $lnot lnot$ has the same truth value as $A$ or as $lnot A$. Since $lnot A$ and $lnot (lnot A)$ have opposite truth values, $A$ and $lnot lnot A$ must have the same truth value.
$endgroup$
– Carl Mummert
Aug 26 '18 at 19:11
3
3
$begingroup$
The interesting thing to me is that the two answers use different viewpoints. They could be looked at as syntactic and semantic. It also strikes me that the first answer could be viewed as looking at LEM as the ability to assume $A lor lnot A$, which is a useful way to look at LEM in the context of constructive mathematics (where we might know LEM holds for some particular statement, and want to use that). The second answer could be viewed as looking at LEM in terms of two-valued semantics, where LEM says that negation is an involution on truth values.
$endgroup$
– Carl Mummert
Aug 26 '18 at 19:15
$begingroup$
The interesting thing to me is that the two answers use different viewpoints. They could be looked at as syntactic and semantic. It also strikes me that the first answer could be viewed as looking at LEM as the ability to assume $A lor lnot A$, which is a useful way to look at LEM in the context of constructive mathematics (where we might know LEM holds for some particular statement, and want to use that). The second answer could be viewed as looking at LEM in terms of two-valued semantics, where LEM says that negation is an involution on truth values.
$endgroup$
– Carl Mummert
Aug 26 '18 at 19:15
|
show 3 more comments
$begingroup$
This question isn't clear. Is the question "Can (~~A≡A) follow from the law of the excluded middle" the answer is 'yes'. That follows immediately from every single tautology implying every other tautology. Or equivalently, "all tautologies imply every other tautology."
However, if the question is "does the law of the excluded middle necessarily imply (~~A≡A)", where "imply" gets understood to mean that the law of the excluded middle will appear in any proof of (~~A≡A) where (~~A≡A) is not an axiom, then the answer is 'no'. As a simple example, (~~A -> A) and (A -> ~~A) along with modus ponens and ((A -> B) -> ((B -> A) -> (A ≡ B))) will imply that (~~A ≡ A). There is no law of the excluded middle there, and (~~A≡A) is not an axiom.
answered Aug 27 '18 at 7:25
Doug SpoonwoodDoug Spoonwood
8,00112144
$endgroup$
1
$begingroup$
I got reminded of the proverb of the centipede who forgot how to walk when asked to explain exactly how it dealt with so many legs (a remark in the same book where my question arose from)
$endgroup$
– User12239
Aug 27 '18 at 8:46
add a comment |
$begingroup$
This question isn't clear. Is the question "Can (~~A≡A) follow from the law of the excluded middle" the answer is 'yes'. That follows immediately from every single tautology implying every other tautology. Or equivalently, "all tautologies imply every other tautology."
However, if the question is "does the law of the excluded middle necessarily imply (~~A≡A)", where "imply" gets understood to mean that the law of the excluded middle will appear in any proof of (~~A≡A) where (~~A≡A) is not an axiom, then the answer is 'no'. As a simple example, (~~A -> A) and (A -> ~~A) along with modus ponens and ((A -> B) -> ((B -> A) -> (A ≡ B))) will imply that (~~A ≡ A). There is no law of the excluded middle there, and (~~A≡A) is not an axiom.
answered Aug 27 '18 at 7:25
Doug SpoonwoodDoug Spoonwood
8,00112144
$endgroup$
1
$begingroup$
I got reminded of the proverb of the centipede who forgot how to walk when asked to explain exactly how it dealt with so many legs (a remark in the same book where my question arose from)
$endgroup$
– User12239
Aug 27 '18 at 8:46
add a comment |
$begingroup$
This question isn't clear. Is the question "Can (~~A≡A) follow from the law of the excluded middle" the answer is 'yes'. That follows immediately from every single tautology implying every other tautology. Or equivalently, "all tautologies imply every other tautology."
However, if the question is "does the law of the excluded middle necessarily imply (~~A≡A)", where "imply" gets understood to mean that the law of the excluded middle will appear in any proof of (~~A≡A) where (~~A≡A) is not an axiom, then the answer is 'no'. As a simple example, (~~A -> A) and (A -> ~~A) along with modus ponens and ((A -> B) -> ((B -> A) -> (A ≡ B))) will imply that (~~A ≡ A). There is no law of the excluded middle there, and (~~A≡A) is not an axiom.
answered Aug 27 '18 at 7:25
Doug SpoonwoodDoug Spoonwood
8,00112144
$endgroup$
This question isn't clear. Is the question "Can (~~A≡A) follow from the law of the excluded middle" the answer is 'yes'. That follows immediately from every single tautology implying every other tautology. Or equivalently, "all tautologies imply every other tautology."
However, if the question is "does the law of the excluded middle necessarily imply (~~A≡A)", where "imply" gets understood to mean that the law of the excluded middle will appear in any proof of (~~A≡A) where (~~A≡A) is not an axiom, then the answer is 'no'. As a simple example, (~~A -> A) and (A -> ~~A) along with modus ponens and ((A -> B) -> ((B -> A) -> (A ≡ B))) will imply that (~~A ≡ A). There is no law of the excluded middle there, and (~~A≡A) is not an axiom.
answered Aug 27 '18 at 7:25
Doug SpoonwoodDoug Spoonwood
8,00112144
answered Aug 27 '18 at 7:25
Doug SpoonwoodDoug Spoonwood
8,00112144
answered Aug 27 '18 at 7:25
Doug SpoonwoodDoug Spoonwood
8,00112144
answered Aug 27 '18 at 7:25
Doug SpoonwoodDoug Spoonwood
8,00112144
8,00112144
1
$begingroup$
I got reminded of the proverb of the centipede who forgot how to walk when asked to explain exactly how it dealt with so many legs (a remark in the same book where my question arose from)
$endgroup$
– User12239
Aug 27 '18 at 8:46
add a comment |
1
$begingroup$
I got reminded of the proverb of the centipede who forgot how to walk when asked to explain exactly how it dealt with so many legs (a remark in the same book where my question arose from)
$endgroup$
– User12239
Aug 27 '18 at 8:46
1
1
$begingroup$
I got reminded of the proverb of the centipede who forgot how to walk when asked to explain exactly how it dealt with so many legs (a remark in the same book where my question arose from)
$endgroup$
– User12239
Aug 27 '18 at 8:46
$begingroup$
I got reminded of the proverb of the centipede who forgot how to walk when asked to explain exactly how it dealt with so many legs (a remark in the same book where my question arose from)
$endgroup$
– User12239
Aug 27 '18 at 8:46
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%2f2895192%2fa-statement-following-from-the-law-of-excluded-middle%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
