Given âÂÂx.¬p(x), use the Fitch System to prove ‰ÂÂx.p(x).

Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
What I am thinking was I need two formulas,
AX.p(X) => something
AX.p(X) => ~ something
I guess something maybe is the p(x) and the other is ~p(x) since we was given EX.~p(x)..But actually it can't work for me. And I guess maybe is EX.~p(x) and ~EX.~p(x)..But if I am doing that then the it will go to deadend..so I give up..;(
Wish someone can help me.
For note about EE:
1: EX.p(X)
2: AX.(p(X) => something)
3: something EE1,2
But something cann't have the free variable from p..in this sample, then soemthing cannot including X..so if something is p(X) it cannot use EE, but if p(Y) then can use EE.
logic predicate-logic first-order-logic natural-deduction formal-proofs
add a comment |Â
up vote
1
down vote
favorite
What I am thinking was I need two formulas,
AX.p(X) => something
AX.p(X) => ~ something
I guess something maybe is the p(x) and the other is ~p(x) since we was given EX.~p(x)..But actually it can't work for me. And I guess maybe is EX.~p(x) and ~EX.~p(x)..But if I am doing that then the it will go to deadend..so I give up..;(
Wish someone can help me.
For note about EE:
1: EX.p(X)
2: AX.(p(X) => something)
3: something EE1,2
But something cann't have the free variable from p..in this sample, then soemthing cannot including X..so if something is p(X) it cannot use EE, but if p(Y) then can use EE.
logic predicate-logic first-order-logic natural-deduction formal-proofs
Hint: first prove $lnot p(x) vdash lnot forall x ~ p(x)$. Note the $x$ represent different variables.
â DanielV
Apr 20 '17 at 3:01
Thanks!! slime face ;) @DanielV
â tang aqua
Apr 21 '17 at 0:49
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
What I am thinking was I need two formulas,
AX.p(X) => something
AX.p(X) => ~ something
I guess something maybe is the p(x) and the other is ~p(x) since we was given EX.~p(x)..But actually it can't work for me. And I guess maybe is EX.~p(x) and ~EX.~p(x)..But if I am doing that then the it will go to deadend..so I give up..;(
Wish someone can help me.
For note about EE:
1: EX.p(X)
2: AX.(p(X) => something)
3: something EE1,2
But something cann't have the free variable from p..in this sample, then soemthing cannot including X..so if something is p(X) it cannot use EE, but if p(Y) then can use EE.
logic predicate-logic first-order-logic natural-deduction formal-proofs
What I am thinking was I need two formulas,
AX.p(X) => something
AX.p(X) => ~ something
I guess something maybe is the p(x) and the other is ~p(x) since we was given EX.~p(x)..But actually it can't work for me. And I guess maybe is EX.~p(x) and ~EX.~p(x)..But if I am doing that then the it will go to deadend..so I give up..;(
Wish someone can help me.
For note about EE:
1: EX.p(X)
2: AX.(p(X) => something)
3: something EE1,2
But something cann't have the free variable from p..in this sample, then soemthing cannot including X..so if something is p(X) it cannot use EE, but if p(Y) then can use EE.
logic predicate-logic first-order-logic natural-deduction formal-proofs
edited Apr 20 '17 at 3:32
Bram28
55.4k33982
55.4k33982
asked Apr 20 '17 at 2:56
tang aqua
233
233
Hint: first prove $lnot p(x) vdash lnot forall x ~ p(x)$. Note the $x$ represent different variables.
â DanielV
Apr 20 '17 at 3:01
Thanks!! slime face ;) @DanielV
â tang aqua
Apr 21 '17 at 0:49
add a comment |Â
Hint: first prove $lnot p(x) vdash lnot forall x ~ p(x)$. Note the $x$ represent different variables.
â DanielV
Apr 20 '17 at 3:01
Thanks!! slime face ;) @DanielV
â tang aqua
Apr 21 '17 at 0:49
Hint: first prove $lnot p(x) vdash lnot forall x ~ p(x)$. Note the $x$ represent different variables.
â DanielV
Apr 20 '17 at 3:01
Hint: first prove $lnot p(x) vdash lnot forall x ~ p(x)$. Note the $x$ represent different variables.
â DanielV
Apr 20 '17 at 3:01
Thanks!! slime face ;) @DanielV
â tang aqua
Apr 21 '17 at 0:49
Thanks!! slime face ;) @DanielV
â tang aqua
Apr 21 '17 at 0:49
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
1
down vote
Given your EE rule, you need to prove $forall x (neg p(x) rightarrow neg forall x P(x))$, which you do by a universal introduction on $neg p(x) rightarrow forall x p(x)$, which on its turn you prove by a conditional Introduction on a subproof that assumes $neg p(x)$ and derives $neg forall x p(x)$ .. and the latter you get by a proof by contradiction as you yourself surmised. So:
$exists x neg p(x)$ Premise
$quad neg p(x)$ Assumption
$quad quad forall x p(x)$ Assumption
$quad quad p(x)$ $forall$ Elim 3
$quad forall x p(x) rightarrow p(x)$ $rightarrow$ Intro 3-4
$quad quad forall x p(x)$ Assumption
$quad quad neg p(x)$ Reiteration 2
$quad forall x p(x) rightarrow neg p(x)$ $rightarrow$ Intro 6-7
$quad neg forall x p(x)$ $neg$ Intro 5,8
$neg p(x) rightarrow neg forall x p(x)$ $rightarrow$ Intro 2-9
$forall x (neg p(x) rightarrow neg forall x p(x))$ $forall$ Intro 10
$neg forall x p(x)$ $exists$ Elim 1, 11
How you know that much~!!?? I always stuck at some points and cannot go through...Probably I go into a wrong way.And Thanks again and again~!!
â tang aqua
Apr 20 '17 at 21:22
@tangaqua After years of practice you really start to 'know' all the different patterns :) So yeah, that took me a long time, so don't feel bad if you're struggling. And I said some time before: you don't have the most user-friendly system either ... so it is not necessarily that you are bad with logic, but just that you have a hard time putting that into this particular proof system.
â Bram28
Apr 20 '17 at 22:06
By your inspiration, I just solve the other prove by myself~! Hahaha~! Helps me a lot~
â tang aqua
Apr 21 '17 at 0:51
@tangaqua Yay! Good for you!! :)
â Bram28
Apr 21 '17 at 0:52
2
@tangaqua You shouldn't try writing a formal proof until you can write an informal proof first. Formal proofs are just a language, not an idea. You have to have the idea (the reason why you think the theorem is true) before you can put the idea into a language.
â DanielV
Apr 21 '17 at 3:11
 |Â
