Practice

Reasoning practice

Write a complete argument, then compare it with a worked solution and review checklist. Your written reasoning is not automatically graded.

Prim’s algorithm and the cut rule Derive a recurrence from a model Multigraph bijections and matrices

Section

Step-by-step lesson Written problems Back to §7.2 in All topics

1 / 3

Concepts for §7.2

Before you begin

Functions Defined on General Sets

X is the set of allowed inputs; Y is the declared set of possible outputs. Both are part of the function specification.

\displaystyle f

\displaystyle X\to Y

Every $x\in X$ must have exactly one image in Y. Different inputs may share an output.

\displaystyle \forall x\in X \exists !y\in Y

\displaystyle y=f(x)

More in lesson §7.1 Function Function evaluation

Definitions and notation for this topic

Intervals and endpoints

\displaystyle [a,b]

;

\displaystyle (a,b)

;

\displaystyle [0,\infty )

For real $a<b$ , [a,b] includes both endpoints; (a,b) excludes both. A square bracket includes its finite endpoint and a round bracket excludes it.

Infinity is not a real endpoint to include, so $\infty$ always has a round bracket in this notation. Intervals contain real values, not only integers.

Separate glossary example

$[0,\infty )=\{x\in \mathbb{R}:x\ge 0\}$ ; $(-1,2]=\{x\in \mathbb{R}:-1<x\le 2\}$ .

Open glossary card

Preimage of a set

\displaystyle f^{-1}(T)=\{x\in A:f(x)\in T\}

For any function f: $A\to B$ and $T\subseteq B$ , $f^{-1}(T)$ is the set of all inputs whose outputs lie in T. No bijectivity is required.

The result is a set and may be empty or have several elements. This use of $f^{-1}$ does not claim an inverse function exists.

Separate glossary example

For f: $\mathbb{R}\to \mathbb{R}$ , $f(x)=x^{2}$ , $f^{-1}(\{4\})=\{-2,2\}$ and $f^{-1}(\{-1\})=\varnothing$ .

Open glossary card

Injection / one-to-one

Different inputs always have different outputs.

Equivalently, $f(a)=f(b)$ implies $a=b$ .

For f: $A\to B$ , the full condition is $\forall x$ , $y\in A (f(x)=f(y)\to x=y)$ . The arrow ↣ is an optional convention in some texts, not required notation for this property.

Separate glossary example

f: $\mathbb{Z}\to \mathbb{Z}$ , $f(x)=2x$

Open glossary card

Surjection / onto

Every element of the codomain is the output of at least one input.

For a target value y, the input $y-1$ works.

For f: $A\to B$ , onto means $\forall b\in B \exists a\in A (f(a)=b)$ . The codomain B matters. The arrow ↠ is an optional notation, not the definition.

Separate glossary example

f: $\mathbb{Z}\to \mathbb{Z}$ , $f(x)=x+1$

Open glossary card

Bijection

A function f: $A\to B$ that is both injective and surjective. Every element of B has exactly one preimage in A.

Specify the function and its domain/codomain. A bare ↔ usually marks a logical biconditional here; it is not a sufficient notation for a bijection.

Separate glossary example

f: $\mathbb{Z}\to \mathbb{Z}$ , $f(x)=x+1$ is bijective: the unique input for y is $x=y-1$ .

f: $\mathbb{Z}\to \mathbb{Z}$ , $f(x)=x+1$

Open glossary card

Inverse function

\displaystyle f^{-1}

\displaystyle B\to A

A bijection f: $A\to B$ has an inverse $f^{-1}$ : $B\to A$ returning the unique input for each output. It satisfies $f^{-1}(f(a))=a$ and $f(f^{-1}(b))=b$ .

The domain and codomain restrictions make the inverse possible. $f^{-1}(y)$ denotes inverse-function evaluation, not the reciprocal $1/f(y)$ ; a preimage $f^{-1}(T)$ of a set remains meaningful without an inverse function.

Separate glossary example

f: $[0,\infty )\to [0,\infty )$ , $f(x)=x^{2}$ has inverse $f^{-1}(y)=\\operatorname{sqrt} y$ . The same square rule on $\mathbb{R}\to \mathbb{R}$ is not bijective.

Open glossary card

Open the lesson §7.2

How to build an argument: methods and reasons

Before writing: assumptions, goals and established facts (§4.2)

