How to prove ~($forall$x Q(x)) is logically equivalent to $exists$x(~Q(x)) using natural deduction for first...
up vote
0
down vote
favorite
I am thinking of assuming Q(x1) and then deriving to reach to a contradiction but I have not been able to do so.
logic first-order-logic natural-deduction
add a comment |
up vote
0
down vote
favorite
I am thinking of assuming Q(x1) and then deriving to reach to a contradiction but I have not been able to do so.
logic first-order-logic natural-deduction
Could you give us some more background? For instance, in my book, this is the definition of $forall$.
– Arthur
Nov 21 at 12:43
here $forall$ stand for "for all" x that belong to domain of discourse.
– user10143594
Nov 21 at 12:51
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I am thinking of assuming Q(x1) and then deriving to reach to a contradiction but I have not been able to do so.
logic first-order-logic natural-deduction
I am thinking of assuming Q(x1) and then deriving to reach to a contradiction but I have not been able to do so.
logic first-order-logic natural-deduction
logic first-order-logic natural-deduction
edited Nov 21 at 12:45
Mauro ALLEGRANZA
63.8k448110
63.8k448110
asked Nov 21 at 12:41
user10143594
103
103
Could you give us some more background? For instance, in my book, this is the definition of $forall$.
– Arthur
Nov 21 at 12:43
here $forall$ stand for "for all" x that belong to domain of discourse.
– user10143594
Nov 21 at 12:51
add a comment |
Could you give us some more background? For instance, in my book, this is the definition of $forall$.
– Arthur
Nov 21 at 12:43
here $forall$ stand for "for all" x that belong to domain of discourse.
– user10143594
Nov 21 at 12:51
Could you give us some more background? For instance, in my book, this is the definition of $forall$.
– Arthur
Nov 21 at 12:43
Could you give us some more background? For instance, in my book, this is the definition of $forall$.
– Arthur
Nov 21 at 12:43
here $forall$ stand for "for all" x that belong to domain of discourse.
– user10143594
Nov 21 at 12:51
here $forall$ stand for "for all" x that belong to domain of discourse.
– user10143594
Nov 21 at 12:51
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
accepted
Hint
1st part, using Natural Deduction :
1) $exists x lnot Qx$ --- premise
2) $forall x Qx$ --- assumed [a]
3) $lnot Qa$ --- assumed [b] from 1) by $exists$-elim
4) $Qa$ --- from 2) by $forall$-elim
5) $bot$ --- contradiction : from 3) and 4)
6) $bot$ --- from 1) and 3) and 5) by $exists$-elim, discharging [b]
7) $lnot forall x Qx$ --- from 2) and 6) by $lnot$-intro, discharging [a].
2nd part : quite similar, using Double Negation.
1) $lnot forall x Qx$ --- premise
2) $lnot exists x lnot Qx$ --- assumed [a]
3) $lnot Qx$ --- assumed [b]
and so on ...
Thanks. Can you also show for other way round?
– user10143594
Nov 21 at 12:46
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
accepted
Hint
1st part, using Natural Deduction :
1) $exists x lnot Qx$ --- premise
2) $forall x Qx$ --- assumed [a]
3) $lnot Qa$ --- assumed [b] from 1) by $exists$-elim
4) $Qa$ --- from 2) by $forall$-elim
5) $bot$ --- contradiction : from 3) and 4)
6) $bot$ --- from 1) and 3) and 5) by $exists$-elim, discharging [b]
7) $lnot forall x Qx$ --- from 2) and 6) by $lnot$-intro, discharging [a].
2nd part : quite similar, using Double Negation.
1) $lnot forall x Qx$ --- premise
2) $lnot exists x lnot Qx$ --- assumed [a]
3) $lnot Qx$ --- assumed [b]
and so on ...
Thanks. Can you also show for other way round?
– user10143594
Nov 21 at 12:46
add a comment |
up vote
0
down vote
accepted
Hint
1st part, using Natural Deduction :
1) $exists x lnot Qx$ --- premise
2) $forall x Qx$ --- assumed [a]
3) $lnot Qa$ --- assumed [b] from 1) by $exists$-elim
4) $Qa$ --- from 2) by $forall$-elim
5) $bot$ --- contradiction : from 3) and 4)
6) $bot$ --- from 1) and 3) and 5) by $exists$-elim, discharging [b]
7) $lnot forall x Qx$ --- from 2) and 6) by $lnot$-intro, discharging [a].
2nd part : quite similar, using Double Negation.
1) $lnot forall x Qx$ --- premise
2) $lnot exists x lnot Qx$ --- assumed [a]
3) $lnot Qx$ --- assumed [b]
and so on ...
Thanks. Can you also show for other way round?
– user10143594
Nov 21 at 12:46
add a comment |
up vote
0
down vote
accepted
up vote
0
down vote
accepted
Hint
1st part, using Natural Deduction :
1) $exists x lnot Qx$ --- premise
2) $forall x Qx$ --- assumed [a]
3) $lnot Qa$ --- assumed [b] from 1) by $exists$-elim
4) $Qa$ --- from 2) by $forall$-elim
5) $bot$ --- contradiction : from 3) and 4)
6) $bot$ --- from 1) and 3) and 5) by $exists$-elim, discharging [b]
7) $lnot forall x Qx$ --- from 2) and 6) by $lnot$-intro, discharging [a].
2nd part : quite similar, using Double Negation.
1) $lnot forall x Qx$ --- premise
2) $lnot exists x lnot Qx$ --- assumed [a]
3) $lnot Qx$ --- assumed [b]
and so on ...
Hint
1st part, using Natural Deduction :
1) $exists x lnot Qx$ --- premise
2) $forall x Qx$ --- assumed [a]
3) $lnot Qa$ --- assumed [b] from 1) by $exists$-elim
4) $Qa$ --- from 2) by $forall$-elim
5) $bot$ --- contradiction : from 3) and 4)
6) $bot$ --- from 1) and 3) and 5) by $exists$-elim, discharging [b]
7) $lnot forall x Qx$ --- from 2) and 6) by $lnot$-intro, discharging [a].
2nd part : quite similar, using Double Negation.
1) $lnot forall x Qx$ --- premise
2) $lnot exists x lnot Qx$ --- assumed [a]
3) $lnot Qx$ --- assumed [b]
and so on ...
edited Nov 21 at 13:14
answered Nov 21 at 12:45
Mauro ALLEGRANZA
63.8k448110
63.8k448110
Thanks. Can you also show for other way round?
– user10143594
Nov 21 at 12:46
add a comment |
Thanks. Can you also show for other way round?
– user10143594
Nov 21 at 12:46
Thanks. Can you also show for other way round?
– user10143594
Nov 21 at 12:46
Thanks. Can you also show for other way round?
– user10143594
Nov 21 at 12:46
add a comment |
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.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3007682%2fhow-to-prove-forallx-qx-is-logically-equivalent-to-existsxqx-usi%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
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
Could you give us some more background? For instance, in my book, this is the definition of $forall$.
– Arthur
Nov 21 at 12:43
here $forall$ stand for "for all" x that belong to domain of discourse.
– user10143594
Nov 21 at 12:51