Unit 3: Relations and Logic
Table of Contents
Relations and Their Properties
A relation R from a set A to a set B is a subset of the Cartesian product A × B. A relation on a set A is a subset of A × A. We write `aRb` to mean (a, b) is in R.
Properties of Relations (on a set A)
- Reflexive: A relation R is reflexive if `aRa` for every element `a` in A.
(Every element is related to itself).
Example: "≤" on the set of integers. `a ≤ a` is always true. - Symmetric: A relation R is symmetric if for all `a, b` in A, `aRb` implies `bRa`.
(If a is related to b, then b must be related to a).
Example: "is equal to" (=). If `a = b`, then `b = a`.
Non-example: "≤". `3 ≤ 5` is true, but `5 ≤ 3` is false. - Transitive: A relation R is transitive if for all `a, b, c` in A, `aRb` and `bRc` implies `aRc`.
(If a is related to b, and b is related to c, then a is related to c).
Example: "<" (less than). If `a < b` and `b < c`, then `a < c`.
Equivalence Relations
A relation R on a set A is an equivalence relation if it is reflexive, symmetric, and transitive.
Equivalence relations are important because they "group" similar elements together.
Classic Example: Congruence modulo m.
Let R be the relation on the set of integers Z defined by `aRb` if `a ≡ b (mod 3)` (i.e., `a - b` is divisible by 3).
- Reflexive: `aRa`? Is `a - a = 0` divisible by 3? Yes.
- Symmetric: If `aRb`, then `a - b = 3k`. Does `bRa`? Is `b - a` divisible by 3?
Yes, because `b - a = -(a - b) = -3k = 3(-k)`. - Transitive: If `aRb` and `bRc`, then `a - b = 3k` and `b - c = 3j`. Does `aRc`?
Add the equations: `(a - b) + (b - c) = 3k + 3j`
`a - c = 3(k + j)`. Yes, `a - c` is divisible by 3.
Since R is reflexive, symmetric, and transitive, it is an equivalence relation.
Equivalence Classes and Partitions
Equivalence Class
Let R be an equivalence relation on a set A. For any element `a` in A, the equivalence class of `a`, denoted `[a]`, is the set of all elements in A that are related to `a`.
[a] = { x ∈ A | xRa }
Example (Congruence mod 3):
- `[0]` = { ..., -6, -3, 0, 3, 6, ... } (all numbers with remainder 0)
- `[1]` = { ..., -5, -2, 1, 4, 7, ... } (all numbers with remainder 1)
- `[2]` = { ..., -4, -1, 2, 5, 8, ... } (all numbers with remainder 2)
- `[3]` = { ..., 0, 3, 6, ... } which is the same set as `[0]`.
Partition
A partition of a set A is a collection of non-empty, disjoint subsets of A whose union is the entire set A.
Theorem: An equivalence relation on a set A partitions the set A into its equivalence classes.
In the example above, the equivalence classes `[0]`, `[1]`, and `[2]` form a partition of the integers Z.
Introduction to Logic and Propositions
A proposition (or statement) is a declarative sentence that is either True or False, but not both.
- Examples: "It is raining." (T or F), "2 + 2 = 4" (T), "2 + 2 = 5" (F).
- Non-examples: "What time is it?" (Question), "Close the door." (Command), "x + 1 = 2" (Predicate, depends on x).
Logical Connectives and Truth Tables
We combine simple propositions (p, q) into compound propositions using connectives.
| Connective | Name | Symbol | Meaning |
|---|---|---|---|
| Negation | "not" | ¬p | The opposite of p. |
| Conjunction | "and" | p ∧ q | True only when both p and q are true. |
| Disjunction | "or" | p ∨ q | True if at least one of p or q is true (inclusive or). |
Truth Table
| p | q | ¬p | p ∧ q | p ∨ q |
|---|---|---|---|---|
| T | T | F | T | T |
| T | F | F | F | T |
| F | T | T | F | T |
| F | F | T | F | F |
Conditional Statements
Implication (p → q)
This is the "if p, then q" statement. `p` is the hypothesis, `q` is the conclusion.
It is only False when `p` is True and `q` is False.
Biconditional (p ↔ q)
This is the "p if and only if q" (iff) statement. It is True only when `p` and `q` have the same truth value (both T or both F).
`p ↔ q` is logically equivalent to `(p → q) ∧ (q → p)`.
Converse, Inverse, and Contrapositive
Given the implication `p → q` ("If you are a student, then you are busy"):
- Converse (q → p): "If you are busy, then you are a student." (Not logically equivalent)
- Inverse (¬p → ¬q): "If you are not a student, then you are not busy." (Not logically equivalent)
- Contrapositive (¬q → ¬p): "If you are not busy, then you are not a student." (Logically equivalent to the original statement)
Quantifiers and Counterexamples
Quantifiers
- Universal Quantifier (∀): Symbol for "for all", "for every".
Example: `∀x ∈ Z, x² ≥ 0` ("For all integers x, x squared is greater than or equal to 0.") - Existential Quantifier (∃): Symbol for "there exists", "for some".
Example: `∃x ∈ Z, x² = 4` ("There exists an integer x such that x squared is 4.")
Counterexamples
To prove a universally quantified statement (∀x, P(x)) is false, you only need to find one single counterexample.
Statement: "All prime numbers are odd." (∀p ∈ Primes, p is odd).
Counterexample: The number 2 is a prime number, but it is not odd. Therefore, the statement is false.