Common Mistakes
Contents
Logic
Truth tables
- Missing intermediate columns
A complete truth table needs to include intermediate steps/columns. For example, if the final
formula is $\sim (p \land \sim q) \rightarrow (q \lor r)$, then you should include intermediate columns such as $\sim
q$, $(p \land \sim q)$, $\sim(p \land \sim q)$, $(q \lor r)$ before computing the final column.
- Incorrect precedence for logical connectives
Another common issue is forgetting operator precedence. For example, some people treat $\sim p \lor q \rightarrow r$
as $\sim p \lor (q \rightarrow r)$, but it should be $(\sim p \lor q) \rightarrow r$, since $\land$ and $\lor$ have
higher precedence than conditionals.
- Not writing conclusion
For problems where you use truth tables to show equivalence, tautology, or contradiction, your conclusion should be
explicit and complete. For example:
- Equivalent: The truth table shows that $(\dots)$ and $(\dots)$ always have the same truth values,
therefore they are equivalent.
- Not equivalent: The truth table shows that $(\dots)$ and $(\dots)$ have different truth values in
row(s) $(\dots)$, therefore they are not equivalent.
- Tautology: Since all truth values of $(\dots)$ are $T$, $(\dots)$ is a tautology.
- Not tautology: Since the truth value of $(\dots)$ is $F$ in row(s) $(\dots)$, $(\dots)$ is not a
tautology.
Similarly for contradiction, and valid arguments.
- Shuffling rows
Do not shuffle rows. Keep the same order of writing the truth table rows -- TTT, TTF, TFT, TFF, FTT, FTF, FFT, FFF.
- Writing 1 and 0 in place of T and F
Do not write 1 and 0 in place of T and F in truth tables. Similarly, do not write T and F in place of 1 and 0 in I/O tables.
Negations
- Negating compound inequalities
To negate a compound statement such as $50 < x < 75$, first rewrite it as $(50 < x) \land (x < 75)$, then
use De Morgan's law to negate. For example, writing $50 \ge x \ge 75$ is not a correct negation.
- Statements with conjunctions and disjunctions
Statements like $p \land q \lor r$ can be confusing to read, because they could be interpreted as $(p \land q) \lor
r$ or $p \land (q \lor r)$. So when writing these, group the “or” using parentheses, e.g. “$n$ is divisible
by 6 and ($n$ is not divisible by 2 or $n$ is not divisible by 3).”
- Interchange formal and informal statements
If the question is in formal language, write the negation in formal language and vice versa.
Arguments
- Not highlighting critical rows
Critical rows should be highlighted in the truth tables that are used to verify the validity and invalidty of arguments. If there are false conclusions in critical rows, they should be highlighted as well.
- Not following the organized format
For problems involving proofs using valid arguments, the format used in the lecture notes / book should be used.
- Missing reasons/justifications
Write proofs as a sequence of short steps, and give a reason for each step (rule, law, definition, or an earlier
line).
Proof techniques
Format
- Not mentioning proof technique
Always mention the proof technique that has been used to provide a proof in the first line.
- Not writing the starting line of proof properly
For proof by contradition, mention the negation properly with keyword "Negation".
For proof by contraposition, mention the contrapositive properly with keyword "Contrapositive".
For proof by division into cases, mention all the cases properly.
- Not giving reasoning / justification
Follow the 2-column format of writing proofs whenever possible: first column for conclusions and second column for reasoning / justification. Reasoning / justification includes definitions, properties, laws, assumptions, hypotheses, theorems, etc.
Converse error
- Confusing converse with contrapositive/inverse
Do not confuse converse with contrapositive
Do not confuse converse with inverse
- Converse error
If the problem is to prove "If $p$, then $q$". We need to suppose $p$ and then derive $q$. Supposing $q$ and then deriving $p$ is not a proof because of converse error.
- Backward reasoning
Suppose we are given a TARGET statement to prove.
The following template is a direct proof and is correct.
TRUE $\implies$ $\implies$ $\implies$ $\cdots$ $\implies$ TARGET
The following template uses backward reasoning (due to converse error) and is incorrect.
TARGET $\implies$ $\implies$ $\implies$ $\cdots$ $\implies$ TRUE
Example: $+1 = -1$ $\implies$ $(+1)^2 = (-1)^2$
Example: $+1 = -1$ $\implies$ $+1 \times 0 = -1 \times 0$
The following template is correct as it uses biconditional.
TARGET $\Longleftrightarrow$ $\Longleftrightarrow$ $\Longleftrightarrow$ $\cdots$ $\Longleftrightarrow$ TRUE
When proving an inequality (for example, AM $\ge$ GM), it is generally not correct to start from the target inequality
and reduce it to something trivial, unless every step is reversible.
Example: Suppose we want to prove arithmetic mean $\ge$ geometric mean for $a,b \ge 0$.
Correct proof:
\begin{align*}
&\frac{a+b}{2} \ge \sqrt{ab} \\
& \Leftrightarrow a+b \ge 2\sqrt{ab} && \text{(multiply both sides by } 2 > 0\text{)}\\
& \Leftrightarrow a - 2\sqrt{ab} + b \ge 0 && \text{(subtract } 2\sqrt{ab} \text{ from both sides)}\\
& \Leftrightarrow (\sqrt{a}-\sqrt{b})^2 \ge 0 && \text{(since } a,b \ge 0\text{, expand/factor)}
\end{align*}
Since $(\sqrt{a}-\sqrt{b})^2 \ge 0$ is always true, the original inequality is proved.
Incorrect proof:
\begin{align*}
&\frac{a+b}{2} \ge \sqrt{ab} \\
& \Rightarrow a+b \ge 2\sqrt{ab} && \text{(multiply both sides by } 2 > 0\text{)}\\
& \Rightarrow a - 2\sqrt{ab} + b \ge 0 && \text{(subtract } 2\sqrt{ab} \text{ from both sides)}\\
& \Rightarrow (\sqrt{a}-\sqrt{b})^2 \ge 0 && \text{(since } a,b \ge 0\text{, expand/factor)}
\end{align*}
Since $(\sqrt{a}-\sqrt{b})^2 \ge 0$ is always true, the original inequality is proved.
Sequences
Induction
- Not writing $P(n)$
The first line of an induction proof should be defining $P(n)$.
- Unjustified base case
In the base case, one must show why it is true by direct computation or a clear argument. Writing only “$P(1)$ is true” (or “base case is true”) without justification will not receive credit.
- Incomplete or incorrect inductive hypothesis
State the hypothesis with correct quantifiers and bounds.
- Ordinary induction:
“Assume that for some $k \in \mathbb{N}$ with $k \ge a$, $P(k)$ is true.”
Here, $a$ is the lower bound (the first base case).
- Strong induction:
“Assume that for some $k \in \mathbb{N}$ with $k \ge b$, $P(i)$ is true for all $i \in [a, k]$.”
Here, $a$ is the lower bound (the first base case) and $b$ is the upper bound (the last base case).
Common mistakes: not writing “for some” explicitly, writing “for all” instead, or omitting the lower/upper bound. For example, the following are all incorrect:
- “Assume $P(k)$.”
- “Assume $P(k)$ for $k \in \mathbb{N}$.”
- “Assume $P(k)$ for $k \ge a$.”
- “Assume $P(k)$ for all $k \in \mathbb{N}$.”
- “Assume $P(k)$ for all $k \ge a$.”
- Missing justification when using the inductive hypothesis
In the inductive step, whenever you use the inductive hypothesis, cite it explicitly "($P(k)$ is true)" and explain why it applies
at that point in the proof.
Sets
Set proofs
- Only proving one direction in set equality
To prove $A = B$, you must prove both $A \subseteq B$ and $B \subseteq A$. Showing only one inclusion is incomplete.
- Using identities when element method is required
Unless the problem explicitly allows identities/laws, use element-based proofs: start with “let $x \in A$” (if you are trying to show $A \subseteq B$), and justify each step using definitions of set operations and properties of sets. Use identities/laws when the problem statement says "Prove using algebraic proof".
- Missing justifications
In set proofs, cite definitions (intersection, union, difference, subset, set equality).
Functions
Prove that a function is one-to-one or onto
- One-to-one
Start with “Let $x_1, x_2 \in D$ such that $f(x_1) = f(x_2)$,” where $D$ is the domain of $f$. Then show that $x_1 = x_2$.
Common mistakes: starting with “Let $f(x_1) = f(x_2)$” without mentioning the domain, or omitting “Let/assume/suppose.”
- Onto
Start with “let $y \in C$,” where $C$ is the codomain of $f$. Then construct $x$ such that $f(x) = y$, and also show $x \in D$, where $D$ is the domain of $f$.
Common mistakes: missing the codomain of $y$, or not showing $x \in D$ after solving for a preimage candidate $x$.