CS2501 Discrete Mathematics

Posted on Edited on Word count in article: 11k Reading time ≈ 39 mins.

This is a note for CS2501 Discrete Mathematics (离散数学) for information security major in SJTU. It is originally written in Chinese to keep consistency with the course language, and later translated to English.

Discrete mathematics mainly contains 3 parts: graph theory, logic, and set theory. Graph theory introduces basic concept of graphs, eulerian and hamiltonian paths and circuits, trees and spanning trees. Logic part introduces propositional logic and predicate logic, including syntax, semantics, equivalence, and inference. Set theory part introduces basic set concepts, relations, functions, and combinatorics.

Graph Theory

When reading this part, take note of CS2501 Data Structure (Not available yet) for reference, especially for algebraic representation of graphs, trees and minimum spanning trees.

Concept of Graphs

The ordered pair is called a graph, where:

  • is a non-empty set called the vertex set;
  • is the set of edges between the vertices.

is a common representation.

Graphs can be divided into finite graphs and infinite graphs. This course only discusses finite graphs.

Loop: An edge associated with only one node.

Multiple edge: Multiple edges existing between the same pair of nodes.

Degree: , the number of edges associated with a node.

  • Out-degree: , the number of edges for which the current node is the starting point.
  • In-degree: , the number of edges for which the current node is the endpoint.
  • Isolated vertex: A vertex with degree 0.
  • Pendant vertex/Pendant edge: A vertex with degree 1 / The edge associated with a pendant vertex.
  • Odd vertex/Even vertex: A vertex with odd/even degree.
  • Regular graph: A graph where all vertices have the same degree, denoted as a -regular graph.

Clearly, .

  • Simple graph: An undirected graph where there is at most one edge between any two nodes and no loops.
  • Empty graph: A simple graph with no edges.
  • Trivial graph: An empty graph with only one vertex.
  • Complete graph: , a simple graph where there is an edge between any two nodes. Clearly, every node in has degree .
  • Weighted graph: A graph where each edge is assigned a real number as its weight.
  • Positive weight graph: A weighted graph where the weight of each edge is a positive real number.

Subgraph: Given , a graph satisfying and .

  • Spanning subgraph: A subgraph satisfying .
  • Induced subgraph: contains all edges of between the vertex subset .
  • Trivial subgraph: itself and the empty graph.

Given two graphs and , we can define the following operations:

  • Union:
  • Intersection:
  • Symmetric difference: , where .

Complement graph: The complement of is .

Out-neighborhood set/Immediate successor set: .

In-neighborhood set/Immediate predecessor set: .

Basic Properties of Graphs

  1. , where is the number of edges in the graph.
  2. (Easily derived from Property 1) The number of vertices with odd degree in must be even.
  3. In a directed graph , the sum of out-degrees equals the sum of in-degrees.
  4. The number of edges in is .
  5. (Derived from degree range and Pigeonhole principle) In a non-empty simple graph , there must exist vertices with the same degree.

Graph Isomorphism

Given two graphs and , if there exists a bijection between and such that if and only if , then these two graphs are said to be isomorphic, denoted as .

Currently, there is no effective algorithm for determining graph isomorphism. The following are necessary conditions for graph isomorphism, used only to determine non-isomorphism:

  • and .
  • The non-increasing sequences of vertex degrees of and are the same.
  • There exist isomorphic induced subgraphs.

Algebraic Representation of Graphs

Adjacency Matrix

In a directed unweighted graph, if there is a directed edge from vertex to vertex , then . If the edge is assigned with a weight , then .

In an undirected unweighted graph, if there is an edge between vertex and vertex , then .

Adjacency matrix can represent loops but cannot represent multiple edges.

Incidence Matrix

Let , then the incidence matrix is an matrix. Incidence matrix can represent multiple edges, but cannot represent loops.

In a directed graph:

  • means is the starting point of edge .
  • means is the endpoint of edge .
  • means is not incident with edge .

In an undirected graph:

  • means is incident with edge .
  • means is not incident with edge .

Adjacency List

Storing a graph in the form of linked lists. Adjacency lists can represent loops and multiple edges.

Walks and Circuits

Basic Definitions

Directed walk: In a directed graph , if an edge sequence satisfies that in , is the endpoint of and is the starting point of , then is called a directed walk in .

Similarly, undirected walks are defined by alternating vertex-edge sequences.

Directed circuit: A directed walk whose endpoint and starting point are the same.

Simple directed walk/Simple directed circuit: A walk/circuit with no repeated edges.

