Confused about proofs by contradiction, the Law of the Excluded Middle and existence of consistent axiomatic systems.True vs. ProvableWhy not both true and false?Why doesn't the independence of the continuum hypothesis immediately imply that ZFC is unsatisfactory?Why is establishing absolute consistency of ZFC impossible?How could a statement be true without proof?Provability of the continuum hypothesis and the incompleteness theoremWhat is the meaning of “true”?Absoluteness of $ textCon(mathsfZFC) $ for Transitive Models of $ mathsfZFC $.Contraposition and law of excluded middleHow is the law of excluded middle necessary for proofs by contradiction?Is there any case where classical logic has “proven” an incorrect result?Systems without the law of excluded middleWill assuming an undecidable statement result in a consistent system?Trying to understand self-reference as it relates to Godel's Second Incompleteness TheoremShowing propositional logic is consistentHow can a formal system ever be non-obviously unsound?Propositional calculus and intuitionist logic

Copy previous line to current line from text file

As a GM, is it bad form to ask for a moment to think when improvising?

Are pressure-treated posts that have been submerged for a few days ruined?

Should homeowners insurance cover the cost of the home?

Has the United States ever had a non-Christian President?

Handling Null values (and equivalents) routinely in Python

Is it normal for gliders not to have attitude indicators?

What was the first story to feature the plot "the monsters were human all along"?

Is there a word for food that's gone 'bad', but is still edible?

Does expanded replace the romannumeral trick for expansion?

How do I allocate more memory to an app on Sheepshaver running Mac OS 9?

Are the Night's Watch still required?

Is there an age requirement to play in Adventurers League?

Why is my arithmetic with a long long int behaving this way?

Why do people keep telling me that I am a bad photographer?

Can there be a single technologically advanced nation, in a continent full of non-technologically advanced nations?

How do I, as a DM, handle a party that decides to set up an ambush in a dungeon?

Find magical solution to magical equation

Can I use a Cat5e cable with an RJ45 and Cat6 port?

Agena docking and RCS Brakes in First Man

Hostile Divisor Numbers

Why do these characters still seem to be the same age after the events of Endgame?

Would you use "llamarse" for an animal's name?

Why is "breaking the mould" positively connoted?



Confused about proofs by contradiction, the Law of the Excluded Middle and existence of consistent axiomatic systems.


True vs. ProvableWhy not both true and false?Why doesn't the independence of the continuum hypothesis immediately imply that ZFC is unsatisfactory?Why is establishing absolute consistency of ZFC impossible?How could a statement be true without proof?Provability of the continuum hypothesis and the incompleteness theoremWhat is the meaning of “true”?Absoluteness of $ textCon(mathsfZFC) $ for Transitive Models of $ mathsfZFC $.Contraposition and law of excluded middleHow is the law of excluded middle necessary for proofs by contradiction?Is there any case where classical logic has “proven” an incorrect result?Systems without the law of excluded middleWill assuming an undecidable statement result in a consistent system?Trying to understand self-reference as it relates to Godel's Second Incompleteness TheoremShowing propositional logic is consistentHow can a formal system ever be non-obviously unsound?Propositional calculus and intuitionist logic













4












$begingroup$


I apologize if my question is too dumb. I'm not particularly educated in this area of Mathematics.



Proof by contradiction consists of assuming a statement $P$ is false, and then reach a contradiction thus allowing us to conclude that $P$ must be true. Such line of reasoning seems to be using the Law of the Excluded Middle, that is, $P lor neg P$ is a tautology.



Wouldn't assuming said law lead to some problems. As an example, it has been proven that if ZFC is consistent, then both ZFC$+$CH and ZFC$+neg$CH are also consistent. Thus, by LEM, there are only two possible options:



1) CH is true, but unprovable within ZFC.



2) $neg$CH is true, but unprovable within ZFC.



Suppose for a second that the first option was correct. Since $neg$ CH is consistent with ZFC, the axiomatic system ZFC$+ neg$CH contains no contradictions. However CH being true does imply that ZFC$+ neg$CH has a contradiction. The second option being true leads to the same result.



What am I missing?




I would truly appreciate any help/thoughts.










share|cite|improve this question











$endgroup$







  • 1




    $begingroup$
    It doesn't make sense to say CH is true in ZFC. CH is true in some models of ZFC, and it's false in other models of ZFC. (Assuming there are any models of ZFC...)
    $endgroup$
    – Derek Elkins
    Apr 30 at 20:45











  • $begingroup$
    what do you exactly mean by "true in ZFC"?
    $endgroup$
    – Zuhair
    Apr 30 at 20:45










  • $begingroup$
    You have in the title a very broad subject, and the body of your Question narrows this only in a fairly confused way. How would you define "CH is true in ZFC"? It might be more productive to begin your investigations on grounds where you have a clear understanding, rather than by combining several topics that are muddled.
    $endgroup$
    – hardmath
    Apr 30 at 20:45










  • $begingroup$
    I meant to say that 'CH is true along the axioms of ZFC'. I'll edit my question. I'm sorry, I'm not familiar with the correct terminology.
    $endgroup$
    – Leo
    Apr 30 at 20:51










  • $begingroup$
    You may be interesting in reading this question and an excellent response: math.stackexchange.com/questions/1746563/…
    $endgroup$
    – Vasya
    Apr 30 at 20:51















