Math 344- Mathematical Reasoning

What Is Mathematical Reasoning?

Mathematical reasoning is the practice of making statements precise and justifying them with proof. The topics here build on each other: logic gives the rules, proof techniques apply them, sets, relations, and functions supply the language, cardinality measures size, and group theory studies structure.

A useful approach: Restate the claim precisely → identify hypotheses and conclusion → choose a proof technique → write each step with a reason → check that the conclusion is what was asked.

1. Logical Reasoning

A proposition is a statement that is true or false. Propositions are combined with connectives, and their truth is determined by truth tables.

Connective	Symbol	Meaning
Negation	$\neg p$	“not $p$ ”
Conjunction	$p \land q$	true only when both are true
Disjunction	$p \lor q$	true when at least one is true
Implication	$p \to q$	false only when $p$ is true and $q$ is false
Biconditional	$p \leftrightarrow q$	true when $p$ and $q$ have the same truth value

Key Equivalences

p \to q \equiv \neg p \lor q \equiv \neg q \to \neg p (contrapositive)

\neg (p \land q) \equiv \neg p \lor \neg q \cdot \neg (p \lor q) \equiv \neg p \land \neg q (De Morgan)

Quantifiers

\forall x P (x)

means “for all

x

P (x)

”.

\exists x P (x)

means “there exists an

x

with

P (x)

”. To negate, flip each quantifier and negate the predicate:

\neg \forall x P (x) \equiv \exists x \neg P (x)

and

\neg \exists x P (x) \equiv \forall x \neg P (x)

Example: Negate “For every

ε > 0

there exists

δ > 0

such that

| x | < δ

implies

| f (x) | < ε

.”

Step 1: Write it symbolically.

\forall ε \exists δ \forall x (| x | < δ \to | f (x) | < ε)

Step 2: Flip quantifiers and negate the implication, using

\neg (p \to q) \equiv p \land \neg q

\exists ε \forall δ \exists x (| x | < δ \land | f (x) | \geq ε)

Conclusion: There is some $ε > 0$ such that for every $δ > 0$ some $x$ with $| x | < δ$ has $| f (x) | \geq ε$ .

An implication with a false hypothesis is always true (vacuously). “If

2 = 3

then the moon is cheese” is a true statement.

Practice: Write the contrapositive and the negation of “If

n^{2}

is even, then

n

is even.”

Contrapositive: if

n

is odd, then

n^{2}

is odd. Negation:

n^{2}

is even and

n

is odd.

Practice: Is

(p \to q) \land (q \to r) \to (p \to r)

a tautology?

Yes. It fails only if

p

is true and

r

is false; then either

q

is true (so

q \to r

is false) or

q

is false (so

p \to q

is false). Either way the hypothesis fails. This is the hypothetical syllogism.

2. Proof Techniques

Technique	Idea	Use When
Direct proof	Assume $p$ , derive $q$ step by step	Hypotheses give something to compute with
Contrapositive	Assume $\neg q$ , derive $\neg p$	The conclusion is easier to negate than to build
Contradiction	Assume the claim is false and reach an absurdity	Proving non-existence or irrationality
Cases	Split into exhaustive cases and prove each	Parity, signs, residues
Induction	Prove a base case and $P (k) \to P (k + 1)$	Statements about all $n \geq n_{0}$
Counterexample	Exhibit one case where it fails	Disproving a “for all” claim

Example (induction): Prove that

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

for all

n \geq 1

Step 1 (base): For

n = 1

, the left side is

1

and the right side is

\frac{1 \cdot 2}{2} = 1

Step 2 (hypothesis): Assume

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

Step 3 (step): Add

k + 1

to both sides.

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

Conclusion: This is the formula for $n = k + 1$ , so it holds for all $n \geq 1$ .

Example (contradiction):

\sqrt{2}

is irrational.

Step 1: Suppose

\sqrt{2} = \frac{a}{b}

in lowest terms. Then

a^{2} = 2 b^{2}

, so

a^{2}

is even, hence

a

is even, say

a = 2 c

Step 2: Then

4 c^{2} = 2 b^{2}

, so

b^{2} = 2 c^{2}

, and

b

is even too.

Conclusion: Both $a$ and $b$ are even, contradicting lowest terms. So $\sqrt{2}$ is irrational.

