Video summary
In deductive logic, proofs and models represent two distinct yet interconnected methods for analyzing sentences within Quantified Logic (QL), distinguished by their syntactic and semantic nature respectively. Syntactic analysis relies on proof theory, indicated by the single turnstile symbol ($\vdash$), which asserts that a statement is derivable or provable based solely on logical rules without reference to truth values; this establishes whether something is a theorem. Conversely, semantic analysis uses model theory, denoted by the double turnstile symbol ($\models$), to determine if an argument holds true across all possible interpretations, thereby establishing validity or tautology. While these approaches differ in their fundamental mechanisms—one manipulating symbols according to rules and the other evaluating truth conditions—they are deeply related through two critical properties of formal systems: soundness and completeness. A system is considered sound when every syntactic proof corresponds to a semantically valid argument, ensuring that no invalid conclusions can be derived; for instance, the rule of conjunction introduction preserves truth because if premises $A$ and $B$ are true in any model where they hold, their combination must also be true.
The relationship between these methods is further defined by completeness, which guarantees that every semantically valid argument has a corresponding syntactic proof within the system; both QL systems discussed possess this property, allowing logicians to use proofs or models interchangeably depending on convenience. However, not all logical frameworks share this balance, as demonstrated by hypothetical rules like "modus pocus," which would allow deriving $C$ from an implication where only one case is true but fails semantic entailment in others, rendering such a system unsound. This distinction highlights that while QL is both sound and complete for basic logic, stronger systems capable of expressing arithmetic are inherently incomplete due to Gödel's incompleteness theorems, meaning there will always be truths about natural numbers that cannot be proven within those specific proof systems. Consequently, understanding when to apply a model versus a proof becomes essential: models are most efficient for demonstrating invalidity by providing a single counterexample or showing consistency with one true instance, whereas proofs are necessary for establishing universal validity, tautology, or contradiction where reasoning must hold across all possibilities.
Practical application of these concepts allows logicians to efficiently address various logical questions such as equivalence, contingency, and inconsistency by choosing the most appropriate tool for the task at hand. For example, proving that a statement is contingent requires showing it can be true in one model while false in another, whereas demonstrating invalidity only demands constructing a single countermodel where premises are true but the conclusion is false. Similarly, establishing logical equivalence involves deriving each sentence from the other via proof or exhibiting models with differing truth values for non-equivalent pairs. The transcript illustrates these strategies through specific exercises involving quantifiers and predicates; one example shows how to prove an autology by using universal introduction after handling free variables in a subproof, while another demonstrates that a seemingly consistent statement is actually contingent only if two different models are constructed. In cases of inconsistency or invalidity, the process often shifts toward model construction to find specific assignments for constants and extensions of predicates that satisfy premises but falsify conclusions, effectively bypassing lengthy derivations when semantic counterexamples suffice.
Ultimately, mastering the interplay between proof-theoretic and semantic concepts enables a flexible approach to solving complex logical problems without reinventing methods from scratch. By leveraging soundness and completeness, students can confidently alternate between deriving proofs in software like Carapace or constructing models with limited domains to verify truth conditions, ensuring that their conclusions are robust regardless of the method used. This dual capability is particularly valuable for exam scenarios where one must determine if a set of sentences is consistent by finding a model where all are true, or prove an argument invalid by identifying a scenario where premises hold but the conclusion fails. The ability to switch seamlessly between these perspectives not only deepens understanding of logical structure but also provides practical strategies for tackling questions about validity, contingency, and equivalence efficiently. As emphasized in the lecture, keeping both tools in mind allows for optimal problem-solving techniques that will serve well in advanced logic courses and examinations, reinforcing the idea that while proofs offer rigorous derivation paths, models provide intuitive checks on truth across interpretations.
Read the full video transcript
hello and welcome back to Phil 320
deductive logic I'm professor Matthew
Brown this is the third in our lectures
on proofs in ql and the final lecture of
the
semester um and today we're going to be
talking about proofs and models in ql
how to use our proof theoretic and our
semantic Concepts to accomplish various
tasks I want to start by just talking
about the relationship between proofs
and models the these are two very
different ways of evaluating sentences
of ql we use these different symbols the
single Turn Style and the double Turn
Style to indicate when we're doing
semantic and syntactic Analysis the
single Turn Style tells us that a proof
is possible right um we denote this with
a single Turn Style and we know this is
a syntactic style of analysis right it's
not the same as semantic entailment
which we wrote with this double Turn
Style on the right here we talked a bit
in the last unit about the difference
between proof theoretic or syntactic and
semantic analyses so um you remember on
the Left Right single Turn Style a says
that a is a theorem a is a theorem of SL
or ql depending on what we're talking
about um the right says with the double
Turn Style that a is a
tautology right similarly the left here
says that we can derive B from a right B
can be proved on the basis of a the
right on the other hand says that a
semantically entails B if a is true then
B must be true we don't have to mention
the truth values of A and B to
understand derivability or provability
but we do have have to mention it if
we're going to account for semantic
entailment
right so now I've I'm I'm saying all of
these are different Notions and they are
because one is syntactic and the other
is
semantic um but how are they connected
how do they relate to one
another well the property of some formal
systems that we call soundness means
that whatever is derivable is also
semantically entailed right a pro system
is sound if there are no proofs of
invalid arguments right if every proof
implies that there is semantic
entailment there is validity so consider
the conjunction introduction rule right
suppose up to this point you have a
proof um where you've derived A and B
and suppose also that you uh have
determined semantically speaking that
the proof is valid
right so A and B are either premises of
the argument or they're valid
consequences of the premises in any
model where the premises are true A and
B are true right so we've done the
semantic analysis of that right given
the definition of Truth in ql right um
specifically part three of that
definition A and B must also be true
right
um so the conjunction introduction rule
when applied to um sentences we know to
be true preserves that truth right so
any application of the conjunction
introduction rule not
only creates a
proof uh where we derive A and B but we
know that that must be also valid a
valid argument because it's semantically
entailed right
consider a new rule that we might add to
our our proof system let's call it modus
Pocus right um here's how I'll Define
that rule suppose on line M uh we have a
conditional of the form if B then C
right modus Pocus as a rule allows us to
conclude C right and you might think
that doesn't sound like a great rule how
did I get C well yes that's part of the
point now let's look at our uh
definition of Truth in ql right um if a
sentence a has the form if B then C for
some wolfs B and C then we know that a
is not
satisfied if um B is satisfied but C is
not and it's satisfied otherwise right
that's how we Define the truth of the
sentence on line M right and and let's
suppose for the sake of argument that we
know that that line is true but we know
that can be true in the case where B is
false and C is false if we allow the
modus Pocus rule in then we have a
derivation from a to c right but a does
not semantically entail
C so the system of ql plus modus Pocus
is not a sound system so conjunction
introduction is sound sound but modus
Pocus is not sound okay so that's
soundness we also have the property of
completeness right a proof system is
complete if there is a proof of every
valid argument right which is to say if
a semantically entails B that implies
that b is derivable from
a now both SL and ql are complete
and sound but not every logical system
is in fact any system that is strong
enough to express the basic arithmetic
of natural numbers is incomplete right
that was uh that was proved in the early
20th century by Kurt gerell right there
will always be statements about natural
numbers that are true but are unprovable
within a proof system that is uh is
powerful enough to express those truths
because ql is sound and complete you can
use proofs or models interchangeably to
establish things like validity tautology
and so on and sometimes it's more
convenient to use a proof other times
it's more convenient to use a model
let's go through the cases right let's
start with the question of is a a
topology if it is a toy the easiest way
to show that is just to
prove uh that a is derivable that a is a
theorem right um but if it is not a
topology the easiest way to do that is
just to give a model where a is false
right same deal with the contradiction
except the negation is there so the
easiest way to show that a is a
contradiction is to prove that not a is
a theorem right whereas the easiest way
to show that it is not a contradiction
is to give a model where a a is true the
question of whether a is contingent the
easiest way to show that in the
affirmative is to give a model where a
is true and another one where is a is
false um whereas the easiest way to show
that it is not contingent is to prove
that it's a theorem or that its negation
is a theorem right now you may be
catching on to a pattern here wherever
you can answer the question with a
single model or a pair of models models
are the easiest way to get
wherever you would have to reason about
all possible models it may be easier
just to do a proof right let's look at
some other cases you want to know
whether A and B are logically equivalent
right you can show this through proof by
proving by deriving B from a and vice
versa right you can show that they're
not equivalent by giving a model where
they have different truth values
right to show that a set of sentences a
is consistent right you can show that by
just giving a model in which all of the
sentences are true you can show that
they're inconsistent by taking all of
the sentences as a as premises and
proving a
contradiction and then finally to show
that the argument if with premises p and
conclusions C is valid all you need to
do is prove C on the basis of P to show
it's invalid it's easier to just give a
model where p is true and C is false
right and so in this way you can uh you
can combine what we learned in unit six
about models with what we've learned in
this unit as well as unit four about
proofs um in order to answer any of
these types of questions about
contingent or logical truths um about
equivalent y consistency and validity
and it would be really to your benefit
to keep all of these things in mind when
you come to exam s right let's try to
look at a number of examples of applying
this sort of proof or model approach
right so here I have six questions um
that I want you to try to answer either
using a proof or a model so take a
moment to pause the video and work
through all six of these questions and
we'll come back and look at them
together okay let's find out how you did
uh going through uh each one
right uh first we want to know is for
all X and for all y lxy or not lxy
autology I think it probably is it
certainly has that sort of um a or not a
form which is which suggests topology
and so our our way to show that it's a
topology is just to prove that it's a
theorem right to prove that we can
derive it without any premises so let's
go over to carap and see if we can make
that work so here we go we have for all
X for all y lxy or l or not lxy I think
the best way to do this is to start with
a conditional introduction
inter indirect proof we did something
very similar in
SL back in unit 4 I'm going to start by
assuming La I want to get La again I'm
using LA because I can't use l XY I
can't have Unbound
variables free variables so I need to
use some constants that's easy just
reiteration right now I have if La then
la
that is um conditional introduction one
to two right to get that into a
disjunction form I just need to use the
material conditional rule that's not lab
or
lab material conditional on line three
we can just shift that around through
commuity on line four and now I want to
start introducing my Universal quantify
fires I'm going to first replace B with
y That's Universal introduction on line
five now I'm going to place the a with
an X lxy or not
lxy it's Universal introduction on line
six
and I I forgot my quantifier there
that's done okay did you get something
similar when you tried this on your
own uh let me know
let's move on to number two we want to
know is there exist an X PX and not PA a
contradiction you might think well it
sort of seems like it right um but pay
attention to the scope of the quantifier
right the existant X PX is only over the
first part right so there is something
that's PX but it's not PA actually that
seems like pretty consistent right so
let's see so if we think that it is not
a contradiction all we have to do is
show a model where it comes out true
right so let's see if we can do that um
let's start with a universe of discourse
that has two items I'm thinking two
items because we have to have one thing
that is PX and we have to have a be not
PX right and not BP not satisfy P so um
if we make the extension of P0 that
satisfies the left hand side there is an
X PX if we make the reference of A1 then
a is not P right a is not in the
extension of P so that makes the right
hand side of the conjunction true so the
conjunction is true that means it's not
a
contradiction is that how you did it let
me
know um our third one is that is the
question is for all X PX and not PA
contingent if it is contingent we just
have to show two models one where it's
true and one where it's false but in
this case I think it is not contingent
because if all X are PX then a is one of
all the things right so not PA couldn't
be true I think this is a
contradiction and so to prove that we
have to
derive um the negation we have to prove
that the negation of it is a theorem
right so let's head over to carap and
give that a go
to prove a theorem we don't have any
premises we just we just begin with an
indirect proof of some kind I am going
to suggest because negation is our main
connective in what we're trying to prove
that we try a negation introduction
proof um so we need to
assume the thing that we want
to uh negate the thing we want to derive
a contradiction from and that's for all
X PX and not PA right so we're going to
assume that for reductio we got a
conjunction here we can definitely use
our conjunction elimination rule on line
one I'm seeing Universal elimination
here is the obvious possibility
Universal elimination online two gets us
PA remember Universal elimination you
can use any constant you want even if it
is in an
assumption I've got PA I can get not PA
from uh our conjunction elimination on
line one right PA and not PA are the
contradiction that we need for a
reductio proof and so I can I can close
out my sub proof and conclude not ax PX
and not PA through negation
introduction lines one through four and
that has done it I hope you had a
similar answer let's look at number
four um here we want to know whether
these two are
equivalent and although you might think
that they're equivalent because they
have a very similar form we've just
subbed out the um predicates because the
predicates mean different things or can
mean different things they don't have to
be equivalent and this simple model can
show it let's look at number five right
number five we ask is this set of four
sentences
consistent right um and uh if they are
consistent we just need to provide a
model where all of them are true but
looking at this set of sentences I kind
of doubt that they're consistent right
um we've got for all X PX in one in one
sentence we've got a not PX there and
another sentence I think that they're
probably uh not consistent inconsistent
and so I'm going to try to prove a
contradiction based on this set so let's
head over again to carap to see if we
can show that so here we are I've loaded
all of the sentences in our um in our
set in as premises in carap and what I
want to do is I want to try to find a
contradiction I want to derive a
contradiction let's look at what we've
got we've got a universal
right so one thing we could do is we
could eliminate the universal on line
one that's an obvious one I've got three
existentials now um and so so we're
going to need to use existential
elimination I think to get anywhere with
this let's see what we can do so let's
start with line three that's where our
not p is
at um so what I'm going to try here is
is
QA and not
PA that's an
assumption I can get not PA through
conjunction elimination on line six I
can get there exists an X not PX through
existential introduction on line seven
okay that's gotten rid of my a from the
Assumption and and so I can bring that
out of the sub proof that is existential
elimination on existential 3 and sub
proof 6 through
8 okay how can I turn that into a
[Music]
contradiction I think I see it right I
can do quantifier negation to move that
negation out front here not for all X
PX that's a quantifier negation online n
right whenever I uh do that exchange of
the negation and the quantifier I I flip
it from one to the other not ax PX um if
we combine it with ax PX we get a
straightforward
contradiction there and that is what I'm
trying to prove that's just conduction
introduction on lines one and
10 um so actually I didn't really need
this line five that was was unnecessary
that was a a dead end which is okay that
happens there may have been another way
to get a
contradiction
but that is the way that I try to do it
now let's see about this uh last
question here we want to know whether
this argument for all X if PX then QX QA
therefore PA is
valid this looks invalid to me this is
uh what we might call the fallacy of
affirming the consequent right um if we
had PA we could derive QA if we had not
QA we could derive not PA but I don't
think we can derive anything from Q from
QA and this conditional let's show this
is invalid by coming up with a model
like I've said before I'm going to start
with a model with just one item in it I
might have to introduce additional items
as we go
through um in this case I think I won't
I can set the extension of P to the
empty set right that means that the
universal for all X PX and QX is
true um trivially right um uh all PS are
Q's when there are no PS no matter what
we might think P
represents um if we set the uh extension
of Q to one and the referent of a to one
then QA is true but PA is false because
there's nothing in the extension of P
including the reference of a and so this
shows that the argument is invalid right
what we've been doing today is just
using our knowledge from unit six on
semantics and models with our uh
Knowledge from Unit Seven here on proofs
combining them together due to the
soundness and completeness of ql to to
solve questions about logical truth
contingency validity
consistency
Etc um using both models and proofs as
is most appropriate you should practice
this because it is going to feature
centrally in the last exam exam 7 so
good luck with the practice exercises
please get in touch if you need some
help um and uh good luck with it I hope
you've enjoyed uh this semester and um I
look forward to seeing your final
progress in the
class um and uh please don't hesitate to
reach out if you need to bye