show 4 more comments
up vote
1
down vote
Here is my solution:
$1.~exists X~lnot p(X)quad $ Premise
$2.~quad lnot p(c)quad$ Existential Elimination:1, Witness Assumed: $[c]$
$3.~qquadforall X~p(X)quad$ Assumption
$4.~qquad p(c)quad$ Universal Elimination:3
$5.~quad forall X~p(X) implies p(c)quad$ Implication Introduction 3-4
$6.~qquadforall X~p(X)quad$ Assumption
$7.~qquadlnot p(c)quad$ Reiteration:2
$8.~quadforall X p(X) implies lnot p(c)quad$ Implication Introduction: 6-7
$9.~quadlnot forall X~p(X)quad$ Negation Introduction 5,8
$10.~lnot forall X~p(X)quad$ Witness Eliminated 2-9
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
Given your EE rule, you need to prove $forall x (neg p(x) rightarrow neg forall x P(x))$, which you do by a universal introduction on $neg p(x) rightarrow forall x p(x)$, which on its turn you prove by a conditional Introduction on a subproof that assumes $neg p(x)$ and derives $neg forall x p(x)$ .. and the latter you get by a proof by contradiction as you yourself surmised. So:
$exists x neg p(x)$ Premise
$quad neg p(x)$ Assumption
$quad quad forall x p(x)$ Assumption
$quad quad p(x)$ $forall$ Elim 3
$quad forall x p(x) rightarrow p(x)$ $rightarrow$ Intro 3-4
$quad quad forall x p(x)$ Assumption
$quad quad neg p(x)$ Reiteration 2
$quad forall x p(x) rightarrow neg p(x)$ $rightarrow$ Intro 6-7
$quad neg forall x p(x)$ $neg$ Intro 5,8
$neg p(x) rightarrow neg forall x p(x)$ $rightarrow$ Intro 2-9
$forall x (neg p(x) rightarrow neg forall x p(x))$ $forall$ Intro 10
$neg forall x p(x)$ $exists$ Elim 1, 11
How you know that much~!!?? I always stuck at some points and cannot go through...Probably I go into a wrong way.And Thanks again and again~!!
â tang aqua
Apr 20 '17 at 21:22
@tangaqua After years of practice you really start to 'know' all the different patterns :) So yeah, that took me a long time, so don't feel bad if you're struggling. And I said some time before: you don't have the most user-friendly system either ... so it is not necessarily that you are bad with logic, but just that you have a hard time putting that into this particular proof system.
â Bram28
Apr 20 '17 at 22:06
By your inspiration, I just solve the other prove by myself~! Hahaha~! Helps me a lot~
â tang aqua
Apr 21 '17 at 0:51
@tangaqua Yay! Good for you!! :)
â Bram28
Apr 21 '17 at 0:52
2
@tangaqua You shouldn't try writing a formal proof until you can write an informal proof first. Formal proofs are just a language, not an idea. You have to have the idea (the reason why you think the theorem is true) before you can put the idea into a language.
â DanielV
Apr 21 '17 at 3:11
 |Â
