Editing Binary relation (section)

== Induced concept lattice ==
Binary relations have been described through their induced [[concept lattice]]s:
A '''concept''' <math>C \subset R</math> satisfies two properties:
* The [[logical matrix]] of <math>C</math> is the [[outer product]] of logical vectors <math>C_{i j} = u_i v_j , \quad u, v</math> [[logical vector]]s.{{clarify|reason=Given R, how are the logical vectors obtained?|date=June 2021}}
* <math>C</math> is maximal, not contained in any other outer product. Thus <math>C</math> is described as a ''non-enlargeable rectangle''.

For a given relation <math>R \subseteq X \times Y,</math> the set of concepts, enlarged by their joins and meets, forms an "induced lattice of concepts", with inclusion <math>\sqsubseteq</math> forming a [[preorder]].

The [[MacNeille completion theorem]] (1937) (that any partial order may be embedded in a [[complete lattice]]) is cited in a 2013 survey article "Decomposition of relations on concept lattices".<ref>[[R. Berghammer]] & M. Winter (2013) "Decomposition of relations on concept lattices", [[Fundamenta Informaticae]] 126(1): 37–82 {{doi|10.3233/FI-2013-871}}</ref> The decomposition is
: <math>R = f E g^\textsf{T}</math>, where <math>f</math> and <math>g</math> are [[Function (mathematics)|function]]s, called {{em|mappings}} or left-total, functional relations in this context. The "induced concept lattice is isomorphic to the cut completion of the partial order <math>E</math> that belongs to the minimal decomposition <math>(f, g, E)</math> of the relation <math>R</math>."

Particular cases are considered below: <math>E</math> total order corresponds to Ferrers type, and <math>E</math> identity corresponds to difunctional, a generalization of [[equivalence relation]] on a set.

Relations may be ranked by the '''Schein rank''' which counts the number of concepts necessary to cover a relation.<ref>[[Ki-Hang Kim]] (1982) ''Boolean Matrix Theory and Applications'', page 37, [[Marcel Dekker]] {{ISBN|0-8247-1788-0}}</ref> Structural analysis of relations with concepts provides an approach for [[data mining]].<ref>Ali Jaoua, Rehab Duwairi, Samir Elloumi, and Sadok Ben Yahia (2009) "Data mining, reasoning and incremental information retrieval through non enlargeable rectangular relation coverage", pages 199 to 210 in ''Relations and Kleene algebras in computer science'', [[Lecture Notes in Computer Science]] 5827, Springer {{mr|id=2781235}}</ref>