Relation closures #

THIS FILE IS SYNCHRONIZED WITH MATHLIB4. Any changes to this file require a corresponding PR to mathlib4.

This file defines the reflexive, transitive, and reflexive transitive closures of relations. It also proves some basic results on definitions in core, such as eqv_gen.

Note that this is about unbundled relations, that is terms of types of the form α → β → Prop. For the bundled version, see rel.

Definitions #

relation.refl_gen: Reflexive closure. refl_gen r relates everything r related, plus for all a it relates a with itself. So refl_gen r a b ↔ r a b ∨ a = b.
relation.trans_gen: Transitive closure. trans_gen r relates everything r related transitively. So trans_gen r a b ↔ ∃ x₀ ... xₙ, r a x₀ ∧ r x₀ x₁ ∧ ... ∧ r xₙ b.
relation.refl_trans_gen: Reflexive transitive closure. refl_trans_gen r relates everything r related transitively, plus for all a it relates a with itself. So refl_trans_gen r a b ↔ (∃ x₀ ... xₙ, r a x₀ ∧ r x₀ x₁ ∧ ... ∧ r xₙ b) ∨ a = b. It is the same as the reflexive closure of the transitive closure, or the transitive closure of the reflexive closure. In terms of rewriting systems, this means that a can be rewritten to b in a number of rewrites.
relation.comp: Relation composition. We provide notation ∘r. For r : α → β → Prop and s : β → γ → Prop, r ∘r srelates a : α and c : γ iff there exists b : β that's related to both.
relation.map: Image of a relation under a pair of maps. For r : α → β → Prop, f : α → γ, g : β → δ, map r f g is the relation γ → δ → Prop relating f a and g b for all a, b related by r.
relation.join: Join of a relation. For r : α → α → Prop, join r a b ↔ ∃ c, r a c ∧ r b c. In terms of rewriting systems, this means that a and b can be rewritten to the same term.

source

theorem is_refl.reflexive {α : Type u_1} {r : α → α → Prop} [is_refl α r] :

reflexive r

source

theorem reflexive.rel_of_ne_imp {α : Type u_1} {r : α → α → Prop} (h : reflexive r) {x y : α} (hr : x ≠ y → r x y) :

r x y

To show a reflexive relation r : α → α → Prop holds over x y : α, it suffices to show it holds when x ≠ y.

source

theorem reflexive.ne_imp_iff {α : Type u_1} {r : α → α → Prop} (h : reflexive r) {x y : α} :

x ≠ y → r x y ↔ r x y

If a reflexive relation r : α → α → Prop holds over x y : α, then it holds whether or not x ≠ y.

source

theorem reflexive_ne_imp_iff {α : Type u_1} {r : α → α → Prop} [is_refl α r] {x y : α} :

x ≠ y → r x y ↔ r x y

If a reflexive relation r : α → α → Prop holds over x y : α, then it holds whether or not x ≠ y. Unlike reflexive.ne_imp_iff, this uses [is_refl α r].

source

@[protected]

theorem symmetric.iff {α : Type u_1} {r : α → α → Prop} (H : symmetric r) (x y : α) :

r x y ↔ r y x

source

theorem symmetric.flip_eq {α : Type u_1} {r : α → α → Prop} (h : symmetric r) :

flip r = r

source

theorem symmetric.swap_eq {α : Type u_1} {r : α → α → Prop} :

symmetric r → function.swap r = r

source

theorem flip_eq_iff {α : Type u_1} {r : α → α → Prop} :

flip r = r ↔ symmetric r

source

theorem swap_eq_iff {α : Type u_1} {r : α → α → Prop} :

function.swap r = r ↔ symmetric r

source

theorem reflexive.comap {α : Type u_1} {β : Type u_2} {r : β → β → Prop} (h : reflexive r) (f : α → β) :

reflexive (r on f)

source

theorem symmetric.comap {α : Type u_1} {β : Type u_2} {r : β → β → Prop} (h : symmetric r) (f : α → β) :

