Basic Information Instructor: Kent Johnson
(learn about Kent here) Office Hours: Tuesday, Thursday after class (and by
appointment) Office Location: SST 755
TA: Christina Conroy
(learn
about Christina here) Email: cconroy@uci.edu Office Hours: Tues., Thurs. 1 - 1:50pm
(and by
appointment)
Office Location: SST 786
Required
Text: We will continue to use the same notes as were used in
the A component of this sequence. If you do not already have a copy of
these notes, please let me know.
Other Texts: A former student in
this course has recommended the following two books as useful ancillary
resources:
Course Password: _______________________________
General remarks.Welcome to
Metalogic.The general goal of this
course is to introduce students to the mathematical properties of some
elementary
formal
languages and the means by which precise and accurate reasoning (i.e.,
proofs)
may be performed within them.Problems
will be given out on a regular basis.Problems that may be completed and handed in for extra credit
will also
be presented from time to time.The
tests will cover any material that has so far been presented in class
or in the
book (or both).
Material
to be
covered.The core of this course will
be based around
some of the central results of first-order logic (FO).So we will certainly address in detail:
Introduction to
FO and its elementary properties:syntax,
models, logical consequence, derivations, some minor results.
Some
fundamental theorems of FO:soundness,
completeness, compactness, Lowenheim-Skolem, nonstandard models of
arithmetic.
In terms of reading, we will cover, in
order, the following sections: 1, 2.2., 3.2, 4, 6.1, 7.3, 8.2, 9.
Time permitting, we
may briefly investigate something in the following areas:
Applications of
FO:Ramsey’s theorem, rational
comparison, some theorems of graph theory,
Model theory:Some basic concepts, methods of ultraproducts,
Los’s theorem, interpretations, Ehrenfeucht-Fraïssé games,
finite model theory.
Modal logic:Soundness, completeness and the finite model
property for a variety of well-known systems, the finite model property
for any modal sentence.
Background.The course sequence LPS/Phil
105/205 A, B, C
constitutes a single survey of mathematical logic.Although Part A will be useful in this course, we will not
develop or assume many of its finer details.However, it will be important that you have or quickly develop
an
ability to engage in mathematical reasoning. Also,
although it is not a prerequisite, students sometimes find it
useful to consult an introductory logic textbook.There
are a great many such books and many of them are
acceptable.Two of them are M.
Bergmann, J. Moor, J. Nelson: The Logic Book, McGraw-Hill,
third
edition, New York 1998, and I. Copi
and C. Cohen, Introduction to logic, 10th ed. Upper Saddle
River, NJ : Prentice Hall,
c1998.
Studying.Acquiring skill
with logic requires more practice than rote memorization of facts.In addition to reading the relevant chapters
of the textbook, you need to do the exercises in the chapters and/or
the
problems discussed in class.Please be
wary of thinking you have studied logic if you've only attended class
and done
the required reading.Moreover, the
material in this course accumulates:the concepts discussed at the very beginning will be with us
until the
very end of the course.It is strongly
recommended that you take steps
to ensure that you do not get behind. You
should be able to do all the problems at the end of each section that
we cover.
Grading.
Your
grade for the course will be based on a
1000
point scale. During the term, there will be several (at least three)
mandatory homework
assignments, and there will be a comprehensive final examination. (Note
that the final is scheduled for Tuesday, March 21, 10:30 - 12:30pm.)
Collectively, the homeworks will be worth 650 points, and the final
will
be worth 350 points. If there are quizzes, the point-value for them
will be added to the previous points, and the total will be normalized
to a 1000-point scale. Letter grades for the course will be determined
as follows:
900 = A
850 = B+
800 = B
750 = C+
700 = C
650 = D+
600 = D
below 600 = F
#1: k should be restricted to being less than or equal to
1, as well as less than or equal to n. (Many thanks to Eric and Kendra
for spotting this!)
#2: Add the negation of the sentence in question to Gamma,
then take any finite subset of the resulting set. Use the linear
structure present in the first omega conditionals in Gamma to show that
the finite subset is consistent. [Hint:
since the set is finite, there must be at least one conditional
missing. Assign all sentence letters occurring in earlier conditionals
the value True, and all those in later conditionals the value False.]
Now use the compactness theorem and argue for the denial of the
statement in question.
Homework
1
#3: Please interpret this question as retaining the
original
rule for the formation of conditionals, and replacing the rule for
negation
with the new one. (Ie, don't interpret it as altering both the rules
for
conditionals and negation.)
At this point, you should be able to do questions 1, 2, 3,
5, and 8. After tomorrow, you should be able to also do: 6, 7, and
probably 9.After tuesday, you should be able to do: 4
If for some reason, we have not covered the requisite
material in time, the due date will be extended. (Fortunately, though,
question
4 is quite easy!)
For the extra credit question, consider the boolean
function
that takes two arguments and which assigns True to an odd number of the
four
possible inputs. Prove by induction that the new set of logical
connectives
only represents those functions that yield an even number of Trues to
the four
possible inputs.
