Fitch proof exercise: showing $(lnot forall x ; P(x)) leftrightarrow (exists x lnot P(x))$












1












$begingroup$


I have got a Problem with the following fitch proof excercise:




$quad;; |$



$triangleright quad | quad ?. quad (lnot forall x ; P(x)) leftrightarrow (exists x lnot P(x))$




This is how far I got: (Notice: I started from the bottom to the top!)



enter image description here



My problem is, that I can't find a way how to contradict $P(c)$. My first idea was, to proof $forall x ; P(x)$ in the subproof in order to get a contradiction.



As you can see, this is only the first part of the proof. I know that I will have to use a Biconditional introduction in the end. I only need help for the first subproof.



Would be great if anyone could give me some hints.










share|cite|improve this question











$endgroup$












  • $begingroup$
    Welcome to math stackexchange. I have tidied up your question -- we like it when titles are very specific! I hope you find the answers helpful.
    $endgroup$
    – 6005
    Jan 5 at 13:02










  • $begingroup$
    Thank you very much. I will do better next time ;).
    $endgroup$
    – Jenew
    Jan 5 at 13:10
















1












$begingroup$


I have got a Problem with the following fitch proof excercise:




$quad;; |$



$triangleright quad | quad ?. quad (lnot forall x ; P(x)) leftrightarrow (exists x lnot P(x))$




This is how far I got: (Notice: I started from the bottom to the top!)



enter image description here



My problem is, that I can't find a way how to contradict $P(c)$. My first idea was, to proof $forall x ; P(x)$ in the subproof in order to get a contradiction.



As you can see, this is only the first part of the proof. I know that I will have to use a Biconditional introduction in the end. I only need help for the first subproof.



Would be great if anyone could give me some hints.










share|cite|improve this question











$endgroup$












  • $begingroup$
    Welcome to math stackexchange. I have tidied up your question -- we like it when titles are very specific! I hope you find the answers helpful.
    $endgroup$
    – 6005
    Jan 5 at 13:02










  • $begingroup$
    Thank you very much. I will do better next time ;).
    $endgroup$
    – Jenew
    Jan 5 at 13:10














1












1








1





$begingroup$


I have got a Problem with the following fitch proof excercise:




$quad;; |$



$triangleright quad | quad ?. quad (lnot forall x ; P(x)) leftrightarrow (exists x lnot P(x))$




This is how far I got: (Notice: I started from the bottom to the top!)



enter image description here



My problem is, that I can't find a way how to contradict $P(c)$. My first idea was, to proof $forall x ; P(x)$ in the subproof in order to get a contradiction.



As you can see, this is only the first part of the proof. I know that I will have to use a Biconditional introduction in the end. I only need help for the first subproof.



Would be great if anyone could give me some hints.










share|cite|improve this question











$endgroup$




I have got a Problem with the following fitch proof excercise:




$quad;; |$



$triangleright quad | quad ?. quad (lnot forall x ; P(x)) leftrightarrow (exists x lnot P(x))$




This is how far I got: (Notice: I started from the bottom to the top!)



enter image description here



My problem is, that I can't find a way how to contradict $P(c)$. My first idea was, to proof $forall x ; P(x)$ in the subproof in order to get a contradiction.



As you can see, this is only the first part of the proof. I know that I will have to use a Biconditional introduction in the end. I only need help for the first subproof.



Would be great if anyone could give me some hints.







logic first-order-logic predicate-logic






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Feb 18 at 14:32









Mauro ALLEGRANZA

66.9k449115




66.9k449115










asked Jan 5 at 12:17









JenewJenew

112




112












  • $begingroup$
    Welcome to math stackexchange. I have tidied up your question -- we like it when titles are very specific! I hope you find the answers helpful.
    $endgroup$
    – 6005
    Jan 5 at 13:02










  • $begingroup$
    Thank you very much. I will do better next time ;).
    $endgroup$
    – Jenew
    Jan 5 at 13:10


















  • $begingroup$
    Welcome to math stackexchange. I have tidied up your question -- we like it when titles are very specific! I hope you find the answers helpful.
    $endgroup$
    – 6005
    Jan 5 at 13:02










  • $begingroup$
    Thank you very much. I will do better next time ;).
    $endgroup$
    – Jenew
    Jan 5 at 13:10
















