Relation
see set, math notation
equiv graph
definition a relation RR between two sets A and B is a sub‹set of the cartesian product of those sets
definition formally in my math notation a relation is a set theoryetical function that takes two objects and returns whether they are related
definition
RR a b = A a /\ B b /\ P a b, where
RRis a relation between elements ofAandBPis a predicate
notation
membership in my math notation RR x y
membership in conventional math notation \(x \mathcal R y\)
Inverse Relation
equiv matrix › transpose
equiv c ‹combinator
definition rr RR
notation rr RR
Homogeneous Relation
aka endorelation, relation on a set
definition a homogeneous relation on a set A is a relation from A to A
Reflexive Relation
every element is related to itself
equiv category › identity law
definition a homogeneous ‹relation is said to be reflexive if RR x x for all x
Reflexive Closure
definition the reflexive closure of a relation is the smallest reflexive ‹relation that contains it --- Wikipedia
definition the reflexive closure of a relation R is R \/ {=}
Symmetric Relation
swapping arguments never changes the result
equiv undirected graph
equiv symmetric matrix
equiv category › isomorphism
definition a homogeneous ‹relation is said to be symmetric if RR x y < RR y x for all x and y
definition a homogeneous ‹relation is said to be symmetric if {= rr} RR
Symmetric Closure
definition the symmetric closure of a relation is the smallest symmetric ‹relation that contains it --- Wikipedia
definition the symmetric closure of a relation R is {\/ rr} R
Transitive Relation
middleman can always be cut out
equiv category › composition
definition a homogeneous ‹relation is said to be transitive if RR x y /\ RR y z < RR x z for all x, y, and z
Transitive Closure
definition the transitive closure of a relation is the smallest transitive ‹relation that contains it --- Wikipedia
Equivalence Relation
--- https://en.wikipedia.org/wiki/Partition_of_a_set
definition a homogeneous ‹relation is said to be an equivalence relation if it is reflexive, symmetric and transitive
properties
every equivalence relation on a set induces a set› partition of that set, whose elements we call equivalence classes
Antisymmetric Relation
distinct elements can't be related in both directions
if related both ways then must be identical
--- https://en.wikipedia.org/wiki/Antisymmetric_relation
definition a homogeneous ‹relation is said to be antisymmetric if RR x y /\ RR y x < x = y for all x and y
properties
an antisymmetric relation is a weaker asymmetric relation that allows for reflexivity
Asymmetric Relation
elements can't be related in both directions
if related one way then not related the other
--- https://en.wikipedia.org/wiki/Asymmetric_relation
definition a homogeneous ‹relation is said to be asymmetric if RR x y < +RR y x for all x and y
definition a homogeneous ‹relation is said to be asymmetric if {+ > rr} RR
properties
a relation is asymmetric if and only if it is both antisymmetric and irreflexive
Irreflexive Relation
no element is related to itself
definition a homogeneous ‹relation on said to be irreflexive if +RR x x for all x
Connected Relation
distinct elements are related in at least one direction
--- https://en.wikipedia.org/wiki/Connected_relation
definition a homogeneous ‹relation is said to be connected if x + y < {\/ rr} RR x y for all x and y
properties
a connected relation is a weaker strongly connected relation that allows for irreflexivity --- me
Strongly Connected Relation
elements are related in at least one direction
--- https://en.wikipedia.org/wiki/Connected_relation
definition a homogeneous ‹relation is said to be strongly connected if {\/ rr} RR x y for all x and y