Elementary directed walk/Elementary directed circuit: A simple directed walk/circuit with no repeated vertices.

The definitions of simple undirected walk/simple undirected circuit/elementary undirected walk/elementary undirected circuit can be understood similarly.

Connected graph: In an undirected graph, there exists a walk between any two vertices. For directed graphs, their direction is not considered. A disconnected graph is the opposite.

Maximal connected subgraph/Connected component: A connected subgraph that is not a proper subgraph of any connected subgraph of the graph. Each connected component of a graph is an induced subgraph of it.

Strongly connected vertices: In a directed graph, there exist paths between two vertices that reach each other.

Strongly connected graph: Every two vertices of a directed graph are strongly connected.

Strongly connected component: A maximal strongly connected subgraph of a directed non-strongly connected graph.

Chord: An edge whose two endpoints are both in an elementary circuit but are not adjacent in that elementary circuit.

Maximal elementary walk: An elementary walk whose two endpoints are not adjacent to vertices outside the elementary walk itself.

Any elementary walk, if not a maximal elementary walk, has at least one endpoint adjacent to a vertex outside the elementary walk itself. To create a maximal elementary walk, simply extend the elementary walk by including that vertex, repeat this process until it becomes a maximal elementary walk.

Bipartite graph: If the vertex set of a graph can be partitioned into two disjoint non-empty subsets such that the two endpoints of every edge of the graph lie in different subsets, then the graph is called a bipartite graph, denoted as . The bipartition subsets of a bipartite graph may not be unique.

Complete bipartite graph: A bipartite graph where every vertex in one subset is adjacent to every vertex in the other subset, denoted as , where , .

A graph containing a subgraph must not be bipartite.

Eulerian Walks and Eulerian Circuits

Eulerian circuit/walk: A simple circuit/walk in an undirected connected graph that traverses every edge.

A necessary and sufficient condition for an undirected connected graph to have an Eulerian circuit is that the degree of each vertex in the graph is even.

Proof of necessity is trivial, and proof of sufficiency can be done recursively since there must exist an elementary circuit in the graph.

If there are only 2 vertices with odd degree in an undirected connected graph, then the graph contains an Eulerian walk. This theorm can be proved by adding an edge between the two odd-degree vertices to make all degrees even, then removing that edge after finding the Eulerian circuit.

Hamiltonian Walks and Circuits

Hamiltonian circuit/walk: An elementary circuit/walk in an undirected graph that visits all vertices. H-circuit/walk problems generally refer to simple graphs.

Sufficiency Theorem 1: If the sum of the degrees of any two vertices in a simple graph is greater than or equal to , then the graph contains a Hamiltonian walk.

Corollary: If the sum of the degrees of any two vertices in a simple graph is greater than or equal to the number of vertices, then the graph contains a Hamiltonian circuit.

Closure of a graph: If and are non-adjacent vertices in satisfying , then let . The final graph obtained is the closure of , denoted as .

The closure of a simple graph is unique.

If there exist two non-adjacent vertices and in a simple graph satisfying , then a necessary and sufficient condition for to have an H-circuit is that has an H-circuit.

Sufficiency Theorem 2: A necessary and sufficient condition for a simple graph to have a Hamiltonian circuit is that its closure has a Hamiltonian circuit.

Necessity Theorem: If is a Hamiltonian graph, then for every non-empty proper subset of , we have , where is the number of connected components of .

Proof: Let be the Hamiltonian circuit, then .

Corollary: Hamiltonian graphs have no cut vertices.

If a Hamiltonian graph alternately labels each vertex, the numbers of the two types of points are the same. Graphs that cannot be labeled (e.g., ) cannot be judged.

A graph that has only a Hamiltonian walk and no Hamiltonian circuit is not a Hamiltonian graph.

There is currently no necessary and sufficient criterion for determining Hamiltonian graphs; judgment for graphs with few vertices relies on experience.

Trees

Definition

Forest: A graph containing no circuits.

Tree: A forest with only one connected component, i.e., a connected graph containing no circuits.

Leaf: A vertex of degree 1.

Cut edge: An edge that does not belong to any circuit. Every edge of a tree is a cut edge.

Spanning tree: A tree that is a spanning subgraph of a graph.

Any undirected connected graph has a spanning tree. Spanning trees are not unique.

Cospanning tree: The subgraph formed by removing the spanning tree from the graph.

The cospanning tree is not necessarily connected, not necessarily circuit-free, therefore it is not necessarily a tree, let alone a spanning tree.

Properties of Trees

