PHL
467 / MA 467, Mathematical Logic Dr.
Poston
11
to 12:15, TR HUMB 114 Office:
HUMB 124
Office
Hours: Phone:
460-6248
MF 9:15 to 9:45; MWF 2:30-3:00;
TR 12:30pm to 1:30pm
Email:
mylastname@jaguar1.usouthal.edu
Course
Webpage: http://www.southalabama.edu/philosophy/poston/mathlogic.htm
Course Description:
This is a course in mathematical logic that will
introduce important aspects of the first-order predicate logic and its
extensions. First-order predicate logic
is the most powerful system of deductive inference that is provably
complete. The extensions of first order
logic include axiom systems formulated within it such as the Peano Axioms for the natural numbers. A number of important facts have been proven
about first-order logic and its extensions, and we will examine some of
them. These facts include: (1) soundness
and completeness for first-order predicate logic; (2) the undecidability
of first-order predicate logic; (3) an axiomization
of arithmetic in first-order predicate logic; (4) Cantor’s proof of transfinite
numbers; (5) the compactness theorem—if every finite subset of a set of
sentences has a model, the whole set has a model; (6) the (downward) Lowenheim-Skolem theorem—if a set of sentences has a model,
it has an enumerable model; (7) The upward Lowenheim-Skolem
theorem—If a set of sentences has an infinite model, is has a nonenumerable model; (8) the (abstract) Godel
completeness theorem: The set of valid sentences is semirecursive;
and (9) Godel’s first incompleteness theorem
according to which any sufficiently strong formal system of arithmetic must be
incomplete, if it is consistent.
The course does not required knowledge of
mathematics beyond basic linear algebra.
However, it will assume that you are comfortable with some standard
methods of mathematical definition and proof, so previous college-level course
works in mathematics (at least one course at the 300 level or higher) or logic
(PHL 321) is required. In some special
cases I will waive these requirements.
If you do not meet these requirements and wish to take the course please
speak with me.
Texts:
Jeffrey, Richard.
Formal Logic: Its
Scope and Limits 4th edition.
(FL) Hackett Publishing Company. Available at the University Book Store.
Boolos, Burgress, & Jeffrey. Computability and Logic 5th edition. (CL) Cambridge University Press. Available at the University
Book Store.
Helpful Resources:
Pollock, J. Technical Methods in Philosophy. (TMP) Westview Press, 1990. Available online at: http://oscarhome.soc-sci.arizona.edu/ftp/PAPERS/TM/TM.pdf
Causey, R. Logic, Sets and Recursion. (LSR) 2nd Edition, 2006.
The HarperCollins Dictionary of Mathematics Collins, 1991.
http://www.math.lsa.umich.edu/research/logic/
http://plato.stanford.edu/contents.html (see entries under logic)
Course Goals:
Course Policies and
Procedures:
Attendance: Attendance in lectures is
expected. If you want to receive a good
grade in the course then you will need to come to class. Each day I will introduce new material and
each class builds on the previous class.
If you must miss class get the notes from one of your fellow students
and make sure you understand the notes.
Make-up Work: Only in exceptional
circumstances will I reschedule homework assignments or exams. If you *have* to miss an exam contact me as
soon as possible. You must notify me at
least one week prior to the exam. If,
for example, you break your arm before class then take an aspirin, come to
class, and go to the hospital after class.
After
all, you still have one good arm to write with!
Disabilities Policy: If you have a specific
disability that qualifies you for academic accommodations, please notify me and
provide certification from Disability Services (Office of Special Students
Services). The Office of Special Students Services is located in the
Academic Dishonesty Policy: Academic dishonesty
includes cheating on tests and homework as well as plagiarism. If you engage in academic dishonesty, I will
notify you that you will receive an ‘F’ in the course. Upon being notified, you
have five days to submit a written request to the department chairperson for a
hearing on the matter, if you wish to have one. If no hearing request is made,
or if the decision from the hearing goes against you, you will receive a course
grade of ‘F’. Please see the Student Academic Conduct Policy of the University
for details.
Note on homework: Naturally you may study with other students,
but do your homework on your own. In the past I have discovered plagiarized homework:
in such cases the above-stated policy applies.
Also, homework is due at the beginning of class on the day listed. I accept only clearly written
homework. I recommend typing the
homework if your handwriting is notorious.
I will not grade any homework that I cannot easily read.
Evaluation:
2 Take-Home exams, each
exam is worth 25% of your total grade.
12 Quizzes, collectively
worth 25% of your total grade. These
quizzes will consist largely of being able to give crucial definitions and to do
proofs (sometimes I’ll just ask you to prove a crucial lemma). I will announce ahead of time which proofs
& definitions you should know.
Homework
assignments, collectively worth 25% of your total grade. We will
have short HW assignments do each day. The
goal of these assignments is to make sure you are learning the course material
and tracking along as the course progresses.
Schedule:
The schedule will develop as we go.
|
|
Daily Plan |
Reading |
Quizzes |
|
Tuesday, 1.13 |
Intro & TF Logic |
Ch 1, FL |
|
|
Thursday, 1.15 |
Truth Trees |
Ch 2, FL |
|
|
Tuesday, 1.20 |
Generality |
Ch 3, FL |
|
|
Thursday, 1.22 |
Generality |
Ch 3, FL |
Q1 |
|
Tuesday, 1.27 |
Multiple Generality |
Ch 3 & 4, FL |
|
|
Thursday, 1.29 |
Multiple Generality |
Ch 4, FL |
Q2 |
|
Tuesday, 2.03 |
Identity |
Ch 5, FL |
|
|
Thursday, 2.05 |
Functions, Group Theory, Robinson Arithmetic |
Ch 6, FL |
|
|
Tuesday, 2.10 |
Group Theory, Robinson Arithmetic, Turing Machines |
Ch 7, FL & Ch 3 CL |
|
|
Thursday, 2.12 |
Turing Machines, The Halting Problem |
Ch 3 & 4 CL |
Q3 |
|
Tuesday, 2.17 |
Turing Machines, The Halting Problem |
Ch 7, FL |
|
|
Thursday, 2.19 |
Register Machines, Godel Numbering |
Ch 7, FL |
|
|
Tuesday 2.24 |
Mardi Gras |
|
|
|
Thursday, 2.26 |
Programs in Logical Notation, Undecidability |
Ch 8, FL |
Q4 |
|
Tuesday, 3.03 |
Undecidability |
Ch 8, FL |
Q5 |
|
Thursday, 3.05 |
Undecidability |
Ch 8, FL |
|
|
Tuesday, 3.10 |
Incompleteness |
Ch 9, FL |
Q6 |
|
Thursday, 3.12 |
Incompleteness |
Ch 9, FL |
|
|
Tuesday, 3.17 |
SPRING BREAK |
|
|
|
Thursday, 3.19 |
SPRING BREAK |
||
|
Tuesday, 3.24 |
Midterm Exam |
Exam |
|
|
Thursday, 3.26 |
Go over Midterm |
||
|
Tuesday, 3.31 |
Enumerability |
Ch 1, CL |
|
|
Thursday, 4.2 |
Diagonalization |
Ch 2, CL |
Q7 |
|
Tuesday, 4.7 |
Recursive Functions |
Ch 6, CL |
|
|
Thursday, 4.9 |
Recursive Sets & Relations |
Ch 7, CL |
Q8 |
|
Tuesday, 4.14 |
Syntax & Semantics |
Chs 9 & 10, CL |
|
|
Thursday, 4.16 |
Models |
Ch 12, CL |
Q9 |
|
Tuesday, 4.21 |
Compactness & Lowenheim-Skolem theorems |
Ch 15, CL |
|
|
Thursday, 4.23 |
Arithmetization |
Ch 16, CL |
Q10 |
|
Tuesday, 4.28 |
Representability of Recursive Functions |
Ch 17, CL |
|
|
Thursday, 4.30 |
Indefinability, Undecidability,
Incompleteness |
Q11 |
|
|
Tuesday, 5.5 |
Final Exam, 10:30
to 12:30 |
|
|