TOPIC 1 / 2

Logic, Sets & Relations

Useful preparation: Product Rule

For a long equation, swipe sideways inside its formula box to see every term.

Meaning & notation

“Every input has a suitable output” permits different outputs for different inputs; “one output works for every input” does not. Logic makes this distinction precise.

Predicate and quantifier: A predicate P(x) becomes a statement when its variable is specified or quantified. The symbols ∀ and ∃ mean “for every” and “there exists”; the domain determines the allowed choices.
Sets and membership: A union contains elements in either set, an intersection contains elements in both, and A⊆B means every member of A belongs to B.
Relation and equivalence class: A relation R on A is a subset of $\displaystyle A \times A$ . Write xRy for membership of the pair. An equivalence class [x] collects all elements related to x.

Conditions before calculation

State every variable’s domain and preserve the order of nested quantifiers. A later existential choice may depend on earlier universally chosen variables.
An equivalence relation must be reflexive, symmetric, and transitive on the entire declared set.
A partial order instead requires reflexivity, antisymmetry, and transitivity. Antisymmetry permits mutual relatedness only for equal elements.

Why the method works

1. Negate from outside inward

To refute a universal assertion, supply one failing input. To refute an existential assertion, rule out every allowed witness. Repeating these rules handles nested statements.

\neg(\forall x\,\exists y\,P(x,y))\iff\exists x\,\forall y\,\neg P(x,y)

2. Translate implication accurately

The implication $\displaystyle P \Rightarrow Q$ rules out a true premise with a false conclusion. Its contrapositive describes exactly the same forbidden situation; its converse generally describes something else.

(P\Rightarrow Q)\iff(\neg Q\Rightarrow\neg P)

3. Explain why classes partition

Reflexivity places each element in its own class. If two classes overlap, symmetry and transitivity transfer membership between them, so they coincide rather than overlap partially.

Worked examples

EXAMPLE 1

Compare “for every integer n, some integer m exceeds n” with the reversed quantifier order.

Choose an arbitrary integer n. The expression $\displaystyle m = n + 2$ is an allowed integer witness.
This witness exceeds n, proving the first statement without selecting a special input.
For the reversed claim, any proposed fixed m fails at $\displaystyle n = m$ . Thus no single witness works for all integers.

Conclusion: The first claim is true; the reversed claim is false.

EXAMPLE 2

On the integers, define aRb when 5 divides $\displaystyle a - b$ . Verify equivalence and identify [2].

The difference $\displaystyle a - a$ is zero, a multiple of 5, so reflexivity holds.
Negating a multiple of 5 gives another multiple, proving symmetry.
If $\displaystyle a - b = 5\, u$ and $\displaystyle b - c = 5\, v$ , add them; $\displaystyle u + v$ is an integer.
$a-c=5(u+v)$
All and only integers differing from 2 by a multiple of 5 belong to its class.
$[2]=\{2+5k:k\in\mathbb Z\}$

Conclusion: The relation partitions the integers into five remainder classes.

Pitfalls & counterexamples

Tempting claim: Symmetric and antisymmetric mean the same thing.

Correction: Symmetry requires the reverse pair; antisymmetry restricts when both directions can occur.

Test the claim: The relation ≤ on integers is antisymmetric, but $\displaystyle 2 \le 5$ does not imply $\displaystyle 5 \le 2$ .

Check your understanding

Negate: for every real x, there exists a real y with $\displaystyle y > x$ .

Write a reason before opening the explanation. This reflection is not graded or saved.

Compare your reasoning

There exists a real x such that every real y satisfies $\displaystyle y \le x$ .

Switch both quantifiers and negate the strict inequality. Keep their order.

Connect this idea

Equivalence classes lead to modular arithmetic and quotient structures. Quantifier order also distinguishes pointwise convergence from uniform convergence.

Practise this topic →Review concept flashcards

Reference reading

Use these texts to study the underlying definitions and theorems in greater depth. The explanations and examples above are written for Numerive.