The following properties are equivalent:

  • A tree is connected and circuitless.
  • A tree is connected and every edge is a cut edge.
  • A tree is connected and has exactly edges.
  • There is a unique walk between any two vertices in a tree.
  • A tree has no circuits, but adding any edge between two vertices creates exactly one circuit.

A tree is a minimally connected graph and also a maximally circuitless connected graph.

There must exist leaf vertices in a tree.

Binary Trees, Huffman Trees

Data structure content, omitted.

Minimum Spanning Tree

Kruskal’s algorithm: Continuously add the current shortest edge to the tree; if it forms a circuit, delete it.

Prim’s algorithm: Arbitrarily select a vertex to form a set, select the shortest edge incident to the vertex set, and add the other endpoint to the vertex set.

Mathematical Logic

Basic Concepts of Propositional Logic

Propositions

Proposition: A declarative sentence that is either true or false (not both). A proposition should only have two values: True (T) and False (F).

True/False proposition: A declarative sentence that matches the facts is a true sentence, otherwise it is a false sentence.

Propositional variable: A symbol representing an arbitrary proposition.

Simple proposition (atomic proposition): A proposition that contains no connectives. A simple proposition cannot be further decomposed.

Compound proposition: A new proposition formed by connecting one or several simple propositions with connectives.

Propositional Connectives and Truth Tables

Negation: Symbol .
T F
F T

Conjunction (and): Symbol

T T T
T F F
F T F
F F F

Disjunction (or): Symbol .
T T T
T F T
F T T
F F F

Conditional proposition (implication): Symbol , meaning if P then Q. .
T T T
T F F
F T T
F F T

A conditional proposition is false only when the antecedent is true and the consequent is false. Actually, constitutes a complete set of connectives.

Biconditional proposition (equivalence): Symbol , read as if and only if. .
T T T
T F F
F T F
F F T

Exclusive or: Symbol .
T T F
T F T
F T T
F F F

For a compound proposition composed of propositional variables, its truth table has rows, meaning there are interpretations.

Well-Formed Formulas

Well-formed formula (WFF): A propositional formula is derived from the following rules:

  • A simple proposition is a well-formed formula.
  • If is a well-formed formula, then is also a well-formed formula.
  • If and are well-formed formulas, then , , , and are also well-formed formulas.
  • Only formulas constructed by the above methods are well-formed formulas.

Precedence of connectives: highest, then , then , then and lowest.

Tautology: A well-formed formula that is true under all interpretations.

Contradiction: A well-formed formula that is false under all interpretations.

Satisfiable formula: A well-formed formula that is true under some interpretation.

Substitution rule: If is a well-formed formula, and formula is obtained by applying the substitution rule to , and if is a tautology, then is also a tautology. To ensure the substitution rule preserves tautologies, only atomic propositions can be substituted, and all occurrences of the same propositional variable must be replaced by the same formula.

Formalization of Propositions

Commonly used expressions are infix expressions, i.e., expressions where connectives are placed between their two operands.

  • Polish notation (prefix expression): An expression where connectives precede their operands.
  • Reverse Polish notation (postfix expression): An expression where connectives follow their operands.

Equivalence and Deductive Inference in Propositional Logic

Equivalence Theorem

Equivalence: For two propositions, if for all interpretations constructed from all propositional variables appearing in them, the two propositions have exactly the same truth value under the same interpretation, then the two propositions are said to be equivalent, denoted as or .

Equivalence theorem: For any well-formed formulas and , if and only if is a tautology.

The equivalence symbol is not a connective; it is only a symbol representing the relation. Equivalence is reflexive, symmetric, and transitive. These attributes will be refered in Part Set Theory.

Equivalent Formulas

Double negation law: .

Associative laws:

  • ;
  • .
  • .

Commutative laws:

  • ;
  • ;
  • .

Distributive laws:

  • ;
  • .
  • ;

De Morgan’s laws:

  • ;
  • .
  • .
  • .

Identity laws:

  • ;
  • .
  • .
  • .
  • .
  • .
  • .
  • .

Replacement Rule

For a subformula of formula , replacing it with an equivalent formula is called replacement.

Replacement and substitution are different. Replacement only requires substituting some subformula of , not necessarily all identical subformulas.

Complete Sets of Connectives

  • Exclusive or: , .
  • NAND: , .
  • NOR: , .

For each interpretation of propositional variables, a connective can give 2 different judgments: true or false. For the group of propositional variables above, we can construct interpretations, each has 2 possible judgments to choose. Thus, kinds of connectives can be defined, where is the number of propositional variables.

Basis: The smallest complete set of connectives.

Dual Formulas