$begingroup$
Welcome to math stackexchange. I have tidied up your question -- we like it when titles are very specific! I hope you find the answers helpful.
$endgroup$
– 6005
Jan 5 at 13:02




$begingroup$
Welcome to math stackexchange. I have tidied up your question -- we like it when titles are very specific! I hope you find the answers helpful.
$endgroup$
– 6005
Jan 5 at 13:02












$begingroup$
Thank you very much. I will do better next time ;).
$endgroup$
– Jenew
Jan 5 at 13:10




$begingroup$
Thank you very much. I will do better next time ;).
$endgroup$
– Jenew
Jan 5 at 13:10










2 Answers
2






active

oldest

votes


















2












$begingroup$

It looks to me like you are trying to show that $lnot P(c)$ as a lemma, where you have made no assumptions about $c$. If that were provable, then it would follow that $forall x ( lnot P(x))$. But that's too strong -- you only want to show that $exists x (lnot P(x))$. (Convince yourself that $forall x ( lnot P(x))$ is not necessarily implied by $lnot (forall x ( P(x))$, perhaps by thinking of an example set of $x$s and predicate $P$.)



So your dilemma is that you need to get the correct $c$ somehow, in order to prove that $exists x (lnot P(x))$; but you only know that $lnot forall x. P(x)$, and there's no way to get a $c$ directly from that statement.



In a situation where you get stuck it's good to try proof by contradiction. So, instead of proving $exists x (lnot P(x))$ (we have no idea how to get $c$ to make this true), try proving
$$
lnot lnot (exists x ( lnot P(x))),
$$

by assuming $lnot exists x ( lnot P(x)))$ and getting a contradiction.
The proof structure will look like this:




1. $lnot ( forall x ( P(x)))$




  1. $lnot exists x ( lnot P(x))$


  2. ...[fill in here]...


  3. $bot$



5. $lnot lnot exists x (lnot P(x))$



6. $exists x (lnot P(x))$ (double negation elimination from 5)




But you have to fill in the details for step 3. ... above.
To do this, show as another lemma there that $forall x (P(x))$. Proving this lemma will just rely on premise $2$, but may require some more nested reasoning$^1$. Then this lemma will get a contradiction with your original assumption $1$.



$^1$ To prove $forall x ( P(x))$ we want to start from no assumptions and get $P(a)$. To do this, assume $lnot P(a)$ and derive a contradiction, thus showing $lnot lnot P(a)$, then double negation to $P(a)$.






share|cite|improve this answer









$endgroup$









  • 1




    $begingroup$
    Thanks for this answer! I managed to find the solution. My fitch program tells me its correct. It was actually way more complex than I thougth.
    $endgroup$
    – Jenew
    Jan 5 at 16:22










  • $begingroup$
    @Jenew Yes, this was a messy one. Sometimes you just end up with tons of sub-proofs by contradiction followed by double-negation elimination.
    $endgroup$
    – 6005
    Jan 5 at 16:40



















1












$begingroup$

Hint



You have to start assuming $lnot Pc$ and $lnot exists x lnot Px$ and find a first contradiction.



Then use Double Negation to derive $Pc$ and from it $forall x Px$ and a new contradiction.



Then, conclude by Double Negation again.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    Right. Although it does not address possible issues with the poster's attempted solution.
    $endgroup$
    – 6005
    Jan 5 at 12:56











Your Answer





StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

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

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

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


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3062661%2ffitch-proof-exercise-showing-lnot-forall-x-px-leftrightarrow-exist%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























2 Answers
2






active

oldest

votes








2 Answers
2






active

oldest

votes









active

oldest

votes






active

oldest

votes









2












$begingroup$

