Algebra Textbook: Book 1 - Set Theory/Set Relations

Set Relations Introduction to Relations Relations are fundamental mathematical structures that formalize the concept of objects being "related" to one another. In set theory, a relation between sets establishes connections between their elements according to specific rules or properties. A binary relation from set to set is a subset of the Cartesian product . That is, . If , we say that " is related to " and often write . When , we call a binary relation on . Representations of Relations Relations can be represented in several ways: Set of Ordered Pairs The most fundamental representation is as a set of ordered pairs. For example, if and , a relation from to might be: This means that 1 is related to a, 2 is related to b, 3 is related to c, and 1 is also related to c. Matrix Representation For finite sets, a relation can be represented as a matrix. If and , then the relation matrix is an matrix where: Directed Graph For a relation on a set , we can represent as a directed graph (digraph) where: Each element of is a vertex There is a directed edge from vertex to vertex if and only if Properties of Relations Binary relations on a set can have various properties: Reflexivity A relation on is reflexive if for every , . Example: The relation "is equal to" on the set of integers is reflexive because every integer equals itself. Irreflexivity A relation on is irreflexive if for every , . Example: The relation "is less than" on the set of integers is irreflexive because no integer is less than itself. Symmetry A relation on is symmetric if for all , if , then . Example: The relation "is a sibling of" on a set of people is symmetric. Antisymmetry A relation on is antisymmetric if for all , if and , then . Example: The relation "less than or equal to" on the set of integers is antisymmetric. Transitivity A relation on is transitive if for all , if and , then . Example: The relation "is greater than" on the set of integers is transitive. Special Types of Relations Certain combinations of properties define important types of relations: Equivalence Relations A relation on a set is an equivalence relation if it is reflexive, symmetric, and transitive. Example: The relation "has the same remainder when divided by 5" on the set of integers is an equivalence relation. An equivalence relation partitions a set into disjoint subsets called equivalence classes. For , the equivalence class of , denoted , is defined as: Partial Orders A relation on a set is a partial order if it is reflexive, antisymmetric, and transitive. Example: The relation "is a subset of" on the power set of a set is a partial order. In a partially ordered set (poset): Two elements and are comparable if either or A total order is a partial order where any two elements are comparable A minimal element is an element that has no other element below it A maximal element is an element that has no other element above it Total Orders A relation on a set is a total order if it is a partial order and for all , either or . Example: The relation "less than or equal to" on the set of real numbers is a total order. Operations on Relations Several operations can be performed on relations: Inverse Relation For a relation from to , the inverse relation from to is defined as: Composition of Relations For relations from to and from to , the composition is a relation from to defined as: Closure of Relations The closure of a relation with respect to a property P is the smallest relation containing that satisfies property P. Examples: Reflexive closure: Symmetric closure: Transitive closure: The smallest transitive relation containing Relations and Functions Functions are special types of relations with unique properties: A relation from to is a function if: For every , there exists at least one such that (total) For every and , if and , then (well-defined) Functions can be: Injective (one-to-one): No two distinct elements in the domain map to the same element in the codomain Surjective (onto): Every element in the codomain is mapped to by some element in the domain Bijective: Both injective and surjective Hasse Diagrams A Hasse diagram is a graphical representation of a finite partially ordered set. In a Hasse diagram: Elements are represented as vertices If and there is no such that , then there is an edge connecting and , with placed above Reflexive and transitive edges are omitted for clarity Hasse diagrams provide a visual way to understand the structure of partial orders. Applications of Relations Relations have numerous applications across mathematics and computer science: Database Theory In relational databases, tables represent relations between entities, and operations like joins correspond to compositions of relations. Graph Theory Many graph properties can be expressed in terms of relations. For example, adjacency in a graph is a relation on the set of vertices. Order Theory Partial and total orders are fundamental in order theory, which has applications in optimization, scheduling, and computer science. Social Network Analysis Relations like "is friends with" or "follows" are modeled as relations in social network analysis. Exercises 1. Let . Define a relation on by if divides . List all ordered pairs in and determine which properties (reflexivity, symmetry, transitivity, etc.) satisfies. 2. Let be the relation on the set of integers defined by if is divisible by 3. Prove that is an equivalence relation and describe its equivalence classes. 3. Draw the Hasse diagram for the partial order "divides" on the set . 4. Let be a relation on a set . Prove that the transitive closure of is , where represents the composition of with itself times. 5. Let be the relation on defined by if or . Prove that is a total order (lexicographic order). 6. Let and . Find the reflexive, symmetric, and transitive closures of . 7. Let be a relation on a set . Prove that is an equivalence relation if and only if and . 8. Let be the set of all people. Define the relation on by if and have a common grandparent. Is reflexive? Symmetric? Transitive? Justify your answers. 9. Let be the power set of a set . Define a relation on by if . Determine which properties satisfies. 10. Let be a symmetric and transitive relation on a set . Prove that is an equivalence relation on , where is the identity relation on .