In induction, always say where the inductive hypothesis is used. A proof that never uses it is suspicious.

Practice: Prove by induction that

2^{n} > n

for all

n \geq 1

Base:

2^{1} = 2 > 1

. Step: if

2^{k} > k

, then

2^{k + 1} = 2 \cdot 2^{k} > 2 k \geq k + 1

since

k \geq 1

Practice: Disprove: “For every integer

n

n^{2} + n + 41

is prime.”

Counterexample

n = 41

41^{2} + 41 + 41 = 41 \cdot 43

, which is composite.

3. Sets

A set is a collection of distinct objects. Write $x \in A$ for membership and $A \subseteq B$ when every element of $A$ is in $B$ . Two sets are equal when each is a subset of the other.

Operation	Notation	Definition
Union	$A \cup B$	${x : x \in A or x \in B}$
Intersection	$A \cap B$	${x : x \in A and x \in B}$
Difference	$A ∖ B$	${x : x \in A and x \notin B}$
Complement	$A^{c}$	$U ∖ A$
Cartesian product	$A \times B$	${(a, b) : a \in A, b \in B}$
Power set	$𝒫 (A)$	the set of all subsets of $A$

{(A \cup B)}^{c} = A^{c} \cap B^{c} \cdot {(A \cap B)}^{c} = A^{c} \cup B^{c} \cdot | A \cup B | = | A | + | B | - | A \cap B |

Example: Prove

{(A \cup B)}^{c} \subseteq A^{c} \cap B^{c}

Step 1: Let

x \in {(A \cup B)}^{c}

. Then

x \notin A \cup B

Step 2: So

x \notin A

and

x \notin B

, meaning

x \in A^{c}

and

x \in B^{c}

Conclusion: $x \in A^{c} \cap B^{c}$ . The reverse inclusion follows by reversing the steps.

To prove

A = B

, show

A \subseteq B

and

B \subseteq A

. To prove

A \subseteq B

, take an arbitrary element of

A

and show it lies in

B

Practice: If

| A | = 3

, how many elements are in

𝒫 (A)

and in

𝒫 (A) \times A

| 𝒫 (A) | = 2^{3} = 8

, and

| 𝒫 (A) \times A | = 8 \cdot 3 = 24

Practice: In a class of 30, 18 take French and 15 take Spanish, and 5 take neither. How many take both?

25 take at least one, so

25 = 18 + 15 - | both |

, giving

| both | = 8

4. The Integers and Modular Arithmetic

Division algorithm: for integers

a

and

b > 0

there are unique

q

r

with

a = b q + r

and

0 \leq r < b

. We write

b | a

r = 0

Congruence:

a \equiv b (mod n)

means

n | (a - b)

. Congruence respects addition and multiplication, so you may reduce at every step.

Greatest Common Divisor

The Euclidean algorithm uses $\gcd (a, b) = \gcd (b, a mod b)$ . Working backwards gives Bézout’s identity: $\gcd (a, b) = a x + b y$ for some integers $x$ , $y$ . Moreover, $a$ has an inverse modulo $n$ exactly when $\gcd (a, n) = 1$ .

Example: Find the inverse of

7

modulo

26

Step 1: Euclid:

26 = 3 \cdot 7 + 5

7 = 1 \cdot 5 + 2

5 = 2 \cdot 2 + 1

. So

\gcd = 1

and the inverse exists.

Step 2: Back-substitute.

1 = 5 - 2 \cdot 2 = 5 - 2 (7 - 5) = 3 \cdot 5 - 2 \cdot 7 = 3 (26 - 3 \cdot 7) - 2 \cdot 7 = 3 \cdot 26 - 11 \cdot 7

Conclusion: $- 11 \equiv 15 (mod 26)$ is the inverse. Check: $7 \cdot 15 = 105 = 4 \cdot 26 + 1$ .

Example: Compute

3^{100} mod 7

Step 1: By Fermat,

3^{6} \equiv 1 (mod 7)

Step 2:

100 = 6 \cdot 16 + 4

, so

3^{100} \equiv 3^{4} = 81 \equiv 4

Conclusion: $3^{100} \equiv 4 (mod 7)$ .

Fermat: if

p

is prime and

p ∤ a

, then

a^{p - 1} \equiv 1 (mod p)

. A prime has no non-trivial divisors, so every non-zero residue mod p has an inverse.

Practice: Solve