Dual formula: Given a well-formed formula , replace every with , every with , and replace all occurrences of with , all occurrences of with . The resulting formula is called the dual of , denoted as .

Denote , where are all propositional variables appearing in .

  • , $(A^)^=A$;
  • $\neg (A^)=(\neg A)^\neg (A^-)=(\neg A)^-$;
  • .

Normal Forms

Normal form theorem: Any propositional formula has an equivalent disjunctive normal form and an equivalent conjunctive normal form.

  • Eliminate biconditionals and conditionals.
  • Push negations inward to propositional variables.
  • Use equivalence transformations.

Minterm: A well-formed formula composed of propositional variables, where each propositional variable appears exactly once, either as the variable itself or as its negation, is called a minterm of the propositional variables.

Encoding: Arrange the propositional variables in a certain order. Represent being true as 1, false as 0. This gives a binary number, and thus a decimal number, which is called the encoding of that minterm.

Principal disjunctive normal form: The disjunctive normal form consisting of the disjunction of all minterms for which the formula is true.

Principal conjunctive normal form: The conjunctive normal form consisting of the conjunction of all maxterms for which the formula is false.

Refer to materials about digital electronics.

Deductive Inference

Inference rules:

  • Premise introduction: Premises can be introduced at any time during the inference process.
  • Conclusion citation: Intermediate conclusions obtained during the inference process can be used as premises for subsequent inference.
  • Substitution rule: Can be applied to propositional variables of tautologies.
  • Replacement rule: Any subformula can be replaced by an equivalent formula.
  • Detachment rule (Modus Ponens): From and , one can infer .
  • Conditional proof: A conditional as a conclusion can be used as a condition.

Resolution Reasoning

That is, after converting the formula into conjunctive normal form, use the detachment rule and conditional proof for inference.

Predicate Logic

Predicates and Individual Terms

Predicate: A word that indicates a property of an object or a relationship between objects. In a proposition, if there is more than one subject, the word indicating the relationship between these subjects is called a predicate. This is a multi-place predicate, denoted by , , , …

Individual term: A word that denotes a specific object.

Domain of discourse (Universe): The set of all possible individuals in predicate logic.

Well-Formed Formulas

Quantifiers are restricted to act on individual variables. Quantifiers are not allowed to act on propositional variables or predicate variables, and predicates of predicates are not discussed.

Focus on first-order predicate logic, not higher-order predicate logic.

  • Propositional constants, propositional variables, and atomic predicate formulas are all well-formed formulas.
  • If is a well-formed formula, then is also a well-formed formula.
  • If and are well-formed formulas, and no variable is bound in and free in , then , , , and are also well-formed formulas.
  • If is a well-formed formula, and is an individual variable in , then and are also well-formed formulas.
  • Only formulas constructed by the above methods are well-formed formulas.

Formalization of Natural Language Statements

The following are some common examples of formalizing natural language statements.

All rational numbers are real numbers: , where means “ is a rational number”, means “ is a real number”.

Cannot be expressed as , because that means “All numbers are rational and real”.

Some real numbers are rational numbers: , where means “ is a rational number”, means “ is a real number”.

Cannot be expressed as , because that means “There exists a number such that if it is real, then it is rational”.

No irrational number is a rational number: , where means “ is a rational number”, means “ is an irrational number”.

Can also be expressed as or , which are logically equivalent.

Analysis of Multiple Quantifications on Predicate Variables

  • , the order of the two quantifiers in this formula can be interchanged, equivalent to .
  • , the order of the two quantifiers in this formula can be interchanged, equivalent to .
  • , the order of the two quantifiers in this formula cannot be interchanged; it is generally not equivalent to .

Formula Representation of Quantifiers in Finite Domains

In a finite domain :

  • ;
  • .

Multiple quantification formulas: Taking binary as an example,

  • ;
  • ;
  • ;
  • .

Universal Validity and the Decision Problem of Formulas

Universally valid formula: A well-formed formula that is true under every interpretation in every domain.

Satisfiable: A well-formed formula that is true under some interpretation in some domain.

Decidable: There exists an algorithm that can decide whether any well-formed formula is universally valid.

Equivalence Calculus in Logic

Negation-type Equivalences

In predicate logic, what needs to be interpreted includes: the domain, predicate variables, propositional variables, functions, free individuals.

Generalization of De Morgan’s laws:

  • ;
  • .

Quantifier Distribution Equivalences

The distribution laws of quantifiers over and are as follows:

  • , where does not occur in ;
  • , where does not occur in ;
  • , where does not occur in ;
  • , where does not occur in .

