Does this prove the validity of this First Order Logic formula?











up vote
3
down vote

favorite












Is this a valid proof for the following problem?



Prove:



$$models (exists x : A(x) to forall x : B(x)) to forall x : (A(x) to B(x))$$



Proof by contradiction:




  1. Assume $(exists x: A(x) to forall x : B(x)) land lnot (forall x(A(x) to B(x))$


  2. $ (lnot exists x : A(x) lor forall x : B(x)) land lnotforall x : (A(x) to B(x))$ logical equivalence


  3. $forall x : lnot A(x) lor forall x : B(x)) land lnot(forall x : (A(x) to B(x))$ logical equivalence


  4. $lnot A(a) lor B(a) land lnot((A(a) to B(a))$ instantiation


  5. $((A(a) to B(a)) land lnot((A(a) to B(a))$ a contradiction



$therefore (exists x: A(x) to forall x : B(x)) to forall x(A(x) to B(x))$



Edit: corrected a typo on step 2



Update: Professor's Solution:




  1. Assume $(exists x: A(x) to forall x : B(x)) land lnot (forall x(A(x) to B(x))$


  2. $ (lnot exists x : A(x) lor forall x : B(x)) land lnotforall x : (A(x) to B(x))$ logical equivalence


  3. $ (lnot exists x : A(x) lor forall x : B(x)) land lnotforall x : (lnot A(x) lor B(x))$ logical equivalence


  4. $ ( forall x : lnot A(x) lor forall x : B(x)) land lnotforall x : (lnot A(x) lor B(x))$ logical equivalence


  5. $ ( forall x : lnot A(x) lor forall x : B(x)) land exists x : lnot(lnot A(x) lor B(x))$ logical equivalence



  6. $ ( forall x : lnot A(x) lor forall x : B(x)) land exists x : ( A(x) land lnot B(x))$ distribute negation


  7. $ ( lnot A(a) lor B(a)) land ( A(a) land lnot B(a))$ instantiation


  8. $ ( lnot A(a) lor B(a)) land ( lnot A(a) lor B(a))$ logical equivalence, resulting in a contradiction


$therefore (exists x: A(x) to forall x : B(x)) to forall x(A(x) to B(x))$



What I learned: it is typically safe to instantiate when there is one existential quantifier, which is not negated.










share|cite|improve this question




















  • 3




    Why on Earth is this downvoted? Sure, the user didn't use $LaTeX$, but come on! They're new!
    – Shaun
    Nov 18 at 1:43










  • Please use MathJax is future, @OldGreg.
    – Shaun
    Nov 18 at 1:44










  • @Shaun: It's not my downvote, but there's a loose group of users who don't like pure proof-verification questions and think they don't add value to the site.
    – Henning Makholm
    Nov 18 at 1:49










  • I am of the view that it is better to edit new contributor's work into mathjax rather then downvoting them for that.
    – Q the Platypus
    Nov 18 at 1:49










  • Same. I've started the hard parts of editing the mathjax into the post, but I'm a bit strapped on time. Finishing up the mathjax edits would be good editing practice if someone else is interested.
    – Larry B.
    Nov 18 at 1:50















up vote
3
down vote

favorite












Is this a valid proof for the following problem?



Prove:



$$models (exists x : A(x) to forall x : B(x)) to forall x : (A(x) to B(x))$$



Proof by contradiction:




  1. Assume $(exists x: A(x) to forall x : B(x)) land lnot (forall x(A(x) to B(x))$


  2. $ (lnot exists x : A(x) lor forall x : B(x)) land lnotforall x : (A(x) to B(x))$ logical equivalence


  3. $forall x : lnot A(x) lor forall x : B(x)) land lnot(forall x : (A(x) to B(x))$ logical equivalence


  4. $lnot A(a) lor B(a) land lnot((A(a) to B(a))$ instantiation


  5. $((A(a) to B(a)) land lnot((A(a) to B(a))$ a contradiction



$therefore (exists x: A(x) to forall x : B(x)) to forall x(A(x) to B(x))$



Edit: corrected a typo on step 2



Update: Professor's Solution:




  1. Assume $(exists x: A(x) to forall x : B(x)) land lnot (forall x(A(x) to B(x))$


  2. $ (lnot exists x : A(x) lor forall x : B(x)) land lnotforall x : (A(x) to B(x))$ logical equivalence


  3. $ (lnot exists x : A(x) lor forall x : B(x)) land lnotforall x : (lnot A(x) lor B(x))$ logical equivalence


  4. $ ( forall x : lnot A(x) lor forall x : B(x)) land lnotforall x : (lnot A(x) lor B(x))$ logical equivalence


  5. $ ( forall x : lnot A(x) lor forall x : B(x)) land exists x : lnot(lnot A(x) lor B(x))$ logical equivalence



  6. $ ( forall x : lnot A(x) lor forall x : B(x)) land exists x : ( A(x) land lnot B(x))$ distribute negation


  7. $ ( lnot A(a) lor B(a)) land ( A(a) land lnot B(a))$ instantiation


  8. $ ( lnot A(a) lor B(a)) land ( lnot A(a) lor B(a))$ logical equivalence, resulting in a contradiction


$therefore (exists x: A(x) to forall x : B(x)) to forall x(A(x) to B(x))$



What I learned: it is typically safe to instantiate when there is one existential quantifier, which is not negated.










share|cite|improve this question




















  • 3




    Why on Earth is this downvoted? Sure, the user didn't use $LaTeX$, but come on! They're new!
    – Shaun
    Nov 18 at 1:43










  • Please use MathJax is future, @OldGreg.
    – Shaun
    Nov 18 at 1:44










  • @Shaun: It's not my downvote, but there's a loose group of users who don't like pure proof-verification questions and think they don't add value to the site.
    – Henning Makholm
    Nov 18 at 1:49










  • I am of the view that it is better to edit new contributor's work into mathjax rather then downvoting them for that.
    – Q the Platypus
    Nov 18 at 1:49










  • Same. I've started the hard parts of editing the mathjax into the post, but I'm a bit strapped on time. Finishing up the mathjax edits would be good editing practice if someone else is interested.
    – Larry B.
    Nov 18 at 1:50













up vote
3
down vote

favorite









up vote
3
down vote

favorite











Is this a valid proof for the following problem?



Prove:



$$models (exists x : A(x) to forall x : B(x)) to forall x : (A(x) to B(x))$$



Proof by contradiction:




  1. Assume $(exists x: A(x) to forall x : B(x)) land lnot (forall x(A(x) to B(x))$


  2. $ (lnot exists x : A(x) lor forall x : B(x)) land lnotforall x : (A(x) to B(x))$ logical equivalence


  3. $forall x : lnot A(x) lor forall x : B(x)) land lnot(forall x : (A(x) to B(x))$ logical equivalence


  4. $lnot A(a) lor B(a) land lnot((A(a) to B(a))$ instantiation


  5. $((A(a) to B(a)) land lnot((A(a) to B(a))$ a contradiction



$therefore (exists x: A(x) to forall x : B(x)) to forall x(A(x) to B(x))$



Edit: corrected a typo on step 2



Update: Professor's Solution:




  1. Assume $(exists x: A(x) to forall x : B(x)) land lnot (forall x(A(x) to B(x))$


  2. $ (lnot exists x : A(x) lor forall x : B(x)) land lnotforall x : (A(x) to B(x))$ logical equivalence


  3. $ (lnot exists x : A(x) lor forall x : B(x)) land lnotforall x : (lnot A(x) lor B(x))$ logical equivalence


  4. $ ( forall x : lnot A(x) lor forall x : B(x)) land lnotforall x : (lnot A(x) lor B(x))$ logical equivalence


  5. $ ( forall x : lnot A(x) lor forall x : B(x)) land exists x : lnot(lnot A(x) lor B(x))$ logical equivalence



  6. $ ( forall x : lnot A(x) lor forall x : B(x)) land exists x : ( A(x) land lnot B(x))$ distribute negation


  7. $ ( lnot A(a) lor B(a)) land ( A(a) land lnot B(a))$ instantiation


  8. $ ( lnot A(a) lor B(a)) land ( lnot A(a) lor B(a))$ logical equivalence, resulting in a contradiction


$therefore (exists x: A(x) to forall x : B(x)) to forall x(A(x) to B(x))$



What I learned: it is typically safe to instantiate when there is one existential quantifier, which is not negated.










share|cite|improve this question















Is this a valid proof for the following problem?



Prove:



$$models (exists x : A(x) to forall x : B(x)) to forall x : (A(x) to B(x))$$



Proof by contradiction:




  1. Assume $(exists x: A(x) to forall x : B(x)) land lnot (forall x(A(x) to B(x))$


  2. $ (lnot exists x : A(x) lor forall x : B(x)) land lnotforall x : (A(x) to B(x))$ logical equivalence


  3. $forall x : lnot A(x) lor forall x : B(x)) land lnot(forall x : (A(x) to B(x))$ logical equivalence


  4. $lnot A(a) lor B(a) land lnot((A(a) to B(a))$ instantiation


  5. $((A(a) to B(a)) land lnot((A(a) to B(a))$ a contradiction



$therefore (exists x: A(x) to forall x : B(x)) to forall x(A(x) to B(x))$



Edit: corrected a typo on step 2



Update: Professor's Solution:




  1. Assume $(exists x: A(x) to forall x : B(x)) land lnot (forall x(A(x) to B(x))$


  2. $ (lnot exists x : A(x) lor forall x : B(x)) land lnotforall x : (A(x) to B(x))$ logical equivalence


  3. $ (lnot exists x : A(x) lor forall x : B(x)) land lnotforall x : (lnot A(x) lor B(x))$ logical equivalence


  4. $ ( forall x : lnot A(x) lor forall x : B(x)) land lnotforall x : (lnot A(x) lor B(x))$ logical equivalence


  5. $ ( forall x : lnot A(x) lor forall x : B(x)) land exists x : lnot(lnot A(x) lor B(x))$ logical equivalence



  6. $ ( forall x : lnot A(x) lor forall x : B(x)) land exists x : ( A(x) land lnot B(x))$ distribute negation


  7. $ ( lnot A(a) lor B(a)) land ( A(a) land lnot B(a))$ instantiation


  8. $ ( lnot A(a) lor B(a)) land ( lnot A(a) lor B(a))$ logical equivalence, resulting in a contradiction


$therefore (exists x: A(x) to forall x : B(x)) to forall x(A(x) to B(x))$



What I learned: it is typically safe to instantiate when there is one existential quantifier, which is not negated.







proof-verification logic first-order-logic






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Nov 20 at 7:03

























asked Nov 18 at 1:34









OldGreg

214




214








  • 3




    Why on Earth is this downvoted? Sure, the user didn't use $LaTeX$, but come on! They're new!
    – Shaun
    Nov 18 at 1:43










  • Please use MathJax is future, @OldGreg.
    – Shaun
    Nov 18 at 1:44










  • @Shaun: It's not my downvote, but there's a loose group of users who don't like pure proof-verification questions and think they don't add value to the site.
    – Henning Makholm
    Nov 18 at 1:49










  • I am of the view that it is better to edit new contributor's work into mathjax rather then downvoting them for that.
    – Q the Platypus
    Nov 18 at 1:49










  • Same. I've started the hard parts of editing the mathjax into the post, but I'm a bit strapped on time. Finishing up the mathjax edits would be good editing practice if someone else is interested.
    – Larry B.
    Nov 18 at 1:50














  • 3




    Why on Earth is this downvoted? Sure, the user didn't use $LaTeX$, but come on! They're new!
    – Shaun
    Nov 18 at 1:43










  • Please use MathJax is future, @OldGreg.
    – Shaun
    Nov 18 at 1:44










  • @Shaun: It's not my downvote, but there's a loose group of users who don't like pure proof-verification questions and think they don't add value to the site.
    – Henning Makholm
    Nov 18 at 1:49










  • I am of the view that it is better to edit new contributor's work into mathjax rather then downvoting them for that.
    – Q the Platypus
    Nov 18 at 1:49










  • Same. I've started the hard parts of editing the mathjax into the post, but I'm a bit strapped on time. Finishing up the mathjax edits would be good editing practice if someone else is interested.
    – Larry B.
    Nov 18 at 1:50








3




3




Why on Earth is this downvoted? Sure, the user didn't use $LaTeX$, but come on! They're new!
– Shaun
Nov 18 at 1:43




Why on Earth is this downvoted? Sure, the user didn't use $LaTeX$, but come on! They're new!
– Shaun
Nov 18 at 1:43












Please use MathJax is future, @OldGreg.
– Shaun
Nov 18 at 1:44




Please use MathJax is future, @OldGreg.
– Shaun
Nov 18 at 1:44












@Shaun: It's not my downvote, but there's a loose group of users who don't like pure proof-verification questions and think they don't add value to the site.
– Henning Makholm
Nov 18 at 1:49




@Shaun: It's not my downvote, but there's a loose group of users who don't like pure proof-verification questions and think they don't add value to the site.
– Henning Makholm
Nov 18 at 1:49












I am of the view that it is better to edit new contributor's work into mathjax rather then downvoting them for that.
– Q the Platypus
Nov 18 at 1:49




I am of the view that it is better to edit new contributor's work into mathjax rather then downvoting them for that.
– Q the Platypus
Nov 18 at 1:49












Same. I've started the hard parts of editing the mathjax into the post, but I'm a bit strapped on time. Finishing up the mathjax edits would be good editing practice if someone else is interested.
– Larry B.
Nov 18 at 1:50




Same. I've started the hard parts of editing the mathjax into the post, but I'm a bit strapped on time. Finishing up the mathjax edits would be good editing practice if someone else is interested.
– Larry B.
Nov 18 at 1:50










3 Answers
3






active

oldest

votes

















up vote
1
down vote













In step 2 you make use of the equivalence



$neg(exists x . A(x) lor forall x.B(x)) iff forall x . neg A(x) ∨ forall x . B(x) $



This is not a real equivalence compare it to demorgans law.



$neg(exists x . A(x) lor forall x.B(x)) iff neg(exists x . A(x)) land neg(forall x.B(x))$






share|cite|improve this answer






























    up vote
    1
    down vote













    If you want a syntactic proof for a conditional statement, I suggest that you should use a Conditional Proof format.



    So assume $exists x~A(x)toforall x~B(x)$ and do something to derive $forall x~(A(x)to B(x))$.



    Then discharge the assumption with conditional introduction.



    $deffitch#1#2{quadbegin{array}{|l} #1\hline #2end{array}}
    fitch{}{fitch{1.~exists x~A(x)~to~forall x~B(x)}{fitch{~ldots}{~ddots}\8.~forall x~(A(x)to B(x))}\9.~(exists x~A(x)toforall x~B(x))toforall x~(A(x)to B(x))}$






    share|cite|improve this answer




























      up vote
      1
      down vote













      Step 4 is wrong!



      It looks like you instantiated all universals with an $a$, but you cannot do that when the universals are part of a larger sentence.



      Consider: Suppose you have



      $$neg forall x P(x) land neg forall x neg P(x)$$



      Now, if we are allowed to just instantiate each of these universals with an $a$, we would get $neg P(a) land neg neg P(a)$, which is a contradiction. But, the orginal statement is not a contradiction at all; if we interpret $P(x)$ as '$x$ is even', and the domain is all numbers, then the original statement is obviously true.



      Even more fundamentally, if you have $neg forall x P(x)$, you cannot fill in anything you want. Using the same interpretation as before, it is clear that $neg forall x P(x)$ is true, but $neg P(0)$ is not. So, you cannot instantiate a universal with anything you wany if it is being negated, but this is what you did when in step 4 you went from $neg forall x (A(x) rightarrow B(x))$ to $neg (A(a) rightarrow B(x))$



      Step 2 is also wrong. The result of rewriting the conditional as an implication should be:



      $(neg exists x A(x) lor forall x B(x)) land neg forall x (A(x) rightarrow B(x))$



      Interestingly, given your step 2, step 3 is also wrong, as pointed out by @QthePlatypus, but with this corrected step 2, your step 3 actually would follow ... so maybe this was just a typo on your part?






      share|cite|improve this answer























      • Thank you for the detailed example. I am a beginner, and I am still struggling with understanding when instantiation is allowed, I don't yet have a good strategy. It looks like a strategy might be to translate the line into informal English, in order to see whether or not instantiating will lead to a contradiction. Would a translation of your example be something like: "No number x is both even and not even."? If you know of any good resources, I would love more practice with quantifiers and instantiation, the more examples the better.
        – OldGreg
        Nov 19 at 3:43












      • thanks again, I made the correction to step 2.
        – OldGreg
        Nov 19 at 3:54










      • @oldgreg The official rule of instantiation is such that you can only use it when the whole statement is a universal. Any universal that is part of a larger statement cannit be instantiated.
        – Bram28
        Nov 19 at 3:59











      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',
      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%2f3003048%2fdoes-this-prove-the-validity-of-this-first-order-logic-formula%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








      up vote
      1
      down vote













      In step 2 you make use of the equivalence



      $neg(exists x . A(x) lor forall x.B(x)) iff forall x . neg A(x) ∨ forall x . B(x) $



      This is not a real equivalence compare it to demorgans law.



      $neg(exists x . A(x) lor forall x.B(x)) iff neg(exists x . A(x)) land neg(forall x.B(x))$






      share|cite|improve this answer



























        up vote
        1
        down vote













        In step 2 you make use of the equivalence



        $neg(exists x . A(x) lor forall x.B(x)) iff forall x . neg A(x) ∨ forall x . B(x) $



        This is not a real equivalence compare it to demorgans law.



        $neg(exists x . A(x) lor forall x.B(x)) iff neg(exists x . A(x)) land neg(forall x.B(x))$






        share|cite|improve this answer

























          up vote
          1
          down vote










          up vote
          1
          down vote









          In step 2 you make use of the equivalence



          $neg(exists x . A(x) lor forall x.B(x)) iff forall x . neg A(x) ∨ forall x . B(x) $



          This is not a real equivalence compare it to demorgans law.



          $neg(exists x . A(x) lor forall x.B(x)) iff neg(exists x . A(x)) land neg(forall x.B(x))$






          share|cite|improve this answer














          In step 2 you make use of the equivalence



          $neg(exists x . A(x) lor forall x.B(x)) iff forall x . neg A(x) ∨ forall x . B(x) $



          This is not a real equivalence compare it to demorgans law.



          $neg(exists x . A(x) lor forall x.B(x)) iff neg(exists x . A(x)) land neg(forall x.B(x))$







          share|cite|improve this answer














          share|cite|improve this answer



          share|cite|improve this answer








          edited Nov 18 at 2:30

























          answered Nov 18 at 2:16









          Q the Platypus

          2,754933




          2,754933






















              up vote
              1
              down vote













              If you want a syntactic proof for a conditional statement, I suggest that you should use a Conditional Proof format.



              So assume $exists x~A(x)toforall x~B(x)$ and do something to derive $forall x~(A(x)to B(x))$.



              Then discharge the assumption with conditional introduction.



              $deffitch#1#2{quadbegin{array}{|l} #1\hline #2end{array}}
              fitch{}{fitch{1.~exists x~A(x)~to~forall x~B(x)}{fitch{~ldots}{~ddots}\8.~forall x~(A(x)to B(x))}\9.~(exists x~A(x)toforall x~B(x))toforall x~(A(x)to B(x))}$






              share|cite|improve this answer

























                up vote
                1
                down vote













                If you want a syntactic proof for a conditional statement, I suggest that you should use a Conditional Proof format.



                So assume $exists x~A(x)toforall x~B(x)$ and do something to derive $forall x~(A(x)to B(x))$.



                Then discharge the assumption with conditional introduction.



                $deffitch#1#2{quadbegin{array}{|l} #1\hline #2end{array}}
                fitch{}{fitch{1.~exists x~A(x)~to~forall x~B(x)}{fitch{~ldots}{~ddots}\8.~forall x~(A(x)to B(x))}\9.~(exists x~A(x)toforall x~B(x))toforall x~(A(x)to B(x))}$






                share|cite|improve this answer























                  up vote
                  1
                  down vote










                  up vote
                  1
                  down vote









                  If you want a syntactic proof for a conditional statement, I suggest that you should use a Conditional Proof format.



                  So assume $exists x~A(x)toforall x~B(x)$ and do something to derive $forall x~(A(x)to B(x))$.



                  Then discharge the assumption with conditional introduction.



                  $deffitch#1#2{quadbegin{array}{|l} #1\hline #2end{array}}
                  fitch{}{fitch{1.~exists x~A(x)~to~forall x~B(x)}{fitch{~ldots}{~ddots}\8.~forall x~(A(x)to B(x))}\9.~(exists x~A(x)toforall x~B(x))toforall x~(A(x)to B(x))}$






                  share|cite|improve this answer












                  If you want a syntactic proof for a conditional statement, I suggest that you should use a Conditional Proof format.



                  So assume $exists x~A(x)toforall x~B(x)$ and do something to derive $forall x~(A(x)to B(x))$.



                  Then discharge the assumption with conditional introduction.



                  $deffitch#1#2{quadbegin{array}{|l} #1\hline #2end{array}}
                  fitch{}{fitch{1.~exists x~A(x)~to~forall x~B(x)}{fitch{~ldots}{~ddots}\8.~forall x~(A(x)to B(x))}\9.~(exists x~A(x)toforall x~B(x))toforall x~(A(x)to B(x))}$







                  share|cite|improve this answer












                  share|cite|improve this answer



                  share|cite|improve this answer










                  answered Nov 19 at 1:43









                  Graham Kemp

                  84.5k43378




                  84.5k43378






















                      up vote
                      1
                      down vote













                      Step 4 is wrong!



                      It looks like you instantiated all universals with an $a$, but you cannot do that when the universals are part of a larger sentence.



                      Consider: Suppose you have



                      $$neg forall x P(x) land neg forall x neg P(x)$$



                      Now, if we are allowed to just instantiate each of these universals with an $a$, we would get $neg P(a) land neg neg P(a)$, which is a contradiction. But, the orginal statement is not a contradiction at all; if we interpret $P(x)$ as '$x$ is even', and the domain is all numbers, then the original statement is obviously true.



                      Even more fundamentally, if you have $neg forall x P(x)$, you cannot fill in anything you want. Using the same interpretation as before, it is clear that $neg forall x P(x)$ is true, but $neg P(0)$ is not. So, you cannot instantiate a universal with anything you wany if it is being negated, but this is what you did when in step 4 you went from $neg forall x (A(x) rightarrow B(x))$ to $neg (A(a) rightarrow B(x))$



                      Step 2 is also wrong. The result of rewriting the conditional as an implication should be:



                      $(neg exists x A(x) lor forall x B(x)) land neg forall x (A(x) rightarrow B(x))$



                      Interestingly, given your step 2, step 3 is also wrong, as pointed out by @QthePlatypus, but with this corrected step 2, your step 3 actually would follow ... so maybe this was just a typo on your part?






                      share|cite|improve this answer























                      • Thank you for the detailed example. I am a beginner, and I am still struggling with understanding when instantiation is allowed, I don't yet have a good strategy. It looks like a strategy might be to translate the line into informal English, in order to see whether or not instantiating will lead to a contradiction. Would a translation of your example be something like: "No number x is both even and not even."? If you know of any good resources, I would love more practice with quantifiers and instantiation, the more examples the better.
                        – OldGreg
                        Nov 19 at 3:43












                      • thanks again, I made the correction to step 2.
                        – OldGreg
                        Nov 19 at 3:54










                      • @oldgreg The official rule of instantiation is such that you can only use it when the whole statement is a universal. Any universal that is part of a larger statement cannit be instantiated.
                        – Bram28
                        Nov 19 at 3:59















                      up vote
                      1
                      down vote













                      Step 4 is wrong!



                      It looks like you instantiated all universals with an $a$, but you cannot do that when the universals are part of a larger sentence.



                      Consider: Suppose you have



                      $$neg forall x P(x) land neg forall x neg P(x)$$



                      Now, if we are allowed to just instantiate each of these universals with an $a$, we would get $neg P(a) land neg neg P(a)$, which is a contradiction. But, the orginal statement is not a contradiction at all; if we interpret $P(x)$ as '$x$ is even', and the domain is all numbers, then the original statement is obviously true.



                      Even more fundamentally, if you have $neg forall x P(x)$, you cannot fill in anything you want. Using the same interpretation as before, it is clear that $neg forall x P(x)$ is true, but $neg P(0)$ is not. So, you cannot instantiate a universal with anything you wany if it is being negated, but this is what you did when in step 4 you went from $neg forall x (A(x) rightarrow B(x))$ to $neg (A(a) rightarrow B(x))$



                      Step 2 is also wrong. The result of rewriting the conditional as an implication should be:



                      $(neg exists x A(x) lor forall x B(x)) land neg forall x (A(x) rightarrow B(x))$



                      Interestingly, given your step 2, step 3 is also wrong, as pointed out by @QthePlatypus, but with this corrected step 2, your step 3 actually would follow ... so maybe this was just a typo on your part?






                      share|cite|improve this answer























                      • Thank you for the detailed example. I am a beginner, and I am still struggling with understanding when instantiation is allowed, I don't yet have a good strategy. It looks like a strategy might be to translate the line into informal English, in order to see whether or not instantiating will lead to a contradiction. Would a translation of your example be something like: "No number x is both even and not even."? If you know of any good resources, I would love more practice with quantifiers and instantiation, the more examples the better.
                        – OldGreg
                        Nov 19 at 3:43












                      • thanks again, I made the correction to step 2.
                        – OldGreg
                        Nov 19 at 3:54










                      • @oldgreg The official rule of instantiation is such that you can only use it when the whole statement is a universal. Any universal that is part of a larger statement cannit be instantiated.
                        – Bram28
                        Nov 19 at 3:59













                      up vote
                      1
                      down vote










                      up vote
                      1
                      down vote









                      Step 4 is wrong!



                      It looks like you instantiated all universals with an $a$, but you cannot do that when the universals are part of a larger sentence.



                      Consider: Suppose you have



                      $$neg forall x P(x) land neg forall x neg P(x)$$



                      Now, if we are allowed to just instantiate each of these universals with an $a$, we would get $neg P(a) land neg neg P(a)$, which is a contradiction. But, the orginal statement is not a contradiction at all; if we interpret $P(x)$ as '$x$ is even', and the domain is all numbers, then the original statement is obviously true.



                      Even more fundamentally, if you have $neg forall x P(x)$, you cannot fill in anything you want. Using the same interpretation as before, it is clear that $neg forall x P(x)$ is true, but $neg P(0)$ is not. So, you cannot instantiate a universal with anything you wany if it is being negated, but this is what you did when in step 4 you went from $neg forall x (A(x) rightarrow B(x))$ to $neg (A(a) rightarrow B(x))$



                      Step 2 is also wrong. The result of rewriting the conditional as an implication should be:



                      $(neg exists x A(x) lor forall x B(x)) land neg forall x (A(x) rightarrow B(x))$



                      Interestingly, given your step 2, step 3 is also wrong, as pointed out by @QthePlatypus, but with this corrected step 2, your step 3 actually would follow ... so maybe this was just a typo on your part?






                      share|cite|improve this answer














                      Step 4 is wrong!



                      It looks like you instantiated all universals with an $a$, but you cannot do that when the universals are part of a larger sentence.



                      Consider: Suppose you have



                      $$neg forall x P(x) land neg forall x neg P(x)$$



                      Now, if we are allowed to just instantiate each of these universals with an $a$, we would get $neg P(a) land neg neg P(a)$, which is a contradiction. But, the orginal statement is not a contradiction at all; if we interpret $P(x)$ as '$x$ is even', and the domain is all numbers, then the original statement is obviously true.



                      Even more fundamentally, if you have $neg forall x P(x)$, you cannot fill in anything you want. Using the same interpretation as before, it is clear that $neg forall x P(x)$ is true, but $neg P(0)$ is not. So, you cannot instantiate a universal with anything you wany if it is being negated, but this is what you did when in step 4 you went from $neg forall x (A(x) rightarrow B(x))$ to $neg (A(a) rightarrow B(x))$



                      Step 2 is also wrong. The result of rewriting the conditional as an implication should be:



                      $(neg exists x A(x) lor forall x B(x)) land neg forall x (A(x) rightarrow B(x))$



                      Interestingly, given your step 2, step 3 is also wrong, as pointed out by @QthePlatypus, but with this corrected step 2, your step 3 actually would follow ... so maybe this was just a typo on your part?







                      share|cite|improve this answer














                      share|cite|improve this answer



                      share|cite|improve this answer








                      edited Nov 19 at 2:31

























                      answered Nov 19 at 0:39









                      Bram28

                      58.6k44185




                      58.6k44185












                      • Thank you for the detailed example. I am a beginner, and I am still struggling with understanding when instantiation is allowed, I don't yet have a good strategy. It looks like a strategy might be to translate the line into informal English, in order to see whether or not instantiating will lead to a contradiction. Would a translation of your example be something like: "No number x is both even and not even."? If you know of any good resources, I would love more practice with quantifiers and instantiation, the more examples the better.
                        – OldGreg
                        Nov 19 at 3:43












                      • thanks again, I made the correction to step 2.
                        – OldGreg
                        Nov 19 at 3:54










                      • @oldgreg The official rule of instantiation is such that you can only use it when the whole statement is a universal. Any universal that is part of a larger statement cannit be instantiated.
                        – Bram28
                        Nov 19 at 3:59


















                      • Thank you for the detailed example. I am a beginner, and I am still struggling with understanding when instantiation is allowed, I don't yet have a good strategy. It looks like a strategy might be to translate the line into informal English, in order to see whether or not instantiating will lead to a contradiction. Would a translation of your example be something like: "No number x is both even and not even."? If you know of any good resources, I would love more practice with quantifiers and instantiation, the more examples the better.
                        – OldGreg
                        Nov 19 at 3:43












                      • thanks again, I made the correction to step 2.
                        – OldGreg
                        Nov 19 at 3:54










                      • @oldgreg The official rule of instantiation is such that you can only use it when the whole statement is a universal. Any universal that is part of a larger statement cannit be instantiated.
                        – Bram28
                        Nov 19 at 3:59
















                      Thank you for the detailed example. I am a beginner, and I am still struggling with understanding when instantiation is allowed, I don't yet have a good strategy. It looks like a strategy might be to translate the line into informal English, in order to see whether or not instantiating will lead to a contradiction. Would a translation of your example be something like: "No number x is both even and not even."? If you know of any good resources, I would love more practice with quantifiers and instantiation, the more examples the better.
                      – OldGreg
                      Nov 19 at 3:43






                      Thank you for the detailed example. I am a beginner, and I am still struggling with understanding when instantiation is allowed, I don't yet have a good strategy. It looks like a strategy might be to translate the line into informal English, in order to see whether or not instantiating will lead to a contradiction. Would a translation of your example be something like: "No number x is both even and not even."? If you know of any good resources, I would love more practice with quantifiers and instantiation, the more examples the better.
                      – OldGreg
                      Nov 19 at 3:43














                      thanks again, I made the correction to step 2.
                      – OldGreg
                      Nov 19 at 3:54




                      thanks again, I made the correction to step 2.
                      – OldGreg
                      Nov 19 at 3:54












                      @oldgreg The official rule of instantiation is such that you can only use it when the whole statement is a universal. Any universal that is part of a larger statement cannit be instantiated.
                      – Bram28
                      Nov 19 at 3:59




                      @oldgreg The official rule of instantiation is such that you can only use it when the whole statement is a universal. Any universal that is part of a larger statement cannit be instantiated.
                      – Bram28
                      Nov 19 at 3:59


















                      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.





                      Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


                      Please pay close attention to the following guidance:


                      • 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.


                      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%2f3003048%2fdoes-this-prove-the-validity-of-this-first-order-logic-formula%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

                      AnyDesk - Fatal Program Failure

                      How to calibrate 16:9 built-in touch-screen to a 4:3 resolution?

                      QoS: MAC-Priority for clients behind a repeater