5 x \equiv 3 (mod 12)

5 \cdot 5 = 25 \equiv 1

, so

5^{- 1} = 5

. Then

x \equiv 5 \cdot 3 = 15 \equiv 3 (mod 12)

Practice: Does

6 x \equiv 4 (mod 9)

have a solution?

\gcd (6, 9) = 3

, which does not divide

4

, so there is no solution.

5. Relations

A relation $R$ on a set $A$ is a subset of $A \times A$ . Write $a R b$ for $(a, b) \in R$ .

Property	Condition
Reflexive	$a R a for all a$
Symmetric	$a R b \Rightarrow b R a$
Antisymmetric	$a R b and b R a \Rightarrow a = b$
Transitive	$a R b and b R c \Rightarrow a R c$

An equivalence relation is reflexive, symmetric, and transitive. It splits

A

into disjoint equivalence classes

[a] = {x : x R a}

. A partial order is reflexive, antisymmetric, and transitive.

Example: Show that congruence mod

3

is an equivalence relation on

ℤ

Reflexive:

a - a = 0

is divisible by

3

Symmetric: if

3 | (a - b)

then

3 | (b - a)

Transitive: if

3 | (a - b)

and

3 | (b - c)

, then

3 | (a - c)

since the sum is

a - c

Conclusion: There are exactly three classes: $[0]$ , $[1]$ , $[2]$ .

Equivalence relations and partitions are the same thing viewed two ways. Divisibility on positive integers and

\subseteq

on sets are standard partial orders.

Practice: On

A = {1, 2, 3}

, let

R = {(1, 1), (2, 2), (1, 2), (2, 3)}

. Which properties hold?

Not reflexive (

3, 3

missing), not symmetric (

(1, 2)

without

(2, 1)

), not transitive (

(1, 2), (2, 3)

force

(1, 3)

). It is antisymmetric.

6. Functions

A function $f : A \to B$ assigns to each $a \in A$ exactly one $f (a) \in B$ . $A$ is the domain, $B$ the codomain, and ${f (a)}$ the range.