symmetric (r on f)

source

theorem transitive.comap {α : Type u_1} {β : Type u_2} {r : β → β → Prop} (h : transitive r) (f : α → β) :

transitive (r on f)

source

theorem equivalence.comap {α : Type u_1} {β : Type u_2} {r : β → β → Prop} (h : equivalence r) (f : α → β) :

equivalence (r on f)

source

def relation.comp {α : Type u_1} {β : Type u_2} {γ : Type u_3} (r : α → β → Prop) (p : β → γ → Prop) (a : α) (c : γ) :

Prop

The composition of two relations, yielding a new relation. The result relates a term of α and a term of γ if there is an intermediate term of β related to both.

Equations

relation.comp r p a c = ∃ (b : β), r a b ∧ p b c

source

theorem relation.comp_eq {α : Type u_1} {β : Type u_2} {r : α → β → Prop} :

relation.comp r eq = r

source

theorem relation.eq_comp {α : Type u_1} {β : Type u_2} {r : α → β → Prop} :

relation.comp eq r = r

source

theorem relation.iff_comp {α : Type u_1} {r : Prop → α → Prop} :

relation.comp iff r = r

source

theorem relation.comp_iff {α : Type u_1} {r : α → Prop → Prop} :

relation.comp r iff = r

source

theorem relation.comp_assoc {α : Type u_1} {β : Type u_2} {γ : Type u_3} {δ : Type u_4} {r : α → β → Prop} {p : β → γ → Prop} {q : γ → δ → Prop} :

relation.comp (relation.comp r p) q = relation.comp r (relation.comp p q)

source

theorem relation.flip_comp {α : Type u_1} {β : Type u_2} {γ : Type u_3} {r : α → β → Prop} {p : β → γ → Prop} :

flip (relation.comp r p) = relation.comp (flip p) (flip r)

source

def relation.fibration {α : Type u_1} {β : Type u_2} (rα : α → α → Prop) (rβ : β → β → Prop) (f : α → β) :

Prop

A function f : α → β is a fibration between the relation rα and rβ if for all a : α and b : β, whenever b : β and f a are related by rβ, b is the image of some a' : α under f, and a' and a are related by rα.

Equations