show 4 more comments
up vote
1
down vote
Given your EE rule, you need to prove $forall x (neg p(x) rightarrow neg forall x P(x))$, which you do by a universal introduction on $neg p(x) rightarrow forall x p(x)$, which on its turn you prove by a conditional Introduction on a subproof that assumes $neg p(x)$ and derives $neg forall x p(x)$ .. and the latter you get by a proof by contradiction as you yourself surmised. So:
$exists x neg p(x)$ Premise
$quad neg p(x)$ Assumption
$quad quad forall x p(x)$ Assumption
$quad quad p(x)$ $forall$ Elim 3
$quad forall x p(x) rightarrow p(x)$ $rightarrow$ Intro 3-4
$quad quad forall x p(x)$ Assumption
$quad quad neg p(x)$ Reiteration 2
$quad forall x p(x) rightarrow neg p(x)$ $rightarrow$ Intro 6-7
$quad neg forall x p(x)$ $neg$ Intro 5,8
$neg p(x) rightarrow neg forall x p(x)$ $rightarrow$ Intro 2-9
$forall x (neg p(x) rightarrow neg forall x p(x))$ $forall$ Intro 10
$neg forall x p(x)$ $exists$ Elim 1, 11
How you know that much~!!?? I always stuck at some points and cannot go through...Probably I go into a wrong way.And Thanks again and again~!!
â tang aqua
Apr 20 '17 at 21:22
@tangaqua After years of practice you really start to 'know' all the different patterns :) So yeah, that took me a long time, so don't feel bad if you're struggling. And I said some time before: you don't have the most user-friendly system either ... so it is not necessarily that you are bad with logic, but just that you have a hard time putting that into this particular proof system.
â Bram28
Apr 20 '17 at 22:06
By your inspiration, I just solve the other prove by myself~! Hahaha~! Helps me a lot~
â tang aqua
Apr 21 '17 at 0:51
@tangaqua Yay! Good for you!! :)
â Bram28
Apr 21 '17 at 0:52
2
@tangaqua You shouldn't try writing a formal proof until you can write an informal proof first. Formal proofs are just a language, not an idea. You have to have the idea (the reason why you think the theorem is true) before you can put the idea into a language.
â DanielV
Apr 21 '17 at 3:11
 |Â
