MC144 Proof and Logical Structures

Course Description

The key idea in the course is that the structure of a proof is largely dictated by the structure of the assertion, the validity of which the proof is intended to establish. For example, a proof which establishes an assertion of the form, ``If condition A, then condition B.'', has a natural structure: the usual proof starts by assuming condition A to be true, and finishes by deducing condition B. The course introduces various proof strategies, with each proof strategy corresponding to a particular assertion format.

Naturally, the course cannot be simply about proofs: proofs have to be about something. The subject matter for the example proofs is drawn from the topics of sets, relations and functions, which are the foundational concepts that make up the language of mathematics.

Aims

• to introduce the idea of mathematical proof and the indisputable nature of a correct proof;
• to give experience of writing simple proofs and to teach the proper use of mathematical notation;
• to introduce the language of mathematics through the concepts of sets, relations and functions.

Objectives

• To familiarise the student with the foundational concepts of mathematics.
• To emphasise the importance of precise unambigous language.
• To make explicit the relationship between the structure of a (true) assertion and the structure of a proof of the assertion.

Transferable Skills

• The ability to write clearly and to think within a logical framework.
• The understanding of proof strategies and the ability to construct proofs.

Syllabus

The idea of mathematical proof and the indisputable nature of a correct proof. Examples of proofs. Statements. The logical connectives , &, , , .The symbols , . Statements containing unknowns. Obtaining negations of statements. Counterexamples. Proof by contradiction. Proof by exhaustive case analysis. Proof via the contrapositive. Existence and uniqueness proofs. Axioms. Definitions. Meaning of `well-defined'.

SET THEORY

Informal notion of a set, membership, empty set, finite sets, the set of natural numbers, subsets identified by a statement with a single unknown, equality of sets, unions, powerset, families indexed by a set. Ordered pair, Cartesian product, intersections, set-theoretic difference, size of finite set, the integers, the rationals (informally), the reals (informally).

RELATIONS

Definition as subset of A². Reflexive, symmetric, transitive, equivalence relations. Set of equivalence classes. Partitions. Proof that set of equivalence classes isa partition. Construction of examples with given properties.

FUNCTIONS

Definition as black box process satisfying three conditions. Domain, range. Notation: f(x), f(X), . Equality of functions. Injections, surjections, bijections. Composition of functions. Injections/surjections/bijections compose. Identity functions, inverse functions. Existence of inverse if and only if bijection. Construction of examples with given properties.

PROPERTIES OF THE NATURAL NUMBERS AND PROOF BY INDUCTION

Well-ordering axiom for the natural numbers. Proof by induction/minimal counterexample. Examples: the positive integer exponent case of binomial theorem; all positive integers may be written as product of primes. Notation: , , factorials.

Reading list

Recommended:

P.J. Eccles, An Introduction to Mathematical Reasoning, Cambridge University Press.

Background:

N. L. Biggs, Discrete Mathematics, Oxford University Press.

P. M. Cohn, Algebra I, John Wiley.

D. Driscoll Schwartz, Conjecture and proof, Harcourt Brace.

S. Galovich, Doing Mathematics, Harcourt Brace.

R. Garnier and J. Taylor, 100% Mathematical Proof, John Wiley.

A. G. Hamilton, Numbers, Sets and Axioms, Cambridge University Press.

G. Pólya, How to Solve It, Penguin.

D. Solow, How to Read and Do Proofs

I. Stewart and D. Tall, The Foundations of Mathematics, Oxford University Press.

D. J. Velleman, How to Prove It, Cambridge University Press.

Details of Assessment