๐๏ธโ๐จ๏ธ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.
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รB
The Cartesian product AรB is the set of all ordered pairs (a,b) where aโA and bโ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}
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: Dom(R)={aโฃ(a,b)โR for some bโB}
The codomain of a relation R is the set of all second elements in the ordered pairs: Codom(R)={bโฃ(a,b)โR for some aโA}
The range of a relation R 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)}
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)โR for all aโ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)โ/R for all aโ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)โR implies (b,a)โR for all a,bโ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)โR and (b,a)โR imply a=b for all a,bโ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)โR and (b,c)โR imply (a,c)โR for all a,b,cโ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โA, either (a,b)โR or (b,a)โ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 IAโ or ฮAโ, is the relation {(a,a)โฃaโA}
The identity relation is reflexive, symmetric, transitive, and antisymmetric
For any relation R on a set A, the intersection of R and IAโ is always a subset of R: RโฉIAโโ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โA under an equivalence relation R is the set [a]Rโ={bโAโฃ(a,b)โ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)