Completeness and Undecidability

Subject PHIL30043 (2011)

Note: This is an archived Handbook entry from 2011.

Credit Points: 12.50
Level: 3 (Undergraduate)
Dates & Locations:

This subject is not offered in 2011.

Time Commitment: Contact Hours: 3 (1 x 2 hour lecture per week and 1 x 1 hour tutorial in weeks 2 to 12)
Total Time Commitment: An average of 8.5 hours per week.
Prerequisites: None.
Corequisites: None.
Recommended Background Knowledge: Completion of at least one of the following is recommended:
Subject
Study Period Commencement:
Credit Points:
Not offered in 2011
12.50
Not offered in 2011
12.50
Non Allowed Subjects: Students who have completed 161-241 or 672-363 (Logic: Completeness or Incompleteness) are not permitted to enrol in this subject.
Core Participation Requirements: For the purposes of considering request for Reasonable Adjustments under the disability Standards for Education (Cwth 2005), and Students Experiencing Academic Disadvantage Policy, academic requirements for this subject are articulated in the Subject Description, Subject Objectives, Generic Skills and Assessment Requirements of this entry.The University is dedicated to provide support to those with special requirements. Further details on the disability support scheme can be found at the Disability Liaison Unit website: http://www.services.unimelb.edu.au/disability/
Subject Overview:

This subject deals with the power and limits of formal logic. It covers topics in logic beyond what is covered in an introduction, such as the completeness and undecidability of first-order logic, and the boundary between the computable and the uncomputable. The course finishes with an elaboration of Godel's incompleteness theorem, and a discussion of its consequences. Concepts and results will be approached via both practical experience with formal techniques and theoretical reflection on those techniques, enabling students to appreciate the philosophical importance of the major logical results and equipping them for further work in logic in philosophy, mathematics, linguistics, computer science and other related fields.

Objectives:

Students who sucessfully complete this class should:

  • develop an overview of core features of formal logic, its scope and its limits.
  • demonstrate an ability to prove results in and about formal logics.
  • develop a command of the connections between proof, computation, decidability, incompleteness and completeness.
  • critically reflect on the strengths and weaknesses of formal logic and its appropriateness for different applications.
Assessment: Tutorial exercises 50% (throughout semester), and a 2 hr written examination (not open-book) 50% (end of semester). This subject has a minimum hurdle requirement of 75% tutorial attendance. Regular participation in tutorials is required. Assessment submitted late without an approved extension will be penalised at 10% per day. In-class tasks missed without approval will not be marked. All pieces of written work must be submitted to pass this subject.
Prescribed Texts:

To be advised.

Breadth Options:

This subject potentially can be taken as a breadth subject component for the following courses:

You should visit learn more about breadth subjects and read the breadth requirements for your degree, and should discuss your choice with your student adviser, before deciding on your subjects.

Fees Information: Subject EFTSL, Level, Discipline & Census Date
Generic Skills:

Students who successfully complete this subject will hone the following skills:

  • Critical, creative thinking.
  • Persuasive and balanced assessment.
  • Reading with attention to detail.
  • Analysis and clarification of unclear concepts.
  • Simplicity and precision in written and oral presentations.
  • Rigorous reasoning about fundamental issues.
Links to further information: http://www.philosophy.unimelb.edu.au/
Related Majors/Minors/Specialisations: History and Philosophy of Science
History and Philosophy of Science
History and Philosophy of Science Major
Philosophy
Philosophy
Philosophy
Philosophy Major
Related Breadth Track(s): Language, Mind && Logic

Download PDF version.