Quantifier distribution over :

  • , where does not occur in ;
  • , where does not occur in .
  • , where does not occur in ;
  • , where does not occur in .

Distribution of over , over :

  • ;
  • .

Distribution laws after variable renaming:

  • ;
  • .

Normal Forms

Prenex normal form: All quantifiers are at the very front of the formula, followed by a quantifier-free formula.

Suffix normal form: All quantifiers are at the very end of the formula, preceded by a quantifier-free formula.

Skolem standard form: A prenex form that does not retain existential quantifiers, only retains universal quantifiers, and converts existentially quantified free variables within the scope into function forms.

Skolem standard form is not equivalent to the original prenex normal form.

Basic Inference Formulas

The basic form of inference is .

The converses of these inference formulas generally do not hold.

Deductive Calculus

Universal quantifier elimination rule (Universal Instantiation): From , one can infer , where is any individual constant in the domain.

Universal quantifier introduction rule (Universal Generalization): If holds, and is an arbitrary individual constant in , then one can infer .

Existential quantifier introduction rule (Existential Generalization): From , one can infer , where is any individual constant in the domain.

Existential quantifier elimination rule (Existential Instantiation): If holds, and from one can infer , where is an arbitrary individual constant in both and , then one can infer .

First eliminate existential quantifiers, then eliminate universal quantifiers, and finally perform propositional logic resolution reasoning. Introduction has no restrictions.

Resolution Reasoning

To prove that is a theorem (, are predicate formulas), i.e., , it is equivalent to prove that is a contradiction. This is the starting point of the resolution method (proof by contradiction).

Set Theory

Sets

Concepts and Representation of Sets

A set is the most basic concept in set theory but is difficult to give a precise definition. As a result, the set is the only concept not defined in set theory, but it is easy to understand and grasp.

Set: A collection of distinct, distinguishable things gathered together to form a whole. Each thing that makes up a set is called an element of the set. If is an element of set , we say belongs to , or is in , denoted . If is not an element of set , we say does not belong to , or is not in , denoted .

The elements in a set are unordered and mutually distinct. Whether any given thing belongs to a given set is determinate.

Roster (Extensional) notation: The method of representing a set by listing all its elements within braces.

Set-builder (Intensional) notation: The method of representing a set by using a property or condition that all elements satisfy. Generally, if is a predicate formula concerning only , then set can be represented as .

Russell’s paradox: The set of all sets cannot be studied. If such set exists, axiom separation rule of set theory ensures the existence of set . If , then by definition of , ; if , then by definition of , . This leads to a contradiction.

Relations Between Sets and Special Sets

Equality: If all elements of set and set are exactly the same, then set and set are said to be equal, denoted ; otherwise, they are not equal, denoted . That is: , .

Principle of extensionality: The same set can be represented by different methods.

Subset: If every element of set is also an element of set , then set is called a subset of set , denoted ; otherwise, set is not a subset of set , denoted . That is: .

Two sets are equal if and only if they are subsets of each other, that is: .

The subset relation is reflexive, antisymmetric, and transitive:

  • ;
  • ;
  • .

Proper subset: If set is a subset of set , and set is not equal to set , then set is called a proper subset of set , or is a proper superset of , denoted ; otherwise, set is not a proper subset of set , denoted . That is: .

Empty set: The set containing no elements, denoted . That is: .

For any set , . The empty set is unique.

Universal set: In a given problem, the set of all things under consideration is called the universal set, denoted , i.e., . The universal set corresponds to the domain of discourse in predicate logic.

Set Operations

  • Union: .
  • Intersection: .
  • Difference (Relative complement): .
  • Complement (Absolute complement): . The absolute complement is the relative complement with respect to .
  • Symmetric difference: .
  • Generalized union: , where is a non-empty set of sets.
  • Generalized intersection: , where is a non-empty set of sets.

Specifically, , and is meaningless.

Power set: Let be a set and the set of all subsets of is called the power set of , denoted , i.e., . All elements of the power set are sets, and the number of elements is .

Define the ordered pair as the set . -tuples can be recursively defined as .

Cartesian product: Let and be two sets. The set of all ordered pairs (where and ) is called the Cartesian product of set and set , denoted , i.e., .

The -ary Cartesian product is defined as .

Precedence of set operations

  • Unary operators (, , , ) take precedence over
  • Binary operators (, , , , ) take precedence over
  • Set relation symbols (, , , ) take precedence over
  • Unary connectives () take precedence over
  • Binary connectives (, , , ) take precedence over
  • Logical relation symbols (, ).