Assumption: a stated hypothesis or an explicitly temporary premise. Identify its domain.
Goal: what remains to be shown. It is not available as a reason for a later step.
Established: a statement derived from hypotheses, definitions, earlier steps or an applicable theorem. Name that reason.
Introduce witnesses when their existence is justified; give different arbitrary quantities different variables. Finish by matching the result to the original goal.

Writing a proof · §4.2

Example: constructing the witness for an odd product

Assumption
$m=2a+1,\ n=2b+1,\quad a,b\in\mathbb Z$
Take arbitrary odd integers m and n.
Reason: Their representations follow from the definition of odd.
Goal
$\exists s\in\mathbb Z:\ mn=2s+1$
This is the goal, not something already known.
Reason: An existential conclusion requires constructing a witness.
Established
$mn=(2a+1)(2b+1)=4ab+2a+2b+1$
Expand before introducing s.
Reason: Substitution and the distributive law.
Established
$s=2ab+a+b\in\mathbb Z,\quad mn=2s+1$
The constructed integer s proves the product odd.
Reason: Closure of integers and the definition of odd; the goal was not assumed.

Direct proof

When to choose: Choose it when definitions turn the hypothesis into usable equations or properties.

For every x in D: $P(x)$ implies $Q(x)$ . Given: an arbitrary x in D satisfying P. Goal: Q for that same x.

Start: Introduce the objects and their domains; assume only the stated hypotheses. Expand the relevant definition.

Finish: State Q and explain why arbitrariness gives the universal claim. Never use Q as a premise.

Worked example with reasons

Assumption
$a,b\in\mathbb Z,\quad a>0,\ b>0,\ a\mid b$
Take arbitrary positive integers a and b with a dividing b.
Reason: These are the hypotheses, not conclusions.
Goal
$a\le b$
We must establish this inequality.
Reason: Writing a goal does not establish it.
Established
$b=aq,\quad q\in\mathbb Z$
Introduce an integer q witnessing divisibility.
Reason: Definition of a dividing b; a is nonzero.
Established
$q=\frac ba>0$
The quotient is positive.
Reason: Both b and a are positive; division by a is allowed.
Established
$q\ge1$
A positive integer cannot lie strictly between 0 and 1.
Reason: This uses q being an integer, not positivity alone.
Established
$aq\ge a,\quad b\ge a$
Replace aq by b to obtain the goal.
Reason: Multiplication by a positive a preserves the inequality; b=aq was established above.

Source concepts · approved book access required

PDF 198 · p. 174, PDF 215 · p. 191

Counterexample

When to choose: Use it to refute a universal claim. A failed proof attempt alone does not refute anything.

To refute every x in D satisfying P also satisfies Q, find one x in D with P true and Q false.

Start: Write the exact claim and choose a permitted test object. Verify its hypotheses.

Finish: Show explicitly which conclusion fails; one valid counterexample refutes the universal claim.

Worked example with reasons

Goal
$\forall n\in\mathbb Z\ (n>1\Rightarrow \operatorname{Prime}(n))$
Test the claim that every integer greater than 1 is prime.
Reason: A universal statement can be disproved by one permitted instance.
Established
$n=9,\quad9\in\mathbb Z,\quad9>1$
The chosen value satisfies the domain and hypothesis.
Reason: A counterexample must meet every hypothesis.
Established
$9=3\cdot3,\quad1<3<9$
Nine has a positive divisor other than 1 and itself, so it is not prime.
Reason: Definition of prime. Composite means nonprime only within integers greater than 1.

Source concepts · approved book access required

PDF 185 · p. 161, PDF 198 · p. 174

Proof by cases

When to choose: Choose cases when a definition or remainder changes the calculation. First show the cases cover every allowed object.

Given P, cover all possibilities $C_{1}$ ,…, $C_{k}$ and prove Q in each.

Start: Derive the case split from a definition or theorem; do not merely list convenient examples.

Finish: Conclude Q because every allowed object belongs to a handled case.

Worked example with reasons

