> TVS{ =bjbjzz 7\z56TTTTThhh8D<h" 6"XXX333z"|"|"|"|"|"|"$#&\"Ty33yy"TTXX"yTTXTXz"yz" X@R f""0" '*'0 'T 30c"333""IH333"yyyy'333333333 : Logic and its Metatheory
Philosophy 432
Spring 2013
T & TH: 300-450pm
Berkey Hall 211A
Instructor Information
Matthew McKeon
Office: 503 South Kedzie Hall
Office hours: 1-2:30pm on T & TH and by appointment.
Telephone: Dept. Office355-4490
E-mail: HYPERLINK "mailto:mckeonm@msu.edu" mckeonm@msu.edu
Required Text
Courseware Package (Text plus CD software): Jon Barwise and John Etchemendy. Language, Proof and Logic. 2nd edition. Stanford, CA: CLSI Publications, 2011.
The courseware package includes several software tools that students will use to complete homework assignments and the self-diagnostic exercises from the text. DO NOT BUY USED BOOKS, BECAUSE THEY LACK THE CD, WHICH CONTAINS THE SOFTWARE. The software, easy to learn and use, makes some of the more technical aspects of symbolic logic accessible to introductory students and it is fun to use (or so I think).
Primary Course Objectives
Deepen your understanding of logical consequence as well as its relationship to the methods of proof (both formal and informal).
Facilitate your ability to do proofs.
Introduce you to first-order set theory and demonstrate its importance to the study of logical consequence. By the end of the course, you will be able to construct proofs of many set-theoretic truths, both elementary and substantive.
Introduce you to some of the central theorems of logic, including the soundness and completeness theorems of propositional and first-order logic, the Lowenheim-Skolem theorem, and the compactness theorem. By the end of the course, you will understand the foundational and philosophical significance of these and other important results.
I hope to give you a sense of what a logician does for a living, and to highlight in an informal way the connections between logic and other fields like linguistics, computer science, cognitive science, and philosophy. Among other things, this will prepare you for serious thinking on the nature of logic and what distinguishes it from other abstract disciplines like mathematics.
To have fun. Logic is not dry and boring. (I hope!) I have designed this course with the hope that you will both learn from and be entertained by the subject matter.
Please let me know at any point if you think we arent making sufficient progress toward these goals, or if there are goals that you think we should have.
Course Requirements
Eight homework assignments. The lowest grade will be dropped. Your average grade will make up 25% of your final course grade. Each assignment consists of exercises from the text. Typically, youll have a week to complete an assignment. An assignment not turned in when I collect the homework counts as late. There will be no make-up for late homework. The homework schedule is on the last page of the syllabus.
Three open-book (not open-notebook) exams. Each exam may consist of some combination of the following: problems similar in kind to those encountered in the text, T/F questions, short-essay questions, and problems that require you to extrapolate from what you have learned in class and from the text. Your average exam grade will comprise 45% of your final grade. The first exam (on Chapters 1-8) is scheduled for Thursday, February 14th. The second (on Chapters 9-13) is scheduled for Tuesday, March 19th. Note well: these exams will not be rescheduled unless a student is hospitalized and makes available the required documentation. The final exam will cover Chapters 14-19. It is scheduled for Tuesday, April 30th from 3-5pm in our classroom. This exam will be rescheduled only if the student is hospitalized during the exam time or there is a confirmed conflict with another final exam.
Approximately six in-class assignments. The lowest grade will be dropped. Your average grade will make up 30% of your final grade. From time-to-time the class will break up into groups and work on exercises which must be turned in by the conclusion of class. The exercises may be composed of T/F questions, multiple choice questions, problems similar to text exercises, and problems that require you to utilize skills and knowledge required to succeed in the course. Assignments may be unannounced. There are no makeups.
Course Overview
This course is a rigorous introduction to logical consequence, the central concept of logic. The primary aim of logic is to tell us what follows logically from what. We shall take logical consequence to be a relation between a given set of sentences and the sentences that logically follow from that set. A central question of the course is: what conditions must be met in order for a sentence to be a logical consequence of others?
We shall develop an account of logical consequence for a symbolic language (specifically, a first-order language (FOL)). This will allow us to investigate rigorous methods for determining when one FOL sentence follows from others, and will help us develop a method for showing that an FOL sentence is not a consequence of others. In order to give you a glimpse of what lies ahead, I say a bit more about the notion of proof, a notion central to mathematics, logic and other deductive disciplines.
A proof, is a step by step demonstration showing that the conclusion of an argument is a logical consequence of the set of the arguments premises. Another way of relating logical consequence to proof is to say that each step in a proof is a logical consequence of previous steps and/or the set of the arguments premises. Hence, in order to build a proof one must be able to determine whether or not the relation of logical consequence holds between sentences. Typically, informal proofs leave out steps (perhaps because they are too obvious) and do not justify each and every step made in moving towards the conclusion (again, obviousness begets brevity). Proofs are not only epistemologically significant as tools for slaying Descartes evil demon and securing knowledge. The formal derivations that make up a proof serve as models of the informal reasoning that we perform in our native languages. This is of importance in, among other areas, computer science and artificial intelligence. Furthermore, the study of proofs allows us to follow Socrates and better know ourselves as reasoners. After all, like Molires M. Jourdain, who spoke prose all his life without knowing it, we reason all the time without being aware of the principles underlying what we are doing.
We shall learn a natural-style deduction system derived from the work of the mathematician Gerhard Gentzen and the logician Fredrick Fitch. Our natural-style deduction system, called Fitch, is basically a collection of inference rules, which license steps in deductive chains of reasoning. Natural deduction systems are distinguished from other types of deduction systems by their usefulness in modeling ordinary, informal deductive inferential practices. Accordingly, we shall introduce and motivate the inference rules of Fitch by uncovering their correlates at work in informal proofs. In logic, we like to reveal the meat and bones of a proof, making each step and justification explicit. We shall do this by first translating the premise(s) and conclusion of the argument at hand into formal sentences from a sample FOL, and then building a proof that appeals exclusively to the inference rules of Fitch. We shall call the result a formal proof. Frequently we shall work on arguments already composed of FOL sentences. As youll come to see, learning how to construct formal proofs using Fitch hones skills at constructing and evaluating informal proofs.
After developing a familiarity with formal and informal methods of proof and the method of counterexample, and after working on translating from English to FOL and back again, we shall study applications of Fitch in employing the axiomatic method. The axiomatic method, made famous by Euclid in geometry, is a method of organizing a body of knowledge by choosing a few truths as basic (the axioms) from which all truths from the relevant domain of knowledge (the theorems) may be deduced using a deduction system such as Fitch. Students will be introduced to axiomatizations of Zermelo-Frankel set theory and of natural number theory (Peano Arithmetic). Well spend time using the informal proof techniques weve learned to derive theorems from the axioms of Zermelo-Frankel set theory and the axioms of Peano arithmetic. Along the way we learn about Russells paradox and about a very powerful rule of inference called the principle of mathematical induction. An inherent limitation with the axiomatic method will be highlighted when we come to Gdel's Incompleteness theorems at the end of the course.
PHL 432, unlike PHL 330, considers historically significant proofs regarding Fitch. This is the metatheory part of PHL 432. More specifically, in PHL 432 we develop a model-theoretic definition of logical consequence, which is a mathematical characterization of the informal notion of logical consequence that we work with during the first half of semester. Then we shall prove that Fitch, our natural deduction system, is sound. That is, we shall prove that if there is a proof in Fitch of sentence X from a class K of sentences, then X is a model-theoretic consequence of K. We also prove the Completeness Theorem for Fitch (i.e. prove that if X is a model-theoretic consequence of K, then a proof of X from K is constructible in Fitch. Proving that Fitch is sound and complete will not only demonstrate that provability in Fitch is adequate as a characterization of logical consequence, but also offers an enlightening (meta-) perspective on the nature of formal proof, logical consequence, and their relationship. After proving the Completeness Theorem for Fitch, we draw two well-known consequences: the Lwenheim-Skolem Theorem and the Compactness Theorem. These are discussed and applied. The course concludes with a sketch of Gdel's Incompleteness Theorems.
Class Time
Class time will primarily be spent going over text exercises, and reviewing or expanding on key points from the reading. It is imperative that students keep up with the rigorous pace of the course by doing the assigned readings in a timely manner, and by doing enough of the relevant practice exercises to get a feel for ones level of understanding BEFORE coming to class. Class time is your opportunity to clear up those things that you find mysterious or troublesome. So, coming to class unaware of what you don't know is not the best way to use class time.
Attendance
I do not take attendance, but, as Woody Allen says, 80% of success is just showing up. Regular class attendance is critical to being successful in this course. In general, it is my experience that the majority of those who frequently miss class are less successful in the course than those who attend regularly. I consider any more than two absences excessive. Students that are absent from class are responsible for missed announcements and for getting class notes. To reiterate, there are no makeups for missed class assignments. A class assignment missed for whatever reason counts as a 0%. Only one such grade on a class assignment may be dropped.
Work Level
Students are expected to work independently outside of class learning course material and practicing the skills necessary to successfully complete logic exercises. The software included with the text is very useful for learning logic. In order to be successful on the exams and homework that come later in the semester, one must understand the earlier material upon which this required work is based. Since later coursework is based on and incorporates earlier work, (again) it is imperative that you keep up with the pace of the course. Furthermore, while the course material is not especially difficult, it does demand quality thinking. Hence, it is vital that throughout the semester you reserve quality time for coursework (doing logic problems when you are rushed or exhausted tends to increase the difficulty of the problems), and that you work diligently and consistently on understanding class material (missing lots of classes and doing the reading for an assignment the night before that assignment is due is a recipe for disaster).
Grading
Grades on required work will be on a 100-pt. scale. Your final grade will be first determined on a 100-pt. scale, and then converted to a 4.0 scale according to the below tabulations. For example, a final grade of an 83% corresponds to a 3.0 and a 77% corresponds to a 2.5.
Final Grades
4.0=90% and above
3.5=85--89%
3.0=80--84%
2.5=75--79%
2.0=70--74%
1.5=65--69%
1.0=60--64%
Tentative Schedule
Alterations to the following schedule are possible in response to class needs.
1/08 Introduction
1/10 Chapters 1 & 2
1/15, 17 Chapters 2, 3 & 4
1/22, 24 Chapters 5 & 6
1/29-2/12 Chapters 7 & 8
2/14 Test #1: Chapters 1-8
2/19 Chapters 9 & 10
2/ 21 Chapter 11
2/26, 28 Chapters 11, 12 & 13
3/04-3/08 Spring break
3/12, 14 Chapters 13 & 14
3/19 Test #2: Chapters 9-13
3/21-4/02 Chapters 14 & 15
4/04-11 Chapters 16 & 17
4/16, 18 Chapter 18
4/23, 25 Chapter 19
Homework Schedule (the homework will be posted on ANGEL)
Due by the start of class Chapter(s) covered
#1 1/22 Chapters 1-4
#2 2/07 Chapters 5-8
#3 2/28 Chapters 9 11
#4 3/12 Chapters 12 & 13
#5 4/04 Chapters 14 & 15
#6 4/16 Chapters 16 & 17
#7 4/23 Chapter 18
#8 4/30* Chapter 19
*Hardcopy must be turned in at the final exam.
PAGE
PAGE \* MERGEFORMAT 3
34567:<>GIZ[st % ' ( 7 8 9 J
t#ƆƂh:Hhb>hOAhWCJH*
hs6CJhuhW0JhWhWhWjhWU
hCJhWhWCJhs hs5hhsCJaJhWCJaJ
hWCJ
hiCJ
hsCJ
hsCJ
hsCJ 2*6IZ[st9 : I J %K6
&Fgdb>$a$gdb>$a$#$%IJK5
6
3>Qfgl!",01\]^
h
CJ
hsCJH*
hS>CJ
h0CJ
hh_QCJ
hUCJ
hcCJ
h}CJ
h CJ
hb>CJ
hs5CJ
hRCJ
hIhCJ
h+CJ
hCCJ
hxCJ
hWCJ
h+CJ
hsCJhs
hrtNCJ36
Qfg^_RST!U!%gdb>$a$gd
&F gdb>
&Fgdb>gdb>
&Fgdb>
&Fgdb>)BC^jn|~fgкИh+hPlh#hs
hK{CJ
hrtNCJ
hwCJ
hHCJ
h CJ
hb>CJhh_Qhh_QCJH*
hh_QCJ
hsCJ
h
5CJ
hs5CJhS>hS>CJH*
hS>CJ
h
CJ
h-CJ7$$$$A*F*H*}***********++,,,,s-y-z-{-~--A.C.?/@/A/L/M/11e333$4%4/414n4445G8I8M8T8U8V8`8n8
h0CJ
hsCJ
hs5CJhs56CJhCVhd+hTQ] hx6hUShR h+6 hs6hhHehIhh.jh!hS:hsh_?%%@*A*>/?/@/A/L/M/1111#4%40414L8M8U8V8j9gdPl
&F$a$gdPl
&FgdTQ]gdx
&F$a$gdb>n8j9k999999999999+:7:9:=:?:A:N:O:R:S:T:o:p:q:t:u:y::::::::::::::::::::::;;;
hCJ
hW5CJ
hRCJ
hY&CJ
hR!CJ
hfCJ
h6ECJ
hCJ
h-WkCJ
h_=CJ
h2ZCJ
h.ACJ
h= CJhPlhPlhPlhs hs5
hs5CJ
hOCJ
hsCJ6j9k9x9y999999999999::;:N:O:p:q:::::$a$gdPl@^@@^@$@^@a$$p^p`a$::::::;;;5;6;P;Q;k;l;;;;;;;;;;;;;;;gdgd;;;;;;;&;*;.;/;2;3;4;6;8;:;=;?;Q;T;U;X;Y;a;b;e;j;n;p;q;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;ľܸܲЮhhh
h\yCJ
hh_QCJ
hfCJ
hW5CJ
h-WkCJ
hsCJ
hY&CJ
hr.CJ
h-%CJ
h0CJ
h6ECJ
hCJ
hRCJB;;;;;;;;;;8<9<g<i<<<<<<=%=H=I=gdUSdhgdCQdhgdCQgd^`gdgdgdxgd|zgdgd;;;;;<6<g<i<m<p<q<t<u<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<===
========#=ѿݻݳݻݻݻݳݻݻݻݳݳݳݳݳݳhCQhyFhf
hQCJ
hCQCJ
hyFCJ
hfCJ
hsCJhs h5hhxhxhxhUSh|zh|zF#=-=.=H=I=J=[=w=z={=}=~====================ŽjhxUmHnHuhxmHnHuhxjhxUhC
hC0JjhC0JUhB|jhB|Uhsh!,^hNvhUShUShPhCQI=z=|=}===============$a$h]h&`#$5
01:px/ =!"#$%^02 0@P`p2( 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p8XV~_HmH nH sH tH 8`8Normal_HmH sH tH 8@8 Heading 1$@&CJ<@< Heading 2$@&5CJ<@< Heading 3$@&6CJDA`DDefault Paragraph FontViVTable Normal :V44
la(k (No List0>@0Title$a$CJ0U`0 Hyperlink>*B*<Q@<Body Text 3$a$CJ4@"40Header
!.)@1.Page Number2B@B2 Body TextCJ4 R4xFooter
H$.a.xFooter Char./q.x0Header CharPK![Content_Types].xmlN0EH-J@%ǎǢ|ș$زULTB l,3;rØJB+$G]7O٭V$!)O^rC$y@/yH*)UDb`}"qۋJחX^)I`nEp)liV[]1M<OP6r=zgbIguSebORD۫qu gZo~ٺlAplxpT0+[}`jzAV2Fi@qv֬5\|ʜ̭NleXdsjcs7f
W+Ն7`gȘJj|h(KD-
dXiJ؇(x$(:;˹!I_TS1?E??ZBΪmU/?~xY'y5g&/ɋ>GMGeD3Vq%'#q$8K)fw9:ĵ
x}rxwr:\TZaG*y8IjbRc|XŻǿI
u3KGnD1NIBs
RuK>V.EL+M2#'fi~Vvl{u8zH
*:(W☕
~JTe\O*tHGHY}KNP*ݾ˦TѼ9/#A7qZ$*c?qUnwN%Oi4=3N)cbJ
uV4(Tn
7_?m-ٛ{UBwznʜ"ZxJZp;{/<P;,)''KQk5qpN8KGbe
Sd̛\17 pa>SR!
3K4'+rzQ
TTIIvt]Kc⫲K#v5+|D~O@%\w_nN[L9KqgVhn
R!y+Un;*&/HrT >>\
t=.Tġ
S; Z~!P9giCڧ!# B,;X=ۻ,I2UWV9$lk=Aj;{AP79|s*Y;̠[MCۿhf]o{oY=1kyVV5E8Vk+֜\80X4D)!!?*|fv
u"xA@T_q64)kڬuV7t'%;i9s9x,ڎ-45xd8?ǘd/Y|t&LILJ`& -Gt/PK!
ѐ'theme/theme/_rels/themeManager.xml.relsM
0wooӺ&݈Э5
6?$Q
,.aic21h:qm@RN;d`o7gK(M&$R(.1r'JЊT8V"AȻHu}|$b{P8g/]QAsم(#L[PK-![Content_Types].xmlPK-!֧60_rels/.relsPK-!kytheme/theme/themeManager.xmlPK-!0C)theme/theme/theme1.xmlPK-!
ѐ' theme/theme/_rels/themeManager.xml.relsPK]
5\ 555558#n8;;#==!#$&)+,6
%j9:;I== "%'(*-'75X/18!!8@0(
B
S ?559*urn:schemas-microsoft-com:office:smarttagsState8*urn:schemas-microsoft-com:office:smarttagsCity9*urn:schemas-microsoft-com:office:smarttagsplace8Q Q ,22fg?'@'A'A'K'L'11729233333333G5H5y5z5z5|5}5}555555555555581133y5z5555558Q Q ,22fg?'@'A'A'K'L'11729233333333G5H5y5z5z5}5}55555558Q Q ,22fg?'@'A'A'K'L'11729233333333G5H5y5z5z5|5}5}55555555555 *P K bp% zeM' Fu3 iB ^ hh^h`OJQJo(hh^h`OJQJo(hh^h`OJQJo(hh^h`OJQJo(hh^h`OJQJo(hh^h`OJQJo(hh^h`OJQJo(hh^h`OJQJo(hh^h`OJQJo( ^zeM'iBFu3bp% *PK _^d+#S:= f+W!-kR! "-%&Y&W5pz<_=S>b>yF+GH:HrtNCQh_QUSTQ]!,^_;PcvpdHeIh.j-Wkslk?@ABDEFGHIJLMNOPQRURoot Entry F W1Table/1'WordDocument7\SummaryInformation(CDocumentSummaryInformation8KCompObjr
F Microsoft Word 97-2003 Document
MSWordDocWord.Document.89q