4












$begingroup$


I apologize if my question is too dumb. I'm not particularly educated in this area of Mathematics.



Proof by contradiction consists of assuming a statement $P$ is false, and then reach a contradiction thus allowing us to conclude that $P$ must be true. Such line of reasoning seems to be using the Law of the Excluded Middle, that is, $P lor neg P$ is a tautology.



Wouldn't assuming said law lead to some problems. As an example, it has been proven that if ZFC is consistent, then both ZFC$+$CH and ZFC$+neg$CH are also consistent. Thus, by LEM, there are only two possible options:



1) CH is true, but unprovable within ZFC.



2) $neg$CH is true, but unprovable within ZFC.



Suppose for a second that the first option was correct. Since $neg$ CH is consistent with ZFC, the axiomatic system ZFC$+ neg$CH contains no contradictions. However CH being true does imply that ZFC$+ neg$CH has a contradiction. The second option being true leads to the same result.



What am I missing?




I would truly appreciate any help/thoughts.










share|cite|improve this question











$endgroup$







  • 1




    $begingroup$
    It doesn't make sense to say CH is true in ZFC. CH is true in some models of ZFC, and it's false in other models of ZFC. (Assuming there are any models of ZFC...)
    $endgroup$
    – Derek Elkins
    Apr 30 at 20:45











  • $begingroup$
    what do you exactly mean by "true in ZFC"?
    $endgroup$
    – Zuhair
    Apr 30 at 20:45










  • $begingroup$
    You have in the title a very broad subject, and the body of your Question narrows this only in a fairly confused way. How would you define "CH is true in ZFC"? It might be more productive to begin your investigations on grounds where you have a clear understanding, rather than by combining several topics that are muddled.
    $endgroup$
    – hardmath
    Apr 30 at 20:45










  • $begingroup$
    I meant to say that 'CH is true along the axioms of ZFC'. I'll edit my question. I'm sorry, I'm not familiar with the correct terminology.
    $endgroup$
    – Leo
    Apr 30 at 20:51










  • $begingroup$
    You may be interesting in reading this question and an excellent response: math.stackexchange.com/questions/1746563/…
    $endgroup$
    – Vasya
    Apr 30 at 20:51













4












4








4


3



$begingroup$


I apologize if my question is too dumb. I'm not particularly educated in this area of Mathematics.



Proof by contradiction consists of assuming a statement $P$ is false, and then reach a contradiction thus allowing us to conclude that $P$ must be true. Such line of reasoning seems to be using the Law of the Excluded Middle, that is, $P lor neg P$ is a tautology.



Wouldn't assuming said law lead to some problems. As an example, it has been proven that if ZFC is consistent, then both ZFC$+$CH and ZFC$+neg$CH are also consistent. Thus, by LEM, there are only two possible options:



1) CH is true, but unprovable within ZFC.



2) $neg$CH is true, but unprovable within ZFC.



Suppose for a second that the first option was correct. Since $neg$ CH is consistent with ZFC, the axiomatic system ZFC$+ neg$CH contains no contradictions. However CH being true does imply that ZFC$+ neg$CH has a contradiction. The second option being true leads to the same result.



What am I missing?




I would truly appreciate any help/thoughts.










share|cite|improve this question











$endgroup$




I apologize if my question is too dumb. I'm not particularly educated in this area of Mathematics.



Proof by contradiction consists of assuming a statement $P$ is false, and then reach a contradiction thus allowing us to conclude that $P$ must be true. Such line of reasoning seems to be using the Law of the Excluded Middle, that is, $P lor neg P$ is a tautology.



Wouldn't assuming said law lead to some problems. As an example, it has been proven that if ZFC is consistent, then both ZFC$+$CH and ZFC$+neg$CH are also consistent. Thus, by LEM, there are only two possible options:



1) CH is true, but unprovable within ZFC.



2) $neg$CH is true, but unprovable within ZFC.



Suppose for a second that the first option was correct. Since $neg$ CH is consistent with ZFC, the axiomatic system ZFC$+ neg$CH contains no contradictions. However CH being true does imply that ZFC$+ neg$CH has a contradiction. The second option being true leads to the same result.



What am I missing?




I would truly appreciate any help/thoughts.







logic soft-question






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Apr 30 at 20:55







Leo

















asked Apr 30 at 20:38









LeoLeo

837517