Additionally, parentheses following mathematical conventions denote priority, with left-to-right priority for equal precedence.

  • Inside parentheses takes precedence over outside.
  • Inside the same parentheses, follow the above priorities.
  • Inside the same parentheses, for operations with the same priority, follow left-to-right order.

Graphical Representation of Sets

Graphical representations (e.g., Venn diagrams, Hasse diagrams) are more intuitive but lack rigorous theoretical foundation; they can only be used for illustration, not for strict mathematical proof.

Properties and Proofs of Set Operations

Some properties of , , and

  • Commutative laws:
    • ;
    • .
  • Associative laws:
    • ;
    • .
  • Distributive laws:
    • ;
    • .
  • Absorption laws:
    • ;
    • .
  • Idempotent laws:
    • ;
    • .
  • Domination (Zero) laws:
    • ;
    • .
  • Identity laws:
    • ;
    • .
  • Complement laws:
    • ;
    • .
  • De Morgan’s laws:
    • ;
    • .

Some properties of

  • ;
  • ;
  • ;
  • .

Some properties of

  • Commutative law: ;
  • Associative law: ;
  • Distributive law: ;
  • Identity law: ;
  • Domination law: .
  • .

Some properties of

Properties of power sets and transitive sets

  • ;
  • ;
  • ;
  • ;
  • ;
  • .

Transitive set: If every element of set is a set, and every element of every element is also an element of set , then set is called a transitive set. That is: is transitive or .

is transitive is transitive.

Properties of generalized union and intersection

If a non-empty set is transitive, then is also transitive.

Properties of Cartesian Product

  • ;
  • If non-empty sets and are not equal, then ;
  • ;
  • If , then , where refers to ;
  • For non-empty sets , .

Cardinality of Finite Set: Define the cardinality (size) of a finite set , denoted , as the number of distinct elements in set .

  • ;
  • ;

Exclusion Principle: Suppose set , where are finite sets (). Then .

Relations

Binary Relations

Binary relation: Let and be two sets. A binary relation from set to set is a subset of the Cartesian product , denoted . If , we say is related to under relation , or and satisfy relation , denoted . Binary relations are simply called relations.

-ary relation: Let be sets. An -ary relation from set to , …, to is a subset of the Cartesian product .

Identity relation: Let be a set. The identity relation from set to set is defined as: .

Universal relation (Total relation): Let be a set. The universal relation from set to set is defined as: .

Empty relation: Let be a set. The empty relation from set to set is defined as: .

Domain: Let be a binary relation from set to set . The set of all elements in that are related to at least one element in is called the domain of relation , denoted , i.e., .

Range: Let be a binary relation from set to set . The set of all elements in that are related to at least one element in is called the range of relation , denoted , i.e., .

Field: Let be a binary relation from set to set . The field of relation , denoted , is .

Relation matrix: Let be a binary relation from set to set . The relation matrix of is an matrix defined by:

Relation graph: Let be a binary relation from set to set . The relation graph of is a directed graph whose vertex set is and whose arc set is .

Inverse of a relation: Let be a binary relation from set to set . The inverse relation from set to set is defined as: . .

Composition of relations: Let be a binary relation from set to set , and a binary relation from set to set . The composition of and is a binary relation from to defined as: . .

Composition is associative but not commutative. The composition operator has higher precedence than set operators.

Restriction of a relation: Let be a binary relation from set to set , and . The restriction of to , denoted , is a binary relation from to defined as: .

Image under a relation: Let be a binary relation from set to set , and . The image of under , denoted , is defined as: .

For a relation from to and a relation from to :

  • ;
  • ;
  • ;
  • .

For relations , from to and relation from to :

  • ;
  • ;

For relation from to and relations , from to :

  • ;

  • .

  • ;

  • ;

  • ;

  • ;

  • .

Properties of Relations

Reflexive relation: Let be a binary relation on a set (i.e., from to ). is reflexive if and only if for every element in , . That is: is reflexive . The identity relation and the universal relation are reflexive.

Irreflexive relation: Let be a binary relation on a set . is irreflexive if and only if for every element in , . That is: is irreflexive . The empty relation is irreflexive.

The union of reflexive and irreflexive relations does not constitute the universal relation. There exist relations that are neither reflexive nor irreflexive.

Symmetric relation: Let be a binary relation on a set . is symmetric if and only if for any two elements and in , if , then . That is: is symmetric . The identity relation is symmetric; the universal relation is also symmetric.

The matrix of a symmetric relation is symmetric.

