Relations

Description

Senior Freshman Mathematics Mind Map on Relations, created by Luke Byrne on 22/04/2018.
Luke Byrne
Mind Map by Luke Byrne, updated more than 1 year ago
Luke Byrne
Created by Luke Byrne almost 6 years ago
17
0

Resource summary

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

              2. A = {1, 3, 7}
                1. B = {1, 2, 5}
                  1. S = {(1, 1), (1, 5), (3, 2)}
                    1. 1S1, 1S5, 3S2 and no other ordered pairs in A x B satisify S.
                      1. Binary Relation
                2. Equivalence Relations
                  1. Reflexive
                    1. iff ∀x ∈ A, xRx
                    2. Symmetric
                      1. ∀x, y ∈ A, xRy → yRx
                      2. Transitive
                        1. ∀x, y, z ∈ A, xRy ∧ yRz → xRz
                        2. xRy, x ≡ y, x ~ y
                          1. Example 1: Equality
                            1. x = x
                              1. x = y ⇒ y = x
                                1. x = y ∧ y = z ⇒ x = z
                                  1. 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.
                                  1. ∀ABC ∈ Γ, ABC ∼ ABC
                                    1. ABC ∼ A′B′C' ⇒ A′B′C′ ∼ ABC
                                      1. ABC ∼ A′B′C' and A′B′C′ ∼ A”B”C” ⇒ ABC ∼ A”B”C”
                              3. 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)
                                          1. xRy ⇔ [x] = [y] (all elements related by R belong to the same equivalence class)
                                            1. ¬(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
                                          1. 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, ... }
                                                  1. [1]R = {1, 4, 7, 10, ... }
                                                    1. [2]R = {2, 5, 8, 11, ... }
                                                      1. [0]R ∪ [1]R ∪ [2]R = N
                                                        1. Mutually disjoint ⇒ R gives a partition of N.
                                                2. 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. Reflexive
                                                          1. ∀x ∈ R, x ≤ x
                                                          2. Anti-Symmetric
                                                            1. ∀x, y ∈ R s.t. x ≤ y ∧ y ≤ x ⇒ x = y
                                                            2. Transitive
                                                              1. ∀x, y, z ∈ R s.t. x ≤ y ∧ y ≤ z ⇒ x ≤ z
                                                              2. 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.
                                                            Show full summary Hide full summary

                                                            Similar

                                                            The SAT Math test essentials list
                                                            lizcortland
                                                            How to improve your SAT math score
                                                            Brad Hegarty
                                                            GCSE Maths: Pythagoras theorem
                                                            Landon Valencia
                                                            Edexcel GCSE Maths Specification - Algebra
                                                            Charlie Turner
                                                            Mathematics
                                                            Corey Lance
                                                            Graph Theory
                                                            Will Rickard
                                                            Projectiles
                                                            Alex Burden
                                                            Mathematics Overview
                                                            PatrickNoonan
                                                            MODE, MEDIAN, MEAN, AND RANGE
                                                            Elliot O'Leary
                                                            FREQUENCY TABLES: MODE, MEDIAN AND MEAN
                                                            Elliot O'Leary
                                                            HISTOGRAMS
                                                            Elliot O'Leary