837517







  • 1




    $begingroup$
    It doesn't make sense to say CH is true in ZFC. CH is true in some models of ZFC, and it's false in other models of ZFC. (Assuming there are any models of ZFC...)
    $endgroup$
    – Derek Elkins
    Apr 30 at 20:45











  • $begingroup$
    what do you exactly mean by "true in ZFC"?
    $endgroup$
    – Zuhair
    Apr 30 at 20:45










  • $begingroup$
    You have in the title a very broad subject, and the body of your Question narrows this only in a fairly confused way. How would you define "CH is true in ZFC"? It might be more productive to begin your investigations on grounds where you have a clear understanding, rather than by combining several topics that are muddled.
    $endgroup$
    – hardmath
    Apr 30 at 20:45










  • $begingroup$
    I meant to say that 'CH is true along the axioms of ZFC'. I'll edit my question. I'm sorry, I'm not familiar with the correct terminology.
    $endgroup$
    – Leo
    Apr 30 at 20:51










  • $begingroup$
    You may be interesting in reading this question and an excellent response: math.stackexchange.com/questions/1746563/…
    $endgroup$
    – Vasya
    Apr 30 at 20:51












  • 1




    $begingroup$
    It doesn't make sense to say CH is true in ZFC. CH is true in some models of ZFC, and it's false in other models of ZFC. (Assuming there are any models of ZFC...)
    $endgroup$
    – Derek Elkins
    Apr 30 at 20:45











  • $begingroup$
    what do you exactly mean by "true in ZFC"?
    $endgroup$
    – Zuhair
    Apr 30 at 20:45










  • $begingroup$
    You have in the title a very broad subject, and the body of your Question narrows this only in a fairly confused way. How would you define "CH is true in ZFC"? It might be more productive to begin your investigations on grounds where you have a clear understanding, rather than by combining several topics that are muddled.
    $endgroup$
    – hardmath
    Apr 30 at 20:45










  • $begingroup$
    I meant to say that 'CH is true along the axioms of ZFC'. I'll edit my question. I'm sorry, I'm not familiar with the correct terminology.
    $endgroup$
    – Leo
    Apr 30 at 20:51










  • $begingroup$
    You may be interesting in reading this question and an excellent response: math.stackexchange.com/questions/1746563/…
    $endgroup$
    – Vasya
    Apr 30 at 20:51







1




1




$begingroup$
It doesn't make sense to say CH is true in ZFC. CH is true in some models of ZFC, and it's false in other models of ZFC. (Assuming there are any models of ZFC...)
$endgroup$
– Derek Elkins
Apr 30 at 20:45





$begingroup$
It doesn't make sense to say CH is true in ZFC. CH is true in some models of ZFC, and it's false in other models of ZFC. (Assuming there are any models of ZFC...)
$endgroup$
– Derek Elkins
Apr 30 at 20:45













$begingroup$
what do you exactly mean by "true in ZFC"?
$endgroup$
– Zuhair
Apr 30 at 20:45




$begingroup$
what do you exactly mean by "true in ZFC"?
$endgroup$
– Zuhair
Apr 30 at 20:45












$begingroup$
You have in the title a very broad subject, and the body of your Question narrows this only in a fairly confused way. How would you define "CH is true in ZFC"? It might be more productive to begin your investigations on grounds where you have a clear understanding, rather than by combining several topics that are muddled.
$endgroup$
– hardmath
Apr 30 at 20:45




$begingroup$
You have in the title a very broad subject, and the body of your Question narrows this only in a fairly confused way. How would you define "CH is true in ZFC"? It might be more productive to begin your investigations on grounds where you have a clear understanding, rather than by combining several topics that are muddled.
$endgroup$
– hardmath
Apr 30 at 20:45












$begingroup$
I meant to say that 'CH is true along the axioms of ZFC'. I'll edit my question. I'm sorry, I'm not familiar with the correct terminology.
$endgroup$
– Leo
Apr 30 at 20:51




$begingroup$
I meant to say that 'CH is true along the axioms of ZFC'. I'll edit my question. I'm sorry, I'm not familiar with the correct terminology.
$endgroup$
– Leo
Apr 30 at 20:51












$begingroup$
You may be interesting in reading this question and an excellent response: math.stackexchange.com/questions/1746563/…
$endgroup$
– Vasya
Apr 30 at 20:51




$begingroup$
You may be interesting in reading this question and an excellent response: math.stackexchange.com/questions/1746563/…
$endgroup$
– Vasya
Apr 30 at 20:51










3 Answers
3






active

oldest

votes


















3












$begingroup$

Your confusion is in conflating the truth of a set of axioms with their consistency. I'll assume ZFC is consistent throughout this explanation (that's not known, but it's assumed in the undecidability result you stated).



