University of California Berkeley Fitch Proof and First Order Logic Question Please help complete this problem set (pSET 13). Please do not bid if not fami

University of California Berkeley Fitch Proof and First Order Logic Question Please help complete this problem set (pSET 13). Please do not bid if not familiar with first order logic and fitch proof. Please type up word or PDF. Additional reference material attached. 12A: Problem Set 13
Due date: Friday May 1, 12pm. Upload completed problem set to bCourses in PDF format. Reminder:
late problem sets do not receive credit.
1. For each of the following arguments, provide an fol Fitch proof which shows the argument to be valid.
Don’t forget to number your lines and cite the rules of inference as appropriate.
(a) ` (¬(a = a)
(a = b))
(b) 9x8zHxz ` 8x9zHzx
(c) (Rcd
8xRxx) ` ¬9y¬(Rcd
Ryy)
(d) (9xF x _ 9xGb) ` 9x(F x _ Gb)
(This one is a bit tricky. -2 if you get it wrong, but +5 bonus if you get it right.)
2. Specify a model where 8x9zHzx is true but 9x8zHxz is false.
1
Fitch-style natural deduction
Handout 6, Philosophy 12A, Berkeley
Contents
1 Introducing Fitch-style proof
1
2 Proof rules for the connectives
2.1 Conjunction Introduction and Conjunction Elimination .
2.2 Disjunction Introduction and Disjunction Elimination . .
2.3 Negation Introduction and Negation Elimination . . . . .
2.4 Conditional Introduction and Conditional Elimination . .
2.5 Biconditional Introduction and Biconditional Elimination
2.6 Reiteration . . . . . . . . . . . . . . . . . . . . . . . . . .
2
3
5
6
8
9
9
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3 Definitions refresher: quantifiers, scope, binding, substitution instances
11
4 Proof rules for the quantifiers
4.1 Existential Introduction . . .
4.2 Universal Elimination . . . .
4.3 Universal Introduction . . . .
4.4 Existential Elimination . . . .
.
.
.
.
12
12
12
13
14
5 Rules for identity
5.1 Identity Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Identity Elimination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
15
15
6 Some closing definitions
16
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1 Introducing Fitch-style proof
Now we want to define a formal notion of proof. A formal proof is a syntactic object. Think
of it as made of symbols. Obviously, not just any collection of symbols from fol counts as
a proof. So we need some rules that tell us what exactly counts as a proof in fol. That’s
what a proof system, such as the system described below, gives us.
There are various perfectly good ways of defining a formal notion of proof for fol—that is,
there are various proof systems for fol. What do they all have in common, which makes
them all proof systems for fol? Here’s the answer:
The central thing any proof system for fol must do is supply a notion of proof
such that a proof exists for an argument if and only if the argument is valid in
fol.
(Recall that an argument is valid in fol just in case any model where the premises are all
true is a model where the conclusion is true.)
1
The proof system introduced below is called a natural deduction system, because it mimics (in a highly idealized way) the structure of (good) argumentation in ordinary language.
This particular style of natural deduction is called Fitch-style. Proofs constructed in this
style are called Fitch proofs or Fitch diagrams.
We are first going to restrict our attention to Fitch proofs in pl. Once we get the hang of
proof in pl, it will be straightforward to extend our proof system to fol.
Here is an example of a Fitch proof:
1
2
((A ^ B)
C)
A
Premise
Assumption
3
B
Assumption
4
(A ^ B)
^I 2,3
5
C
6
7
(B
(A
E 1,4
C)
(B
I 3-5
C))
I 2-6
A Fitch-proof starts with a vertical list of zero or more premises arranged to the immediate
right of a vertical line, called a scope line. In the above example we have just one premise.
A short horizontal line is drawn between the premises of a Fitch proof and the lines beneath
them; this marks o? where the reasoning from the premises begins. The goal is to build a
proof step-by-step which ends with the conclusion of the argument we are trying to prove.
Each step is justified by rule of inference (these are explained below), or else serves as a
temporary assumption. A new scope line within the original scope line appears whenever
a provisional assumption is made, with a short horizontal line marking o? the assumption.
The new scope line corresponds to a subproof environment. Certain proof rules allow
you to discharge the assumption of a subproof environment and return to the previous scope
line. ( I does this on lines 6 and 7 of the example above—this is explained more below.)
Each line of the proof must be explicitly permitted by the proof system rules, as described
below.
As the example above illustrates, each line of a Fitch proof requires some annotation which
indicates the justification for that line. Each time you extend your proof by an additional
line, you need to indicate the justification for that extension, by citing the rule you used to
together with the lines that allowed you to apply the rule. The point of everything below
is to explain how these rules work, and how you can use them to build proofs.
2 Proof rules for the connectives
We introduce a standard set of Fitch-style natural deduction rules below. In the statement
of each rule, the annotated lines (towards the bottom) show how a proof is permitted to
2
continue, given what kind of things occur in the proof above it. (If there is more than
one annotated line displayed for a given rule (e.g., ^E), you can derive either of the lines
displayed.)
Here’s a useful notion for understanding and explaining the rules. Let’s say that if appears
on line i of a proof, then is available at a line j below line i if and only if every scope
line that is within extends to line j. To illustrate by using our example above: the w?
on line 1 is available on every line below it. It is along the main scope line of the proof,
and the main scope line of course extends to every numbered line. (Thus every premise in
any proof is available on any line beneath it.) By contrast, the w? on line 3 (viz., B) is
available on lines 4 and 5, but not on lines 6 or 7, because there is a scope line that line 3
is within which does not extend to lines 6 or 7.
Now let’s look at the rules of inference—our proof rules. Each connective comes with an
introduction rule and an elimination rule. We’ll start with those.
2.1 Conjunction Introduction and Conjunction Elimination
These abstract pictures describe how these rules work:
^I:
^E:
i
i
..
.
j
^E i
..
.
( ^ )
( ^ )
..
.
^E i
^I i, j
Conjunction Introduction (^I) says that you can write a conjunction on a line if each
conjunct is available on that line. Note: we won’t interpret this rule (or the other rules) as
saying that line i literally has to be above line j in the proof. The order doesn’t matter.
Let’s see a simple example of this rule in action. Suppose our premises are A and B, and
our conclusion is (A ^ B). Now clearly that’s a valid argument: {A, B} ? (A ^ B). Is it
provable in our Fitch proof system—that is, {A, B} ` (A ^ B)? Indeed it is. The proof is
very simple and direct:
1
A
Premise
2
B
Premise
3
(A ^ B)
^I 1,2
The annotation “^I 1, 2” on line 3 supplies the justification for this line. It is a key part of
the proof. It means that you derived line 3 from lines 1 and 2 using the ^I proof rule.
3
Note that we also could have used the ^I proof rule to prove (B ^ A):
1
A
Premise
2
B
Premise
3
(B ^ A)
^I 1,2
That’s to say, when you derive a conjunction, the order of the conjuncts is up to you—either
order is permitted by the ^I rule.
In your annotations, you generally have to state the rule you used and the lines you applied
the rules to, but those don’t have to be written in a particular order. We could have supplied
the annotation like this:
1
A
Premise
2
B
Premise
3
(B ^ A)
1, 2 ^I
A point of clarification: in the abstract picture of how ^I works above, it look as if the
two w?s used to derive a conjunction must occur along exactly the same scope line as the
conjunction derived from them. But we’re going to interpret the rule in a more flexible
manner than this. Again, the intended understanding of the ^I rule above is that the w?s
on lines i and j must be available at the line the where the conjunction is derived. Observe
that this more flexible understanding is already in play in our example proof from earlier.
Let’s see it again:
1
2
((A ^ B)
C)
A
Premise
Assumption
3
B
Assumption
4
(A ^ B)
^I 2,3
5
C
6
7
(B
(A
E 1,4
C)
(B
I 3-5
C))
I 2-6
We haven’t explained some of the rules used here yet, but don’t worry about that for now.
The relevant thing to notice is that the w?s on line 2 and 3 are available at line 4, and
hence we can form the conjunction of these and write the conjunction down on this line,
citing ^I as justification.
Conjunction Elimination (^E) says that from a conjunction you can derive either of the
conjuncts. A simple example:
4
1
(A ^ B)
Premise
2
B
1 ^E
This is a Fitch proof that B follows from (A ^ B). Here is another example:
1
((A
2
(A
B) ^ C)
Premise
1 ^E
B)
Putting our two rules together, we can prove that (A ^ B) entails (B ^ A):
1
(A ^ B)
Premise
2
A
1 ^E
3
B
1 ^E
4
(B ^ A)
2,3 ^I
2.2 Disjunction Introduction and Disjunction Elimination
Disjunction Introduction (_I) says that if is available at a line you can derive the disjunction of with any other w? at all, and you can arrange the resulting disjunction in
either order. Disjunction Elimination (_E) says that if a disjunction is a available at a line,
and the negation of one of the disjuncts is also available at a line, you can derive the other
disjunct.
_I:
_E:
i
i
( _ ) [or: ( _ )]
..
.
j
¬
..
.
..
.
( _ )
_I i
( _ )
_I i
_E i, j
A simple example of _I:
1
P
Premise
2
(P _ Q)
1 _I
Note that the introduced disjunct can be simple or complex:
5
1
P
Premise
2
(P _ (Q ^ (¬P _ R)))
1 _I
… and you can make it appear first or second in the disjunction:
1
P
Premise
2
((Q ^ (¬P _ R)) _ P )
1 _I
Here is a simple example of _E:
1
(A _ B)
Premise
2
¬A
Premise
3
B
1,2 _E
Another:
1
((A
Q) _ ¬B)
Premise
2
¬(A
Q)
Premise
3
¬B
1,2 _E
Let’s now see all of our rules for conjunction and disjunction in action in a single proof:
1
((P _ Q) ^ ¬Q)
Premise
2
¬Q
1, ^E
3
(P _ Q)
1, ^E
4
P
1,3 _E
5
(P ^ ¬Q)
2,4 ^I
6
((P ^ ¬Q) _ R)
5 _I
2.3 Negation Introduction and Negation Elimination
Negation Introduction (¬I) encodes the idea of reductio ad absurdum, or proof by contradiction. It allows you to derive a sentence of the form ¬ by provisionally supposing is true
and deriving a contradiction within the scope of that supposition. Negation Elimination
(¬E) encodes the idea that a pair of negation symbols cancel out.
6
¬I:
¬E:
i
Assumption
..
.
i
..
.
¬E i
¬
j
¬
¬¬
..
.
¬I i-j
Let’s see a simple example of ¬I in action:
1
(P ^ Q)
2
¬P
Assumption
3
P
1 ^E
4
¬¬P
Premise
2-3 ¬I
We’re showing here that ¬¬P can be proved from (P ^ Q). Taking (P ^ Q) as a premise, we
immediately temporary suppose ¬P . This is what happens on line 2, where a subproof environment is created. Next, within the subproof environment, we derive P from our premise
using ^E. Now notice that within our subproof environment, we can find contradictory
lines: line 2 has ¬P , whereas line 3 has P . This means that from our assumption of ¬P , we
can derive a contradiction. And this fact means our temporary assumption must be false,
given our premises. This is what the ¬I rule encodes. Once it is evident a contradiction
can be derived, we can return to the earlier scope line as we do on line 4, and conclude the
negation of the thing we temporarily supposed. When we leave the subproof and justify
this with ¬I, we cite the lines corresponding to the whole subproof environment.
Note that in this example of ¬I, one of our two contradictory sentences was actually the
very assumption introduced on line 2. That is unusual, but permissible. As long as you can
find two sentences along a subproof scope line such that one is the negation of the other,
you can apply ¬I to conclude the negation of the thing you supposed right outside that
scope line. The two sentence may both occur beneath the assumption, or one of them may
be the assumption itself.
The rule for ¬E is straightforward. It just lets us drop double negations. For example:
1
¬¬(P ^ Q)
Premise
2
(P ^ Q)
1, ¬E
7
2.4 Conditional Introduction and Conditional Elimination
I:
E:
i
i
..
.
Assumption
..
.
j
..
.
j
I i-j
E i,j
Conditional Introduction ( I) lets you introduce a conditional by using a subproof environment. If you provisionally suppose the antecedent of a conditional and are able to derive the
consequent of the conditional within the scope of this supposition, then you can “discharge”
the supposition and derive the conditional immediately outside the subproof environment.
Here is a simple example:
(P ^ Q)
1
Premise
2
P
Assumption
3
Q
1, ^E
4
(P
Q)
2-3,
I
Another:
1
(P ^ Q)
Premise
2
P
Assumption
3
Q
1, ^E
4
(Q _ A)
3, _I
5
(P
(Q _ A))
2-4,
I
Conditional Elimination ( E) is also called Modus Ponens. If a conditional together with
its antecedent are available at a line, you can derive the consequent of the conditional at
that line. Example:
1
((P _ R)
(Q ^ R))
2
(P _ R)
Premise
3
(Q ^ R)
1,2
Premise
E
Our example from earlier provides an illustration of both rules:
8
1
((A ^ B)
2
C)
A
Premise
Assumption
3
B
Assumption
4
(A ^ B)
^I 2,3
5
C
6
7
(B
(A
E 1,4
C)
(B
I 3-5
C))
I 2-6
On line 2, we make the supposition of A. On line 3, we make another supposition within that
supposition, of B. (You can do that!) From these two suppositions, (A^B) is easily derived
on line 4. E is then applied to derive C on line 5 within the sub-subproof environment.
Then the innermost supposition (of B) is discharged, and the conditional (B C) is derived
on line 6 with I. Finally the original supposition A is discharged on line 7, using I once
again.
2.5 Biconditional Introduction and Biconditional Elimination
$I:
$E:
i
(
..
.
)
j
(
..
.
)
( $ )
i
$I i, j
( $ )
..
.
(
)
^E i
(
)
^E i
Biconditional Introduction ($I) and Biconditional Elimination ($E) are reminiscent of the
corresponding conjunction rules. That is not surprising, since of course a biconditional just
is equivalent to a conjunction of conditionals.
2.6 Reiteration
This rule doesn’t have to do with any particular connective, but it’s useful to have.
9
Reit:
Reiteration lets you repeat a w? occurring on a line above it, as long as that
w? is along the same scope line or along
a scope line to the left of the reiterated
w?. In particular it allows you to “move
formulas inward”.
i
..
.
Reit i
Here is a simple example of a case where Reit is handy:
1
P
Premise
2
¬P
Assumption
3
P
1, Reit
4
¬¬P
2-3, ¬I
Here is another:
1
((¬P ^ W ) _ ¬R)
Premise
2
P
Assumption
3
((¬P ^ W ) _ ¬R)
1, Reit
4
(P
((¬P ^ W ) _ ¬R))
10
2-3,
I
3 Definitions refresher: quantifiers, scope, binding, substitution instances
To extend our Fitch proof system to fol, we need to state introduction and elimination
rules for the quantifiers and for identity. Before we get to those, however, here are some
definitions that will be helpful to keep in mind.
Def. A quantifier is an expression of the form Q?, where Q is a quantifier symbol (i.e., 9
or 8) and ? is a variable.
Def. The scope of a quantifier is the w? that it attaches to. More precisely: If Q? is a
quantifier and is a w?, then the scope of the occurrence of Q? in the expression Q? is
.
Examples:
• The scope of 9x in 9x8y(F x
• The scope of 8y in 9x8y(F x
• The scope of 9x in (9x8y(F x
Gy) is 8y(F x
Gy) is (F x
Gy).
Gy).
Gy) ^ F x) is 8y(F x
Gy).
Def. Any occurrence of the variable ? in the scope of an occurrence of 9? or 8? is bound
by that occurrence of the quantifier, as long as that occurrence of ? is not also in the scope
of some closer occurrence of 9? or 8?.
Examples:
• In (9x8y(F x
ables.
Gx y) ^ F x), the quantifier 9x binds the highlighted vari-
• In 9x8x(F x Gx y), the quantifier 8x binds the highlighted variables, and
the quantifier 9x binds no variables.
Def. A substitution instance of a closed quantified formula is the result of deleting
the quantifier, then replacing every variable bound by the quantifier with the same individual
constant. If we have a quantified sentence of the form Q? and ? is a constant, then ?/?
denotes the substitution instance of Q? which results from deleting Q? and replacing every
occurrence of ? in which was previously bound by Q? with ?.
Examples:
• F a is a substitution instance of 9xF x, 8xF x, 9yF y, and so on.
• F aa and F bb are substitution instances of 9xF xx, but F ab is not. (The same constant
has to replace each variable that was bound by the quantifier removed.)
• 9xF xb is a substitution instance of 8y9xF xy, and also of 9z9xF xz.
• 9xF x is a substitution instance of 8y9xF x—and indeed, its only substitution instance.
11
4 Proof rules for the quantifiers
4.1 Existential Introduction
Existential Introduction (9I) lets you derive an existentially quantified formula from any
substitution instance of that formula. The form of reasoning this rules encodes is also
called existential generalization. It says that if you have established on some line of
the proof, and is a substitution instance of a w? of the form 9? , then you can derive
any w? of that form:
9I: Where
?/?
is a substitution instance of 9? ,
i
..
.
9?
9I i ?/?
Here are a number of di?erent ways of applying the rule:
1
F ab
Premise
2
9xF xb
9I 1 a/x
3
9xF ax
9I 1 b/x
4
9yF yb
9I 1 a/y
5
9yF ay
9I 1 b/y
6
9x9yF xy
9I 5 a/x
4.2 Universal Elimination
Universal Elimination (8E) says that you can derive any substitution instance of a universally quantified formula:
8E: Where
i
?/?
is a substitution instance of 8? ,
8?
..
.
8E i ?/?
For example, from 8xF bx, one can use 8E to derive F ba, or F bb, or F bc:
12
1
8xF bx
Premise
2
F ba
8E 1 a/x
3
F bb
8E 1 b/x
4
F bc
8E 1 c/x
That’s because these are all substitution instances of 8xF bx.
4.3 Universal Introduction
The rule for 8I involves a subproof environment. But it is a subproof environment of a
special sort. This subproof environment serves to mark the fact that a constant symbol ?
is temporarily being used to stand for an arbitrary object. We represent this by opening
the subproof environment with a numbered line that just contains that constant symbol
surrounded by a box. This is a “flagging step”: we are flagging that the constant is going
to be used to reason about an arbitrary thing. The constant selected must not appear
in a w? outside the subproof environment. The flagging step is like saying “Consider
an arbitrary thing, call it a.” (Or whatever constant it is that you choose.) The normal
course is then derive to some w?s containing a within the subproof context introduced by
the flagging step. Since the choice of a was arbitrary, whatever conclusions were drawn
could have been drawn about anything; and thus a universal claim is derivable immediately
outside the subproof environment.
Here is a formal way to state the rule:
8I: Where the constant ? does not occur outside lines i-j,
i
?
..
.
j
8?
?/?
8I i-j ?/?
By ?/? , we mean the result of replacing any occurrences of the constant ? in
with
the variable ? in such a way that the resulting sentence, when prefixed with 8?, yields a
universally quantified sentence of which is a substitution instance. For example, if is
F ab, then 8x x/a…
Purchase answer to see full
attachment