Links to an external site. with a minimum grade of C.

Course Objectives: The student will learn the basics of formal logic and computability, up to and including the Goedel’s incompleteness theorems.

Textbook: Set theory and foundations of mathematics an introduction to mathematical logic. Volume II, Foundations of mathematics 

Links to an external site.

The link is to a multi-user textbook available in UF library. There are many other textbooks covering the same material, but the approach may be different enough to confuse a student.

Presentation project. Every student should prepare a project for presentation in class. The presentation should take 30-50 minutes; the presentation date will be negotiated individually. It is expected that the presenter discusses the topic with the instructor beforehand. A list of suggested presentation topics:

1. Hilbert (or Lukasiewicz) system. This is one possible way of setting up propositional and predicate logic, somewhat different from the natural deduction system we will use in class. (relevant to Chapter 2 and 3)
2. Modal logic. There are in fact several different modal logics. They can be viewed as propositional logic enriched by unary operators often verbalized as “it is possible that” and “necessarily”, and some axioms for them.  (Chapter 2)
3. Tarski–Seidenberg theorem on the decidability of the real numbers. This remarkable theorem says that there is an algorithm for deciding whether a given predicate sentence using addition and multiplication is true or false in real numbers. (Chapter 4)
4. Pressburger Arithmetic. This is the fragment of Peano Arithmetic which does not use multiplication. Unlike the full PA, it is complete and decidable: every sentence in its language can be either proved or disproved from its axioms. (Chapter 4)
5. Primitive recursion and Ackermann function. Primitive recursive functions form a natural subclass of computable functions. Ackermann function is the most famous example of a computable function which is not primitive recursive. (Chapter 6)
6. Busy beaver and zero jump. One way of producing a non-computable function is the busy beaver “game”–the task of designing a Turing machine on a given number of states which runs for as long as possible and then stops. (Chapter 6)
7. Sentences unprovable in Peano Arithmetic. Goedel’s incompleteness theorem tells us that there are true arithmetic sentences which are unprovable in PA. There are many such sentences which have concrete mathematical content. The presenter should select an example, explain its meaning and roughly why it is unprovable. (Chapter 7)
8. Provability logic. This is a modal logic in which the square symbol is interpreted as “it is provable that”. A theorem of Solovay shows that a sentence is a theorem in provability logic if and only if all of its instances are provable in Peano Arithmetic. This makes it possible to give a very brief proof of second Goedel’s incompleteness theorem. (this is the most challenging project) (Chapter 7)

 

Grading: There will be five take-home assignments, with an option to return an improved solution after the first round of grading. Each will be worth 20 points. Each student should select and present a project; this is worth 20 points as well. There is no other basis for the grade. The total grade will be figured according to the standard flat curve: A above 93%, A- 90-92%, B+ 87-89%, B 83-86%, B- 80-82%, C+ 77-79%, C 73-76%, C- 70-72%, D+ 67-69%, D 63-66%, D- 60-62 %, E, I, NG, WF 59%.

Provisional timeline of the course: The assignments will be due September 6, September 27, October 25, November 8, and December 6 in turn, always at 11:30pm. (These are all Fridays. ) They will cover Chapters 2, 3, 4, 6, 7 of the textbook respectively.

Diversity, equity, and inclusion statement. It is my intent that students from all diverse backgrounds and perspectives be well served by this course, that students’ learning needs be addressed both in and out of class, and that the diversity that students bring to this class be viewed as a resource, strength, and benefit. It is my intent to present materials and activities that are respectful of diversity: gender, sexuality, disability, age, socioeconomic status, ethnicity, race, religion, and culture. Your suggestions are encouraged and appreciated. Please let me know ways to improve the effectiveness of the course for you personally or for other students or student groups. In particular, I will gladly honor your request to address you by an alternate/ preferred name or gender pronoun. Please advise me of this preference early in the semester so I may make appropriate changes to our records.

Honor code. UF students are bound by The Honor Pledge which states, “We, the members of the University of Florida community, pledge to hold ourselves and our peers to the highest standards of honor and integrity by abiding by the Honor Code. On all work submitted for credit by students at the University of Florida, the following pledge is either required or implied: “On my honor, I have neither given nor received unauthorized aid in doing this assignment.” The Honor Code specifies a number of behaviors that are in violation of this code and the possible sanctions. Click here to read the Honor Code. Links to an external site.Furthermore, you are obligated to report any condition that facilitates academic misconduct to appropriate personnel. If you have any questions or concerns, please consult with the instructor  in this class.

Class attendance. Requirements for class attendance and make-up exams, assignments, and other work in this course are consistent with university policies. Click here to read the university attendance policies.Links to an external site.

Accommodations for students with disabilities. Students with disabilities who experience learning barriers and would like to request academic accommodations should connect with the disability Resource Center. Click here to get started with the Disability Resource Center. Links to an external site.It is important for students to share their accommodation letter with their instructor and discuss their access needs, as early as possible in the semester.

Online evaluations. Students are expected to provide professional and respectful feedback on the quality of instruction in this course by completing course evaluations online via GatorEvals. Click here for guidance on how to give feedback in a professional and respectful manner. Links to an external site.Students will be notified when the evaluation period opens, and can complete evaluations through the email they receive from GatorEvals, in their Canvas course menu under GatorEvals, or via ufl.bluera.com/ufl/.  Links to an external site.Summaries of course evaluation results are available to students here.Links to an external site.

Complaints. The official UF policy for filing a complaint about the course may be found here.

Health and wellness. U Matter, We Care: If you or someone you know is in distress, please contact umatter@ufl.edu, 352-392-1575, or visit U Matter, We Care website Links to an external site.to refer or report a concern and a team member will reach out to the student in distress.

Counseling and Wellness Center: Visit the Counseling and Wellness Center website Links to an external site.or call 352-392-1575 for information on crisis services as well as non-crisis services.

Student Health Care Center: Call 352-392-1161 for 24/7 information to help you find the care you need, or visit the Student Health Care Center website Links to an external site..

University Police Department: Visit UF Police Department website Links to an external site.or call 352-392-1111 (or 9-1-1 for emergencies).

UF Health Shands Emergency Room / Trauma Center: For immediate medical care call 352-733-0111 or go to the emergency room at 1515 SW Archer Road,

Gainesville, FL 32608; Visit the UF Health Emergency Room and Trauma Center websiteLinks to an external site.

Academic resources. E-learning technical support: Contact the UF Computing Help Desk  Links to an external site.at 352-392-4357 or via e-mail at helpdesk@ufl.edu.

Career Connections Center Links to an external site.: Reitz Union Suite 1300, 352-392-1601. Career assistance and counseling services.

Library Support Links to an external site.: Various ways to receive assistance with respect to using the libraries or finding resources.

Teaching Center Links to an external site.: Broward Hall, 352-392-2010 or to make an appointment 352- 392-6420. General study skills and tutoring.

Writing Studio: 2215 Turlington Hall, 352-846-1138. Help brainstorming, formatting, and writing papers.

Student Complaints On-Campus: Visit the Student Honor Code and Student Conduct Code webpage for more information Links to an external site..

On-Line Students Complaints: View the Distance Learning Student Complaint Process Links to an external site..