Type	Condition	Meaning
Injective	$f (a) = f (a^{'}) \Rightarrow a = a^{'}$	no two inputs share an output
Surjective	$\forall b \exists a f (a) = b$	every element of B is hit
Bijective	both	a perfect pairing; has an inverse $f^{- 1}$

The composition is $(g \circ f) (x) = g (f (x))$ . Compositions of injections are injective, and compositions of surjections are surjective.

Example: Classify

f : ℤ \to ℤ

f (x) = 2 x + 3

Injective:

2 x + 3 = 2 y + 3

gives

x = y

Surjective?

f (x)

is always odd, so

4

is never hit.

Conclusion: $f$ is injective but not surjective. On $ℝ$ it would be a bijection with $f^{- 1} (y) = \frac{(y - 3)}{2}$ .

Domain and codomain matter:

x^{2}

is not injective on

ℝ

, but it is injective on

[0, \infty)

Practice: Is

f : ℝ \to ℝ

f (x) = x^{3}

a bijection?

Yes. It is strictly increasing (so injective), and every

y

has a real cube root (so surjective). The inverse is

\sqrt[3]{y}

Practice: If

g \circ f

is injective, must

f

be injective?

Yes. If

f (a) = f (a^{'})

, then

g (f (a)) = g (f (a^{'}))

, so

a = a^{'}

. (

g

need not be injective.)

7. Cardinality

Sets

A

and

B

have the same cardinality,

| A | = | B |

, if there is a bijection

A \to B

. We write

| A | \leq | B |

if there is an injection

A \to B

A set is finite if it is in bijection with ${1, \dots, n}$ for some $n$ . Infinite sets can be matched with proper subsets of themselves, which no finite set can do.

| A | \leq | B | and | B | \leq | A | \Rightarrow | A | = | B | (Cantor–Schröder–Bernstein)

Example: Show

| ℕ | = | even natural numbers |

Step 1: Define

f (n) = 2 n

Step 2: It is injective (

2 n = 2 m \Rightarrow n = m

) and surjective (every even number is

2 n

Conclusion: $ℕ$ has the same size as a proper subset of itself.

Cantor’s theorem:

| A | < | 𝒫 (A) |

for every set

A

. So there is no largest infinity.

Practice: Why is

| (0, 1) | = | ℝ |

The map

x \mapsto \tan (π (x - \frac{1}{2}))

is a bijection from

(0, 1)

onto

ℝ

8. Countable and Uncountable Sets

A set is countably infinite if it is in bijection with

ℕ

, and countable if it is finite or countably infinite. Otherwise it is uncountable.

Set	Status	Why
$ℤ$	countable	list $0, 1, - 1, 2, - 2, \dots$
$ℕ \times ℕ$	countable	list along diagonals
$ℚ$	countable	injects into $ℤ \times ℕ$
Countable union of countable sets	countable	same diagonal listing
$(0, 1), ℝ$	uncountable	Cantor’s diagonal argument
$𝒫 (ℕ)$	uncountable	Cantor’s theorem

Example (diagonal argument):

(0, 1)

is uncountable.

Step 1: Suppose

x_{1}, x_{2}, x_{3}, \dots

is a complete list, written in decimals.

Step 2: Build

y

whose

n

th digit is

5

unless the

n

th digit of

x_{n}

5

, in which case use

6

. (Avoiding

0

and

9

prevents double representations.)

Conclusion: $y$ differs from every $x_{n}$ in the $n$ th digit, so $y$ is not on the list. No list is complete.

Consequently the real numbers cannot be listed, but the algebraic numbers can. Hence “most” real numbers are transcendental.

Practice: Is the set of all finite strings over

{a, b}

countable?

Yes. For each length

n

there are

2^{n}

strings, a finite set. A countable union of finite sets is countable. (List by length, then alphabetically.)

9. Elements of Algebra and Group Theory

A group

(G, *)

is a set with an operation satisfying: closure; associativity; an identity

e

with

e * a = a * e = a

; and an inverse

a^{- 1}

for each

a

with

a * a^{- 1} = e

. It is abelian if

a * b = b * a

Structure	Group?	Reason
$(ℤ, +)$	Yes	identity $0$ , inverse $- a$
$(ℤ, \times)$	No	$2$ has no integer inverse
$(ℤ_{n}, +)$	Yes	addition mod $n$
$(ℤ_{n}^{*}, \times)$	Yes	units: $a$ with $\gcd (a, n) = 1$
$S_{n} (permutations)$	Yes	composition; non-abelian for $n \geq 3$

Subgroups, Order, and Lagrange

A subset $H \subseteq G$ is a subgroup if it is itself a group under the same operation. The order of an element $a$ is the smallest $n > 0$ with $a^{n} = e$ . A group generated by one element is cyclic.

| H | divides | G | (Lagrange’s theorem)

Example: Find the order of every element of

(ℤ_{6}, +)

Step 1: The order of

a

is the smallest

n

with

n a \equiv 0 (mod 6)

Step 2:

0

has order

1

;

1

and

5

have order

6

;

2

and

4

have order

3

;

3

has order

2

Conclusion: $ℤ_{6}$ is cyclic, generated by $1$ (or $5$ ). All element orders divide $6$ , as Lagrange predicts.

Identities and inverses are unique. Also,

{(a b)}^{- 1} = b^{- 1} a^{- 1}

: the order reverses, just as when taking off shoes and socks.

Practice: Show that

({1, 2, 3}, \times mod 4)

is not a group.

Closure fails:

2 \times 2 = 4 \equiv 0

, which is not in the set. (Also

2

has no inverse because

\gcd (2, 4) \neq 1

Practice: Show that

(ℤ_{5}^{*}, \times)

is cyclic.

Powers of

2

mod

5

2, 4, 3, 1

. These are all four elements, so

2

is a generator.

Key Takeaways

Logic: an implication is equivalent to its contrapositive; negate quantifiers by flipping them.
Choose a proof technique to match the statement: induction for “all n”, contradiction for impossibility, one counterexample to disprove “for all”.
To show set equality, prove both inclusions.
$a$ has an inverse mod $n$ exactly when $\gcd (a, n) = 1$ ; reduce at every step.
Equivalence relations correspond to partitions; check reflexive, symmetric, transitive.
A bijection is both injective and surjective, and exactly those functions have inverses.
$ℕ$ , $ℤ$ , and $ℚ$ are countable; $ℝ$ and $𝒫 (ℕ)$ are not (diagonal argument).
A group needs closure, associativity, identity, and inverses; subgroup orders divide the group order.