It looks to me like you are trying to show that $lnot P(c)$ as a lemma, where you have made no assumptions about $c$. If that were provable, then it would follow that $forall x ( lnot P(x))$. But that's too strong -- you only want to show that $exists x (lnot P(x))$. (Convince yourself that $forall x ( lnot P(x))$ is not necessarily implied by $lnot (forall x ( P(x))$, perhaps by thinking of an example set of $x$s and predicate $P$.)



So your dilemma is that you need to get the correct $c$ somehow, in order to prove that $exists x (lnot P(x))$; but you only know that $lnot forall x. P(x)$, and there's no way to get a $c$ directly from that statement.



In a situation where you get stuck it's good to try proof by contradiction. So, instead of proving $exists x (lnot P(x))$ (we have no idea how to get $c$ to make this true), try proving
$$
lnot lnot (exists x ( lnot P(x))),
$$

by assuming $lnot exists x ( lnot P(x)))$ and getting a contradiction.
The proof structure will look like this:




1. $lnot ( forall x ( P(x)))$




  1. $lnot exists x ( lnot P(x))$


  2. ...[fill in here]...


  3. $bot$



5. $lnot lnot exists x (lnot P(x))$



6. $exists x (lnot P(x))$ (double negation elimination from 5)




But you have to fill in the details for step 3. ... above.
To do this, show as another lemma there that $forall x (P(x))$. Proving this lemma will just rely on premise $2$, but may require some more nested reasoning$^1$. Then this lemma will get a contradiction with your original assumption $1$.



$^1$ To prove $forall x ( P(x))$ we want to start from no assumptions and get $P(a)$. To do this, assume $lnot P(a)$ and derive a contradiction, thus showing $lnot lnot P(a)$, then double negation to $P(a)$.






share|cite|improve this answer









$endgroup$









  • 1




    $begingroup$
    Thanks for this answer! I managed to find the solution. My fitch program tells me its correct. It was actually way more complex than I thougth.
    $endgroup$
    – Jenew
    Jan 5 at 16:22










  • $begingroup$
    @Jenew Yes, this was a messy one. Sometimes you just end up with tons of sub-proofs by contradiction followed by double-negation elimination.
    $endgroup$
    – 6005
    Jan 5 at 16:40
















2












$begingroup$

It looks to me like you are trying to show that $lnot P(c)$ as a lemma, where you have made no assumptions about $c$. If that were provable, then it would follow that $forall x ( lnot P(x))$. But that's too strong -- you only want to show that $exists x (lnot P(x))$. (Convince yourself that $forall x ( lnot P(x))$ is not necessarily implied by $lnot (forall x ( P(x))$, perhaps by thinking of an example set of $x$s and predicate $P$.)



So your dilemma is that you need to get the correct $c$ somehow, in order to prove that $exists x (lnot P(x))$; but you only know that $lnot forall x. P(x)$, and there's no way to get a $c$ directly from that statement.



In a situation where you get stuck it's good to try proof by contradiction. So, instead of proving $exists x (lnot P(x))$ (we have no idea how to get $c$ to make this true), try proving
$$
lnot lnot (exists x ( lnot P(x))),
$$

by assuming $lnot exists x ( lnot P(x)))$ and getting a contradiction.
The proof structure will look like this:




1. $lnot ( forall x ( P(x)))$




  1. $lnot exists x ( lnot P(x))$


  2. ...[fill in here]...


  3. $bot$



5. $lnot lnot exists x (lnot P(x))$



6. $exists x (lnot P(x))$ (double negation elimination from 5)




But you have to fill in the details for step 3. ... above.
To do this, show as another lemma there that $forall x (P(x))$. Proving this lemma will just rely on premise $2$, but may require some more nested reasoning$^1$. Then this lemma will get a contradiction with your original assumption $1$.



$^1$ To prove $forall x ( P(x))$ we want to start from no assumptions and get $P(a)$. To do this, assume $lnot P(a)$ and derive a contradiction, thus showing $lnot lnot P(a)$, then double negation to $P(a)$.






share|cite|improve this answer









