Scientific Journal of KubSAU

Partially ordered set is a basic concept of modern settheoretic mathematics. The problem of linear set ordering with given binary relations is well-known. Every partial order over a finite set can be linearly ordered, but not every binary relation over this set can be linearly ordered as well. Up to now, there is no known formula for calculating the number of partial orders over a given finite set. It appears that there is a formula for calculating linearly ordered binary relations over a finite set. This article is concerned with derivation of this formula. The fact from work of G.N. Titov [9] that a binary relation over a finite set is linearly ordered if and only if any diagonal block, derived from the binary relation matrix as a result of setting main diagonal elements to zero, contains at least one zero row (diagonal block of matrix means any matrix composed of elements at the crossings of rows and columns of a given matrix with the same numbers), plays a key role in process of corroboration. The main conclusion of the article is a theorem that allows to find the number of linearly ordered binary relations over a set of n elements using the formula. A recurrence formula for the number of linearly ordered (irreflexive) binary relations over a finite set of n elements, provided in the lemma, was derived as well