relation.fibration rα rβ f = ∀ ⦃a : α⦄ ⦃b : β⦄, rβ b (f a) → (∃ (a' : α), rα a' a ∧ f a' = b)

source

theorem acc.of_fibration {α : Type u_1} {β : Type u_2} {rα : α → α → Prop} {rβ : β → β → Prop} (f : α → β) (fib : relation.fibration rα rβ f) {a : α} (ha : acc rα a) :

acc rβ (f a)

If f : α → β is a fibration between relations rα and rβ, and a : α is accessible under rα, then f a is accessible under rβ.

source

theorem acc.of_downward_closed {α : Type u_1} {β : Type u_2} {rβ : β → β → Prop} (f : α → β) (dc : ∀ {a : α} {b : β}, rβ b (f a) → (∃ (c : α), f c = b)) (a : α) (ha : acc (inv_image rβ f) a) :

acc rβ (f a)

source

@[protected]

def relation.map {α : Type u_1} {β : Type u_2} {γ : Type u_3} {δ : Type u_4} (r : α → β → Prop) (f : α → γ) (g : β → δ) :

γ → δ → Prop

The map of a relation r through a pair of functions pushes the relation to the codomains of the functions. The resulting relation is defined by having pairs of terms related if they have preimages related by r.

Equations

relation.map r f g = λ (c : γ) (d : δ), ∃ (a : α) (b : β), r a b ∧ f a = c ∧ g b = d

Instances for relation.map

relation.map.decidable

source

theorem relation.map_apply {α : Type u_1} {β : Type u_2} {γ : Type u_3} {δ : Type u_4} {r : α → β → Prop} {f : α → γ} {g : β → δ} {c : γ} {d : δ} :

relation.map r f g c d ↔ ∃ (a : α) (b : β), r a b ∧ f a = c ∧ g b = d

source

@[simp]

theorem relation.map_id_id {α : Type u_1} {β : Type u_2} (r : α → β → Prop) :

relation.map r id id = r

source

@[simp]

theorem relation.map_map {α : Type u_1} {β : Type u_2} {γ : Type u_3} {δ : Type u_4} {ε : Type u_5} {κ : Type u_6} (r : α → β → Prop) (f₁ : α → γ) (g₁ : β → δ) (f₂ : γ → ε) (g₂ : δ → κ) :

relation.map (relation.map r f₁ g₁) f₂ g₂ = relation.map r (f₂ ∘ f₁) (g₂ ∘ g₁)

source

@[protected, instance]

def relation.map.decidable {α : Type u_1} {β : Type u_2} {γ : Type u_3} {δ : Type u_4} {r : α → β → Prop} {f : α → γ} {g : β → δ} {c : γ} {d : δ} [decidable (∃ (a : α) (b : β), r a b ∧ f a = c ∧ g b = d)] :

decidable (relation.map r f g c d)

Equations

relation.map.decidable = _inst_1

source

inductive relation.refl_trans_gen {α : Type u_1} (r : α → α → Prop) (a : α) :

α → Prop

refl : ∀ {α : Type u_1} {r : α → α → Prop} {a : α}, relation.refl_trans_gen r a a
tail : ∀ {α : Type u_1} {r : α → α → Prop} {a b c : α}, relation.refl_trans_gen r a b → r b c → relation.refl_trans_gen r a c

refl_trans_gen r: reflexive transitive closure of r

Instances for relation.refl_trans_gen

source

theorem relation.refl_trans_gen.cases_tail_iff {α : Type u_1} (r : α → α → Prop) (a ᾰ : α) :

relation.refl_trans_gen r a ᾰ ↔ ᾰ = a ∨ ∃ {b : α}, relation.refl_trans_gen r a b ∧ r b ᾰ

source

inductive relation.refl_gen {α : Type u_1} (r : α → α → Prop) (a : α) :

α → Prop

refl : ∀ {α : Type u_1} {r : α → α → Prop} {a : α}, relation.refl_gen r a a
single : ∀ {α : Type u_1} {r : α → α → Prop} {a b : α}, r a b → relation.refl_gen r a b

refl_gen r: reflexive closure of r

Instances for relation.refl_gen

relation.refl_gen.is_refl

source

theorem relation.refl_gen_iff {α : Type u_1} (r : α → α → Prop) (a ᾰ : α) :

relation.refl_gen r a ᾰ ↔ ᾰ = a ∨ r a ᾰ

source

inductive relation.trans_gen {α : Type u_1} (r : α → α → Prop) (a : α) :

α → Prop

single : ∀ {α : Type u_1} {r : α → α → Prop} {a b : α}, r a b → relation.trans_gen r a b
tail : ∀ {α : Type u_1} {r : α → α → Prop} {a b c : α}, relation.trans_gen r a b → r b c → relation.trans_gen r a c

trans_gen r: transitive closure of r

Instances for relation.trans_gen

source

theorem relation.trans_gen_iff {α : Type u_1} (r : α → α → Prop) (a ᾰ : α) :

relation.trans_gen r a ᾰ ↔ r a ᾰ ∨ ∃ {b : α}, relation.trans_gen r a b ∧ r b ᾰ

source

theorem relation.refl_gen.to_refl_trans_gen {α : Type u_1} {r : α → α → Prop} {a b : α} :

relation.refl_gen r a b → relation.refl_trans_gen r a b

source

theorem relation.refl_gen.mono {α : Type u_1} {r p : α → α → Prop} (hp : ∀ (a b : α), r a b → p a b) {a b : α} :

relation.refl_gen r a b → relation.refl_gen p a b

source

@[protected, instance]

def relation.refl_gen.is_refl {α : Type u_1} {r : α → α → Prop} :

is_refl α (relation.refl_gen r)

source

@[trans]

theorem relation.refl_trans_gen.trans {α : Type u_1} {r : α → α → Prop} {a b c : α} (hab : relation.refl_trans_gen r a b) (hbc : relation.refl_trans_gen r b c) :

relation.refl_trans_gen r a c

source

theorem relation.refl_trans_gen.single {α : Type u_1} {r : α → α → Prop} {a b : α} (hab : r a b) :

relation.refl_trans_gen r a b

source

theorem relation.refl_trans_gen.head {α : Type u_1} {r : α → α → Prop} {a b c : α} (hab : r a b) (hbc : relation.refl_trans_gen r b c) :

relation.refl_trans_gen r a c

source

theorem relation.refl_trans_gen.symmetric {α : Type u_1} {r : α → α → Prop} (h : symmetric r) :

symmetric (relation.refl_trans_gen r)

source

theorem relation.refl_trans_gen.cases_tail {α : Type u_1} {r : α → α → Prop} {a b : α} :

relation.refl_trans_gen r a b → (b = a ∨ ∃ (c : α), relation.refl_trans_gen r a c ∧ r c b)

source

theorem relation.refl_trans_gen.head_induction_on {α : Type u_1} {r : α → α → Prop} {b : α} {P : Π (a : α), relation.refl_trans_gen r a b → Prop} {a : α} (h : relation.refl_trans_gen r a b) (refl : P b relation.refl_trans_gen.refl) (head : ∀ {a c : α} (h' : r a c) (h : relation.refl_trans_gen r c b), P c h → P a _) :

P a h

source

theorem relation.refl_trans_gen.trans_induction_on {α : Type u_1} {r : α → α → Prop} {P : Π {a b : α}, relation.refl_trans_gen r a b → Prop} {a b : α} (h : relation.refl_trans_gen r a b) (ih₁ : ∀ (a : α), P relation.refl_trans_gen.refl) (ih₂ : ∀ {a b : α} (h : r a b), P _) (ih₃ : ∀ {a b c : α} (h₁ : relation.refl_trans_gen r a b) (h₂ : relation.refl_trans_gen r b c), P h₁ → P h₂ → P _) :

P h

source

theorem relation.refl_trans_gen.cases_head {α : Type u_1} {r : α → α → Prop} {a b : α} (h : relation.refl_trans_gen r a b) :

a = b ∨ ∃ (c : α), r a c ∧ relation.refl_trans_gen r c b

source

theorem relation.refl_trans_gen.cases_head_iff {α : Type u_1} {r : α → α → Prop} {a b : α} :

relation.refl_trans_gen r a b ↔ a = b ∨ ∃ (c : α), r a c ∧ relation.refl_trans_gen r c b

source

theorem relation.refl_trans_gen.total_of_right_unique {α : Type u_1} {r : α → α → Prop} {a b c : α} (U : relator.right_unique r) (ab : relation.refl_trans_gen r a b) (ac : relation.refl_trans_gen r a c) :

relation.refl_trans_gen r b c ∨ relation.refl_trans_gen r c b

source

theorem relation.trans_gen.to_refl {α : Type u_1} {r : α → α → Prop} {a b : α} (h : relation.trans_gen r a b) :

relation.refl_trans_gen r a b

source

@[trans]

theorem relation.trans_gen.trans_left {α : Type u_1} {r : α → α → Prop} {a b c : α} (hab : relation.trans_gen r a b) (hbc : relation.refl_trans_gen r b c) :

relation.trans_gen r a c

source

@[trans]

theorem relation.trans_gen.trans {α : Type u_1} {r : α → α → Prop} {a b c : α} (hab : relation.trans_gen r a b) (hbc : relation.trans_gen r b c) :

relation.trans_gen r a c

source

theorem relation.trans_gen.head' {α : Type u_1} {r : α → α → Prop} {a b c : α} (hab : r a b) (hbc : relation.refl_trans_gen r b c) :

relation.trans_gen r a c

source

theorem relation.trans_gen.tail' {α : Type u_1} {r : α → α → Prop} {a b c : α} (hab : relation.refl_trans_gen r a b) (hbc : r b c) :

relation.trans_gen r a c

source

theorem relation.trans_gen.head {α : Type u_1} {r : α → α → Prop} {a b c : α} (hab : r a b) (hbc : relation.trans_gen r b c) :

relation.trans_gen r a c

source

theorem relation.trans_gen.head_induction_on {α : Type u_1} {r : α → α → Prop} {b : α} {P : Π (a : α), relation.trans_gen r a b → Prop} {a : α} (h : relation.trans_gen r a b) (base : ∀ {a : α} (h : r a b), P a _) (ih : ∀ {a c : α} (h' : r a c) (h : relation.trans_gen r c b), P c h → P a _) :

P a h

source

theorem relation.trans_gen.trans_induction_on {α : Type u_1} {r : α → α → Prop} {P : Π {a b : α}, relation.trans_gen r a b → Prop} {a b : α} (h : relation.trans_gen r a b) (base : ∀ {a b : α} (h : r a b), P _) (ih : ∀ {a b c : α} (h₁ : relation.trans_gen r a b) (h₂ : relation.trans_gen r b c), P h₁ → P h₂ → P _) :

P h

source

@[trans]

theorem relation.trans_gen.trans_right {α : Type u_1} {r : α → α → Prop} {a b c : α} (hab : relation.refl_trans_gen r a b) (hbc : relation.trans_gen r b c) :

relation.trans_gen r a c

source

theorem relation.trans_gen.tail'_iff {α : Type u_1} {r : α → α → Prop} {a c : α} :

relation.trans_gen r a c ↔ ∃ (b : α), relation.refl_trans_gen r a b ∧ r b c

source

theorem relation.trans_gen.head'_iff {α : Type u_1} {r : α → α → Prop} {a c : α} :

relation.trans_gen r a c ↔ ∃ (b : α), r a b ∧ relation.refl_trans_gen r b c

source

theorem acc.trans_gen {α : Type u_1} {r : α → α → Prop} {a : α} (h : acc r a) :

acc (relation.trans_gen r) a

source

theorem acc_trans_gen_iff {α : Type u_1} {r : α → α → Prop} {a : α} :

acc (relation.trans_gen r) a ↔ acc r a

source

theorem well_founded.trans_gen {α : Type u_1} {r : α → α → Prop} (h : well_founded r) :

well_founded (relation.trans_gen r)

source

theorem relation.trans_gen_eq_self {α : Type u_1} {r : α → α → Prop} (trans : transitive r) :

relation.trans_gen r = r

source

theorem relation.transitive_trans_gen {α : Type u_1} {r : α → α → Prop} :

transitive (relation.trans_gen r)

source

@[protected, instance]

def relation.trans_gen.is_trans {α : Type u_1} {r : α → α → Prop} :

is_trans α (relation.trans_gen r)

source

theorem relation.trans_gen_idem {α : Type u_1} {r : α → α → Prop} :

relation.trans_gen (relation.trans_gen r) = relation.trans_gen r

source

theorem relation.trans_gen.lift {α : Type u_1} {β : Type u_2} {r : α → α → Prop} {p : β → β → Prop} {a b : α} (f : α → β) (h : ∀ (a b : α), r a b → p (f a) (f b)) (hab : relation.trans_gen r a b) :

relation.trans_gen p (f a) (f b)

source

theorem relation.trans_gen.lift' {α : Type u_1} {β : Type u_2} {r : α → α → Prop} {p : β → β → Prop} {a b : α} (f : α → β) (h : ∀ (a b : α), r a b → relation.trans_gen p (f a) (f b)) (hab : relation.trans_gen r a b) :

relation.trans_gen p (f a) (f b)

source

theorem relation.trans_gen.closed {α : Type u_1} {r : α → α → Prop} {a b : α} {p : α → α → Prop} :

(∀ (a b : α), r a b → relation.trans_gen p a b) → relation.trans_gen r a b → relation.trans_gen p a b

source

theorem relation.trans_gen.mono {α : Type u_1} {r : α → α → Prop} {a b : α} {p : α → α → Prop} :

(∀ (a b : α), r a b → p a b) → relation.trans_gen r a b → relation.trans_gen p a b

source

theorem relation.trans_gen.swap {α : Type u_1} {r : α → α → Prop} {a b : α} (h : relation.trans_gen r b a) :

relation.trans_gen (function.swap r) a b

source

theorem relation.trans_gen_swap {α : Type u_1} {r : α → α → Prop} {a b : α} :

relation.trans_gen (function.swap r) a b ↔ relation.trans_gen r b a

source

theorem relation.refl_trans_gen_iff_eq {α : Type u_1} {r : α → α → Prop} {a b : α} (h : ∀ (b : α), ¬r a b) :

relation.refl_trans_gen r a b ↔ b = a

source

theorem relation.refl_trans_gen_iff_eq_or_trans_gen {α : Type u_1} {r : α → α → Prop} {a b : α} :

relation.refl_trans_gen r a b ↔ b = a ∨ relation.trans_gen r a b

source

theorem relation.refl_trans_gen.lift {α : Type u_1} {β : Type u_2} {r : α → α → Prop} {p : β → β → Prop} {a b : α} (f : α → β) (h : ∀ (a b : α), r a b → p (f a) (f b)) (hab : relation.refl_trans_gen r a b) :

relation.refl_trans_gen p (f a) (f b)

source

theorem relation.refl_trans_gen.mono {α : Type u_1} {r : α → α → Prop} {a b : α} {p : α → α → Prop} :

(∀ (a b : α), r a b → p a b) → relation.refl_trans_gen r a b → relation.refl_trans_gen p a b

source

theorem relation.refl_trans_gen_eq_self {α : Type u_1} {r : α → α → Prop} (refl : reflexive r) (trans : transitive r) :

relation.refl_trans_gen r = r

source

theorem relation.reflexive_refl_trans_gen {α : Type u_1} {r : α → α → Prop} :

reflexive (relation.refl_trans_gen r)

source

theorem relation.transitive_refl_trans_gen {α : Type u_1} {r : α → α → Prop} :

transitive (relation.refl_trans_gen r)

source

@[protected, instance]

def relation.refl_trans_gen.is_refl {α : Type u_1} {r : α → α → Prop} :

is_refl α (relation.refl_trans_gen r)

source

@[protected, instance]

def relation.refl_trans_gen.is_trans {α : Type u_1} {r : α → α → Prop} :

is_trans α (relation.refl_trans_gen r)

source

theorem relation.refl_trans_gen_idem {α : Type u_1} {r : α → α → Prop} :

relation.refl_trans_gen (relation.refl_trans_gen r) = relation.refl_trans_gen r

source

theorem relation.refl_trans_gen.lift' {α : Type u_1} {β : Type u_2} {r : α → α → Prop} {p : β → β → Prop} {a b : α} (f : α → β) (h : ∀ (a b : α), r a b → relation.refl_trans_gen p (f a) (f b)) (hab : relation.refl_trans_gen r a b) :

relation.refl_trans_gen p (f a) (f b)

source

theorem relation.refl_trans_gen_closed {α : Type u_1} {r : α → α → Prop} {a b : α} {p : α → α → Prop} :

(∀ (a b : α), r a b → relation.refl_trans_gen p a b) → relation.refl_trans_gen r a b → relation.refl_trans_gen p a b

source

theorem relation.refl_trans_gen.swap {α : Type u_1} {r : α → α → Prop} {a b : α} (h : relation.refl_trans_gen r b a) :

relation.refl_trans_gen (function.swap r) a b

source

theorem relation.refl_trans_gen_swap {α : Type u_1} {r : α → α → Prop} {a b : α} :

relation.refl_trans_gen (function.swap r) a b ↔ relation.refl_trans_gen r b a

source

def relation.join {α : Type u_1} (r : α → α → Prop) :

α → α → Prop

The join of a relation on a single type is a new relation for which pairs of terms are related if there is a third term they are both related to. For example, if r is a relation representing rewrites in a term rewriting system, then confluence is the property that if a rewrites to both b and c, then join r relates b and c (see relation.church_rosser).

Equations

relation.join r = λ (a b : α), ∃ (c : α), r a c ∧ r b c

source

theorem relation.church_rosser {α : Type u_1} {r : α → α → Prop} {a b c : α} (h : ∀ (a b c : α), r a b → r a c → (∃ (d : α), relation.refl_gen r b d ∧ relation.refl_trans_gen r c d)) (hab : relation.refl_trans_gen r a b) (hac : relation.refl_trans_gen r a c) :

relation.join (relation.refl_trans_gen r) b c

A sufficient condition for the Church-Rosser property.

source

theorem relation.join_of_single {α : Type u_1} {r : α → α → Prop} {a b : α} (h : reflexive r) (hab : r a b) :

relation.join r a b

source

theorem relation.symmetric_join {α : Type u_1} {r : α → α → Prop} :

symmetric (relation.join r)

source

theorem relation.reflexive_join {α : Type u_1} {r : α → α → Prop} (h : reflexive r) :

reflexive (relation.join r)

source

theorem relation.transitive_join {α : Type u_1} {r : α → α → Prop} (ht : transitive r) (h : ∀ (a b c : α), r a b → r a c → relation.join r b c) :

transitive (relation.join r)

source

theorem relation.equivalence_join {α : Type u_1} {r : α → α → Prop} (hr : reflexive r) (ht : transitive r) (h : ∀ (a b c : α), r a b → r a c → relation.join r b c) :

equivalence (relation.join r)

source

theorem relation.equivalence_join_refl_trans_gen {α : Type u_1} {r : α → α → Prop} (h : ∀ (a b c : α), r a b → r a c → (∃ (d : α), relation.refl_gen r b d ∧ relation.refl_trans_gen r c d)) :

equivalence (relation.join (relation.refl_trans_gen r))

source

theorem relation.join_of_equivalence {α : Type u_1} {r : α → α → Prop} {a b : α} {r' : α → α → Prop} (hr : equivalence r) (h : ∀ (a b : α), r' a b → r a b) :

relation.join r' a b → r a b

source

theorem relation.refl_trans_gen_of_transitive_reflexive {α : Type u_1} {r : α → α → Prop} {a b : α} {r' : α → α → Prop} (hr : reflexive r) (ht : transitive r) (h : ∀ (a b : α), r' a b → r a b) (h' : relation.refl_trans_gen r' a b) :

r a b

source

theorem relation.refl_trans_gen_of_equivalence {α : Type u_1} {r : α → α → Prop} {a b : α} {r' : α → α → Prop} (hr : equivalence r) :

(∀ (a b : α), r' a b → r a b) → relation.refl_trans_gen r' a b → r a b

source

theorem equivalence.eqv_gen_iff {α : Type u_1} {r : α → α → Prop} {a b : α} (h : equivalence r) :

eqv_gen r a b ↔ r a b

source

theorem equivalence.eqv_gen_eq {α : Type u_1} {r : α → α → Prop} (h : equivalence r) :

eqv_gen r = r

source

theorem eqv_gen.mono {α : Type u_1} {a b : α} {r p : α → α → Prop} (hrp : ∀ (a b : α), r a b → p a b) (h : eqv_gen r a b) :

eqv_gen p a b