Let $diamond p$ denote "$p$ is consistent" and $square p$ denote "$p$ is provable" viz. modal logic (I'm tweaking its concepts slightly for the present context). Also, let $c,,z$ respectively denote the CH and ZFC. From the law of the excluded middle $clorneg c$ we deduce $zto((zland c)lor(zlandneg c))$, and the undecidability of $c$ in $z$ means that $(diamond(zland c))land(diamond(zlandneg c))$. But these results are not inconsistent. In particular, $zland c$ does not imply $square(zland c)$, and hence does not contradict $diamond(zlandneg c)$.



In particular, a general instance of the law of the excluded middle, $plorneg p$, doesn't imply $(square p)lor(square(neg p))$. Similarly, the law of non-contradiction $neg(plandneg p)$ doesn't imply $neg((diamond p)land(diamond(neg p)))$.



Just to relate all this to something you said earlier:




Proof by contradiction consists of assuming a statement $P$ is false,
and then reach a contradiction thus allowing us to conclude that $P$
must be true.




An intuitionistic logician, who rejects the law of the excluded middle, would instead say you assume some statement is true, reach a contradiction, and thus conclude the statement was false. In other words, $(qtobot)toneg q$. The case $q:=neg p$ gives $(neg ptobot)tonegneg p$, which if $p=negneg p$ simplifies to $(neg ptobot)to p$ as you intended. This simplification follows from the law of the excluded middle, but fails in intuitionistic logic. One way to understand this is that intuitionistic logic tracks provability rather than truth (this isn't necessarily how to read it, but it gives the right logical structure). In other words, $plorneg p$ fails in intuitionistic logic because $(square p)lor(square(neg p))$ fails in classical logic.






share|cite|improve this answer









$endgroup$












  • $begingroup$
    So is it possible for $P land neg P$ to be true in a consistent axiomatic system? I'm saying this since you claim $z land c$ doesn't contradict $z land neg c$ being consistent.
    $endgroup$
    – Leo
    Apr 30 at 22:07











  • $begingroup$
    Oh wait. $z land neg c$ being consistent doesn't even imply $z land neg c$, right?
    $endgroup$
    – Leo
    Apr 30 at 22:12










  • $begingroup$
    @Leo A consistent system is, by definition, one in which $Plandneg P$ is never true. But you work in out in your second comment; yes, a statement doesn't have to be true just because it's consistent.
    $endgroup$
    – J.G.
    May 1 at 5:06


















2












$begingroup$

Usually when it is said that a "sentence $s$ is true of some theory $T$" it is meant that $s$ is satisfied in some particular model of $T$ that is considered as a standard model of $T$, that is a model that most captures the informal concept the formal system is about.



To say that $s$ is true in $T$ does imply that $T + s$ is consistent! But it doesn't necessarily imply that $T + neg s $ is inconsistent at all. To say that $T + neg s$ is inconsistent is to say that $s$ is not satisfied in any model of $T$ and not just the standard one. The picture should be clear by now, since $s$ being satisfied in a particular model of $T$ doesn't at all imply that $neg s$ cannot be satisfied in another model of $T$.






share|cite|improve this answer









$endgroup$








  • 1




    $begingroup$
    I guess I now have to study models. I'm not even sure what they are.
    $endgroup$
    – Leo
    Apr 30 at 21:06






  • 2




    $begingroup$
    well models are the semantic counterpart of the formal system. Yes, you need to study them, otherwise it would be difficult to understand this situation.
    $endgroup$
    – Zuhair
    Apr 30 at 21:07


















1












$begingroup$

Let me make it very clear: Truth is always relative to a structure/model. Remember, every first-order sentence over a language $L$ can be true in some $L$-structure but false in another. For a trivial example "$∀x,y ( x·y = y·x )$" is true in every abelian group but false in every non-abelian group. Likewise "CH is true" is meaningless unless we specify explicitly or implicitly the structure we are talking about. Once you precisely specify this, all the problems will go away. Historically, some philosophers have made this same mistake of confusing syntax with semantics.



In fact, the independence of CH directly implies via Godel's completeness theorem that there is a model of ZFC in which CH is true, as well as a model of ZFC in which CH is false. There is simply no contradiction because those are two different models!



Some people may use "true in ZFC" to mean "provable by ZFC", but that would then mean "true in all models of ZFC", which certainly does not hold for CH. Also, if you come across statements that Godel's incompleteness theorems are about "true but unprovable sentences", note that there is still a model we are talking about, namely the standard model $mathbbN$ of PA. For more on that see this post.






share|cite|improve this answer









$endgroup$













    Your Answer








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

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

    else
    createEditor();

    );

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



    );













    draft saved

    draft discarded


















    StackExchange.ready(
    function ()
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3208738%2fconfused-about-proofs-by-contradiction-the-law-of-the-excluded-middle-and-exist%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









    3












    $begingroup$

    Your confusion is in conflating the truth of a set of axioms with their consistency. I'll assume ZFC is consistent throughout this explanation (that's not known, but it's assumed in the undecidability result you stated).



    Let $diamond p$ denote "$p$ is consistent" and $square p$ denote "$p$ is provable" viz. modal logic (I'm tweaking its concepts slightly for the present context). Also, let $c,,z$ respectively denote the CH and ZFC. From the law of the excluded middle $clorneg c$ we deduce $zto((zland c)lor(zlandneg c))$, and the undecidability of $c$ in $z$ means that $(diamond(zland c))land(diamond(zlandneg c))$. But these results are not inconsistent. In particular, $zland c$ does not imply $square(zland c)$, and hence does not contradict $diamond(zlandneg c)$.



    In particular, a general instance of the law of the excluded middle, $plorneg p$, doesn't imply $(square p)lor(square(neg p))$. Similarly, the law of non-contradiction $neg(plandneg p)$ doesn't imply $neg((diamond p)land(diamond(neg p)))$.



    Just to relate all this to something you said earlier:




    Proof by contradiction consists of assuming a statement $P$ is false,
    and then reach a contradiction thus allowing us to conclude that $P$
    must be true.




    An intuitionistic logician, who rejects the law of the excluded middle, would instead say you assume some statement is true, reach a contradiction, and thus conclude the statement was false. In other words, $(qtobot)toneg q$. The case $q:=neg p$ gives $(neg ptobot)tonegneg p$, which if $p=negneg p$ simplifies to $(neg ptobot)to p$ as you intended. This simplification follows from the law of the excluded middle, but fails in intuitionistic logic. One way to understand this is that intuitionistic logic tracks provability rather than truth (this isn't necessarily how to read it, but it gives the right logical structure). In other words, $plorneg p$ fails in intuitionistic logic because $(square p)lor(square(neg p))$ fails in classical logic.






    share|cite|improve this answer









    $endgroup$












    • $begingroup$
      So is it possible for $P land neg P$ to be true in a consistent axiomatic system? I'm saying this since you claim $z land c$ doesn't contradict $z land neg c$ being consistent.
      $endgroup$
      – Leo
      Apr 30 at 22:07











    • $begingroup$
      Oh wait. $z land neg c$ being consistent doesn't even imply $z land neg c$, right?
      $endgroup$
      – Leo
      Apr 30 at 22:12










    • $begingroup$
      @Leo A consistent system is, by definition, one in which $Plandneg P$ is never true. But you work in out in your second comment; yes, a statement doesn't have to be true just because it's consistent.
      $endgroup$
      – J.G.
      May 1 at 5:06















    3












    $begingroup$

    Your confusion is in conflating the truth of a set of axioms with their consistency. I'll assume ZFC is consistent throughout this explanation (that's not known, but it's assumed in the undecidability result you stated).



    Let $diamond p$ denote "$p$ is consistent" and $square p$ denote "$p$ is provable" viz. modal logic (I'm tweaking its concepts slightly for the present context). Also, let $c,,z$ respectively denote the CH and ZFC. From the law of the excluded middle $clorneg c$ we deduce $zto((zland c)lor(zlandneg c))$, and the undecidability of $c$ in $z$ means that $(diamond(zland c))land(diamond(zlandneg c))$. But these results are not inconsistent. In particular, $zland c$ does not imply $square(zland c)$, and hence does not contradict $diamond(zlandneg c)$.



    In particular, a general instance of the law of the excluded middle, $plorneg p$, doesn't imply $(square p)lor(square(neg p))$. Similarly, the law of non-contradiction $neg(plandneg p)$ doesn't imply $neg((diamond p)land(diamond(neg p)))$.



    Just to relate all this to something you said earlier:




    Proof by contradiction consists of assuming a statement $P$ is false,
    and then reach a contradiction thus allowing us to conclude that $P$
    must be true.




    An intuitionistic logician, who rejects the law of the excluded middle, would instead say you assume some statement is true, reach a contradiction, and thus conclude the statement was false. In other words, $(qtobot)toneg q$. The case $q:=neg p$ gives $(neg ptobot)tonegneg p$, which if $p=negneg p$ simplifies to $(neg ptobot)to p$ as you intended. This simplification follows from the law of the excluded middle, but fails in intuitionistic logic. One way to understand this is that intuitionistic logic tracks provability rather than truth (this isn't necessarily how to read it, but it gives the right logical structure). In other words, $plorneg p$ fails in intuitionistic logic because $(square p)lor(square(neg p))$ fails in classical logic.






    share|cite|improve this answer









    $endgroup$












    • $begingroup$
      So is it possible for $P land neg P$ to be true in a consistent axiomatic system? I'm saying this since you claim $z land c$ doesn't contradict $z land neg c$ being consistent.
      $endgroup$
      – Leo
      Apr 30 at 22:07











    • $begingroup$
      Oh wait. $z land neg c$ being consistent doesn't even imply $z land neg c$, right?
      $endgroup$
      – Leo
      Apr 30 at 22:12










    • $begingroup$
      @Leo A consistent system is, by definition, one in which $Plandneg P$ is never true. But you work in out in your second comment; yes, a statement doesn't have to be true just because it's consistent.
      $endgroup$
      – J.G.
      May 1 at 5:06













    3












    3








    3





    $begingroup$

    Your confusion is in conflating the truth of a set of axioms with their consistency. I'll assume ZFC is consistent throughout this explanation (that's not known, but it's assumed in the undecidability result you stated).



    Let $diamond p$ denote "$p$ is consistent" and $square p$ denote "$p$ is provable" viz. modal logic (I'm tweaking its concepts slightly for the present context). Also, let $c,,z$ respectively denote the CH and ZFC. From the law of the excluded middle $clorneg c$ we deduce $zto((zland c)lor(zlandneg c))$, and the undecidability of $c$ in $z$ means that $(diamond(zland c))land(diamond(zlandneg c))$. But these results are not inconsistent. In particular, $zland c$ does not imply $square(zland c)$, and hence does not contradict $diamond(zlandneg c)$.



    In particular, a general instance of the law of the excluded middle, $plorneg p$, doesn't imply $(square p)lor(square(neg p))$. Similarly, the law of non-contradiction $neg(plandneg p)$ doesn't imply $neg((diamond p)land(diamond(neg p)))$.



    Just to relate all this to something you said earlier:




    Proof by contradiction consists of assuming a statement $P$ is false,
    and then reach a contradiction thus allowing us to conclude that $P$
    must be true.




    An intuitionistic logician, who rejects the law of the excluded middle, would instead say you assume some statement is true, reach a contradiction, and thus conclude the statement was false. In other words, $(qtobot)toneg q$. The case $q:=neg p$ gives $(neg ptobot)tonegneg p$, which if $p=negneg p$ simplifies to $(neg ptobot)to p$ as you intended. This simplification follows from the law of the excluded middle, but fails in intuitionistic logic. One way to understand this is that intuitionistic logic tracks provability rather than truth (this isn't necessarily how to read it, but it gives the right logical structure). In other words, $plorneg p$ fails in intuitionistic logic because $(square p)lor(square(neg p))$ fails in classical logic.






    share|cite|improve this answer









    $endgroup$



    Your confusion is in conflating the truth of a set of axioms with their consistency. I'll assume ZFC is consistent throughout this explanation (that's not known, but it's assumed in the undecidability result you stated).



    Let $diamond p$ denote "$p$ is consistent" and $square p$ denote "$p$ is provable" viz. modal logic (I'm tweaking its concepts slightly for the present context). Also, let $c,,z$ respectively denote the CH and ZFC. From the law of the excluded middle $clorneg c$ we deduce $zto((zland c)lor(zlandneg c))$, and the undecidability of $c$ in $z$ means that $(diamond(zland c))land(diamond(zlandneg c))$. But these results are not inconsistent. In particular, $zland c$ does not imply $square(zland c)$, and hence does not contradict $diamond(zlandneg c)$.



    In particular, a general instance of the law of the excluded middle, $plorneg p$, doesn't imply $(square p)lor(square(neg p))$. Similarly, the law of non-contradiction $neg(plandneg p)$ doesn't imply $neg((diamond p)land(diamond(neg p)))$.



    Just to relate all this to something you said earlier:




    Proof by contradiction consists of assuming a statement $P$ is false,
    and then reach a contradiction thus allowing us to conclude that $P$
    must be true.




    An intuitionistic logician, who rejects the law of the excluded middle, would instead say you assume some statement is true, reach a contradiction, and thus conclude the statement was false. In other words, $(qtobot)toneg q$. The case $q:=neg p$ gives $(neg ptobot)tonegneg p$, which if $p=negneg p$ simplifies to $(neg ptobot)to p$ as you intended. This simplification follows from the law of the excluded middle, but fails in intuitionistic logic. One way to understand this is that intuitionistic logic tracks provability rather than truth (this isn't necessarily how to read it, but it gives the right logical structure). In other words, $plorneg p$ fails in intuitionistic logic because $(square p)lor(square(neg p))$ fails in classical logic.







    share|cite|improve this answer












    share|cite|improve this answer



    share|cite|improve this answer










    answered Apr 30 at 21:08









    J.G.J.G.

    35.6k23554




    35.6k23554











    • $begingroup$
      So is it possible for $P land neg P$ to be true in a consistent axiomatic system? I'm saying this since you claim $z land c$ doesn't contradict $z land neg c$ being consistent.
      $endgroup$
      – Leo
      Apr 30 at 22:07











    • $begingroup$
      Oh wait. $z land neg c$ being consistent doesn't even imply $z land neg c$, right?
      $endgroup$
      – Leo
      Apr 30 at 22:12










    • $begingroup$
      @Leo A consistent system is, by definition, one in which $Plandneg P$ is never true. But you work in out in your second comment; yes, a statement doesn't have to be true just because it's consistent.
      $endgroup$
      – J.G.
      May 1 at 5:06
















    • $begingroup$
      So is it possible for $P land neg P$ to be true in a consistent axiomatic system? I'm saying this since you claim $z land c$ doesn't contradict $z land neg c$ being consistent.
      $endgroup$
      – Leo
      Apr 30 at 22:07











    • $begingroup$
      Oh wait. $z land neg c$ being consistent doesn't even imply $z land neg c$, right?
      $endgroup$
      – Leo
      Apr 30 at 22:12










    • $begingroup$
      @Leo A consistent system is, by definition, one in which $Plandneg P$ is never true. But you work in out in your second comment; yes, a statement doesn't have to be true just because it's consistent.
      $endgroup$
      – J.G.
      May 1 at 5:06















    $begingroup$
    So is it possible for $P land neg P$ to be true in a consistent axiomatic system? I'm saying this since you claim $z land c$ doesn't contradict $z land neg c$ being consistent.
    $endgroup$
    – Leo
    Apr 30 at 22:07





    $begingroup$
    So is it possible for $P land neg P$ to be true in a consistent axiomatic system? I'm saying this since you claim $z land c$ doesn't contradict $z land neg c$ being consistent.
    $endgroup$
    – Leo
    Apr 30 at 22:07













    $begingroup$
    Oh wait. $z land neg c$ being consistent doesn't even imply $z land neg c$, right?
    $endgroup$
    – Leo
    Apr 30 at 22:12




    $begingroup$
    Oh wait. $z land neg c$ being consistent doesn't even imply $z land neg c$, right?
    $endgroup$
    – Leo
    Apr 30 at 22:12












    $begingroup$
    @Leo A consistent system is, by definition, one in which $Plandneg P$ is never true. But you work in out in your second comment; yes, a statement doesn't have to be true just because it's consistent.
    $endgroup$
    – J.G.
    May 1 at 5:06




    $begingroup$
    @Leo A consistent system is, by definition, one in which $Plandneg P$ is never true. But you work in out in your second comment; yes, a statement doesn't have to be true just because it's consistent.
    $endgroup$
    – J.G.
    May 1 at 5:06











    2












    $begingroup$

    Usually when it is said that a "sentence $s$ is true of some theory $T$" it is meant that $s$ is satisfied in some particular model of $T$ that is considered as a standard model of $T$, that is a model that most captures the informal concept the formal system is about.



    To say that $s$ is true in $T$ does imply that $T + s$ is consistent! But it doesn't necessarily imply that $T + neg s $ is inconsistent at all. To say that $T + neg s$ is inconsistent is to say that $s$ is not satisfied in any model of $T$ and not just the standard one. The picture should be clear by now, since $s$ being satisfied in a particular model of $T$ doesn't at all imply that $neg s$ cannot be satisfied in another model of $T$.






    share|cite|improve this answer









    $endgroup$








    • 1




      $begingroup$
      I guess I now have to study models. I'm not even sure what they are.
      $endgroup$
      – Leo
      Apr 30 at 21:06






    • 2




      $begingroup$
      well models are the semantic counterpart of the formal system. Yes, you need to study them, otherwise it would be difficult to understand this situation.
      $endgroup$
      – Zuhair
      Apr 30 at 21:07















    2












    $begingroup$

    Usually when it is said that a "sentence $s$ is true of some theory $T$" it is meant that $s$ is satisfied in some particular model of $T$ that is considered as a standard model of $T$, that is a model that most captures the informal concept the formal system is about.



    To say that $s$ is true in $T$ does imply that $T + s$ is consistent! But it doesn't necessarily imply that $T + neg s $ is inconsistent at all. To say that $T + neg s$ is inconsistent is to say that $s$ is not satisfied in any model of $T$ and not just the standard one. The picture should be clear by now, since $s$ being satisfied in a particular model of $T$ doesn't at all imply that $neg s$ cannot be satisfied in another model of $T$.






    share|cite|improve this answer









    $endgroup$








    • 1




      $begingroup$
      I guess I now have to study models. I'm not even sure what they are.
      $endgroup$
      – Leo
      Apr 30 at 21:06






    • 2




      $begingroup$
      well models are the semantic counterpart of the formal system. Yes, you need to study them, otherwise it would be difficult to understand this situation.
      $endgroup$
      – Zuhair
      Apr 30 at 21:07













    2












    2








    2





    $begingroup$

    Usually when it is said that a "sentence $s$ is true of some theory $T$" it is meant that $s$ is satisfied in some particular model of $T$ that is considered as a standard model of $T$, that is a model that most captures the informal concept the formal system is about.



    To say that $s$ is true in $T$ does imply that $T + s$ is consistent! But it doesn't necessarily imply that $T + neg s $ is inconsistent at all. To say that $T + neg s$ is inconsistent is to say that $s$ is not satisfied in any model of $T$ and not just the standard one. The picture should be clear by now, since $s$ being satisfied in a particular model of $T$ doesn't at all imply that $neg s$ cannot be satisfied in another model of $T$.






    share|cite|improve this answer









    $endgroup$



    Usually when it is said that a "sentence $s$ is true of some theory $T$" it is meant that $s$ is satisfied in some particular model of $T$ that is considered as a standard model of $T$, that is a model that most captures the informal concept the formal system is about.



    To say that $s$ is true in $T$ does imply that $T + s$ is consistent! But it doesn't necessarily imply that $T + neg s $ is inconsistent at all. To say that $T + neg s$ is inconsistent is to say that $s$ is not satisfied in any model of $T$ and not just the standard one. The picture should be clear by now, since $s$ being satisfied in a particular model of $T$ doesn't at all imply that $neg s$ cannot be satisfied in another model of $T$.







    share|cite|improve this answer












    share|cite|improve this answer



    share|cite|improve this answer










    answered Apr 30 at 21:02









    ZuhairZuhair

    435212




    435212







    • 1




      $begingroup$
      I guess I now have to study models. I'm not even sure what they are.
      $endgroup$
      – Leo
      Apr 30 at 21:06






    • 2




      $begingroup$
      well models are the semantic counterpart of the formal system. Yes, you need to study them, otherwise it would be difficult to understand this situation.
      $endgroup$
      – Zuhair
      Apr 30 at 21:07












    • 1




      $begingroup$
      I guess I now have to study models. I'm not even sure what they are.
      $endgroup$
      – Leo
      Apr 30 at 21:06






    • 2




      $begingroup$
      well models are the semantic counterpart of the formal system. Yes, you need to study them, otherwise it would be difficult to understand this situation.
      $endgroup$
      – Zuhair
      Apr 30 at 21:07







    1




    1




    $begingroup$
    I guess I now have to study models. I'm not even sure what they are.
    $endgroup$
    – Leo
    Apr 30 at 21:06




    $begingroup$
    I guess I now have to study models. I'm not even sure what they are.
    $endgroup$
    – Leo
    Apr 30 at 21:06




    2




    2




    $begingroup$
    well models are the semantic counterpart of the formal system. Yes, you need to study them, otherwise it would be difficult to understand this situation.
    $endgroup$
    – Zuhair
    Apr 30 at 21:07




    $begingroup$
    well models are the semantic counterpart of the formal system. Yes, you need to study them, otherwise it would be difficult to understand this situation.
    $endgroup$
    – Zuhair
    Apr 30 at 21:07











    1












    $begingroup$

    Let me make it very clear: Truth is always relative to a structure/model. Remember, every first-order sentence over a language $L$ can be true in some $L$-structure but false in another. For a trivial example "$∀x,y ( x·y = y·x )$" is true in every abelian group but false in every non-abelian group. Likewise "CH is true" is meaningless unless we specify explicitly or implicitly the structure we are talking about. Once you precisely specify this, all the problems will go away. Historically, some philosophers have made this same mistake of confusing syntax with semantics.



    In fact, the independence of CH directly implies via Godel's completeness theorem that there is a model of ZFC in which CH is true, as well as a model of ZFC in which CH is false. There is simply no contradiction because those are two different models!



    Some people may use "true in ZFC" to mean "provable by ZFC", but that would then mean "true in all models of ZFC", which certainly does not hold for CH. Also, if you come across statements that Godel's incompleteness theorems are about "true but unprovable sentences", note that there is still a model we are talking about, namely the standard model $mathbbN$ of PA. For more on that see this post.






    share|cite|improve this answer









    $endgroup$

















      1












      $begingroup$

      Let me make it very clear: Truth is always relative to a structure/model. Remember, every first-order sentence over a language $L$ can be true in some $L$-structure but false in another. For a trivial example "$∀x,y ( x·y = y·x )$" is true in every abelian group but false in every non-abelian group. Likewise "CH is true" is meaningless unless we specify explicitly or implicitly the structure we are talking about. Once you precisely specify this, all the problems will go away. Historically, some philosophers have made this same mistake of confusing syntax with semantics.



      In fact, the independence of CH directly implies via Godel's completeness theorem that there is a model of ZFC in which CH is true, as well as a model of ZFC in which CH is false. There is simply no contradiction because those are two different models!



      Some people may use "true in ZFC" to mean "provable by ZFC", but that would then mean "true in all models of ZFC", which certainly does not hold for CH. Also, if you come across statements that Godel's incompleteness theorems are about "true but unprovable sentences", note that there is still a model we are talking about, namely the standard model $mathbbN$ of PA. For more on that see this post.






      share|cite|improve this answer









      $endgroup$















        1












        1








        1





        $begingroup$

        Let me make it very clear: Truth is always relative to a structure/model. Remember, every first-order sentence over a language $L$ can be true in some $L$-structure but false in another. For a trivial example "$∀x,y ( x·y = y·x )$" is true in every abelian group but false in every non-abelian group. Likewise "CH is true" is meaningless unless we specify explicitly or implicitly the structure we are talking about. Once you precisely specify this, all the problems will go away. Historically, some philosophers have made this same mistake of confusing syntax with semantics.



        In fact, the independence of CH directly implies via Godel's completeness theorem that there is a model of ZFC in which CH is true, as well as a model of ZFC in which CH is false. There is simply no contradiction because those are two different models!



        Some people may use "true in ZFC" to mean "provable by ZFC", but that would then mean "true in all models of ZFC", which certainly does not hold for CH. Also, if you come across statements that Godel's incompleteness theorems are about "true but unprovable sentences", note that there is still a model we are talking about, namely the standard model $mathbbN$ of PA. For more on that see this post.






        share|cite|improve this answer









        $endgroup$



        Let me make it very clear: Truth is always relative to a structure/model. Remember, every first-order sentence over a language $L$ can be true in some $L$-structure but false in another. For a trivial example "$∀x,y ( x·y = y·x )$" is true in every abelian group but false in every non-abelian group. Likewise "CH is true" is meaningless unless we specify explicitly or implicitly the structure we are talking about. Once you precisely specify this, all the problems will go away. Historically, some philosophers have made this same mistake of confusing syntax with semantics.



        In fact, the independence of CH directly implies via Godel's completeness theorem that there is a model of ZFC in which CH is true, as well as a model of ZFC in which CH is false. There is simply no contradiction because those are two different models!



        Some people may use "true in ZFC" to mean "provable by ZFC", but that would then mean "true in all models of ZFC", which certainly does not hold for CH. Also, if you come across statements that Godel's incompleteness theorems are about "true but unprovable sentences", note that there is still a model we are talking about, namely the standard model $mathbbN$ of PA. For more on that see this post.







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered May 1 at 2:18









        user21820user21820

        40.5k544163




        40.5k544163



























            draft saved

            draft discarded
















































            Thanks for contributing an answer to Mathematics Stack Exchange!


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

            But avoid


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

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

            Use MathJax to format equations. MathJax reference.


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




            draft saved


            draft discarded














            StackExchange.ready(
            function ()
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3208738%2fconfused-about-proofs-by-contradiction-the-law-of-the-excluded-middle-and-exist%23new-answer', 'question_page');

            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            Popular posts from this blog

            Category:9 (number) SubcategoriesMedia in category "9 (number)"Navigation menuUpload mediaGND ID: 4485639-8Library of Congress authority ID: sh85091979ReasonatorScholiaStatistics

            Circuit construction for execution of conditional statements using least significant bitHow are two different registers being used as “control”?How exactly is the stated composite state of the two registers being produced using the $R_zz$ controlled rotations?Efficiently performing controlled rotations in HHLWould this quantum algorithm implementation work?How to prepare a superposed states of odd integers from $1$ to $sqrtN$?Why is this implementation of the order finding algorithm not working?Circuit construction for Hamiltonian simulationHow can I invert the least significant bit of a certain term of a superposed state?Implementing an oracleImplementing a controlled sum operation

            Magento 2 “No Payment Methods” in Admin New OrderHow to integrate Paypal Express Checkout with the Magento APIMagento 1.5 - Sales > Order > edit order and shipping methods disappearAuto Invoice Check/Money Order Payment methodAdd more simple payment methods?Shipping methods not showingWhat should I do to change payment methods if changing the configuration has no effects?1.9 - No Payment Methods showing upMy Payment Methods not Showing for downloadable/virtual product when checkout?Magento2 API to access internal payment methodHow to call an existing payment methods in the registration form?