# Math 3325 – Introduction to Discrete mathematics

## Fundamental Concepts of Mathematics

Three credits. Three hours of lecture per week. Prerequisite: MATH 3018 or permission.

Elementary set theory and methods of proof. Elementary properties of the natural numbers. Even, odd, prime and composite numbers. Unique factorization theorem. Well ordering property of the natural numbers. Division algorithm. Euclid’s algorithm and the greatest common factor (gcf). The gcf of two integers as an integer linear combination of the integers. Mathematical induction. Relations and functions. Composition of functions. Injections, surjections and bijections. Inverse functions. The definition of a finite set and its cardinality. Permutations and sequences. Elementary combinatorics. The binomial theorem. The pigeonhole principle. Binary relations and directed graphs. Equivalence and partial order relations on a set.

## Objectives

This course is intended to provide an introduction to the conceptual basis underlying high school mathematics. Emphasis will be placed on the in-depth understanding of fundamental mathematical ideas and the associated modes of reasoning and proof rather than on superficial coverage of many topics. The course will also help bridge the conceptual gap between the pre-calculus/calculus sequence and more advanced courses in mathematics by fostering the mathematical maturity necessary for success in those courses. Specific course objectives can be found here.

## Syllabus: Semester II, 2011-12

1. Introduction to proof (4 hours)
1. Valid and invalid arguments.
2. Direct proofs and counterexamples.
3. Argument by contradiction and contraposition.
4. Proof by dichotomy
2. Introduction to Set Theory (4 hours)
1. Some axioms of set theory.
2. Set operations and their algebraic properties.
3. Mathematical induction (6 hours)
1. Principle of mathematical induction.
2. Examples of proofs by mathematical induction:
• The sum of an arithmetic progression
• The sum of a geometric progression.
• The towers of Hanoi.
4. The Integers and their properties. (10 hours)
1. Even and odd integers.
2. Prime and composite numbers. Divisibility.
3. The unique factorization theorem.
4. Well ordering property of the natural numbers.
5. The division algorithm.
6. Euclid’s algorithm.
7. Greatest common factors and least common multiples.
8. The greatest common factor of two integers as an integer linear combination of the integers.
5. Relations and functions. (6 hours)
1. The definition of a binary relation.
2. The definition of a function, domain, codomain and graph.
3. Composition of functions.
4. Injections, surjections and bijections.
5. Inverse functions.
6. Examples of functions.
• Permutations.
• Sequences.
• Elementary functions for calculus.
6. Elementary combinatorics. (13 hours)
1. The definition of cardinality for finite sets.
2. The pigeonhole principle and applications.
3. The disjoint union of sets and its cardinality.
4. The cardinality of the union of two sets.
5. The inclusion–exclusion principle.
6. Counting of special sets
• The number of subsets of a finite set.
• The number of subsets of a given size in a finite set.
• Pascals identity.
• The binomial theorem.
• The number of bipartitions of a finite set.
• The number of permutations.
• The number of bijections between finite sets.
• The number of functions with finite domain and codomain.
• The number of injective functions with finite domain and codomain.
7. Binary relations and directed graphs (4 hours)
1. Pre-order relations
2. Equivalence relations.
3. Partial order and total order relations.
4. The equivalence relation associated with a pre-order and the corresponding order induced on the set of equivalence classes

## Texts

1. Eccles Introduction to Mathematical Reasoning, Cambridge University Press, 1997.
2. Stewart and Tall, Foundations of Mathematics, Oxford University Press

## Bibliography

1. Matousek and Nesetril, Invitation to Discrete Mathematics, Oxford University Press, 1998.
2. Sussana S. Epp, Discrete Mathematics with Applications, Second edition, Wadsworth Publishing Company, Belmont, 1995. ISBN 0-534-94446-9.
3. Norman L. Biggs, Discrete Mathematics, Oxford University Press, 1995. ISBN 0-198-53477-2.
4. D. Burghes et al, Center for Innovation in Mathematics Teaching, University of Exeter.
Discrete Mathematics, Heinemann, 1994. ISBN 0-435-51608-6.
5. R. F. Lax Modern Algebra and Discrete Structures, R. F. Lax, Harper Collins, 1991, ISBN0-060-43878-9

### Evaluation

Grade will be based upon 4 exams.