Assumption
$n\in\mathbb Z,\quad 2\nmid n$
Let n be an arbitrary odd integer.
Reason: The hypothesis fixes the domain but does not yet provide the required m.
Goal
$n^2=8m+1\quad m\in\mathbb Z$
We need to construct an integer m.
Reason: The conclusion is existential: both the equation and integrality must be shown.
Established
$n=4q+r,\quad q\in\mathbb Z,\quad r\in\{0,1,2,3\}$
Only $r=1$ or $r=3$ is possible for odd n.
Reason: Quotient–remainder theorem 4.5.1; residues 0 and 2 make n even. This proves completeness.
Established
$(4q+1)^2=16q^2+8q+1=8(2q^2+q)+1$
Case 1: set $m=2q^{2}+q$ .
Reason: Expand the square and factor 8. Sums and products of integers are integers.
Established
$(4q+3)^2=16q^2+24q+9=8(2q^2+3q+1)+1$
Case 2: set $m=2q^{2}+3q+1$ .
Reason: Expansion, $9=8+1$ , then factor 8; the constructed m is an integer.
Established
$\exists m\in\mathbb Z:\ n^2=8m+1$
Both possible cases give the required integer; it may depend on the case.
Reason: Exhaustive cases establish the original claim for arbitrary odd n.

Source concepts · approved book access required

PDF 230 · p. 206, PDF 231 · p. 207

Contraposition

When to choose: Use it when negating the conclusion gives a more useful starting definition.

To prove $P\Rightarrow Q$ , prove $\neg Q\Rightarrow \neg P$ . Given $\neg Q$ ; goal $\neg P$ .

Start: Write the contrapositive and introduce an arbitrary object satisfying $\neg Q$ .

Finish: Establish $\neg P$ , then invoke equivalence with the original implication.

Worked example with reasons

Goal
$2\mid n^2\Rightarrow 2\mid n$
Prove the statement for every integer n.
Reason: This is Proposition 4.7.4.
Assumption
$2\nmid n$
Instead prove: if n is odd, then $n^{2}$ is odd.
Reason: $P\Rightarrow Q$ is equivalent to $\neg Q\Rightarrow \neg P$ . For integers, not even means odd. We do not assume $n^{2}$ even here.
Established
$n=2k+1,\quad k\in\mathbb Z$
Introduce an integer k.
Reason: Definition of odd.
Established
$n^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1$
The square is odd.
Reason: Algebra and closure of integers show $2k^{2}+2k$ is an integer; then use the definition of odd.
Established
$2\mid n^2\Rightarrow 2\mid n$
The original implication follows from the proved contrapositive.
Reason: Logical equivalence of a conditional and its contrapositive.

Source concepts · approved book access required

PDF 246 · p. 222, PDF 247 · p. 223, PDF 248 · p. 224

Contradiction

When to choose: Use it when the negation creates incompatible established facts.

Assume the hypotheses and the negation of the desired conclusion; derive a contradiction.

Start: State exactly what is temporarily assumed for contradiction.

Finish: Name the conflicting statements and discharge the assumption.

Worked example with reasons

Goal
$2\mid n^2\Rightarrow 2\mid n$
Prove the statement for every integer n.
Reason: This is Proposition 4.7.4.
Assumption
$2\mid n^2,\quad 2\nmid n$
Assume a counterexample: $n^{2}$ is even but n is not even.
Reason: Negating the universal conditional gives one integer satisfying the hypothesis and negating the conclusion. Every integer is either even or odd.
Established
$n=2k+1,\quad k\in\mathbb Z$
Introduce an integer k.
Reason: Definition of odd.
Established
$n^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1$
The square is odd.
Reason: Algebra and closure of integers show $2k^{2}+2k$ is an integer; then use the definition of odd.
Established
$2\mid n^2\ \land\ 2\nmid n^2$
This is impossible; the assumed counterexample cannot exist.
Reason: No integer is both even and odd (Theorem 4.7.2). Discharging the contradictory assumption proves the original claim.

Source concepts · approved book access required

PDF 246 · p. 222, PDF 247 · p. 223, PDF 248 · p. 224

Mathematical induction

When to choose: Use it for a claim indexed by every integer n from a starting value, when the next case relates to the previous one.

Prove $P(n_{0})$ . For arbitrary $k\ge n_{0}$ , assume $P(k)$ and derive $P(k+1)$ .

Start: State the indexed property and starting value; check the base without using the induction hypothesis.

Finish: Invoke induction only after both the base and the implication are established.

Worked example with reasons

