Introduction
Predicates and relations are fundamental concepts in logic that allow us to express properties of objects and connections between objects. They form the basis of predicate logic and are essential for knowledge representation.
Understanding predicates and relations is essential for:
- Mathematics: Expressing mathematical properties and relationships
- Computer Science: Database design, knowledge representation, logic programming
- Artificial Intelligence: Knowledge bases and reasoning systems
- Formal Verification: Specifying system properties
- Philosophy: Analyzing complex arguments
This comprehensive guide explores predicates, relations, and their applications.
Predicates
Definition
A predicate is a function that takes one or more arguments and returns true or false.
Notation: P(x), Q(x, y), R(x, y, z), …
Unary Predicates
A unary predicate takes one argument and expresses a property of that object.
Examples:
- Human(x) = “x is human”
- Prime(x) = “x is prime”
- Red(x) = “x is red”
- Student(x) = “x is a student”
Evaluation:
- Human(Socrates) = true
- Prime(7) = true
- Red(grass) = false
- Student(Alice) = true
Binary Predicates
A binary predicate takes two arguments and expresses a relationship between two objects.
Examples:
- Parent(x, y) = “x is the parent of y”
- Greater(x, y) = “x is greater than y”
- Loves(x, y) = “x loves y”
- Sibling(x, y) = “x and y are siblings”
Evaluation:
- Parent(John, Mary) = true (if John is Mary’s parent)
- Greater(5, 3) = true
- Loves(Alice, Bob) = true (if Alice loves Bob)
- Sibling(Tom, Jerry) = true (if Tom and Jerry are siblings)
N-ary Predicates
An n-ary predicate takes n arguments.
Examples:
- Between(x, y, z) = “y is between x and z”
- Gives(x, y, z) = “x gives y to z”
- Teaches(x, y, z) = “x teaches y to z”
Evaluation:
- Between(1, 5, 10) = true
- Gives(Alice, book, Bob) = true (if Alice gives a book to Bob)
- Teaches(Professor, Math, Student) = true
Relations
Definition
A relation is a set of tuples that satisfy a predicate.
Formal Definition: A relation R on sets A₁, A₂, …, Aₙ is a subset of A₁ × A₂ × … × Aₙ.
Binary Relations
A binary relation R on sets A and B is a subset of A × B.
Examples:
- Parent relation: {(John, Mary), (John, Tom), (Jane, Mary), (Jane, Tom)}
- Greater relation: {(5, 3), (5, 2), (3, 2), …}
- Loves relation: {(Alice, Bob), (Bob, Carol), …}
Representing Relations
As a Set of Tuples:
Parent = {(John, Mary), (John, Tom), (Jane, Mary), (Jane, Tom)}
As a Table:
Parent(x, y):
x | y
------|------
John | Mary
John | Tom
Jane | Mary
Jane | Tom
As a Graph:
John ──→ Mary
John ──→ Tom
Jane ──→ Mary
Jane ──→ Tom
Properties of Relations
Reflexivity
A relation R is reflexive if every element is related to itself.
Definition: ∀x (xRx)
Example: Equality (=) is reflexive because x = x for all x
Non-example: Parent is not reflexive because no one is their own parent
Symmetry
A relation R is symmetric if whenever x is related to y, y is related to x.
Definition: ∀x ∀y (xRy → yRx)
Example: Sibling is symmetric because if x is a sibling of y, then y is a sibling of x
Non-example: Parent is not symmetric because if x is a parent of y, y is not a parent of x
Transitivity
A relation R is transitive if whenever x is related to y and y is related to z, then x is related to z.
Definition: ∀x ∀y ∀z (xRy ∧ yRz → xRz)
Example: Ancestor is transitive because if x is an ancestor of y and y is an ancestor of z, then x is an ancestor of z
Non-example: Parent is not transitive because if x is a parent of y and y is a parent of z, x is not a parent of z (x is a grandparent)
Equivalence Relations
A relation is an equivalence relation if it is reflexive, symmetric, and transitive.
Examples:
- Equality (=)
- Congruence modulo n
- “Has the same age as”
- “Is in the same class as”
Importance: Equivalence relations partition a set into equivalence classes.
Partial Order Relations
A relation is a partial order if it is reflexive, antisymmetric, and transitive.
Antisymmetry: ∀x ∀y (xRy ∧ yRx → x = y)
Examples:
- Less than or equal to (≤)
- Subset (⊆)
- Divisibility (|)
Total Order Relations
A total order is a partial order where every two elements are comparable.
Definition: ∀x ∀y (xRy ∨ yRx)
Examples:
- Less than or equal to (≤) on real numbers
- Alphabetical order on strings
Inverse Relations
The inverse of a relation R, denoted R⁻¹, is obtained by reversing the order of elements in each tuple.
Definition: (x, y) ∈ R⁻¹ if and only if (y, x) ∈ R
Examples:
- If Parent = {(John, Mary), (Jane, Tom)}, then Parent⁻¹ = {(Mary, John), (Tom, Jane)}
- If Greater = {(5, 3), (3, 2)}, then Greater⁻¹ = {(3, 5), (2, 3)} (which is Less)
Composition of Relations
The composition of relations R and S, denoted R ∘ S, is defined as:
Definition: (x, z) ∈ R ∘ S if there exists y such that (x, y) ∈ S and (y, z) ∈ R
Example:
- Let Parent = {(John, Mary), (Mary, Alice)}
- Let Sibling = {(Mary, Tom), (Tom, Mary)}
- Then Parent ∘ Sibling = {(John, Tom)} (John is the parent of Mary’s sibling Tom)
Functions as Relations
A function is a special type of relation where each input has exactly one output.
Definition: A relation f is a function if ∀x ∀y ∀z ((x, y) ∈ f ∧ (x, z) ∈ f → y = z)
Examples:
- f(x) = x² is a function
- Parent is not a function (a person can have multiple parents)
- Age is a function (each person has exactly one age)
Applications
In Mathematics
Example: Define the divisibility relation:
Divides(x, y) = "x divides y" (y is divisible by x)
Properties:
- Reflexive: x divides x
- Transitive: if x divides y and y divides z, then x divides z
- Not symmetric: 2 divides 4, but 4 doesn’t divide 2
In Computer Science
Database Relations:
Student(ID, Name, Age, Major)
Course(CourseID, Title, Credits)
Enrollment(StudentID, CourseID, Grade)
Graph Relations:
Edge(x, y) = "there is an edge from x to y"
Path(x, y) = "there is a path from x to y"
In Artificial Intelligence
Knowledge Representation:
Knows(person, fact)
Believes(agent, proposition)
Causes(event1, event2)
Practice Problems
Problem 1: Identify Predicate Type
Classify each as unary, binary, or n-ary:
- Tall(x)
- Taller(x, y)
- Between(x, y, z)
Solution:
- Unary (one argument)
- Binary (two arguments)
- Ternary/3-ary (three arguments)
Problem 2: Evaluate Predicates
Given:
- Human(Socrates) = true
- Mortal(x) = true for all x
- Parent(John, Mary) = true
Evaluate:
- Human(Socrates) ∧ Mortal(Socrates)
- Parent(Mary, John)
- ∀x (Human(x) → Mortal(x))
Solution:
- true ∧ true = true
- false (John is Mary’s parent, not vice versa)
- true (all humans are mortal)
Problem 3: Identify Relation Properties
For the relation “is equal to” (=), identify which properties it has:
- Reflexive?
- Symmetric?
- Transitive?
Solution:
- Reflexive: Yes (x = x for all x)
- Symmetric: Yes (if x = y then y = x)
- Transitive: Yes (if x = y and y = z then x = z)
- Therefore, it’s an equivalence relation
Problem 4: Compose Relations
Given:
- Parent = {(John, Mary), (Mary, Alice)}
- Sibling = {(Mary, Tom)}
Find Parent ∘ Sibling
Solution:
- (John, Tom) ∈ Parent ∘ Sibling because (John, Mary) ∈ Parent and (Mary, Tom) ∈ Sibling
- Result: Parent ∘ Sibling = {(John, Tom)}
Related Resources and Tools
Online Learning Platforms
- Stanford Encyclopedia of Philosophy - Relations - Academic treatment
- Khan Academy - Relations and Functions - Video tutorials
- Coursera - Discrete Mathematics - University course
- MIT OpenCourseWare - Mathematics for Computer Science - Free materials
Interactive Tools
- Relation Visualizer - Wolfram MathWorld - Visualize relations
- Logic Evaluator - Logic Online - Evaluate predicates
- Graph Visualizer - Graphviz - Visualize relation graphs
- Truth Table Generator - Stanford Tool - Create tables
Recommended Books
- “Introduction to Logic” by Irving M. Copi and Carl Cohen - Classic textbook
- “A Concise Introduction to Logic” by Patrick J. Hurley - Accessible introduction
- “Discrete Mathematics and Its Applications” by Kenneth Rosen - Comprehensive treatment
- “forall x: An Introduction to Formal Logic” by P.D. Magnus - Free online textbook
Academic Journals
- Journal of Symbolic Logic - Leading journal on mathematical logic
- Studia Logica - International journal on logic and philosophy
- Logic and Logical Philosophy - Open access journal
Software Tools
- Prolog - Logic programming language
- Coq - Interactive theorem prover
- Isabelle - Generic proof assistant
- Z3 - SMT solver
Glossary of Key Terms
- Antisymmetry: Property where xRy ∧ yRx → x = y
- Binary Relation: Relation between two objects
- Equivalence Relation: Reflexive, symmetric, and transitive relation
- Function: Relation where each input has exactly one output
- Inverse Relation: Relation obtained by reversing tuple order
- N-ary Predicate: Predicate with n arguments
- Partial Order: Reflexive, antisymmetric, and transitive relation
- Predicate: Function mapping objects to true/false
- Reflexive: Property where xRx for all x
- Relation: Set of tuples satisfying a predicate
- Symmetric: Property where xRy → yRx
- Transitive: Property where xRy ∧ yRz → xRz
- Unary Predicate: Predicate with one argument
Conclusion
Predicates and relations are fundamental tools for expressing properties and connections in logic. By mastering predicates and relations, you develop the ability to:
- Express complex mathematical and logical statements
- Reason about properties and relationships
- Design databases and knowledge bases
- Understand formal specifications
- Apply logic to real-world problems
The next article in this series will explore Translating English to Predicate Logic, learning how to convert natural language statements into formal logical notation.
What types of relations do you encounter most in your work? Have you used predicates in databases or logic programming? Share your examples in the comments below!
Comments