Antisymmetric relation: Let be a binary relation on a set . is antisymmetric if and only if for any two distinct elements and in , if and , then . That is: is antisymmetric . The identity relation is antisymmetric; the universal relation is not antisymmetric.

Symmetry and antisymmetry can both hold, or both not hold.

The definition of antisymmetry can also be expressed using the contrapositive: if , then .

Transitive relation: Let be a binary relation on a set . is transitive if and only if for any three elements , , and in , if and , then . That is: is transitive . The identity relation is transitive; the universal relation is also transitive.

If and are both reflexive/symmetric, then , , and are also reflexive/symmetric.

If and are both transitive/antisymmetric, then and are also transitive/antisymmetric, but is generally not transitive/antisymmetric.

If is symmetric, then ; if is antisymmetric, then .

Closures of Relations

Power of a relation: Let be a binary relation on a set . The th power (where is a non-negative integer) is defined as:

  • ;
  • .

If is a finite set and is a binary relation on , then there exist positive integers and such that .

  • ;
  • .

Reflexive/Symmetric/Transitive closure: Let be a binary relation on a set . The reflexive closure , symmetric closure , and transitive closure of are defined as:

  • //;
  • // is reflexive/symmetric/transitive;
  • If and is reflexive/symmetric/transitive, then //.

The reflexive/symmetric/transitive closure is the smallest superset of with the reflexive/symmetric/transitive property.

For any binary relation on a non-empty set :

  • is reflexive ;
  • is symmetric ;
  • is transitive .

For binary relations , on a non-empty set , if , then:

  • ;
  • ;
  • .
  • ;
  • ;
  • .

Construction methods for closures

  • Reflexive closure: ;
  • Symmetric closure: ;
  • Transitive closure: .

Warshall’s algorithm:
Let be a finite set, a binary relation on , and the relation matrix of . Define a sequence of matrices , , as follows:

  • ;
  • Then is the relation matrix of the transitive closure of .

For a relation on a non-empty set :

  • If is reflexive, then and are reflexive.
  • If is symmetric, then and are symmetric.
  • If is transitive, then is transitive.

For a relation on a non-empty set :

  • ;
  • ;
  • .

Equivalence Relations and Partitions

Equivalence relation: Let be a binary relation on a set . is called an equivalence relation if and only if is reflexive, symmetric, and transitive.

Equivalence class: Let be an equivalence relation on a set . For any element in , the set of all elements in that are related to under is called the equivalence class of , denoted , i.e., . Geometrically, an equivalence class corresponds to one of the square blocks on the diagonal.

  • ;
  • ;
  • ;

Quotient set: Let be an equivalence relation on a set . The set of all distinct equivalence classes of under is called the quotient set of by , denoted , i.e., .

Partition: Let be a non-empty set. A collection is called a partition of if:

  • For all , ;
  • For all , if , then ;
  • .

The quotient set is the partition of induced by the equivalence relation , denoted . Conversely, a partition induces an equivalence relation .

For a partition of a non-empty set and an equivalence relation , induces if and only if induces .

Tolerance Relations and Coverings

Tolerance relation (Compatibility relation): Let be a binary relation on a set . If is reflexive and symmetric, then is called a tolerance relation on .

Tolerance class: Let be a tolerance relation on a set . For any element in , the set of all elements in related to under is called a tolerance class of , denoted , i.e., .

Maximal tolerance class: Let be a tolerance relation on a set . For any element in , the union of all tolerance classes containing is called the maximal tolerance class of , denoted $[a]_R^[a]_R^=\cup{[b]_R | b \in A \land \langle a,b \rangle \in R}$.

Covering: Let be a non-empty set. A collection is called a covering of if:

  • For all , ;
  • .

A partition is a covering, but a covering is not necessarily a partition. Elements in a covering may intersect.

The set of maximal tolerance classes is a covering of induced by the tolerance relation , denoted , called the complete covering.

Partial Orders

Partial order relation: Let be a binary relation on a set . is called a partial order relation if and only if is reflexive, antisymmetric, and transitive, often denoted .

Quasi-order relation: Let be a binary relation on a set . is called a quasi-order relation if and only if is irreflexive and transitive, often denoted . It can be proven that quasi-order relations are antisymmetric.

Partially ordered set (poset): Let be a non-empty set and a partial order on . The ordered pair is called a partially ordered structure.

Covering relation: Let be a partially ordered set, and . If and there exists no such that , then we say covers . The covering relation of can be defined as: .

Let be a partially ordered set, :

  • If , then is called the least element of ;
  • If , then is called the greatest element of ;
  • If , then is called a minimal element of ;
  • If , then is called a maximal element of .