Goal
$1+3+\cdots+(2n-1)=n^2,\quad n\ge1$
Prove the sum formula for every positive integer n.
Reason: The domain and indexed property specify what induction must cover.
Established
$n=1:\quad1=1^2$
The first case holds.
Reason: Direct evaluation establishes the base.
Assumption
$1+3+\cdots+(2k-1)=k^2,\quad k\ge1$
Fix an arbitrary integer k and assume only its case.
Reason: This temporary induction hypothesis is permitted to prove the implication $P(k)\Rightarrow P(k+1)$ .
Established
$1+3+\cdots+(2k-1)+(2k+1)=k^2+2k+1$
Separate the next term and replace the old sum by $k^{2}$ .
Reason: This is the exact point where the induction hypothesis is used.
Established
$k^2+2k+1=(k+1)^2$
This is the required case $k+1$ .
Reason: Algebra proves the implication. The base and induction principle now give all integers $n\ge 1$ .

Source concepts · approved book access required

PDF 304 · p. 280

Negating quantified statements

When to choose: Use it to identify precisely what would make a quantified claim false, especially before a counterexample or contradiction.

Negate one outer quantifier at a time, preserving variable order, domains and the scope of the predicate.

Start: Mark the scope of each quantifier; move the negation inward one rule at a time.

Finish: Read the final statement and check that it describes failure of the original claim. Equivalence does not by itself prove either statement true.

Worked example with reasons

Goal
$\neg\forall x\in D\ \exists y\in E\ P(x,y)$
Rewrite the negation without changing its meaning.
Reason: The domains D and E remain fixed throughout.
Established
$\exists x\in D\ \neg\exists y\in E\ P(x,y)$
There is an x for which the inner existential statement fails.
Reason: Negation of a universal quantifier: $\neg \forall x R(x) \Leftrightarrow \exists x \neg R(x)$ .
Established
$\exists x\in D\ \forall y\in E\ \neg P(x,y)$
For that same x, every y fails P.
Reason: Negation of an existential quantifier: $\neg \exists y P(x,y) \Leftrightarrow \forall y \neg P(x,y)$ . The order $\exists x\forall y$ is preserved.

Source concepts · approved book access required

PDF 164 · p. 140

Theorem, proposition, lemma and corollary

Theorem / proposition

Both are statements established by proof. The name often signals how a text organizes or emphasizes a result, not a different degree of truth.

Lemma

A proved auxiliary result used in another argument. For example, $-|r|\le r\le |r|$ for real r supports later bounds. If $r\ge 0$ , $|r|=r$ and $-r\le r$ ; if $r<0$ , $|r|=-r$ and $r\le -r$ . These cases cover every real r.

Lemma 4.5.4, printed p. 207 / PDF 231

Corollary

A result derived from an established theorem. If r is rational, $r+r$ is rational by closure of rational numbers under addition (Theorem 4.3.2); because $2r=r+r$ , its double is rational.

Example 4.3.4, printed p. 187 / PDF 211; printed box: Corollary 4.2.3

Keep the domain conditions

With Epp’s definition, d divides 0 for every nonzero integer d: $0=d\cdot 0$ . Do not omit $d\ne 0$ .

Prime and composite classifications here concern integers $n>1$ . “Not prime” alone does not make 0, 1 or a negative integer composite.

§7.2 · Injection and surjectionLevel 1

f: $\{1,2,3\}\to \{a,b,c\}$ , with $f(1)=a$ , $f(2)=b$ , $f(3)=b$ . Classify f.

Choose one answer Both injective and surjective Injective but not surjective Surjective but not injective Neither injective nor surjective

My reasoning (optional)

Check answer checks the result above. Your reasoning is saved, not automatically graded; compare it with the walkthrough.

Symbols

Back to §7.2 in All topics Concept in Epp: §7.2, printed page 439 ↗

Common mistake

Surjectivity depends on the declared codomain, not just the values actually attained.

Practice

Reasoning practice

Before you begin

Theorem / proposition

Lemma

Corollary

f:{1,2,3}→{a,b,c}\{1,2,3\}\to \{a,b,c\}{1,2,3}→{a,b,c}, with f(1)=af(1)=af(1)=a, f(2)=bf(2)=bf(2)=b, f(3)=bf(3)=bf(3)=b. Classify f.

f: $\{1,2,3\}\to \{a,b,c\}$ , with $f(1)=a$ , $f(2)=b$ , $f(3)=b$ . Classify f.