$endgroup$









  • 1




    $begingroup$
    Thanks for this answer! I managed to find the solution. My fitch program tells me its correct. It was actually way more complex than I thougth.
    $endgroup$
    – Jenew
    Jan 5 at 16:22










  • $begingroup$
    @Jenew Yes, this was a messy one. Sometimes you just end up with tons of sub-proofs by contradiction followed by double-negation elimination.
    $endgroup$
    – 6005
    Jan 5 at 16:40














2












2








2





$begingroup$

It looks to me like you are trying to show that $lnot P(c)$ as a lemma, where you have made no assumptions about $c$. If that were provable, then it would follow that $forall x ( lnot P(x))$. But that's too strong -- you only want to show that $exists x (lnot P(x))$. (Convince yourself that $forall x ( lnot P(x))$ is not necessarily implied by $lnot (forall x ( P(x))$, perhaps by thinking of an example set of $x$s and predicate $P$.)



So your dilemma is that you need to get the correct $c$ somehow, in order to prove that $exists x (lnot P(x))$; but you only know that $lnot forall x. P(x)$, and there's no way to get a $c$ directly from that statement.



In a situation where you get stuck it's good to try proof by contradiction. So, instead of proving $exists x (lnot P(x))$ (we have no idea how to get $c$ to make this true), try proving
$$
lnot lnot (exists x ( lnot P(x))),
$$

by assuming $lnot exists x ( lnot P(x)))$ and getting a contradiction.
The proof structure will look like this:




1. $lnot ( forall x ( P(x)))$




  1. $lnot exists x ( lnot P(x))$


  2. ...[fill in here]...


  3. $bot$



5. $lnot lnot exists x (lnot P(x))$



6. $exists x (lnot P(x))$ (double negation elimination from 5)




But you have to fill in the details for step 3. ... above.
To do this, show as another lemma there that $forall x (P(x))$. Proving this lemma will just rely on premise $2$, but may require some more nested reasoning$^1$. Then this lemma will get a contradiction with your original assumption $1$.



$^1$ To prove $forall x ( P(x))$ we want to start from no assumptions and get $P(a)$. To do this, assume $lnot P(a)$ and derive a contradiction, thus showing $lnot lnot P(a)$, then double negation to $P(a)$.






share|cite|improve this answer









$endgroup$



It looks to me like you are trying to show that $lnot P(c)$ as a lemma, where you have made no assumptions about $c$. If that were provable, then it would follow that $forall x ( lnot P(x))$. But that's too strong -- you only want to show that $exists x (lnot P(x))$. (Convince yourself that $forall x ( lnot P(x))$ is not necessarily implied by $lnot (forall x ( P(x))$, perhaps by thinking of an example set of $x$s and predicate $P$.)



So your dilemma is that you need to get the correct $c$ somehow, in order to prove that $exists x (lnot P(x))$; but you only know that $lnot forall x. P(x)$, and there's no way to get a $c$ directly from that statement.



In a situation where you get stuck it's good to try proof by contradiction. So, instead of proving $exists x (lnot P(x))$ (we have no idea how to get $c$ to make this true), try proving
$$
lnot lnot (exists x ( lnot P(x))),
$$

by assuming $lnot exists x ( lnot P(x)))$ and getting a contradiction.
The proof structure will look like this:




1. $lnot ( forall x ( P(x)))$




  1. $lnot exists x ( lnot P(x))$


  2. ...[fill in here]...


  3. $bot$



5. $lnot lnot exists x (lnot P(x))$



6. $exists x (lnot P(x))$ (double negation elimination from 5)




But you have to fill in the details for step 3. ... above.
To do this, show as another lemma there that $forall x (P(x))$. Proving this lemma will just rely on premise $2$, but may require some more nested reasoning$^1$. Then this lemma will get a contradiction with your original assumption $1$.



$^1$ To prove $forall x ( P(x))$ we want to start from no assumptions and get $P(a)$. To do this, assume $lnot P(a)$ and derive a contradiction, thus showing $lnot lnot P(a)$, then double negation to $P(a)$.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered Jan 5 at 12:51









60056005

36.3k751125




