237 – Dr. Michelle Williams

What is Mathematical Thinking?

Mathematical thinking is the use of logic, definitions, patterns, relationships, and proof to understand mathematical ideas. In discrete mathematics, the goal is often not simply to calculate an answer, but to explain why a statement is true or false.

A useful approach: Understand the definitions → identify what is known → choose a strategy → work logically → justify each step → check the conclusion.

2. Proof Techniques

A mathematical proof is a logical argument showing that a statement follows from definitions, known facts, and previously established results.

Direct Proof

To prove an implication $p \to q$ , assume $p$ is true and show that $q$ follows.

Example: Prove that the sum of two even integers is even.

Step 1: Let the even integers be

2 m

and

2 n

Step 2: Add them.

2 m + 2 n = 2 (m + n)

Step 3: Since

m + n

is an integer,

2 (m + n)

is even.

Conclusion: The sum of two even integers is even.

Proof by Contrapositive

Instead of proving $p \to q$ , prove its logically equivalent contrapositive:

\neg q \to \neg p

Proof by Contradiction

Assume the statement to be proved is false and show that this assumption leads to a contradiction.

Proof by Cases

Divide the problem into cases that cover all possible situations, then prove the statement in each case.

Mathematical Induction

Induction is commonly used to prove statements about positive integers.

1. Base case: Show the statement is true for the first value.

2. Inductive hypothesis: Assume it is true for

n = k

3. Inductive step: Show it is then true for

n = k + 1

Example: Show the first

n

positive integers have sum

1 + 2 + \dots + n = \frac{n (n + 1)}{2}

The base case $n = 1$ gives $1 = 1$ . The inductive step assumes the formula for $k$ , adds $k + 1$ , and simplifies to the formula for $k + 1$ .

Practice: Which proof method would be especially appropriate for a statement involving all positive integers and a formula containing

n

Mathematical induction.

3. Sets

A set is a well-defined collection of distinct objects called elements.

A = {1,2,3,4}

Basic Set Operations

Operation	Symbol	Meaning
Union	$A \cup B$	Elements in $A$ , $B$ , or both
Intersection	$A \cap B$	Elements common to both
Difference	$A - B$	Elements in $A$ but not $B$
Complement	$A^{c}$	Elements outside $A$ in the universal set
Subset	$A \subseteq B$	Every element of $A$ is in $B$

Let

A = {1,2,3,4}

and

B = {3,4,5,6}

A \cup B = {1,2,3,4,5,6}

A \cap B = {3,4}

A - B = {1,2}

Practice: Let

A = {2,4,6,8}

and

B = {1,2,3,4}

. Find

A \cap B

{2,4}

4. The Integers and Modular Arithmetic

The integers are the numbers

ℤ = {\dots, - 3, - 2, - 1,0,1,2,3, \dots}

Divisibility

We say $a$ divides $b$ , written $a | b$ , if there is an integer $k$ such that

b = a k

Modular Arithmetic

Two integers $a$ and $b$ are congruent modulo $n$ when $n$ divides their difference:

a \equiv b (\mod n) ⟺ n | (a - b)

Example:

17 \equiv 5 (\mod 12)

because $17 - 5 = 12$ , which is divisible by 12.

Working with Remainders

29 \equiv 5 (\mod 12)

because $29 = 12 (2) + 5$ .

Practice: Is

38 \equiv 2 (\mod 12)

Yes.

38 - 2 = 36

, and

12 | 36

5. Relations

A relation describes a connection between elements of sets. A relation from $A$ to $B$ can be represented using ordered pairs.

Properties of Relations

Property	Condition
Reflexive	$a R a$ for every $a$
Symmetric	If $a R b$ , then $b R a$
Antisymmetric	If $a R b$ and $b R a$ , then $a = b$
Transitive	If $a R b$ and $b R c$ , then $a R c$

Equivalence Relations

A relation is an equivalence relation when it is reflexive, symmetric, and transitive.

For equality,

=

, we have:

a = a

a = b \Rightarrow b = a

a = b, b = c \Rightarrow a = c

Thus equality is an equivalence relation.

Practice: Is the relation "has the same remainder when divided by 3" an equivalence relation on the integers?

Yes. Congruence modulo 3 is reflexive, symmetric, and transitive.