show 4 more comments
up vote
1
down vote
up vote
1
down vote
Given your EE rule, you need to prove $forall x (neg p(x) rightarrow neg forall x P(x))$, which you do by a universal introduction on $neg p(x) rightarrow forall x p(x)$, which on its turn you prove by a conditional Introduction on a subproof that assumes $neg p(x)$ and derives $neg forall x p(x)$ .. and the latter you get by a proof by contradiction as you yourself surmised. So:
$exists x neg p(x)$ Premise
$quad neg p(x)$ Assumption
$quad quad forall x p(x)$ Assumption
$quad quad p(x)$ $forall$ Elim 3
$quad forall x p(x) rightarrow p(x)$ $rightarrow$ Intro 3-4
$quad quad forall x p(x)$ Assumption
$quad quad neg p(x)$ Reiteration 2
$quad forall x p(x) rightarrow neg p(x)$ $rightarrow$ Intro 6-7
$quad neg forall x p(x)$ $neg$ Intro 5,8
$neg p(x) rightarrow neg forall x p(x)$ $rightarrow$ Intro 2-9
$forall x (neg p(x) rightarrow neg forall x p(x))$ $forall$ Intro 10
$neg forall x p(x)$ $exists$ Elim 1, 11
Given your EE rule, you need to prove $forall x (neg p(x) rightarrow neg forall x P(x))$, which you do by a universal introduction on $neg p(x) rightarrow forall x p(x)$, which on its turn you prove by a conditional Introduction on a subproof that assumes $neg p(x)$ and derives $neg forall x p(x)$ .. and the latter you get by a proof by contradiction as you yourself surmised. So:
$exists x neg p(x)$ Premise
$quad neg p(x)$ Assumption
$quad quad forall x p(x)$ Assumption
$quad quad p(x)$ $forall$ Elim 3
$quad forall x p(x) rightarrow p(x)$ $rightarrow$ Intro 3-4
$quad quad forall x p(x)$ Assumption
$quad quad neg p(x)$ Reiteration 2
$quad forall x p(x) rightarrow neg p(x)$ $rightarrow$ Intro 6-7
$quad neg forall x p(x)$ $neg$ Intro 5,8
$neg p(x) rightarrow neg forall x p(x)$ $rightarrow$ Intro 2-9
$forall x (neg p(x) rightarrow neg forall x p(x))$ $forall$ Intro 10
$neg forall x p(x)$ $exists$ Elim 1, 11
edited Apr 21 '17 at 11:32
answered Apr 20 '17 at 3:30
Bram28
55.4k33982
55.4k33982
How you know that much~!!?? I always stuck at some points and cannot go through...Probably I go into a wrong way.And Thanks again and again~!!
â tang aqua
Apr 20 '17 at 21:22
@tangaqua After years of practice you really start to 'know' all the different patterns :) So yeah, that took me a long time, so don't feel bad if you're struggling. And I said some time before: you don't have the most user-friendly system either ... so it is not necessarily that you are bad with logic, but just that you have a hard time putting that into this particular proof system.
â Bram28
Apr 20 '17 at 22:06
By your inspiration, I just solve the other prove by myself~! Hahaha~! Helps me a lot~
â tang aqua
Apr 21 '17 at 0:51
@tangaqua Yay! Good for you!! :)
â Bram28
Apr 21 '17 at 0:52
2
@tangaqua You shouldn't try writing a formal proof until you can write an informal proof first. Formal proofs are just a language, not an idea. You have to have the idea (the reason why you think the theorem is true) before you can put the idea into a language.
â DanielV
Apr 21 '17 at 3:11
 |Â
show 4 more comments
How you know that much~!!?? I always stuck at some points and cannot go through...Probably I go into a wrong way.And Thanks again and again~!!
â tang aqua
Apr 20 '17 at 21:22
@tangaqua After years of practice you really start to 'know' all the different patterns :) So yeah, that took me a long time, so don't feel bad if you're struggling. And I said some time before: you don't have the most user-friendly system either ... so it is not necessarily that you are bad with logic, but just that you have a hard time putting that into this particular proof system.
â Bram28
Apr 20 '17 at 22:06
By your inspiration, I just solve the other prove by myself~! Hahaha~! Helps me a lot~
â tang aqua
Apr 21 '17 at 0:51
@tangaqua Yay! Good for you!! :)
â Bram28
Apr 21 '17 at 0:52
2
@tangaqua You shouldn't try writing a formal proof until you can write an informal proof first. Formal proofs are just a language, not an idea. You have to have the idea (the reason why you think the theorem is true) before you can put the idea into a language.
â DanielV
Apr 21 '17 at 3:11
How you know that much~!!?? I always stuck at some points and cannot go through...Probably I go into a wrong way.And Thanks again and again~!!
â tang aqua
Apr 20 '17 at 21:22
How you know that much~!!?? I always stuck at some points and cannot go through...Probably I go into a wrong way.And Thanks again and again~!!
â tang aqua
Apr 20 '17 at 21:22
@tangaqua After years of practice you really start to 'know' all the different patterns :) So yeah, that took me a long time, so don't feel bad if you're struggling. And I said some time before: you don't have the most user-friendly system either ... so it is not necessarily that you are bad with logic, but just that you have a hard time putting that into this particular proof system.
â Bram28
Apr 20 '17 at 22:06
@tangaqua After years of practice you really start to 'know' all the different patterns :) So yeah, that took me a long time, so don't feel bad if you're struggling. And I said some time before: you don't have the most user-friendly system either ... so it is not necessarily that you are bad with logic, but just that you have a hard time putting that into this particular proof system.
â Bram28
Apr 20 '17 at 22:06
By your inspiration, I just solve the other prove by myself~! Hahaha~! Helps me a lot~
â tang aqua
Apr 21 '17 at 0:51
By your inspiration, I just solve the other prove by myself~! Hahaha~! Helps me a lot~
â tang aqua
Apr 21 '17 at 0:51
@tangaqua Yay! Good for you!! :)
â Bram28
Apr 21 '17 at 0:52
@tangaqua Yay! Good for you!! :)
â Bram28
Apr 21 '17 at 0:52
2
2
@tangaqua You shouldn't try writing a formal proof until you can write an informal proof first. Formal proofs are just a language, not an idea. You have to have the idea (the reason why you think the theorem is true) before you can put the idea into a language.
â DanielV
Apr 21 '17 at 3:11
@tangaqua You shouldn't try writing a formal proof until you can write an informal proof first. Formal proofs are just a language, not an idea. You have to have the idea (the reason why you think the theorem is true) before you can put the idea into a language.
â DanielV
Apr 21 '17 at 3:11
 |Â