36.3k751125








  • 1




    $begingroup$
    Thanks for this answer! I managed to find the solution. My fitch program tells me its correct. It was actually way more complex than I thougth.
    $endgroup$
    – Jenew
    Jan 5 at 16:22










  • $begingroup$
    @Jenew Yes, this was a messy one. Sometimes you just end up with tons of sub-proofs by contradiction followed by double-negation elimination.
    $endgroup$
    – 6005
    Jan 5 at 16:40














  • 1




    $begingroup$
    Thanks for this answer! I managed to find the solution. My fitch program tells me its correct. It was actually way more complex than I thougth.
    $endgroup$
    – Jenew
    Jan 5 at 16:22










  • $begingroup$
    @Jenew Yes, this was a messy one. Sometimes you just end up with tons of sub-proofs by contradiction followed by double-negation elimination.
    $endgroup$
    – 6005
    Jan 5 at 16:40








1




1




$begingroup$
Thanks for this answer! I managed to find the solution. My fitch program tells me its correct. It was actually way more complex than I thougth.
$endgroup$
– Jenew
Jan 5 at 16:22




$begingroup$
Thanks for this answer! I managed to find the solution. My fitch program tells me its correct. It was actually way more complex than I thougth.
$endgroup$
– Jenew
Jan 5 at 16:22












$begingroup$
@Jenew Yes, this was a messy one. Sometimes you just end up with tons of sub-proofs by contradiction followed by double-negation elimination.
$endgroup$
– 6005
Jan 5 at 16:40




$begingroup$
@Jenew Yes, this was a messy one. Sometimes you just end up with tons of sub-proofs by contradiction followed by double-negation elimination.
$endgroup$
– 6005
Jan 5 at 16:40











1












$begingroup$

Hint



You have to start assuming $lnot Pc$ and $lnot exists x lnot Px$ and find a first contradiction.



Then use Double Negation to derive $Pc$ and from it $forall x Px$ and a new contradiction.



Then, conclude by Double Negation again.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    Right. Although it does not address possible issues with the poster's attempted solution.
    $endgroup$
    – 6005
    Jan 5 at 12:56
















1












$begingroup$

Hint



You have to start assuming $lnot Pc$ and $lnot exists x lnot Px$ and find a first contradiction.



Then use Double Negation to derive $Pc$ and from it $forall x Px$ and a new contradiction.



Then, conclude by Double Negation again.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    Right. Although it does not address possible issues with the poster's attempted solution.
    $endgroup$
    – 6005
    Jan 5 at 12:56














1












1








1





$begingroup$

Hint



You have to start assuming $lnot Pc$ and $lnot exists x lnot Px$ and find a first contradiction.



Then use Double Negation to derive $Pc$ and from it $forall x Px$ and a new contradiction.



Then, conclude by Double Negation again.






share|cite|improve this answer











$endgroup$



Hint



You have to start assuming $lnot Pc$ and $lnot exists x lnot Px$ and find a first contradiction.



Then use Double Negation to derive $Pc$ and from it $forall x Px$ and a new contradiction.



Then, conclude by Double Negation again.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Jan 5 at 13:04

























answered Jan 5 at 12:29









Mauro ALLEGRANZAMauro ALLEGRANZA

66.9k449115




66.9k449115












  • $begingroup$
    Right. Although it does not address possible issues with the poster's attempted solution.
    $endgroup$
    – 6005
    Jan 5 at 12:56


















  • $begingroup$
    Right. Although it does not address possible issues with the poster's attempted solution.
    $endgroup$
    – 6005
    Jan 5 at 12:56
















$begingroup$
Right. Although it does not address possible issues with the poster's attempted solution.
$endgroup$
– 6005
Jan 5 at 12:56




$begingroup$
Right. Although it does not address possible issues with the poster's attempted solution.
$endgroup$
– 6005
Jan 5 at 12:56


















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%2f3062661%2ffitch-proof-exercise-showing-lnot-forall-x-px-leftrightarrow-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

Quarter-circle Tiles

build a pushdown automaton that recognizes the reverse language of a given pushdown automaton?

Mont Emei