Chapter 3Elementary Discrete Mathslides.en.pdf:153-156

Relations

Reflexive, symmetric, transitive, equivalence, partial order

Def 2.1 — Binary relationDef 2.4 — Total relationDef 2.5 — ConverseDef 2.6 — CompositionDef 2.7 — Relation propertiesDef 2.7 — Equivalence relationDef 2.10 — Partial orderDef 2.11 — Linear order
Concept

A binary relation R⊆A×BR \subseteq A \times B is a set of ordered pairs.

If A=BA = B, we say RR is a relation on AA.

Properties (for RR a relation on AA):
- Reflexive: ∀a.(a,a)∈R\forall a. (a, a) \in R
- Irreflexive: ∀a.(a,a)∉R\forall a. (a, a) \notin R
- Symmetric: ∀a,b.(a,b)∈R⇒(b,a)∈R\forall a, b. (a, b) \in R \Rightarrow (b, a) \in R
- Antisymmetric: ∀a,b.(a,b)∈R∧(b,a)∈R⇒a=b\forall a, b. (a, b) \in R \land (b, a) \in R \Rightarrow a = b
- Transitive: ∀a,b,c.(a,b)∈R∧(b,c)∈R⇒(a,c)∈R\forall a, b, c. (a, b) \in R \land (b, c) \in R \Rightarrow (a, c) \in R
- Total: ∀a∈A.∃b∈B.(a,b)∈R\forall a \in A. \exists b \in B. (a, b) \in R

Derived operations:
- Converse: R−1:={(b,a)∣(a,b)∈R}R^{-1} := \{(b, a) \mid (a, b) \in R\}
- Composition: R∘S:={(a,c)∣∃b.(a,b)∈R∧(b,c)∈S}R \circ S := \{(a, c) \mid \exists b. (a, b) \in R \land (b, c) \in S\}

Special relations:
- Equivalence relation: reflexive + symmetric + transitive
- Partial order: reflexive + antisymmetric + transitive
- Linear (total) order: partial order where all pairs comparable

Animation — relations venn
Transcript — click a line to jump9 cues
  1. 0.0sRelation Properties
  2. 1.2sFive cyan dots a, b, c, d, e appear
  3. 4.5sGreen self-loops on every dot, reflexive caption
  4. 6.5sSymmetric caption: if xRy then yRx
  5. 7.5sc-loop fades out, replaced by a-to-b and b-to-a arrows
  6. 9.7sTransitive caption: aRb and bRc implies aRc
  7. 10.8sb-to-c arrow draws in amber
  8. 12.4sa-to-c arrow appears grey, then lights up amber
  9. 13.7sReflexive plus symmetric plus transitive = equivalence
Exemplars and exemplanda

An exemplar (or 'exemplans') is a specific mathematical object used to illustrate a concept. An exemplandum (or 'exemplum') is the general concept being illustrated. Example:

  • '3' is an exemplar of the concept 'prime number' (the exemplandum).
  • 'Z\mathbb{Z}' is an exemplar of the concept 'abelian group'.
  • The graph K4K_4 is an exemplar of the concept 'complete graph'.

Distinguishing them matters when generalizing: a property proved for one exemplar may not hold for another. Counterexamples are exemplars that violate a proposed general statement.

Formula grammatical roles

Mathematical formulas play grammatical roles analogous to natural language:
- Subject — the main object the formula is about (e.g. xx in 'x>0x > 0').
- Predicate — a property or relation asserted about the subject (e.g. '>0> 0').
- Connective — joins sub-formulas (∧,∨,⇒,⇔\land, \lor, \Rightarrow, \Leftrightarrow).
- Quantifier — binds variables (∀,∃\forall, \exists).

Example: 'Every prime greater than 2 is odd.' Decomposition:
- Quantifier: 'every' (∀\forall).
- Subject: 'prime greater than 2'.
- Predicate: 'is odd'.

Recognising the grammatical role helps with paraphrasing (turning formulas back into MathTalk).

Practice — score 100% to advance
Multiple choice
Q1
Which properties make an equivalence relation?
Q2
What is the converse of R={(1,2),(2,3)}R = \{(1,2), (2,3)\}?
Q3
Is ≤\leq on N\mathbb{N} a partial order?
Q4
Is ≤\leq on N\mathbb{N} a total order?
Q5
Is == on any set an equivalence relation?
Q6
Composition R∘SR \circ S: {(1,2)}∘{(2,3)}\{(1,2)\} \circ \{(2,3)\} = ?
Q7
If RR is transitive, is R−1R^{-1} transitive?
Q8
An exemplandum is:
Q9
In '∀x. P(x)⇒Q(x)\forall x.\, P(x) \Rightarrow Q(x)', the symbol ∀\forall is a:
Fill in the blank
Q1
In the sentence '3 is an example of a prime number', '3' is the ___ and 'prime number' is the ___.
Match definitions
Match each concept on the left to its definition on the right.
Order the steps
Arrange these proof steps in the correct order using the arrows.
1
But it IS reflexive and symmetric. Now check transitivity: (1,2)∘(2,1)=(1,1)(1,2) \circ (2,1) = (1,1). Is (1,1)∈R(1,1) \in R? Yes. ✓
2
Start with the binary relation R={(1,2),(2,1),(1,1),(2,2)}R = \{(1,2), (2,1), (1,1), (2,2)\}.
3
Step 2: check symmetry — (1,2)∈R(1,2) \in R, is (2,1)∈R(2,1) \in R? Yes. ✓
4
So RR is NOT antisymmetric — therefore NOT a partial order.
5
Step 3: check antisymmetry — (1,2)∈R(1,2) \in R and (2,1)∈R(2,1) \in R, but 1≠21 \neq 2. ✗
6
Step 1: check reflexivity — (1,1)∈R(1,1) \in R? Yes. (2,2)∈R(2,2) \in R? Yes. ✓
7
Conclusion: RR is reflexive + symmetric + transitive = equivalence relation.
Loading…