Mixing
Prove (¬(∀ð‘¥(¬ð‘ƒ(ð‘¥)))) ⊢ (∃𑥠ð‘ƒ(ð‘¥)) by Natural Deduction
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
I want to prove (¬(∀ð‘¥(¬ð‘ƒ(ð‘¥)))) ⊢ (∃ð‘¥ð‘ƒ(ð‘¥)) using only the basic rules of the Natural Deduction system for propositional logic and predicate logic.
I am not sure how to get rid of the negation before the universal quantifier.
How should I prove this?
logic first-order-logic predicate-logic quantifiers natural-deduction
asked 3 hours ago
Mathrocks
82
add a comment |Â
up vote
1
down vote
favorite
I want to prove (¬(∀ð‘¥(¬ð‘ƒ(ð‘¥)))) ⊢ (∃ð‘¥ð‘ƒ(ð‘¥)) using only the basic rules of the Natural Deduction system for propositional logic and predicate logic.
I am not sure how to get rid of the negation before the universal quantifier.
How should I prove this?
logic first-order-logic predicate-logic quantifiers natural-deduction
asked 3 hours ago
Mathrocks
82
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I want to prove (¬(∀ð‘¥(¬ð‘ƒ(ð‘¥)))) ⊢ (∃ð‘¥ð‘ƒ(ð‘¥)) using only the basic rules of the Natural Deduction system for propositional logic and predicate logic.
I am not sure how to get rid of the negation before the universal quantifier.
How should I prove this?
logic first-order-logic predicate-logic quantifiers natural-deduction
asked 3 hours ago
Mathrocks
82
I want to prove (¬(∀ð‘¥(¬ð‘ƒ(ð‘¥)))) ⊢ (∃ð‘¥ð‘ƒ(ð‘¥)) using only the basic rules of the Natural Deduction system for propositional logic and predicate logic.
I am not sure how to get rid of the negation before the universal quantifier.
How should I prove this?
logic first-order-logic predicate-logic quantifiers natural-deduction
logic first-order-logic predicate-logic quantifiers natural-deduction
asked 3 hours ago
Mathrocks
82
asked 3 hours ago
Mathrocks
82
asked 3 hours ago
Mathrocks
82
asked 3 hours ago
Mathrocks
82
asked 3 hours ago
Mathrocks
82
82
add a comment |Â
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
3
down vote
If in doubt, try reductio ....
So after the initial premiss, assume $negexists xPx$
Now what?
You'll have to make another assumption to get anywhere ....
So suppose $Pa$ (the obvious thing ...why??)
Then you can infer $exists xPx$, contradiction!
So you can infer $neg Pa$
And that gives you $forall xneg Px$
And now the end is in sight, because this contradicts the initial premiss ...
Join up the dots, and finish the proof.
answered 3 hours ago
Peter Smith
39.7k339118
add a comment |Â
up vote
1
down vote
Natural deduction rules are all about introduction and eliminations of connectives and quantifiers. Â Hence the rules' names. Â Writing a natural deduction proof basically consists of deciding what needs to be introduced or eliminated and when. Â The rules themselves tell you how.
I am not sure how to get rid of the negation before the universal quantifier.
Okay, obviously, eliminating the negation will be done using the rule of negation elimination. Â That was easy!
Well, the hard bit of this is arranging to have what the rule requires. Â Although it is not that hard.
It requires two contradicting statements and we have only one premise in the base context. Â An assumption must be raised! Â So what do we assume to derive a contradiction of the premise? Â Also what do we do with that contradiction?
Well, if the premise actually does entails the conclusion, assuming the contrary should derive a contradiction.  So let us assume that: $negexists x~P(x)$ , and aim to derive this: $forall x~lnot P(x)$.  This also tells use what we're doing with that contradiction.  We will be using a proof by reduction to absurdity — discharging the assumption by introducing a negation, and then eliminating the double negation that results to derive the desired conclusion.
Okay, now, to get that contradiction you need to introduce a universal quantifier. Â Continue thinking in this manner and the proof almost writes itself.
$$deffitch#1#2quadbeginarray#1\hline#2endarrayfitchnegforall x~neg P(x)qquad~~~textsfPremisefitchnegexists x~P(x)qquadtextsfAssumption~vdots\forall x~neg P(x)qquadtextsfUniversal Introduction\botqquadqquadquad~textsfNegation Elimination\negnegexists x~P(x)qquadquadtextsfNegation Introduction\exists x~P(x)qquadqquadtextsfDouble Negation Elimination$$
answered 1 hour ago
Graham Kemp
82.8k43378
That is a good proof outline.
– DanielV
14 mins ago
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
If in doubt, try reductio ....
So after the initial premiss, assume $negexists xPx$
Now what?
You'll have to make another assumption to get anywhere ....
So suppose $Pa$ (the obvious thing ...why??)
Then you can infer $exists xPx$, contradiction!
So you can infer $neg Pa$
And that gives you $forall xneg Px$
And now the end is in sight, because this contradicts the initial premiss ...
Join up the dots, and finish the proof.
answered 3 hours ago
Peter Smith
39.7k339118
add a comment |Â
up vote
3
down vote
If in doubt, try reductio ....
So after the initial premiss, assume $negexists xPx$
Now what?
You'll have to make another assumption to get anywhere ....
So suppose $Pa$ (the obvious thing ...why??)
Then you can infer $exists xPx$, contradiction!
So you can infer $neg Pa$
And that gives you $forall xneg Px$
And now the end is in sight, because this contradicts the initial premiss ...
Join up the dots, and finish the proof.
answered 3 hours ago
Peter Smith
39.7k339118
add a comment |Â
up vote
3
down vote
up vote
3
down vote
If in doubt, try reductio ....
So after the initial premiss, assume $negexists xPx$
Now what?
You'll have to make another assumption to get anywhere ....
So suppose $Pa$ (the obvious thing ...why??)
Then you can infer $exists xPx$, contradiction!
So you can infer $neg Pa$
And that gives you $forall xneg Px$
And now the end is in sight, because this contradicts the initial premiss ...
Join up the dots, and finish the proof.
answered 3 hours ago
Peter Smith
39.7k339118
If in doubt, try reductio ....
So after the initial premiss, assume $negexists xPx$
Now what?
You'll have to make another assumption to get anywhere ....
So suppose $Pa$ (the obvious thing ...why??)
Then you can infer $exists xPx$, contradiction!
So you can infer $neg Pa$
And that gives you $forall xneg Px$
And now the end is in sight, because this contradicts the initial premiss ...
Join up the dots, and finish the proof.
answered 3 hours ago
Peter Smith
39.7k339118
answered 3 hours ago
Peter Smith
39.7k339118
answered 3 hours ago
Peter Smith
39.7k339118
answered 3 hours ago
Peter Smith
39.7k339118
39.7k339118
add a comment |Â
add a comment |Â
up vote
1
down vote
Natural deduction rules are all about introduction and eliminations of connectives and quantifiers. Â Hence the rules' names. Â Writing a natural deduction proof basically consists of deciding what needs to be introduced or eliminated and when. Â The rules themselves tell you how.
I am not sure how to get rid of the negation before the universal quantifier.
Okay, obviously, eliminating the negation will be done using the rule of negation elimination. Â That was easy!
Well, the hard bit of this is arranging to have what the rule requires. Â Although it is not that hard.
It requires two contradicting statements and we have only one premise in the base context. Â An assumption must be raised! Â So what do we assume to derive a contradiction of the premise? Â Also what do we do with that contradiction?
Well, if the premise actually does entails the conclusion, assuming the contrary should derive a contradiction.  So let us assume that: $negexists x~P(x)$ , and aim to derive this: $forall x~lnot P(x)$.  This also tells use what we're doing with that contradiction.  We will be using a proof by reduction to absurdity — discharging the assumption by introducing a negation, and then eliminating the double negation that results to derive the desired conclusion.
Okay, now, to get that contradiction you need to introduce a universal quantifier. Â Continue thinking in this manner and the proof almost writes itself.
$$deffitch#1#2quadbeginarray#1\hline#2endarrayfitchnegforall x~neg P(x)qquad~~~textsfPremisefitchnegexists x~P(x)qquadtextsfAssumption~vdots\forall x~neg P(x)qquadtextsfUniversal Introduction\botqquadqquadquad~textsfNegation Elimination\negnegexists x~P(x)qquadquadtextsfNegation Introduction\exists x~P(x)qquadqquadtextsfDouble Negation Elimination$$
answered 1 hour ago
Graham Kemp
82.8k43378
That is a good proof outline.
– DanielV
14 mins ago
add a comment |Â
up vote
1
down vote
Natural deduction rules are all about introduction and eliminations of connectives and quantifiers. Â Hence the rules' names. Â Writing a natural deduction proof basically consists of deciding what needs to be introduced or eliminated and when. Â The rules themselves tell you how.
I am not sure how to get rid of the negation before the universal quantifier.
Okay, obviously, eliminating the negation will be done using the rule of negation elimination. Â That was easy!
Well, the hard bit of this is arranging to have what the rule requires. Â Although it is not that hard.
It requires two contradicting statements and we have only one premise in the base context. Â An assumption must be raised! Â So what do we assume to derive a contradiction of the premise? Â Also what do we do with that contradiction?
Well, if the premise actually does entails the conclusion, assuming the contrary should derive a contradiction.  So let us assume that: $negexists x~P(x)$ , and aim to derive this: $forall x~lnot P(x)$.  This also tells use what we're doing with that contradiction.  We will be using a proof by reduction to absurdity — discharging the assumption by introducing a negation, and then eliminating the double negation that results to derive the desired conclusion.
Okay, now, to get that contradiction you need to introduce a universal quantifier. Â Continue thinking in this manner and the proof almost writes itself.
$$deffitch#1#2quadbeginarray#1\hline#2endarrayfitchnegforall x~neg P(x)qquad~~~textsfPremisefitchnegexists x~P(x)qquadtextsfAssumption~vdots\forall x~neg P(x)qquadtextsfUniversal Introduction\botqquadqquadquad~textsfNegation Elimination\negnegexists x~P(x)qquadquadtextsfNegation Introduction\exists x~P(x)qquadqquadtextsfDouble Negation Elimination$$
answered 1 hour ago
Graham Kemp
82.8k43378
That is a good proof outline.
– DanielV
14 mins ago
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Natural deduction rules are all about introduction and eliminations of connectives and quantifiers. Â Hence the rules' names. Â Writing a natural deduction proof basically consists of deciding what needs to be introduced or eliminated and when. Â The rules themselves tell you how.
I am not sure how to get rid of the negation before the universal quantifier.
Okay, obviously, eliminating the negation will be done using the rule of negation elimination. Â That was easy!
Well, the hard bit of this is arranging to have what the rule requires. Â Although it is not that hard.
It requires two contradicting statements and we have only one premise in the base context. Â An assumption must be raised! Â So what do we assume to derive a contradiction of the premise? Â Also what do we do with that contradiction?
Well, if the premise actually does entails the conclusion, assuming the contrary should derive a contradiction.  So let us assume that: $negexists x~P(x)$ , and aim to derive this: $forall x~lnot P(x)$.  This also tells use what we're doing with that contradiction.  We will be using a proof by reduction to absurdity — discharging the assumption by introducing a negation, and then eliminating the double negation that results to derive the desired conclusion.
Okay, now, to get that contradiction you need to introduce a universal quantifier. Â Continue thinking in this manner and the proof almost writes itself.
$$deffitch#1#2quadbeginarray#1\hline#2endarrayfitchnegforall x~neg P(x)qquad~~~textsfPremisefitchnegexists x~P(x)qquadtextsfAssumption~vdots\forall x~neg P(x)qquadtextsfUniversal Introduction\botqquadqquadquad~textsfNegation Elimination\negnegexists x~P(x)qquadquadtextsfNegation Introduction\exists x~P(x)qquadqquadtextsfDouble Negation Elimination$$
answered 1 hour ago
Graham Kemp
82.8k43378
Natural deduction rules are all about introduction and eliminations of connectives and quantifiers. Â Hence the rules' names. Â Writing a natural deduction proof basically consists of deciding what needs to be introduced or eliminated and when. Â The rules themselves tell you how.
I am not sure how to get rid of the negation before the universal quantifier.
Okay, obviously, eliminating the negation will be done using the rule of negation elimination. Â That was easy!
Well, the hard bit of this is arranging to have what the rule requires. Â Although it is not that hard.
It requires two contradicting statements and we have only one premise in the base context. Â An assumption must be raised! Â So what do we assume to derive a contradiction of the premise? Â Also what do we do with that contradiction?
Well, if the premise actually does entails the conclusion, assuming the contrary should derive a contradiction.  So let us assume that: $negexists x~P(x)$ , and aim to derive this: $forall x~lnot P(x)$.  This also tells use what we're doing with that contradiction.  We will be using a proof by reduction to absurdity — discharging the assumption by introducing a negation, and then eliminating the double negation that results to derive the desired conclusion.
Okay, now, to get that contradiction you need to introduce a universal quantifier. Â Continue thinking in this manner and the proof almost writes itself.
$$deffitch#1#2quadbeginarray#1\hline#2endarrayfitchnegforall x~neg P(x)qquad~~~textsfPremisefitchnegexists x~P(x)qquadtextsfAssumption~vdots\forall x~neg P(x)qquadtextsfUniversal Introduction\botqquadqquadquad~textsfNegation Elimination\negnegexists x~P(x)qquadquadtextsfNegation Introduction\exists x~P(x)qquadqquadtextsfDouble Negation Elimination$$
answered 1 hour ago
Graham Kemp
82.8k43378
answered 1 hour ago
Graham Kemp
82.8k43378
answered 1 hour ago
Graham Kemp
82.8k43378
answered 1 hour ago
Graham Kemp
82.8k43378
82.8k43378
That is a good proof outline.
– DanielV
14 mins ago
add a comment |Â
That is a good proof outline.
– DanielV
14 mins ago
That is a good proof outline.
– DanielV
14 mins ago
That is a good proof outline.
– DanielV
14 mins ago
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%2f2975472%2fprove-%25c2%25ac%25e2%2588%2580%25c2%25ac-%25e2%258a%25a2-%25e2%2588%2583-by-natural-deduction%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
