A Bridge to Higher Mathematics

Valentin Deaconu, Donald C. Pfaff

• Publisher: Chapman and Hall/CRC
• Year: 2016
• Print ISBN: 9781138441637
• eBook ISBN: 9781498775274
• Topic: Mathematics
• Subtopic: Applied Mathematics
• Index: Mathematics

A Bridge to Higher Mathematics is more than simply another book to aid the transition to advanced mathematics. The authors intend to assist students in developing a deeper understanding of mathematics and mathematical thought.

The only way to understand mathematics is by doing mathematics. The reader will learn the language of axioms and theorems and will write convincing and cogent proofs using quantifiers. Students will solve many puzzles and encounter some mysteries and challenging problems.

The emphasis is on proof. To progress towards mathematical maturity, it is necessary to be trained in two aspects: the ability to read and understand a proof and the ability to write a proof.

The journey begins with elements of logic and techniques of proof, then with elementary set theory, relations and functions. Peano axioms for positive integers and for natural numbers follow, in particular mathematical and other forms of induction. Next is the construction of integers including some elementary number theory. The notions of finite and infinite sets, cardinality of counting techniques and combinatorics illustrate more techniques of proof.

For more advanced readers, the text concludes with sets of rational numbers, the set of reals and the set of complex numbers. Topics, like Zorn's lemma and the axiom of choice are included. More challenging problems are marked with a star.

All these materials are optional, depending on the instructor and the goals of the course.

1

Elements of logic

Logic is the systematic study of the form of valid arguments. Valid arguments are important not just in mathematics, but also in computer science, artificial intelligence or in everyday life.

In this chapter we introduce mathematical statements and logical operations between them like negation, disjunction and conjunction. We construct truth tables and determine when two statements are equivalent, in preparation for making meaningful judgments and writing correct proofs. We introduce new symbols, like the universal quantifier ∀ and the existential quantifier ∃, and learn how to negate statements involving quantifiers. Quantifiers will be used throughout the book.

1.1 True and false statements

We can use words and symbols to make meaningful sentences, also called statements. For example:

a) Mary snores.

b) A healthy warthog has four legs.

c) 2 + 3 = 5.

d) x + 5 = 7.

e) ∫0π sin xdx=2

f) ∀x ∈ ℝ ∃ y ∈ ℝ such that y² = x.

g) x/x = 1.

h) 3 ∈ [1, 2).

i) Dr. Pfaff is the president of the United States.

Some of these statements have eccentric formats, using symbols that you may not have seen before. By the way, ∀ means for all, ∈ means belongs to (or is an element of) and ∃ means there exists. The symbol ∀ is also called the universal quantifier, and the symbol ∃ is called the existential quantifier.

The statements could be true, like statements b, c, e; could be false, like statements f, h, i; or could be neither true nor false, like statements a, d, g. The last possibility occurs because we don’t have enough information. For statement a, we could ask: which Mary are we talking about? Is she snoring now or in general? For statement d, do we know that x = 2? For statement g, do we know x to be a nonzero number? We don’t, and these kind of ambiguous statements (neither true nor false) also appear in real life.

To make things easier, let’s agree that a proposition is a statement which is either true or false. Each proposition has a truth value denoted T for true or F for false. All statements b, c, e, f, h, i are propositions, but a, d, g are not. We can modify statements d and g as

d’) ∀x : x + 5 = 7 and

g’) ∃x : x/x = 1,

which become propositions. Of course, the proposition d’ is false since, for example, 1 + 5 ≠ 7 and the proposition g’ is true because we can take x = 2 and 2/2 = 1.

1.2 Logical connectives and truth tables

It is important to understand the meaning of key words that will be used throughout mathematics. Primary words which must be clarified are the logical terms “not”, “and”, “or”, “if...then”, and “if and only if”. The word “and” is used to combine two sentences to form a new sentence which is always different from the original ones. For example, combining sentences c and h above we get

2 + 3 = 5 and 3 ∈ [1, 2),

which is false, since 3 does not belong to the interval [1, 2). The meaning of this compound sentence can be determined in a straightforward way from the meanings of its component parts. Similar remarks hold for the other basic logical terms, also called connectives. We will think of the above basic logical terms as operations on sentences. Though there are linguistic conventions which dictate the proper form of a correctly constructed sentence, we will find it convenient to write all our compound sentences in a manner reminiscent of algebra and arithmetic. Thus, irrespective of where the word “not” should appear in a sentence, in order to placate the grammarians, we will write it sometimes at the beginning. For example, though a grammar book would tell us that “not Dr. Pfaff is the president of the United States” is improper usage, and that the correct way is to write “Dr. Pfaff is not the president of the United States”, it will prove easier for us to work with the first form. We regard the two as the same for our purposes.

We will use the following symbolic notation.

Definition 1.1. The negation of a statement P is denoted by ¬P, verbalized as “it is not the case that P” or just “not P”.

The operation of negation always reverses the truth value of a sentence. We summarize this in this truth table:

P	¬P
T	F
F	T

Recall that T stands for true and F for false.

Definition 1.2. We write P ∧ Q for “P and Q”, the conjunction of two sentences. This is true precisely when both of the constituent parts are correct, but false otherwise.

This is in line with normal everyday usage of the word “and”. Nobody would deny that I am telling the truth if I say

(2 + 2 = 4) ∧ (3 + 3 = 6),

nor would anyone hesitate to call me a liar if I boldly announced that

(2 + 2 = 4) ∧ (3 + 3 = 5).

Her...

Table of contents

• Cover
• Half Title
• Title Page
• Copyright Page
• Contents
• Preface
• 1 Elements of logic
• 2 Proofs: Structures and strategies
• 3 Elementary theory of sets
• 4 Functions
• 5 Relations
• 6 Axiomatic theory of positive integers
• 7 Elementary number theory
• 8 Cardinality: Finite sets, infinite sets
• 9 Counting techniques and combinatorics
• 10 The construction of integers and rationals
• 11 The construction of real and complex numbers
• Bibliography
• Answers to select exercises
• Index