Relations

Relations

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

2. General Relations

   • Take x = y for example.
     • The elements x is some notation R to y (equality in this case).
       • We can also denote it as xRy or (x, y) ∈ E.
     • Let x, y in R, then E = {(x, x) | x ∈ R} ⊂ R x R.
       • The "diagonal" in R x R gives exactly the elements equal to each other.
         • 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.
           • Cartesian Products
       • A = {1, 3, 7}
       • B = {1, 2, 5}
       • S = {(1, 1), (1, 5), (3, 2)}
         • 1S1, 1S5, 3S2 and no other ordered pairs in A x B satisify S.
         • Binary Relation

3. Equivalence Relations

   • Reflexive
     • iff ∀x ∈ A, xRx
   • Symmetric
     • ∀x, y ∈ A, xRy → yRx
   • Transitive
     • ∀x, y, z ∈ A, xRy ∧ yRz → xRz
   • xRy, x ≡ y, x ~ y
   • Example 1: Equality
     • x = x
       • x = y ⇒ y = x
         • x = y ∧ y = z ⇒ x = z
           • Therefore equality, =, is an equivalence relation
     • Example 2: Triangles
       • 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.
       • ∀ABC ∈ Γ, ABC ∼ ABC
         • ABC ∼ A′B′C' ⇒ A′B′C′ ∼ ABC
           • ABC ∼ A′B′C' and A′B′C′ ∼ A”B”C” ⇒ ABC ∼ A”B”C”

4. Partitions

   • Collection of non-empty sets, any two of which are disjoint s.t. their union is A
     • 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.
       • 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.
         • 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.
       • For any equivalence relation R on a set A, its equivalence classes form a partition of A
         • ∀x ∈ A, ∃y ∈ A s.t. x ∈ [y] (every element of A sits somewhere)
         • xRy ⇔ [x] = [y] (all elements related by R belong to the same equivalence class)
         • ¬(xRy) ⇔ [x] ∩ [y] = ∅ (if two elements are not related by R, the they belong to disjoint equivalence classes)
   • {(n, n + 1 | n ∈ Z} is a partition of R
   • A = N (natural numbers)
     • x ≡ y mod 3
       • We have the equivalence classes [0]R, [1]R and [2]R given by the three possible remainders under division by 3.
         • [0]R = {0, 3, 6, 9, ... }
         • [1]R = {1, 4, 7, 10, ... }
         • [2]R = {2, 5, 8, 11, ... }
         • [0]R ∪ [1]R ∪ [2]R = N
           • Mutually disjoint ⇒ R gives a partition of N.

5. Partial Orders

   • Anti-Symmetric
     • A relation R on A is called anti-symmetric if ∀x, y ∈ A s.t. xRy ∧ yRx, then x = y
   • A partial order is a relation on a set A that is reflexive, anti-symmetric and transitive.
     • ≤
       • Reflexive
         • ∀x ∈ R, x ≤ x
       • Anti-Symmetric
         • ∀x, y ∈ R s.t. x ≤ y ∧ y ≤ x ⇒ x = y
       • Transitive
         • ∀x, y, z ∈ R s.t. x ≤ y ∧ y ≤ z ⇒ x ≤ z
       • A = R
         • Same conclusion is A = Z or A = N
   • Most important example is the relation ⊆ "being a subset of" as a partial order.

Bilder und Dateien der Mindmap