6. Functions

A function assigns exactly one output to every element in its domain.

f : A \to B

Domain and Range

The domain is the set of allowed inputs. The range is the set of outputs produced by the function.

Types of Functions

Type	Description
Injective	Different inputs have different outputs.
Surjective	Every element of the codomain is an output.
Bijective	Both injective and surjective.

Example: Consider

f (x) = 2 x + 1

on the real numbers. If

f (a) = f (b)

, then

2 a + 1 = 2 b + 1

2 a = 2 b

a = b

Therefore $f$ is injective.

Composition

(f \circ g) (x) = f (g (x))

Practice: If

f (x) = x + 2

and

g (x) = 3 x

, find

(f \circ g) (x)

(f \circ g) (x) = f (3 x) = 3 x + 2

7. Cardinality

The cardinality of a set describes its size. For a finite set, cardinality is simply the number of elements in the set.

| {a, b, c, d} | = 4

Two sets have the same cardinality when there is a bijection between them. This idea becomes especially important when studying infinite sets.

The sets

{1,2,3} and {a, b, c}

have the same cardinality because a bijection can pair each element of the first set with exactly one element of the second.

Practice: What is the cardinality of

A = {2,4,6,8,10,12}

| A | = 6

8. Countable and Uncountable Sets

An infinite set is countably infinite if its elements can be placed in a one-to-one correspondence with the positive integers.

Examples of Countable Sets

The positive integers $ℕ$
The integers $ℤ$
The rational numbers $ℚ$

Although the integers are infinite, they can be listed:

0,1, - 1,2, - 2,3, - 3, \dots

This shows that the integers can be put into correspondence with the natural numbers.

Uncountable Sets

The real numbers $ℝ$ are uncountable. There is no list that contains every real number in an interval such as $(0,1)$ .

Cantor's Diagonal Idea

Suppose every real number between 0 and 1 were listed. Cantor's diagonal argument constructs a new number by changing selected digits of the listed numbers. The new number differs from the first number in one digit, from the second in another digit, and so on. Therefore it cannot appear anywhere on the list.

Key conclusion:

| ℕ | < | ℝ |

The natural numbers are countably infinite, while the real numbers are uncountable. Thus not all infinite sets have the same cardinality.

Practice: Which of the following is uncountable:

ℕ

ℤ

ℚ

, or

ℝ

ℝ

, the real numbers, are uncountable.

Mixed Practice Problems

Problem 1: Determine whether

p \to q

is true when

p

is false and

q

is false.

True. An implication is false only when

p

is true and

q

is false.

Problem 2: Prove that the sum of two odd integers is even.

Let the integers be

2 m + 1

and

2 n + 1

. Their sum is

2 m + 1 + 2 n + 1 = 2 (m + n + 1)

, which is even.

Problem 3: Let

A = {1,2,3,4}

and

B = {3,4,5,6}

. Find

A \cup B

and

A \cap B

A \cup B = {1,2,3,4,5,6}

and

A \cap B = {3,4}

Problem 4: Find

23 mod 7

23 \equiv 2 (\mod 7)

Problem 5: Is the function

f (x) = x^{2}

from

ℝ

ℝ

injective?

No. For example,

f (2) = f (- 2) = 4

, even though

2 \neq - 2

Problem 6: Are the integers countable or uncountable?

The integers are countably infinite.

Challenge Problems

Prove that the sum of two odd integers is even using a direct proof.
Prove a simple divisibility statement using the contrapositive.
Use mathematical induction to prove a formula for a finite sum.
Show that congruence modulo $n$ is an equivalence relation.
Determine whether a given function is injective, surjective, both, or neither.
Construct a bijection between two finite sets of the same cardinality.
Explain why the integers can be listed even though there are infinitely many of them.
Explain, in your own words, why Cantor's diagonal argument shows that the real numbers are uncountable.

Key Ideas to Remember

Logic provides the foundation for mathematical reasoning.
A proof explains why a mathematical statement must be true.
Sets provide a way to organize and describe mathematical objects.
Modular arithmetic studies remainders and congruence.
Relations describe connections between elements.
Functions assign exactly one output to each input in their domain.
Cardinality measures the size of a set, including infinite sets.
Some infinite sets are countable, while others, such as the real numbers, are uncountable.