How to determine if a binary relation R on M is a bisimulation?

  • Context: Graduate 
  • Thread starter Thread starter Dragonfall
  • Start date Start date
  • Tags Tags
    Binary Relation
Click For Summary
SUMMARY

A binary relation R on a system M is classified as a bisimulation if it satisfies the condition R ⊆ R', where for elements a, b in M, the relation aR'b holds true if and only if for every child x of a, there exists a child y of b such that xRy, and vice versa. The discussion also introduces the concept of an accessible pointed graph, which is a directed graph featuring a distinguished node from which all other nodes are reachable. The relation ~ defined on the class of all sets V is shown to be a bisimulation, as it captures the necessary conditions for the relation to hold.

PREREQUISITES
  • Understanding of directed graphs and their properties.
  • Familiarity with binary relations and set theory.
  • Knowledge of the concept of bisimulation in mathematical logic.
  • Basic comprehension of accessible pointed graphs.
NEXT STEPS
  • Study the formal definition of bisimulation in the context of modal logic.
  • Explore the properties of directed graphs and their applications in computer science.
  • Learn about the role of accessible pointed graphs in category theory.
  • Investigate examples of bisimulations in various mathematical frameworks.
USEFUL FOR

Mathematicians, computer scientists, and logicians interested in the formal properties of relations in graph theory and modal logic.

Dragonfall
Messages
1,023
Reaction score
5
Let M be a system (possibly proper class-sized directed graph where the class of children of a given node is a set). A binary relation R on M is a BISIMULATION if [tex]R\subset R'[/tex], where for [tex]a, b\in M[/tex]

[tex]aR'b \Leftrightarrow ((\forall x \in a_M\exists y\in b_M xRy) \wedge (\forall x \in b_M\exists y\in a_M xRy))[/tex]

where [tex]a_M[/tex] is the set of children of a in M.

So let ~ be the relation on the class of all sets V such that a~b iff there exists an accessible pointed graph that is the picture of both a and b.

An accessible pointed graph is a directed graph with a distinguished node from where every other node is connected by a path.

Show that ~ is a bisimulation.

I'm not sure what bisimulation says. Can someone explain it in more familiar terms?
 
Physics news on Phys.org
The wording above (quoted from the book) is very bad. It took me a long time to understand that R is a bisimulation if R is contained in the ' operation.
 

Similar threads

Graduate When can transitivity emerge from cycle-suppressing dynamics?
  • · Replies 1 ·
Replies
1
Views
535
MHB Binary Relations and Equivalence Classes | Proving R is an Equivalence Relation
  • · Replies 3 ·
Replies
3
Views
2K
MHB Example for which the relation does not stand
  • · Replies 1 ·
Replies
1
Views
1K
MHB Example of Set for Relation Restriction to A
  • · Replies 1 ·
Replies
1
Views
1K
Graduate Is R Transitive if R^2 is a Subset of R?
  • · Replies 2 ·
Replies
2
Views
2K
MHB What Defines a Nonreflexive Relation in Set Theory?
  • · Replies 3 ·
Replies
3
Views
3K
Undergrad Supremum proof & relation to Universal quantifier
  • · Replies 5 ·
Replies
5
Views
3K
Graduate About the “Axiom of Dependent Choice”
  • · Replies 2 ·
Replies
2
Views
2K
MHB Proper Subsets and Relations of Sets
  • · Replies 1 ·
Replies
1
Views
2K
Binary operation on equivalence classes
  • · Replies 3 ·
Replies
3
Views
2K