Relations

To define subsets of Cartesian products with certain properties, and to understand the predicates "=" (equality) and other predicates in predicate logic in a more abstract light.
General Relations
1. Take x = y for example.
  1. The elements x is some notation R to y (equality in this case).
    1. We can also denote it as xRy or (x, y) ∈ E.
  2. Let x, y in R, then E = {(x, x) | x ∈ R} ⊂ R x R.
    1. The "diagonal" in R x R gives exactly the elements equal to each other.
      1. Let A, B be sets. A subset of the Cartesian product A x B is called a relation between A and B. A subset of the Cartesian product A x A is called a relation on A.
        Attachments:
        Cartesian Products
    2. A = {1, 3, 7}
    3. B = {1, 2, 5}
    4. S = {(1, 1), (1, 5), (3, 2)}
      1. 1S1, 1S5, 3S2 and no other ordered pairs in A x B satisify S.
      2. Binary Relation
Equivalence Relations
1. Reflexive
  1. iff ∀x ∈ A, xRx
2. Symmetric
  1. ∀x, y ∈ A, xRy → yRx
3. Transitive
  1. ∀x, y, z ∈ A, xRy ∧ yRz → xRz
4. xRy, x ≡ y, x ~ y
5. Example 1: Equality
  1. x = x
    1. x = y ⇒ y = x
      1. x = y ∧ y = z ⇒ x = z
        Therefore equality, =, is an equivalence relation
  2. Example 2: Triangles
    1. Let Γ be the set of all triangles in the plane. ABC ~ A'B'C' if ABC and A'B'C' are similar triangles i.e. have equal angles.
    2. ∀ABC ∈ Γ, ABC ∼ ABC
      1. ABC ∼ A′B′C' ⇒ A′B′C′ ∼ ABC
        ABC ∼ A′B′C' and A′B′C′ ∼ A”B”C” ⇒ ABC ∼ A”B”C”
Partitions
1. Collection of non-empty sets, any two of which are disjoint s.t. their union is A
  1. If R is an equivalence relation on a set A, and x ∈ A, the equivalence class of x, denoted [x]R, is the set {y | xRy}. The collection of all equivalence classes is called A modulo R, and denoted A/R.
    1. When the elements of some set S have a notion of equivalence (an equivalence relation) defined on them, then one may naturally split the set S into equivalence classes.
      1. If X is the set of all cars, and ~ is the equivalence relation "has the same colour as", then one particular equivalence class consists of all green cars. X/~ could be naturally identified with the set of all car colours.
    2. For any equivalence relation R on a set A, its equivalence classes form a partition of A
      1. ∀x ∈ A, ∃y ∈ A s.t. x ∈ [y] (every element of A sits somewhere)
      2. xRy ⇔ [x] = [y] (all elements related by R belong to the same equivalence class)
      3. ¬(xRy) ⇔ [x] ∩ [y] = ∅ (if two elements are not related by R, the they belong to disjoint equivalence classes)
2. {(n, n + 1 | n ∈ Z} is a partition of R
3. A = N (natural numbers)
  1. x ≡ y mod 3
    1. We have the equivalence classes [0]R, [1]R and [2]R given by the three possible remainders under division by 3.
      1. [0]R = {0, 3, 6, 9, ... }
      2. [1]R = {1, 4, 7, 10, ... }
      3. [2]R = {2, 5, 8, 11, ... }
      4. [0]R ∪ [1]R ∪ [2]R = N
        Mutually disjoint ⇒ R gives a partition of N.
Partial Orders
1. Anti-Symmetric
  1. A relation R on A is called anti-symmetric if ∀x, y ∈ A s.t. xRy ∧ yRx, then x = y
2. A partial order is a relation on a set A that is reflexive, anti-symmetric and transitive.
  1. ≤
    1. Reflexive
      1. ∀x ∈ R, x ≤ x
    2. Anti-Symmetric
      1. ∀x, y ∈ R s.t. x ≤ y ∧ y ≤ x ⇒ x = y
    3. Transitive
      1. ∀x, y, z ∈ R s.t. x ≤ y ∧ y ≤ z ⇒ x ≤ z
    4. A = R
      1. Same conclusion is A = Z or A = N
3. Most important example is the relation ⊆ "being a subset of" as a partial order.

Media attachments

Triangles (binary/octet-stream)

Next up

Relations

Description

Resource summary

Media attachments

Similar

	Created by Luke Byrne over 6 years ago