show 4 more comments
up vote
1
down vote
Here is my solution:
$1.~exists X~lnot p(X)quad $ Premise
$2.~quad lnot p(c)quad$ Existential Elimination:1, Witness Assumed: $[c]$
$3.~qquadforall X~p(X)quad$ Assumption
$4.~qquad p(c)quad$ Universal Elimination:3
$5.~quad forall X~p(X) implies p(c)quad$ Implication Introduction 3-4
$6.~qquadforall X~p(X)quad$ Assumption
$7.~qquadlnot p(c)quad$ Reiteration:2
$8.~quadforall X p(X) implies lnot p(c)quad$ Implication Introduction: 6-7
$9.~quadlnot forall X~p(X)quad$ Negation Introduction 5,8
$10.~lnot forall X~p(X)quad$ Witness Eliminated 2-9
add a comment |Â
up vote
1
down vote
Here is my solution:
$1.~exists X~lnot p(X)quad $ Premise
$2.~quad lnot p(c)quad$ Existential Elimination:1, Witness Assumed: $[c]$
$3.~qquadforall X~p(X)quad$ Assumption
$4.~qquad p(c)quad$ Universal Elimination:3
$5.~quad forall X~p(X) implies p(c)quad$ Implication Introduction 3-4
$6.~qquadforall X~p(X)quad$ Assumption
$7.~qquadlnot p(c)quad$ Reiteration:2
$8.~quadforall X p(X) implies lnot p(c)quad$ Implication Introduction: 6-7
$9.~quadlnot forall X~p(X)quad$ Negation Introduction 5,8
$10.~lnot forall X~p(X)quad$ Witness Eliminated 2-9
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Here is my solution:
$1.~exists X~lnot p(X)quad $ Premise
$2.~quad lnot p(c)quad$ Existential Elimination:1, Witness Assumed: $[c]$
$3.~qquadforall X~p(X)quad$ Assumption
$4.~qquad p(c)quad$ Universal Elimination:3
$5.~quad forall X~p(X) implies p(c)quad$ Implication Introduction 3-4
$6.~qquadforall X~p(X)quad$ Assumption
$7.~qquadlnot p(c)quad$ Reiteration:2
$8.~quadforall X p(X) implies lnot p(c)quad$ Implication Introduction: 6-7
$9.~quadlnot forall X~p(X)quad$ Negation Introduction 5,8
$10.~lnot forall X~p(X)quad$ Witness Eliminated 2-9
Here is my solution:
$1.~exists X~lnot p(X)quad $ Premise
$2.~quad lnot p(c)quad$ Existential Elimination:1, Witness Assumed: $[c]$
$3.~qquadforall X~p(X)quad$ Assumption
$4.~qquad p(c)quad$ Universal Elimination:3
$5.~quad forall X~p(X) implies p(c)quad$ Implication Introduction 3-4
$6.~qquadforall X~p(X)quad$ Assumption
$7.~qquadlnot p(c)quad$ Reiteration:2
$8.~quadforall X p(X) implies lnot p(c)quad$ Implication Introduction: 6-7
$9.~quadlnot forall X~p(X)quad$ Negation Introduction 5,8
$10.~lnot forall X~p(X)quad$ Witness Eliminated 2-9
edited Aug 23 at 2:10
Graham Kemp
80.7k43275
80.7k43275
answered Aug 23 at 1:37
caozi
184
184
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2242845%2fgiven-%25e2%2588%2583x-%25c2%25acpx-use-the-fitch-system-to-prove-%25c2%25ac%25e2%2588%2580x-px%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Hint: first prove $lnot p(x) vdash lnot forall x ~ p(x)$. Note the $x$ represent different variables.
â DanielV
Apr 20 '17 at 3:01
Thanks!! slime face ;) @DanielV
â tang aqua
Apr 21 '17 at 0:49