1. Statements, logic and quantifier order

Learning goals and mathematical language

Separate a statement from an open predicate, track the scope of each variable, and distinguish implication, converse and equivalence. A statement has a truth value. An open predicate such as $x^2>1$ acquires a truth value only after $x$ is specified or quantified over a declared domain. The same formula can have different truth values on different domains.

For statements $P,Q$, the conjunction $P\land Q$ is true when both are true; $P\lor Q$ is inclusive “or,” true when at least one is true. The negation $\neg P$ reverses truth. The implication $P\Rightarrow Q$ is false only when $P$ is true and $Q$ false. Thus a false premise makes an implication true; it does not prove that the conclusion alone is true. The equivalence $P\Leftrightarrow Q$ consists of both implications.

The universal statement $\forall x\in A\ P(x)$ asserts the predicate for every member. The existential statement $\exists x\in A\ P(x)$ asserts at least one witness. Universal statements over the empty set are true, and existential statements over it are false. This convention agrees with the absence of a counterexample or witness.

Theorem: negating quantifiers and implications

The following equivalences hold:

$$\neg(\forall x\in A\ P(x))\ \Leftrightarrow\ \exists x\in A\ \neg P(x),$$ $$\neg(\exists x\in A\ P(x))\ \Leftrightarrow\ \forall x\in A\ \neg P(x), \qquad \neg(P\Rightarrow Q)\ \Leftrightarrow\ P\land\neg Q.$$

Also $P\Rightarrow Q$ is equivalent to its contrapositive $\neg Q\Rightarrow\neg P$, but not generally to its converse $Q\Rightarrow P$.

Proof. A universal assertion fails exactly when a counterexample exists, proving the first equivalence. Existence fails exactly when every candidate fails, proving the second. The only false implication has true premise and false conclusion, proving the third. Both an implication and its contrapositive fail precisely in that same truth assignment. The converse fails instead at false $P$, true $Q$, so the equivalence does not extend to it.

Quantifier order and worked examples

A witness depending on the input. Over $\mathbb R$, $\forall x\exists y\ (y>x)$ is true: after choosing $x$, take $y=x+1$. But $\exists y\forall x\ (y>x)$ is false: a proposed fixed $y$ is defeated by $x=y+1$. Writing $y=y(x)$ can remind us of allowed dependence, but does not replace a proof.

Negating an eventual bound. The assertion

$$\forall\varepsilon>0\ \exists N\in\mathbb N\ \forall n\ge N: |a_n-L|<\varepsilon$$

has negation $\exists\varepsilon_0>0\ \forall N\in\mathbb N\ \exists n\ge N:|a_n-L|\ge\varepsilon_0$. A single bad early term is not enough to negate eventual convergence; the bad indices must occur past every proposed threshold.

Restricted universals. “Every integer divisible by six is even” is $\forall n\in\mathbb Z\,[6\mid n\Rightarrow2\mid n]$. Its negation requires an integer divisible by six but not by two. An odd number not divisible by six does not qualify as a counterexample, since its premise is false.

Graded practice

1. Foundation. Negate “every real number has a positive square,” then determine the original statement's truth.
2. Core. Write the converse and contrapositive of “if $n$ is divisible by four, then $n$ is even,” over integers, and determine each truth value.
3. Core. Compare $\forall x\in\mathbb R\exists y\in\mathbb R:x+y=0$ with $\exists y\in\mathbb R\forall x\in\mathbb R:x+y=0$.
4. Proof. Negate $\exists M>0\forall n\in\mathbb N:|a_n|\le M$ and explain why the result expresses unboundedness.

Full solutions

1. The negation is “there exists a real $x$ with $x^2\le0$.” The witness $x=0$ proves the negation, so the original universal assertion is false.
2. The converse is “if $n$ is even, then four divides $n$,” false at $n=2$. The contrapositive is “if $n$ is not even, then four does not divide $n$,” true because a multiple of four is twice an integer. The original is also true.
3. The first is true using $y=-x$ after $x$ is specified. The second is false: a fixed $y$ cannot solve both $0+y=0$ and $1+y=0$.
4. The negation is $\forall M>0\exists n\in\mathbb N:|a_n|>M$. Every proposed positive bound fails at some index; the index may depend on $M$. That is precisely the absence of a finite absolute bound.

Summary and term definitions

A predicate contains free variables; a quantifier specifies how those variables range. A counterexample satisfies a universal claim's premises but violates its conclusion. The converse reverses an implication, while the contrapositive reverses and negates both sides. Quantifier order records dependence; negate one scope at a time and preserve the declared domains.