A statement following from the law of excluded middle
Clash Royale CLAN TAG#URR8PPP
up vote
5
down vote
favorite
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
add a comment |Â
up vote
5
down vote
favorite
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
add a comment |Â
up vote
5
down vote
favorite
up vote
5
down vote
favorite
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
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 at 16:14
Selflearner
263211
263211
add a comment |Â
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
4
down vote
accepted
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$
Thanks for your complete illustration
– Selflearner
Aug 26 at 18:23
add a comment |Â
up vote
3
down vote
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$.
Why talk about "equivalent" ?
– Max
Aug 26 at 17:14
@Max - What is wrong with the word "equivalent"?
– Taroccoesbrocco
Aug 26 at 17:27
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$
– Max
Aug 26 at 17:39
2
@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.
– Carl Mummert
Aug 26 at 19:11
3
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.
– Carl Mummert
Aug 26 at 19:15
 |Â
show 5 more comments
up vote
0
down vote
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.
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)
– Selflearner
Aug 27 at 8:46
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
4
down vote
accepted
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$
Thanks for your complete illustration
– Selflearner
Aug 26 at 18:23
add a comment |Â
up vote
4
down vote
accepted
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$
Thanks for your complete illustration
– Selflearner
Aug 26 at 18:23
add a comment |Â
up vote
4
down vote
accepted
up vote
4
down vote
accepted
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$
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 at 17:17
Max
10.8k1836
10.8k1836
Thanks for your complete illustration
– Selflearner
Aug 26 at 18:23
add a comment |Â
Thanks for your complete illustration
– Selflearner
Aug 26 at 18:23
Thanks for your complete illustration
– Selflearner
Aug 26 at 18:23
Thanks for your complete illustration
– Selflearner
Aug 26 at 18:23
add a comment |Â
up vote
3
down vote
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$.
Why talk about "equivalent" ?
– Max
Aug 26 at 17:14
@Max - What is wrong with the word "equivalent"?
– Taroccoesbrocco
Aug 26 at 17:27
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$
– Max
Aug 26 at 17:39
2
@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.
– Carl Mummert
Aug 26 at 19:11
3
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.
– Carl Mummert
Aug 26 at 19:15
 |Â
show 5 more comments
up vote
3
down vote
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$.
Why talk about "equivalent" ?
– Max
Aug 26 at 17:14
@Max - What is wrong with the word "equivalent"?
– Taroccoesbrocco
Aug 26 at 17:27
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$
– Max
Aug 26 at 17:39
2
@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.
– Carl Mummert
Aug 26 at 19:11
3
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.
– Carl Mummert
Aug 26 at 19:15
 |Â
show 5 more comments
up vote
3
down vote
up vote
3
down vote
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$.
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$.
edited Aug 26 at 17:36
answered Aug 26 at 17:00
Taroccoesbrocco
3,75951433
3,75951433
Why talk about "equivalent" ?
– Max
Aug 26 at 17:14
@Max - What is wrong with the word "equivalent"?
– Taroccoesbrocco
Aug 26 at 17:27
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$
– Max
Aug 26 at 17:39
2
@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.
– Carl Mummert
Aug 26 at 19:11
3
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.
– Carl Mummert
Aug 26 at 19:15
 |Â
show 5 more comments
Why talk about "equivalent" ?
– Max
Aug 26 at 17:14
@Max - What is wrong with the word "equivalent"?
– Taroccoesbrocco
Aug 26 at 17:27
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$
– Max
Aug 26 at 17:39
2
@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.
– Carl Mummert
Aug 26 at 19:11
3
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.
– Carl Mummert
Aug 26 at 19:15
Why talk about "equivalent" ?
– Max
Aug 26 at 17:14
Why talk about "equivalent" ?
– Max
Aug 26 at 17:14
@Max - What is wrong with the word "equivalent"?
– Taroccoesbrocco
Aug 26 at 17:27
@Max - What is wrong with the word "equivalent"?
– Taroccoesbrocco
Aug 26 at 17:27
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$
– Max
Aug 26 at 17:39
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$
– Max
Aug 26 at 17:39
2
2
@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.
– Carl Mummert
Aug 26 at 19:11
@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.
– Carl Mummert
Aug 26 at 19:11
3
3
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.
– Carl Mummert
Aug 26 at 19:15
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.
– Carl Mummert
Aug 26 at 19:15
 |Â
show 5 more comments
up vote
0
down vote
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.
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)
– Selflearner
Aug 27 at 8:46
add a comment |Â
up vote
0
down vote
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.
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)
– Selflearner
Aug 27 at 8:46
add a comment |Â
up vote
0
down vote
up vote
0
down vote
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.
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 at 7:25
Doug Spoonwood
7,82312043
7,82312043
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)
– Selflearner
Aug 27 at 8:46
add a comment |Â
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)
– Selflearner
Aug 27 at 8:46
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)
– Selflearner
Aug 27 at 8:46
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)
– Selflearner
Aug 27 at 8:46
add a comment |Â
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
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
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
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
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