Unit 3: Relations and Logic

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)

1. 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.
2. 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.
3. 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.

Truth Table

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.