Difference between least and minimal elements: The least element should be less than or equal to all other elements in ; a minimal element is not greater than any other element in (less than or equal to some, and incomparable to others). The least (greatest) element may not exist, but if it exists, it is unique. A non-empty finite set must have minimal (maximal) elements, but they may not be unique.

  • If , then is called a lower bound of ;
  • If , then is called an upper bound of ;
  • If , then is called the greatest lower bound (or infimum) of , denoted ;
  • If , then is called the least upper bound (or supremum) of , denoted .

The supremum and infimum may or may not be in , but they must be in . Upper (lower) bounds may not exist, and if they exist, they may not be unique. The supremum (infimum) may not exist, but if it exists, it is unique.

Total order relation: Let be a binary relation on a set . is called a total order relation (or linear order) if and only if is a partial order and for any two elements and in , either or holds.

Chain: Let be a partially ordered set. A subset is called a chain in if for any two elements and in , either or holds.

Antichain: Let be a partially ordered set. A subset is called an antichain in if for any two distinct elements and in , neither nor holds.

Dilworth’s theorem (Decomposition theorem for posets): Let be a finite partially ordered set. Then can be partitioned into a number of antichains, and the minimum number of antichains needed equals the length of the longest chain in .

Well-order relation: Let be a binary relation on a set . is called a well-order relation if and only if is a total order and every non-empty subset of has a least element. A well-ordered set must be totally ordered. A finite totally ordered set must be well-ordered.

Well-ordering theorem (Zermelo’s theorem): Every set can be well-ordered. That is, for any set , there exists a well-order relation such that is a well-ordered structure.

Interval: In a totally ordered set , for with , the set is called a closed interval; is an open interval; is a left-closed right-open interval; is a left-open right-closed interval. Intervals including limits can also be defined.

Functions

Functions and the Axiom of Choice

Function: For a relation from set to , if for every , there exists a unique such that , and , then the relation is called a function from set to set , denoted . For , we write or .

Partial function: If , then is called a partial function from set to set , denoted .

In the matrix representation of a function relation, each row has exactly one 1, others 0. In the relation graph of a function, each starting vertex has exactly one outgoing edge.

For sets and , denote the set of all functions from to as . For finite sets and , if and , then .

The empty set and functions. There is exactly one function from to any set , namely the empty function ; there is no function from any non-empty set to . That is: , (when ).

Image under a function: Let be a function, . The image of under , denoted , is defined as: .

Inverse image (Preimage): Let be a function, . The inverse image (or preimage) of under , denoted , is defined as: .

Surjective function (Onto): Let be a function. If , then is called a surjective function from to .

Injective function (One-to-one): Let be a function. If for any two distinct elements and in , , then is called an injective function from to .

Bijective function (One-to-one correspondence): Let be a function. If is both injective and surjective, then is called a bijective function from to .

Specifically, is injective; is bijective.

Constant function: Let be a function. If there exists such that for all , , then is called a constant function.

Identity function: Let be a set. The identity function on is defined as: for all , .

Monotonic increasing/decreasing function: Let and be two totally ordered sets, and a function. If for any , , then is called monotonic increasing. If , then is called monotonic decreasing.

-ary operation: Let be a set, a positive integer. A function is called an -ary operation on .

Functional: Let , , be sets. A function is called a functional on .

A functional maps elements of to functions from to .

Characteristic function: Let . The function defined by:

is called the characteristic function of set .

The characteristic function is another way to represent a set. In fuzzy set theory, membership functions with range are used.

Canonical (Natural) projection: Let be an equivalence relation on a set . The function defined by for all is called the canonical projection of the equivalence relation .

Axiom of Choice: For any relation , there exists a function such that and .

Composition and Inverse of Functions

Composition of functions: Let , . The composition is a function from to defined by for all .

Properties of and Property of
Surjective & Surjective Surjective
Injective & Injective Injective
Bijective & Bijective Bijective
Property of Properties of and
Surjective surjective
Injective injective
Bijective Both and bijective

Inverse of a function: Let . If there exists a function such that for all , and for all , , then is called the inverse function of , denoted .

A function has an inverse if and only if it is bijective.

Left inverse and right inverse: Let be a function.

  • If there exists a function such that , then is called a left inverse of .
  • If there exists a function such that , then is called a right inverse of .

A function has a left inverse if and only if it is injective. It has a right inverse if and only if it is surjective. It has both a left and a right inverse if and only if it is bijective. In that case, the left and right inverses coincide, equaling .