Formal Logic I Unit 11 Review: Relations and Identity

Key Concepts

• Relations define how elements from one set are connected or associated with elements from another set
• Relations can be represented using ordered pairs, where the first element comes from the first set and the second element comes from the second set
• The domain of a relation is the set of all first elements in the ordered pairs, while the codomain is the set of all second elements
• Relations can have various properties such as reflexivity, symmetry, transitivity, and antisymmetry
• Identity relation is a special type of relation where each element is related to itself and no other elements
• Equivalence relations partition a set into disjoint subsets called equivalence classes
• Ordering relations establish a hierarchy or ranking among elements in a set
• Relations play a crucial role in mathematical logic and can be used to model and analyze various logical concepts and structures

Defining Relations

• A relation $R$ from set $A$ to set $B$ is a subset of the Cartesian product $A \times B$
  • The Cartesian product $A \times B$ is the set of all ordered pairs $(a, b)$ where $a \in A$ and $b \in B$
• Relations can be represented using various methods such as:
  • Set of ordered pairs: $R = \{(a, b) | a \in A, b \in B, \text{ and } a \text{ is related to } b\}$
  • Graph: Nodes represent elements and edges represent the relationship between elements
  • Matrix: Rows represent elements from set $A$, columns represent elements from set $B$, and entries indicate the relationship
• The domain of a relation $R$ is the set of all first elements in the ordered pairs: $\text{Dom}(R) = \{a | (a, b) \in R \text{ for some } b \in B\}$
• The codomain of a relation $R$ is the set of all second elements in the ordered pairs: $\text{Codom}(R) = \{b | (a, b) \in R \text{ for some } a \in A\}$
• The range of a relation $R$ is the set of all second elements that are actually related to some element in the domain: $\text{Ran}(R) = \{b | (a, b) \in R \text{ for some } a \in \text{Dom}(R)\}$

Types of Relations

• Binary relation: Relates elements from one set to elements of another set (or the same set)
• Ternary relation: Relates elements from three sets (or the same set)
• n-ary relation: Relates elements from n sets (or the same set)
• Unary relation: A property that elements of a set may or may not possess (e.g., "is even" for natural numbers)
• Recursive relation: A relation defined in terms of itself (e.g., the "is ancestor of" relation can be defined using the "is parent of" relation)
• Functional relation (or function): For each element in the domain, there is exactly one element in the codomain that it is related to
• Injective relation (or one-to-one): Each element in the codomain is related to at most one element in the domain
• Surjective relation (or onto): Each element in the codomain is related to at least one element in the domain
• Bijective relation (or one-to-one correspondence): A relation that is both injective and surjective

Properties of Relations

• Reflexive: A relation $R$ on a set $A$ is reflexive if $(a, a) \in R$ for all $a \in A$
  • Example: The relation "is equal to" on the set of real numbers is reflexive
• Irreflexive: A relation $R$ on a set $A$ is irreflexive if $(a, a) \notin R$ for all $a \in A$
  • Example: The relation "is greater than" on the set of real numbers is irreflexive
• Symmetric: A relation $R$ on a set $A$ is symmetric if $(a, b) \in R$ implies $(b, a) \in R$ for all $a, b \in A$
  • Example: The relation "is sibling of" on the set of people is symmetric
• Antisymmetric: A relation $R$ on a set $A$ is antisymmetric if $(a, b) \in R$ and $(b, a) \in R$ imply $a = b$ for all $a, b \in A$
  • Example: The relation "is less than or equal to" on the set of real numbers is antisymmetric
• Transitive: A relation $R$ on a set $A$ is transitive if $(a, b) \in R$ and $(b, c) \in R$ imply $(a, c) \in R$ for all $a, b, c \in A$
  • Example: The relation "is ancestor of" on the set of people is transitive
• Connex (or total): A relation $R$ on a set $A$ is connex if for all $a, b \in A$, either $(a, b) \in R$ or $(b, a) \in R$
  • Example: The relation "is less than or equal to" on the set of real numbers is connex

Identity Relation

• The identity relation on a set $A$, denoted by $I_A$ or $\Delta_A$, is the relation $\{(a, a) | a \in A\}$
• The identity relation is reflexive, symmetric, transitive, and antisymmetric
• For any relation $R$ on a set $A$, the intersection of $R$ and $I_A$ is always a subset of $R$: $R \cap I_A \subseteq R$
• The identity relation is the smallest reflexive relation on a set
• The identity relation plays a crucial role in defining equivalence relations and ordering relations

Equivalence Relations

• An equivalence relation on a set $A$ is a relation that is reflexive, symmetric, and transitive
• Equivalence relations partition a set into disjoint subsets called equivalence classes
  • An equivalence class of an element $a \in A$ under an equivalence relation $R$ is the set $[a]_R = \{b \in A | (a, b) \in R\}$
• The set of all equivalence classes under an equivalence relation $R$ on a set $A$ is called the quotient set, denoted by $A/R$
• The equivalence class of any element is non-empty and contains the element itself
• Two equivalence classes under the same equivalence relation are either identical or disjoint
• Examples of equivalence relations:
  • "Has the same birthday as" on the set of people
  • "Is congruent modulo n" on the set of integers (for a fixed n)

Ordering Relations

• A partial order on a set $A$ is a relation that is reflexive, antisymmetric, and transitive
  • Example: The relation "is a subset of" on the set of all subsets of a given set is a partial order
• A total order (or linear order) on a set $A$ is a partial order that is also connex
  • Example: The relation "is less than or equal to" on the set of real numbers is a total order
• A strict partial order on a set $A$ is a relation that is irreflexive and transitive
  • Example: The relation "is a proper subset of" on the set of all subsets of a given set is a strict partial order
• A strict total order (or strict linear order) on a set $A$ is a strict partial order that is also connex
  • Example: The relation "is less than" on the set of real numbers is a strict total order
• Hasse diagrams are used to visualize partial orders by representing elements as nodes and the order relation as edges, omitting edges that can be inferred by transitivity

Applications in Logic

• Relations are used to model and analyze various logical concepts and structures
• Propositional logic: Relations between propositions (e.g., implication, equivalence)
• First-order logic: Relations between elements of a domain (e.g., equality, ordering)
• Modal logic: Relations between possible worlds (e.g., accessibility relations)
• Set theory: Relations between sets (e.g., subset, equality)
• Algebra: Relations between algebraic structures (e.g., isomorphism, homomorphism)
• Graph theory: Relations between nodes in a graph (e.g., adjacency, reachability)
• Formal languages: Relations between strings (e.g., concatenation, prefix)
• Artificial intelligence: Relations between entities in knowledge representation and reasoning systems (e.g., semantic networks, description logics)