Fiveable
Fiveable
You have 2 free guides left ๐Ÿ˜ง
Unlock your guides
You have 2 free guides left ๐Ÿ˜ง
Unlock your guides

Formal Logic I

๐Ÿ‘๏ธโ€๐Ÿ—จ๏ธFormal Logic I Unit 11 โ€“ Relations and Identity

Relations and identity are fundamental concepts in formal logic. They help us understand how elements in sets are connected and associated with each other. These concepts provide a framework for analyzing and representing various logical structures and relationships. Equivalence relations and ordering relations are two important types of relations. Equivalence relations partition sets into distinct classes, while ordering relations establish hierarchies among elements. These concepts have wide-ranging applications in mathematics, computer science, and other fields.

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 RR from set AA to set BB is a subset of the Cartesian product Aร—BA \times B
    • The Cartesian product Aร—BA \times B is the set of all ordered pairs (a,b)(a, b) where aโˆˆAa \in A and bโˆˆBb \in B
  • Relations can be represented using various methods such as:
    • Set of ordered pairs: R={(a,b)โˆฃaโˆˆA,bโˆˆB, and a is related to b}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 AA, columns represent elements from set BB, and entries indicate the relationship
  • The domain of a relation RR is the set of all first elements in the ordered pairs: Dom(R)={aโˆฃ(a,b)โˆˆR for some bโˆˆB}\text{Dom}(R) = \{a | (a, b) \in R \text{ for some } b \in B\}
  • The codomain of a relation RR is the set of all second elements in the ordered pairs: Codom(R)={bโˆฃ(a,b)โˆˆR for some aโˆˆA}\text{Codom}(R) = \{b | (a, b) \in R \text{ for some } a \in A\}
  • The range of a relation RR is the set of all second elements that are actually related to some element in the domain: Ran(R)={bโˆฃ(a,b)โˆˆR for some aโˆˆDom(R)}\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 RR on a set AA is reflexive if (a,a)โˆˆR(a, a) \in R for all aโˆˆAa \in A
    • Example: The relation "is equal to" on the set of real numbers is reflexive
  • Irreflexive: A relation RR on a set AA is irreflexive if (a,a)โˆ‰R(a, a) \notin R for all aโˆˆAa \in A
    • Example: The relation "is greater than" on the set of real numbers is irreflexive
  • Symmetric: A relation RR on a set AA is symmetric if (a,b)โˆˆR(a, b) \in R implies (b,a)โˆˆR(b, a) \in R for all a,bโˆˆAa, b \in A
    • Example: The relation "is sibling of" on the set of people is symmetric
  • Antisymmetric: A relation RR on a set AA is antisymmetric if (a,b)โˆˆR(a, b) \in R and (b,a)โˆˆR(b, a) \in R imply a=ba = b for all a,bโˆˆAa, b \in A
    • Example: The relation "is less than or equal to" on the set of real numbers is antisymmetric
  • Transitive: A relation RR on a set AA is transitive if (a,b)โˆˆR(a, b) \in R and (b,c)โˆˆR(b, c) \in R imply (a,c)โˆˆR(a, c) \in R for all a,b,cโˆˆAa, b, c \in A
    • Example: The relation "is ancestor of" on the set of people is transitive
  • Connex (or total): A relation RR on a set AA is connex if for all a,bโˆˆAa, b \in A, either (a,b)โˆˆR(a, b) \in R or (b,a)โˆˆR(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 AA, denoted by IAI_A or ฮ”A\Delta_A, is the relation {(a,a)โˆฃaโˆˆA}\{(a, a) | a \in A\}
  • The identity relation is reflexive, symmetric, transitive, and antisymmetric
  • For any relation RR on a set AA, the intersection of RR and IAI_A is always a subset of RR: RโˆฉIAโŠ†RR \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 AA 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โˆˆAa \in A under an equivalence relation RR is the set [a]R={bโˆˆAโˆฃ(a,b)โˆˆR}[a]_R = \{b \in A | (a, b) \in R\}
  • The set of all equivalence classes under an equivalence relation RR on a set AA is called the quotient set, denoted by A/RA/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 AA 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 AA 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 AA 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 AA 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)


ยฉ 2025 Fiveable Inc. All rights reserved.
APยฎ and SATยฎ are trademarks registered by the College Board, which is not affiliated with, and does not endorse this website.

ยฉ 2025 Fiveable Inc. All rights reserved.
APยฎ and SATยฎ are trademarks registered by the College Board, which is not affiliated with, and does not endorse this website.