What is Statement, connectives? — Mathematics

Definition 1.1 University Mathematics — Year 1 · Chapter 1 — Logic, Sets and Maps

A statement (or proposition) is a sentence which is either true (T) or false (F) — exactly one of the two. From statements $P$ and $Q$ one forms:

the negation $\lnot P$ (“not $P$ ”), true exactly when $P$ is false;
the conjunction $P \land Q$ (“ $P$ and $Q$ ”), true exactly when both are true;
the disjunction $P \lor Q$ (“ $P$ or $Q$ ”), true exactly when at least one is true (this “or” is inclusive);
the implication $P \implies Q$ , false exactly when $P$ is true and $Q$ is false;
the equivalence $P \iff Q$ , true exactly when $P$ and $Q$ have the same truth value.

Examples

Example 1.6 (Negating everyday mathematical sentences)

Let $f \colon \R \to \R$ . The sentence “ $f$ is increasing” reads

\forall x \in \R,\ \forall y \in \R,\quad x \leq y \implies f(x) \leq f(y) ,

and its negation, by Proposition 1.5 plus the rule $\lnot(P \implies Q) \iff P \land \lnot Q$ :

\exists x \in \R,\ \exists y \in \R,\quad x \leq y \ \text{ and }\ f(x) > f(y) :

a single witnessing pair suffices. Likewise “ $f$ is bounded” is $\exists M \in \R,\ \forall x \in \R,\ \abs{f(x)} \leq M$ , with negation

\forall M \in \R,\ \exists x \in \R,\quad \abs{f(x)} > M :

whatever bound is proposed, some point beats it. The insight: a correct negation never contains “not” applied to a quantified block — it is a new positive statement, in which the roles are exchanged: one now produces the witnesses one previously received.

Example 1.7 (Order of quantifiers)

The order of different quantifiers matters:

\forall x \in \R,\ \exists y \in \R,\ y > x \quad\text{is true (take } y = x+1\text{),}

\exists y \in \R,\ \forall x \in \R,\ y > x \quad\text{is false (no real number exceeds all reals).}

In the first statement $y$ may depend on $x$ ; in the second, one single $y$ must work for all $x$ . Two identical quantifiers, on the other hand, always commute.

Example 1.13 (Proving unique existence)

A statement $\exists!\,x,\ P(x)$ is two statements, proved separately: existence (exhibit or construct some $x_0$ with $P(x_0)$ ) and uniqueness (assume $P(x)$ and $P(x')$ , deduce $x = x'$ ). Sample: there is a unique real $x$ with $x^3 + x = 2$ . Existence: $x_0 = 1$ works, since $1 + 1 = 2$ . Uniqueness: if $x^3 + x = x'^3 + x'$ , then

0 = (x^3 - x'^3) + (x - x') = (x - x')\,\bigl(x^2 + xx' + x'^2 + 1\bigr),

and the second factor is positive (it equals $\bigl(x + \tfrac{x'}2\bigr)^2 + \tfrac34 x'^2 + 1 \geq 1$ ), so $x = x'$ . Note the division of labor: existence used a lucky guess, uniqueness used algebra valid for arbitrary solutions — neither argument does the other’s job, and forgetting the second half is a standing temptation once a solution has been found.

Read in context →