Все выпуски

Любое бинарное отношение σ⊆X (где X - произвольное множество) порождает на множестве X² характеристическую функцию: если (x,y)∈σ, то σ(x,y)=1, а иначе σ(x,y)=0. В терминах характеристических функций на множестве всех бинарных отношений множества X вводится понятие бинарного рефлексивного отношения смежности и определяется алгебраическая система, состоящая из всех бинарных отношений множества и из всех неупорядоченных пар различных смежных бинарных отношений. Если X - конечное множество, то эта алгебраическая система - граф («граф графов»).

Показано, что если σ и τ - смежные отношения, то σ является частичным порядком тогда и только тогда, когда τ является частичным порядком. Исследованы некоторые особенности строения графа G(X) частичных порядков. В частности, если X состоит из n элементов, а T₀(n) - это число помеченных T₀-топологий, определенных на множестве X, то количество вершин в графе G(X) равно T₀(n), а количество компонент связности равно T₀(n-1).

Для всякого отношения частичного порядка σ определяется понятие его опорного множества S(σ), являющегося некоторым подмножеством множества X. Если X - конечное множество, а частичные порядки σ и τ принадлежат одной и той же компоненте связности графа G(X), то равенство S(σ)=S(τ) имеет место тогда и только тогда, когда σ=τ. Показано, что в каждой компоненте связности графа G(X) совокупность опорных множеств ее элементов является специфическим частично упорядоченным множеством относительно естественного отношения включения множеств.

Any binary relation σ⊆X (where X is an arbitrary set) generates a characteristic function on the set X²: if (x,y)∈σ, then σ(x,y)=1, otherwise σ(x,y)=0. In terms of characteristic functions on the set of all binary relations of the set X we introduced the concept of a binary reflexive relation of adjacency and determined the algebraic system consisting of all binary relations of a set and of all unordered pairs of various adjacent binary relations. If X is finite set then this algebraic system is a graph (“a graph of graphs”).

It is shown that if σ and τ are adjacent relations then σ is a partial order if and only if τ is a partial order. We investigated some features of the structure of the graph G(X) of partial orders. In particular, if X consists of n elements, and T₀(n) is the number of labeled T₀-topologies defined on the set X, then the number of vertices in a graph G(X) is T₀(n), and the number of connected components is T₀(n-1).

For any partial order σ there is defined the notion of its support set S(σ), which is some subset of X. If X is finite set, and partial orders σ and τ belong to the same connected component of the graph G(X), then the equality S(σ)=S(τ) holds if and only if σ=τ. It is shown that in each connected component of the graph G(X) the union of support sets of its elements is a specific partially ordered set with respect to natural inclusion relation of sets.