About finite lower neighbourhood in functional space.pdf Основным объектом рассмотрения в докладе является пространство - множествос замыканием. Пространства комбинаторных объектов (графов, функций, разбиенийи др.) возникают естественным образом в различных разделах дискретной математики(таких, как теория графов, математическая логика и др.), но рассматриваемыевопросы наиболее важные приложения имеют для пространств дискретных функцийс замыканием относительно суперпозиции. Одной из задач, возникающих при изучениитаких пространств, является задача о полноте, требующая описания всех порождающихмножеств пространства (или некоторого его подпространства). Обобщениемэтой задачи является задача о выразимости в пространстве некоторого его подмножестваX , требующая описания всех подмножеств пространства, замыкания которыхвключают подмножество X . Естественным средством решения этой задачи являетсянижняя окрестность подмножества X - так называется всякая такая система Sзамкнутых подмножеств рассматриваемого пространства, что замыкание любого подмножестваY включает X , если и только если Y не содержится целиком ни в одномклассе из системы S . В приложениях для нижней окрестности желательна конечность,а для её классов - существование эффективных описаний. Довольно легко понять,что подмножество, обладающее конечной нижней окрестностью, конечно порождено.В связи с этим имеет смысл задача, состоящая в поиске условий, при которых заданноеили произвольное конечно порождённое подмножество пространства обладаетконечной нижней окрестностью. Эта задача, в более слабой форме поставленнаяв [1], является основной в данном докладе. Необходимым условием существованияконечной нижней окрестности подмножества является его компактность, а необходимымусловием существования в пространстве конечных нижних окрестностей длявсех конечно порождаемых подмножеств является финитарность пространства (состоящаяв возможности так ввести алгебраические операции в пространство, чтобыего замкнутыми подмножествами оказались в точности все возможные подалгебрыполученной алгебры). В свете сказанного представляют интерес условия, при которыхкомпактное подмножество пространства (в частности, произвольное конечно порождаемоеподмножество финитарного пространства) имеет конечную нижнюю окрестность.Некоторые такие конструктивные и легко проверяемые в приложениях условия (обобщающиетеорему А. В. Кузнецова о полноте из [2] и теорему С. В. Яблонского из [3])рассматриваются в докладе. Изучаются также условия, при которых замкнутые подмножествапредупорядоченного пространства, в частности принадлежащие нижнимокрестностям, допускают эффективное описание посредством конечных запрещающихмножеств.

Скачать электронную версию публикации