Систематизация классов определимости
В статье рассматриваются различные виды определимости, а также классификации этого понятия. Проводится систематизация классов определимости. В статті розглядаються різновиди визначеності, а також класифікації цього поняття. Систематизуються класи визначеності. In the article considering some types...
Saved in:
| Published in: | Культура народов Причерноморья |
|---|---|
| Date: | 2007 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Кримський науковий центр НАН України і МОН України
2007
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/98662 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Систематизация классов определимости / А.С. Сарачева // Культура народов Причерноморья. — 2007. — № 106. — С. 283-286. — Бібліогр.: 10 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-98662 |
|---|---|
| record_format |
dspace |
| spelling |
Сарачева, А.С. 2016-04-16T16:16:58Z 2016-04-16T16:16:58Z 2007 Систематизация классов определимости / А.С. Сарачева // Культура народов Причерноморья. — 2007. — № 106. — С. 283-286. — Бібліогр.: 10 назв. — рос. 1562-0808 https://nasplib.isofts.kiev.ua/handle/123456789/98662 В статье рассматриваются различные виды определимости, а также классификации этого понятия. Проводится систематизация классов определимости. В статті розглядаються різновиди визначеності, а також класифікації цього поняття. Систематизуються класи визначеності. In the article considering some types of definable, and classifications of this term. Classes of definable was classified. ru Кримський науковий центр НАН України і МОН України Культура народов Причерноморья История логики ХХ века Систематизация классов определимости Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Систематизация классов определимости |
| spellingShingle |
Систематизация классов определимости Сарачева, А.С. История логики ХХ века |
| title_short |
Систематизация классов определимости |
| title_full |
Систематизация классов определимости |
| title_fullStr |
Систематизация классов определимости |
| title_full_unstemmed |
Систематизация классов определимости |
| title_sort |
систематизация классов определимости |
| author |
Сарачева, А.С. |
| author_facet |
Сарачева, А.С. |
| topic |
История логики ХХ века |
| topic_facet |
История логики ХХ века |
| publishDate |
2007 |
| language |
Russian |
| container_title |
Культура народов Причерноморья |
| publisher |
Кримський науковий центр НАН України і МОН України |
| format |
Article |
| description |
В статье рассматриваются различные виды определимости, а также классификации этого понятия. Проводится систематизация классов определимости.
В статті розглядаються різновиди визначеності, а також класифікації цього
поняття. Систематизуються класи визначеності.
In the article considering some types of definable, and classifications of this
term. Classes of definable was classified.
|
| issn |
1562-0808 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/98662 |
| citation_txt |
Систематизация классов определимости / А.С. Сарачева // Культура народов Причерноморья. — 2007. — № 106. — С. 283-286. — Бібліогр.: 10 назв. — рос. |
| work_keys_str_mv |
AT saračevaas sistematizaciâklassovopredelimosti |
| first_indexed |
2025-11-24T09:02:48Z |
| last_indexed |
2025-11-24T09:02:48Z |
| _version_ |
1850843997542547456 |
| fulltext |
ИСТОРИЯ ЛОГИКИ ХХ ВЕКА
283
Сарачева А.С.
СИСТЕМАТИЗАЦИЯ КЛАССОВ ОПРЕДЕЛИМОСТИ
Введение.
Одно из центральных понятий логической семантики – понятие определимости, связано с выразимостью
одних логических объектов через другие. Определимостью можно назвать некоторое отношение между явле-
нием X и множеством M , в которое X не входит. Единственное условие, предъявляемое к M , состоит в
том, что M – структура, т.е. множество, в котором имеют место постадийные преобразования элементов M
и результатов преобразований. Для этого предполагается: в M , помимо элементов входят преобразующие
средства L . Преобразования L как и всякие преобразующие силы, превращают любой элемент из M в эле-
мент, не обязательно принадлежащий M .
В литературе есть несколько дефиниций определимости. Предполагается, что обобщенным является сле-
дующее:
Определение. Будем говорить, что X определим в структуре M , если и только если предъявлен процесс
ncccc ,...,,, 321 , такой, что:
Любое jc – либо элемент M , либо получено из предшествующих jc элементов (т.е. ,1−jc 2−jc и т.д.): по-
средством L .
nc находится в одном из следующих отношений к X : тождества, равенства, приближения, подобия, ана-
логии и т.п.; представления, замены, взаимозаменяемости. Список отношений можно уточнять.
Это определение дано в [1].
Много примеров определимости можно найти в математике. Это может быть выразимость (определи-
мость) периодических функций действительных переменных через другие (представление функции в виде ря-
да Фурье); сопоставление с функцией )(xy функции известного класса ),...,,,()( 10 nxyxY ααα≡ , которая за-
висит от 1+n параметров jα , выбранных специальным способом. Кроме этого примером определимости
может служить нахождение корней уравнения вида 0)( =xf , где )(xf непрерывная функция (график этой
функции не содержит точек разрыва) и т.д.
Дефиниция определимости функции через другие выглядит так:
Определение. Функция )(xf определима через другие функции тогда и только тогда, когда существует
другая функция с такими же переменными, такая, что ее график полностью совпадает с графиком исходной
функции.
Рассмотрим такой пример из численных методов математики [9]:
Допустим, в некоторые дискретные моменты времени nxxx ,...,, 21 наблюдаются значения функции )(xf ,
требуется восстановить ее значения при других x . Другими словами, необходимо определить функцию, если
известны ее значения в некоторых точках. В этом случае целесообразно искать не саму функцию, а некоторое
ее приближение в виде: )...,,,()( 10 nxgxf ααα≈ . Значения параметров jα
выбираются так, чтобы значе-
ния )(xg совпадали со значениями )(xf для данного множества 1+n значений аргумента kx (узлов ин-
терполяции). Понятно, что график приближенной функции будет совпадать с графиком функции )(xf , с не-
которой погрешностью. Приближать функции можно многочленами, в некоторых случаях удобнее делать это
тригонометрическими полиномами, иногда дробно–рациональными полиномами. Например, так:
∑
∑
=
==≈
m
k
k
k
n
j
jj
xb
xa
xgxf
0
0)()(
В любом случае определимость будет иметь место.
Ярким примером из гармонического анализа, рассматриваемого колебательные движения, может служить
выразимость периодической функции2 в виде ряда Фурье:
∑
∞
=
++=
1
0 )sincos()(
n
nn nxbnxaaxf
, где jj baa ,,0 – коэффициенты Фурье (см. [9])
В связи с бурным развитием науки, многие ученые обобщают понятие определимости в логических тер-
минах. Кроме того выделяют различные типы, классы определимостей, не только функций, также других объ-
ектов.
Сколько классов определимости существует? На какие типы делится это понятие?
2 Функция )(tf является периодической с периодом T , если )()( tfTtf ≡+ . [9]
Сарачева А.С.
СИСТЕМАТИЗАЦИЯ КЛАССОВ ОПРЕДЕЛИМОСТИ
284
Вообще говоря, понятие определимости не является “абсолютным”, оно зависит от теории, в которой рас-
сматриваются логические объекты, от самих объектов, для которых вводится это понятие. Поэтому разбить на
классы все виды определимости и построить единую систему практически невозможно. В связи с этим, суще-
ствует несколько классификаций этого понятия (разными авторами), но нужно отметить, что каждая собирает
разработанные именно этим автором определимости. Рассмотрим некоторые из них.
Аналитическая определимость явлений.
Напомним некоторые определения из [1].
Будем рассматривать множество М элементов произвольной природы А, В, С..., вступающих в связи (от-
ношения) α, β, γ,…, образуя комбинации.
Комбинационный процесс для множества с элементами А, В, С, Д,… и бинарными связками α, β, γ задает-
ся так:
А, В, С, Д… – элементарные комбинации.
Если х, у – комбинации, то комбинациями и являются так же α(х, у), β(х, у), γ(х, у).
Определение. Элемент Х аналитически определим в |М|, если и только если в |М| выстраивается конфигу-
рация из фрагментов |М|, в силу которой и результатом которой является Х//[] – одна из комбинаций |М|, не
содержащая Х. Точнее: пусть в |М| с правилами отбора L: L1, L2, L3, …Ln из фрагментов А1, А2, …Ак, строится
конфигурационная последовательность С1, С2, С3, …, Сm, такая, что Сm есть Х// [], где [] – одно из комбинаций
|М|, составленное из А1, А2, …Ак, или их частей, но без Х, тогда говорят: Х определимо в М.
// – отношение взаимозаменяемости. |М| – структура (множество элементов М,, множество связей его эле-
ментов, множество комбинаций из элементов М, посредством связей).
Это определение введено Николко В.Н., в его работе “Аналитическая определимость явлений”. Автор вы-
деляет два класса аналитической определимости (А–определимости): ДА–определимость (дедуктивная опре-
делимость) и ТА–определимость (тождественно–аналитическая определимость).
Определение. Некоторое Х ДА–определимо в некотором множестве М тогда и только тогда, когда в этом
множестве выводима комбинация ( AX → ) и комбинация ( XA → ), что обозначают Х//А, где Х – элемент
множества М, А – комбинация множества М, не содержащая Х.
Определение. Х ТА–определим в множестве М, если и только если в М существует отборочный процесс,
благодаря которому Х=[], где [] – одна из комбинаций М, не содержащая Х.
Наглядным примером этой определимости служит решение простейшего линейного уравнения: 4х+10=0
[1]. Решение этого уравнения представляет собой последовательность конструкций, отвечающую условиям
дефиниции определимости явлений.
В свою очередь ТА–определимость можно разделить на подклассы. Отобразим это в таблице:
Аналитическая определимость (А–определимость)
ТА–определимость ДА–определимость
Программная определимость явлений
(ПТА–определимость)
Грамматическая опреде-
лимость
Социальная определимость
Определение. Х ПТА–определим в множестве М, если и только если, существует программа сборки (или
поиска) элементов М, в некоторую комбинацию из М, не содержащую Х, но тождественную Х.
Определение. Х грамматически определим в языке М, если и только если, в М найдется не содержащая Х
речевая конструкция, адекватная Х
Существует также два непересекающихся между собой класса определимости: программная аналитиче-
ская определимость и теоретико–множественная аналитическая определимость.
Классификация определимости В.А.Смирнова.
Большой вклад в развитие теории определимости внес В.А.Смирнов, в работах которого представлено
достаточно много материала по этому вопросу.
Классически различают явную и неявную определимости, причем рассматривают синтаксическое и се-
мантическое понятие этих терминов. [4] Под синтаксическими терминами понимают понятия “переменная”,
“формула”, “предложение”, “аксиома” и т.д.
Пусть Т – теория. Под теорией будем понимать множество предложений, замкнутое относительно выво-
димости. Пусть Р – к–местный предикат. [2]
Определение. Предикат Р явно семантически определим в теории Т, если семантически можно обосновать
утверждение:
MM (∀ ||= MT ⇒ ||= )),...,(),...,((,..., 111 nnn xxAxxPxx ≡∀∀ , то есть каждая возможная реализа-
ция теории Т, являющаяся ее моделью, является моделью и для формулы
)),...,(),...,((,..., 111 nnn xxAxxPxx ≡∀∀ .
||= – знак семантического следования3.
Определение. Р неявно семантически определим в теории Т, ели любые две возможные реализации , кото-
рые приписывают одно и то же значение всем предикатам, отличным от предиката Р, припишут одинаковые
значения и самому предикату Р.
3 р ||= q означает, что из истинности р следует истинность q .[11]
ИСТОРИЯ ЛОГИКИ ХХ ВЕКА
285
Определение. Говорят, что Р явно синтаксически определим в терминах предложений Т, если найдется та-
кая формула ),...,( 1 nxxA , не содержащая Р такая, что доказуемо следующее утверждение:
T ├ )),...,(),...,((,..., 111 nnn xxAxxPxx ≡∀∀ ,
где ├ – синтаксическое отношение выводимости4.
Пусть теперь выполнены следующие условия:
),...,(' 1 nxxP – n–местный предикат, не содержащийся в теории Т. Пусть Т’ – теория, образованная из
теории Т, заменой в каждом положении всех вхождений предиката Px на предикат xP' .
Определение. Предикат Px неявно синтаксически определим в Т, если
'TT U ├ )),...,('),...,((,..., 111 nnn xxPxxPxx ≡∀ ,
то есть в теории 'TT U доказуемо утверждение об эквивалентности двух предикатов P и 'P .
Из выше указанных определений определимости ясно, что решение проблем, связанных с определимо-
стью, сводится к нахождению формулы A , но метод ее отыскания не прописан. Большую роль в этом процес-
се (отыскания) сыграли интерполяционная теорема Крейга, а также теорема А.Падоа и обратная ей теорема
Бета (об эквивалентности явной и неявной определимостей).
Теорема (Падоа). Если Р явно синтаксически определим в Т, то Р неявно синтаксически определим в Т.
Теорема (Бета). Если Р синтаксически неявно определим в Т, то Р явно синтаксически определим в Т.
Все типы определимости, описанные В.А.Смирновым, можно представить в виде таблицы:
Полная определимость Неполная (частичная) определимость
Явная определимость (семантическая, синтаксическая)
Неявная определимость (семантическая, синтаксическая)
Условная определимость (явная, неявная)
Дизъюнктивная определимость (явная, неявная)
Условно–параметрическая определимость (явная, неявная)
Параметрическая определимость (явная, неявная)
Нужно отметить, что для выше перечисленных типов определимости также различают синтаксическое и
семантическое аспекты. Из названий классов определимости ясно, что некоторые из них вводятся с помощью
различных типов определений. Прежде всего, условная определимость. Дадим краткую характеристику.
Итак, пусть Р – термин, зависящий от l переменных, т.е P = ),...,( 1 lxxP . Т – множество предложений.
Определение. Термин Р явно условно определим в терминах предложений Т тогда и только тогда, когда
существует условие S и формула α , содержащие ровно l различных свободных переменных, и сформулиро-
ванные в терминах, отличных от Р, такие, что
T ├ PxSxx ⊃∀ ( ~ )α ,
где ⊃ – знак следования, а ~ – знак тождества.
Определение. Термин Р неявно условно определим в терминах предложений Т тогда и только тогда, когда
',TT ├ PxSxx ⊃∀ ( ~ xP' ),
где 'T – теория, образованная из теории Т, заменой в каждом положении всех вхождений предиката Px
на предикат xP' .
Для этого класса определимости также справедлива теорема Бета об эквивалентности.
Рассмотрим теперь случай неполной определимости, то есть такой определимости, к которой отнесены
термины, определимые не всегда в других терминах.
Определение. Термин Р дизъюнктивно определим в терминах теории Т тогда и только тогда, когда суще-
ствуют формулы nαα ,...,1 , с различными свободными переменными, такие, что
T ├ Pxx(∀ ~ )1α ∨ … ∨ Pxx(∀ ~ )nα .
Аналогичным способом вводятся понятия условно–параметрической и параметрической определимости.
Для всех них справедлива теорема Бета.
Определение. к–местный термин Р условно–параметрически определим в терминах теории Т тогда и
только тогда, когда существует такая формула S с m различными свободными переменными myy ,...,1 и
формулы nαα ,...,1 , с mk + различными свободными переменными kxx ,...,1 , myy ,...,1 , сформулирован-
ными в терминах, отличных от Р, такие, что
4 р |– q означает, что q выводимо из р с помощью некоторых четко описанных правил. [11]
Сарачева А.С.
СИСТЕМАТИЗАЦИЯ КЛАССОВ ОПРЕДЕЛИМОСТИ
286
T ├ ySy∃ & y∀ ⊃Sy( ni≤≤
∨
1 Pxx(∀ ~ iα )).
Определение. . к–местный термин Р параметрически определим в терминах теории Т тогда и только тогда,
когда существуют формулы nαα ,...,1 , с mk + различными свободными переменными kxx ,...,1 ,
myy ,...,1 , сформулированными в терминах, отличных от Р, такие, что
T ├ ni≤≤
∨
1 Pxxy (∀∃ ~ xyiα ).
Имеется также вид определимости, который обобщает условно–параметрическую и дизъюнктивную оп-
ределимости. При анализе этих видов определимости нужно учесть, что возможны формулировки в терминах
явной и неявной семантической и явной и неявной синтаксической определимости.
Рассмотрим теперь некоторое обобщенное понятие определимости свойств и отношений в первопорядко-
вой теории – понятие К–определимости. [3].
Пусть S – первопорядковая теория, U – область ее интерпретации5. Рассмотрим некоторое отношение R на
области U. Чтобы понятие теории стало точным, необходимо фиксировать язык, на котором делаются утвер-
ждения теории. Язык теории Т обозначим S. Пусть К – произвольный класс формул языка S: он непротиворе-
чив и замкнут относительно формальной выводимости. Пусть дана следующая арифметическая функция
)(nD , определяемая следующим способом:
+=+
=
=
1)()1(
1)1(
)(
nDnD
D
nD
Определение. Будем говорить, что n–местный предикат R К–определим в S тогда и только тогда, когда
существует формула А языка S, содержащая в точности n попарно различных свободных переменных
naa ,...,1 такая, что
nkk ∀∀ ,...,1 [ (),...,(())))(),...,((()),...,(( 111 ⊃¬∧∈⊃ nnn kkRKkDkDAkkR ¬ ))(),...,(( 1 nkDkDA
K∈ ].
Воспроизведем понятие К–определимости для функции.
Определение. n–местная функция ϕ К–определима в S тогда и только тогда, когда существует такой терм
α в S, содержащий в точности n попарно различных свободных переменных naa ,...,1 , что
nkk ∀∀ ,...,1 [ KkDkDkkD nn ∈≈ ))(),...,(()),...,((( 11 αϕ ]
Рассматривая различные первопорядковые теории, получаем различные виды К–определимости. В каче-
стве первопорядковой теории рассмотрим арифметику Р. Тогда в качестве множества К могут выступать мно-
жества Tr (класс формул, общезначимых в области целых положительных чисел) и класс Т (класс теорем сис-
темы Р). Оба этих класса непротиворечивы, замкнуты. [3].
В этом случае получаем следующую классификацию определимости свойств и отношений в первопоряд-
ковой теории, в частности, в арифметике Р.
К–определимость
Пусть К = Tr, получаем Tr–определимость предикатов и
функций.
Пусть К = T, получаем T–определимость предикатов. Эту оп-
ределимость называют иногда рекурсивной определимостью
предикатов.
Источники и литература
1. Николко В.Н. Аналитическая определимость явлений./ Учебно-методические материалы по курсу “Теория
определений” для студентов философского факультета. – Симферополь, 2004.
2. Смирнов В.А. Логические методы научного знания. – М., 1987.
3. Смирнова Е.Д. Логические основы семантики.
4. Бочаров В.А., Смирнова Е.Д. Определимость // Новая философская энциклопедия. Т.III. – М., 2000 .
5. Клини С.К. Введение в математику./ Издание иностранной литературы.– М., 1957.
6. Клини С.К.. Математическая логика./ Издание иностранной литературы.– М., 1973.
7. Робинсон. А Введение в теорию моделей и математику алгебры. – М.1967.
8. Э.Мендельсон. Введение в математическую логику. – М.1971. – 318 с.
9. Корн Г., Т. Корн. Справочник по математике для научных работников и инженеров. – М., “Наука”, 1984г.
10. Линдон Р.. Заметки по логике./ Издательство “Мир”. – М.,1968. – 128 с.
5 Интерпретация – любая система, состоящая из непустого множества U, называемого областью интерпретации и какого–
либо соответствия ϕ : nU → U .[8]
|