WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Логіки першого порядку - Реферат

Логіки першого порядку - Реферат

..., an bn , то fA (a1 , ..., an) fA (b1 , ..., bn).
Нехай A=(A, ), відношення конгруентності на A . Фактор система B=(B, ) системи A по відгошенню задається так.
Для кожного a A позначимо [a]={c A | a c}. Задамо множину В={[a] | a A}. Таку множину В позначатимемо також .
Для кожного f Fs арності п задамо fB ([a1],..., [an])=[fA (a1 ,..., an)].
Для кожного p Ps арності п покладемо
pB([a1], ..., [an]) = T знайдуться c1 [a1], ..., cn [an] такі, що pA (c1 , ..., cn)=T.
Конгруентність відношення гарантує коректність такого визна-чення функцій fB . Спрaвді, для довільних c1 , ..., cn таких, що [a1]=[c1], ..., [an]=[cn], маємо a1 c1 , ..., an cn , звідки за конгруентні-стю fA (a1 , ..., an) fA (с1 , ..., сn), тому [fA (a1 , ..., an)]=.[fA (c1 , ..., cn)].
Задамо канонічне відображення : А? наступним чином:
для кожного a A покладемо (а)=[a].
Із визначень випливає, що канонічне відображення : А? є гомоморфізмом АС A=(A, ) в АС B=(B, ). Такий гомоморфізм називається канонічним.
Приклад 4. Нехай N = (N, ar). Задамо відношення на N таким чином: m n mod(m, 2)=mod(n, 2). Таке відношення є відношенням конгруентності на N. Покладемо {[0], [1]}. Тут [0] та [1] є відповідно множиною парних та непарних натуральних чисел.
ФС + та інтерпретуються на ( , ar) наступним чином :
+([0], [0])=[0]; ([0], [0])=[0];
+([0], [1])=[1]; ([0], [1])=[0];
+([1], [0])=[1]; ([1], [0])=[0];
+([1], [1])=[0]; ([1], [1])=[1].
Константні символи 0 та 1 інтерпретуються як [0] та [1].
Таку фактор-систему ( , ar) позначимо Nmod2. Тепер задамо канонічне відображення : N? : (n) = .
В подальших визначеннях імена & та x похідних логічних операції & та x трактуємо як символи розширеного алфавіту. Визначення формули мови розширеного алфавіту цілком зрозуміле.
Формулу, утворену з атомарних формул за допомогою символів логічних операцій , & та x, назвемо -позитивною формулою.
Формулу, утворену з атомарних формул за допомогою допомогою символів логічних операцій , &, x та x, назвемо позитивною формулою.
Кожне відображення : А?В можна розширити до відображення : АХ ?ВХ таким чином: ([xi aai] i ) = [xi a (ai)] i ). Зокрема, ((a1 , ..., an)) = ( (a1) , ..., (an)).
Теорема 5.1. Нехай : А?В гомоморфізм АС A=(A, ) в АС B=(B, ). Тоді :
1) для кожного терма t сигнатури з множиною предметних імен Х для довільних d AХ маємо (tA(d)) = tB( (d)) ;
2) для кожної -позитивної формули сигнатури з множиною вільних імен Х для довільних d AХ маємо: якщо А (d)=Т, то В( (d))=Т.
Теорема 5.2 Нехай сюр'єктивне відображення : А?В є гомо-морфізмом АС A=(A, ) в АС B=(B, ). Тоді виконується твердження 1) теореми 4.5.1 та
2) для кожної позитивної формули сигнатури з множиною вільних імен Х для довільних d AХ маємо: якщо А (d)=Т, то В ( (d))=Т.
Наслідок. Нехай сюр'єктивний гомоморфізм АС A=(A, ) в АС B=(B, ). Тоді для кожної позитивної формули сигнатури якщо A , то B .
Теорема 5.3. Нехай : А?В сильний гомоморфізм АС A=(A, ) в АС B=(B, ). Тоді виконується твердження 1) теореми 4.5.1 та
2) для кожної формули сигнатури з множиною вільних імен Х для довільних d AХ маємо А (d)= В( (d)).
Наслідок 1 (теорема про ізоморфізм). Нехай : А?В ізоморфізм АС A=(A, ) в АС B=(B, ). Тоді виконуються твердження 1) теореми 4.5.1 та твердження 2) теореми 4.5.3.
Наслідок 2. Нехай сильний гомоморфізм АС A=(A, ) в АС B=(B, ). Тоді для кожної формули сигнатури A B .
Приклад 5. Умова позитивності в формулюванні теорем 4.5.1 та 4.5.2 істотна. Справді,канонічне відображення : N? ={[0], [1]} є сюр'єктивним гомоморфізмом АС N в АС Nmod2 . Розглянемо формулу (1+1)=0, яку позначимо . Тоді маємо N , але N mod2 , адже +([1], [1])=[0].
6. ІЗОМОРФІЗМ ТА ЕЛЕМЕНТАРНА ЕКВІВАЛЕНТНІСТЬ АГЕБРАЇЧНИХ СИСТЕМ. МЕТОД АВТОМОРФІЗМІВ
АС A=(A, ) та B=(B, ) назвемо елементарно еквівалентними, якщо для кожної формули сигнатури A B .
Те, що АС A та B елементарно еквівалентні, позначаємо A B.
Елементарна еквівалентність алгебраїчних систем означає, що вони мають однакові властивості на рівні логіки 1-го порядку, тобто їх ніяк не можна відрізнити, використовуючи мову 1-го порядку.
Приклад 1. (R; { , =}) (Q; { , =}). Справді, нехай формула x y(x=y y y). Тоді (R; { , =}) та (Q; { , =}) .
Приклад 2. (Z; {+, =}) (Q; {+, =}). Справді, нехай формула x y(x=y+y). Тоді (Q; {+, =}) та (Z; {+, =}) .
Приклад 3. (N, { , =}) (Z, { , =}). Справді, нехай формула m x(m x). Тоді (N, {<, =}) та (Z, {<, =}) .
Із теореми про ізоморфізм (наслідок 1 теореми 4.5.3) випливає:
Твердження 1. Нехай ізоморфізм АС A=(A, ) в АС B=(B, ). Тоді для кожної формули сигнатури A B .
Твердження 2. Нехай автоморфізм АС A=(A, ). Тоді для кожної формули сигнатури з множиною вільних імен Х для довільних d AХ маємо А (d)= А( (d)).
Із твердження 1 дістаємо, що з ізоморфізму АС A та B випливає їх елементарна еквівалентність. Зворотне, взагалі кажучи, невірне, бо елементарно еквівалентні АС можуть мати носії різної потужності. Наприклад, можна довести (Q, {<, =}) (R, {<, =}), але ці АС неізоморфні, бо множина Q зліченна, а множина R має потужність континууму.
Таким чином, якщо A B, то A B ; якщо A B, то A B.
Для доведення виразимості предикату P в АС A достатньо вказати таку формулу , що P суть A . В той же час для дове-дення невиразимості предикатів в АС доводиться використовувати потужніші засоби. Розглянемо метод доведення невиразимості предикатів в АС за допомогою автоморфізмів.
Теорема 6.1. Нехай автоморфізм АС A=(A, ). Якщо преди-кат P :AX?{T, F} виразимий в A, то P(d)=P( (d)) для всіх d AХ.
Нехай P виразимий в A деякою формулою сигнатури , тобто P суть A . Використовуючи твердження 2, маємо P(d)= А(d)= А( (d))=Р( (d)) для довільних d AХ.
Отже, для доведення невиразимості P в A досить знайти авто-морфізм системи A такий, що порушується умова P(d)=P( (d)).
Приклад 4. Предикат "z=x+y" не виразимий в АС Z<=(Z, {<, =}).
Відображення (х)=х+1 є автоморфізмом Z< , бо бієктивне і зберігає значення предикатів < та = . Але (0)=1, тому вірно 0=0+0 та невірно (0)= (0)+ (0).
Приклад 6. Предикат "xПриклад 7. Предикат "y=x+1" не виразимий в АС (N, {y=x+2, =}).
Відображення (х)= є автоморфізмом такої АС, бо бієктивне і зберігає значення базових предикатів. Предикат "y=x+1" позначимо Р(х, у). Тоді маємо Р(1, 0)=T та Р( (0), (1))=Р(0, 1)=F.
Приклад 8. Предикат "х=2" не виразимий в АС (N, { , =}).
Відображення, задане умовою (2a 3b c)=2b 3a c, є автоморфізмом такої АС, бо бієктивне і зберігає значення функції та предикату =. Предикат "х=2" позначимо Р(х). Тоді Р(2)=T та Р( (2))=Р(3)=F.
Loading...

 
 

Цікаве