Конструктивна математика

року міністерство освіти РФ.

СФ ПГУ.

Дисципліна «Інформатика і математика».

РЕФЕРАТ.

«Конструктивна математика».

Студентка:

Группа:

Преподаватель:

Северодвинск.

I. Вступ. Історія конструктивної математики 3 — 4 стр.

II.Основная часть.

1. Характерні риси конструктивної математики. 4 -11 стр.

2. Конструктивна семантика як сукупність способов понимания суджень в конструктивної математиці. 11−15 стр.

3. Структура конструктивної математики.

1).Конструктивное дійсне число.

15 стр.

2).Конструктивный объект.

16 -17 стр.

3).Конструктивное метричне простір. 17−18 стр.

III.

Заключение

Роль «конструювання» у математиці. 18−19 стр.

IV.

Список литературы

.

20 стр.

I.ВСТУПЛЕНИЕ.

ІСТОРІЯ КОНСТРУКТИВНОЇ МАТЕМАТИКИ.

Конструктивна математика, конструктивне направлення у математиці, -математика, будована відповідно до тим чи іншим конструктивним математичним світоглядом, зазвичай хто прагне пов’язувати твердження про існуванні математичних об'єктів із можливістю їх побудови і отвергающим це ряд установок традиційної теоретико — множинної математики, що призводять до появі чистих теорем існування (зокрема, абстракцію актуальною нескінченності та універсальному характері виключеного третього закону). Конструктивізм в математиці проявлявся протягом усього її історії, хоча, повидимому, лише К. Гаусс вперше чітко висловив принципове для конструктивної математики відмінність стає (потенційної) актуальною математичної нескінченності та заперечив проти вживання останньої. Подальші критичні кроки у цьому напрямі було зроблено Л. Кронекером, А. Пуанкаре і особливо Л Брауэром. У критиці Л. Брауэра, що збіглася по часу з кризою підстав математики кінця ХIX-начала XX в. в., енергійно відхилялася як віра у екзистенційний характер нескінченних множин, і переконання в допустимості необмеженої екстраполяції класичних логічних принципів, особливо закону виключеного третього. Як альтернативу теоретикомножинному підходу Л. Брауэр, та був та її послідовники, розробили оригінальну програму побудови математики, відому нині під назвою интуиционизм. Интуиционистскую математику Л. Брауэра вважатимуться першої систематичної спробою побудови математики на конструктивної основі. Паралельно успіхам интуиционистов у створеній Д. Гильбертом з метою обґрунтування теоретико — множинної математики доказів теорії було чітко виявлено ряд початкових понять, які послужили згодом відправною точкою відмінних интуиционизма конструктивних течій. Значна частина коштів відповідних робіт (у своїй виявився досить широке спектр тлумачення різними дослідниками термінів «конструктивний», «ефективний» тощо. буд.) спиралася на успіхи, досягнуті (знову — таки під впливом ідей Д. Гільберта) до вивчення математичного поняття алгоритму .Одне з найпослідовніших і закінчених підходів побудувати конструктивної математики цій основі доставляється заснованої А. А. Марковой радянської школою конструктивної математики, формування основних понять якої відноситься до 50-му рр. ХХ в. Сам термін «конструктивна математика» часто вживається у вузькому значенні слова для найменування математики, споруджуваної радянським конструктивним направлением.

II.ОСНОВНАЯ ЧАСТЬ.

1. ХАРАКТЕРНІ ЧЕРТЫ КОНСТРУКТИВНОЇ МАТЕМАТИКИ.

Конструктивна математика коротко то, можливо охарактеризована такими основними чертами:

. предметом вивчення є конструктивні процеси що у результат їхньої виконання конструктивні объекты;

. розгляд конструктивних процесів та виробляється у рамках абстракції потенційної здійсненності які з винятком ідеї актуальною бесконечности;

. інтуїтивне поняття ефективності пов’язують із точним поняттям алгоритма;

. використовується спеціальна, враховує специфіку конструктивних процесів та конструктивна логика.

Поняття конструктивного процесу об'єкта є початковими; ставлення до них мають своїм джерелом практичну матеріальну діяльність людини. Прикладами конструктивних процесів можуть бути складання годин на конвеєрі, повна чи часткова розбирання в ремонтної майстерні, набір текстів (з коректурами) у друкарні, формування та розформування поїздів тощо. Характерною рисою конструктивних процесів є протекающее щодо окремих кроків оперування у межах деяких чітко зазначених правив із елементарними, явно отличимыми друг від друга об'єктами, считающимися неразложимыми в ході цих процесів. Виникає внаслідок постаті, що складаються з вихідних елементарних об'єктів, і вважаються конструктивними об'єктами. Конструктивна математика — не має необхідності заглиблюватись у загальне поняття конструктивного процесу об'єкта, оскільки її потреб виявляється цілком достатнім один спеціальний вид конструктивних об'єктів — слова у цьому чи іншому алфавите.

Побудова слів (це поняття також представляється початковою) відбувається наступного основе.

Спочатку фіксується певний алфавіт, тобто список нерозкладних, впевнено відрізняються друг від друга елементарних знаків (літер). Кожна літера алфавіту може копіюватися; що у результаті послідовних актів такого копіювання прямолінійні ланцюжка знаків вважаються словами в вихідному алфавіті. До слів у цьому алфавіті зручно назвати також і порожній слово, тобто ланцюжок, яка містить жодного знака. Наприклад, ланцюжка «аввссд» і «книга» є словами у російському алфавіті. При зверненні зі словом конструктивна математика — й у проявляється її абстрактний характер — використовує абстракції ототожнення і потенційної здійсненності. Перша їх дозволяє, відволікаючи від відмінностей копій і оригіналу, казати про різних копіях даної букви і про ній самій, як про окремої букві. Наприклад, кажуть, що у слово «аввссд» тричі входить літера «в» російського алфавіту, тоді як насправді під час написання даного слова відтворилися три різних конкретних копії вихідної літери. Цю угоду природним чином поширюється на однакові з написання (рівні графічно) слова. Наприклад, про поїздку двох конкретних словах: слові «книга» і слові «книга» говорять як про один слові. У допущенні абстракції ототожнення проявляється гадана конструктивної математикою початкова здатність людини до «читання» слів, тобто до багаторазовому і стійкого упізнанню знакових ланцюжків як однакових чи різних. А ще обставина як мінімальну передумову будь-який наукової діяльності вказував Д.Гильберт. Абстракція потенційної здійсненності дозволяє нехтувати в міркуваннях про написанні слів реальними обмеженнями у просторі, часу й матеріалі. Отже, про уявних аж надто довгих словах починають розмірковувати як «про реально існуючих, зокрема вважають за можливе до будь-якого даному слову приписати справа (чи зліва) будь-який інший слово. Звідси випливає і можливість розгляду хоч греблю гати великих натуральних чисел, і навіть складання будь-яких двох натуральних чисел, оскільки натуральними числами можна, наприклад, вважати слова виду Про, OI, OII тощо. в алфавіті OI. Разом про те абстракція потенційної здійсненності Демшевського не дозволяє розглядати свого роду завершені «нескінченні» слова сукупність «всіх» слів у цьому алфавіті (зокрема, не сприймається як завершений об'єкт і натуральний ряд). Такі розгляду вимагають залучення сильнішою абстракції - абстракції актуальною нескінченності, яка відхиляється конструктивної математикой.

Прийняття абстракції потенційної здійсненності призводить до з того що поруч із елементарними, повністю обозримыми конструктивними процесами (наприклад, написанням коротких слів) розглядаються уявлювані, які підлягають реальному відтворення конструктивні процеси. Такі процеси задаються своїми вказівок; самі ці настанови з суті й стають предметом дослідження. Який Задає конструктивний процес розпорядження (для простоти йдеться про процеси, оперують зі словом) має бути у загальнозрозумілий і немає однозначно визначати крок по кроку послідовне побудова слів, причому кроки повинні прагнути бути елементарними, тобто не припускати нічого, крім вміння читати, писати (і прати) слова. Кроки ці, в такий спосіб, зводяться до написання і графічної порівнянню деяких слів, і навіть для заміни входжень одних слів до інших третіми словами. Закінчення процесу визначається самим розпорядженням і може залежати від результатів, отриманих на кроках, попередніх заключному, причому ухвалення рішення про заключному характері має бути описаний хіба що елементарний характер. Можлива ситуація, коли ніякої крок немає заключним, тобто після кожного досконалого кроку дане розпорядження вимагає зробити наступний крок. Такому розпорядження відповідає ніякої потенційно здійсненний конструктивний процес, однак виявляється зручною умовна термінологія, за якою відповідне розпорядження визначає необмежено продолжаемый (потенційно нескінченний) процес. Для виправдання цієї термінології можна було також розширити вихідні ставлення до конструктивних процесах, розглядаючи поруч із потенційно реалізованими процесами більш абстрактні освіти — процеси, отождествляемые зі своїми вказівок. У зв’язку з появою необмежено продолжаемых конструктивних процесів виникає запитання про засобах, з яких можна переконатися у обрабатываемости задаваемого даним розпорядженням конструктивного процесу. Конструктивна математика приймає тут важливий принцип, званий принципом конструктивного підбору і дозволяє встановлювати такі факти методом від супротивного, тобто наводячи до безглуздя припущення щодо необмеженої продолжаемости відповідного конструктивного процесу. Приклади розпоряджень: (1) написати I; (2) до произвольному слову в алфавіті OI приписати справа I; (3) п.1: написати I перейти до п.2; п.2: стерти I (то є замінити цю букву порожнім словом) перейти до п.1; (4) п.1: до произвольному слову в алфавіті OI приписати справа I перейти до п.2; п.2: якщо обрабатываемое в момент слово збігаються з OII, то закінчити процес, інакше повернутися до п.1; (5) п.1: написати Про і стати до п.2; п.2: до обрабатываемому в момент слову приписати справа I і можливість перейти до п.3; п.3: якщо вийшло досконале натуральне число, то закінчити процес, інакше приписати до обрабатываемому у цей момент слову справа I перейти до п. 2.Предписание «написати I «задає конструктивний процес, оканчивающийся за крок написанням однобуквенного слова I. Процес виконання (3) необмежено продовжуємо. У час невідомо, закінчується чи конструктивний процес, задаваемый (5) в (5) для стислості використовувалися теорії чисел. Кілька особливий характер мають розпорядження (2) і (4): виконання може початися вже з будь-якої світової слова у зазначеному алфавіті, у своїй конструктивний процес, определяемый (2), завжди закінчується, тоді як у розпорядження (4) він необмежено триває при деяких вихідних словах. Розпорядження зазначених типів прийнято називати алгоритмами (у цьому контексті йдеться про алгоритми, оперують зі словами).

До необхідності розгляду алгоритмів наводить конструктивна трактування экзистенциональных тверджень. Твердження про існування конструктивного об'єкта з цим властивістю, тобто твердження виду (x, А (x), відповідно до уявлення про конструктивних об'єктах, як результат конструктивних процесів вважається у конструктивної математиці встановленим у тому випадку, коли зазначений потенційно здійсненний конструктивний об'єкт, який закінчується побудовою шуканого об'єкта. Відповідно встановлення параметрического затвердження існування (x (у, А (x, у) («будь-кого x існує в такий, що, А (x, у)») передбачає вказівку «загального» конструктивного процесу, який з довільного конструктивного об'єкта x даного вихідного типу, і який спливає побудовою шуканого у. Інакше кажучи, (x (у, А (x, у) висловлює існування алгоритму, яке знаходить у, з x. З такої трактування існування випливає і конструктивне розуміння диз’юнкції: судження «А чи У» вважається встановленою, лише коли пред’явлено конструктивний процес, який закінчується зазначенням його вірного члена. Подальше роз’яснення сенсу суджень складнішою структури та вироблення правил роботи з ними, відповідних вихідним конструктивним настановам, становить завдання конструктивної семантики і створенні конструктивної логіки. Наведена конструктивна трактування тверджень існування й диз’юнкції істотно відрізняється від традиційної: в теоретикомножинної математиці, наприклад, судження (x, А (x) то, можливо доведено приведенням до безглуздя його заперечення. Таке доказ зазвичай зовсім позбавлений жодного способу побудови шуканого конструктивного об'єкта. Конструктивна математика вважає, що таке міркування доводить не (x, А (x), яке «подвійне заперечення», тобто (((x, А (x). Останнє судження у конструктивної математиці як, власне кажучи, більш слабке, ніж (x, А (x). Отже, конструктивна математика — не приймає закону зняття подвійного заперечення, а, отже, і прийняття закону виключеного третього (на відсутність підстав щодо прийняття останнього вказує конструктивна трактування дизъюнкции).

Початкові математичні структури — натуральні, цілі і раціональні числа — безпосередньо можуть трактуватися як слова деяких простих типів в фіксованому алфавіті, у своїй відповідні відносини рівності і близько легко зводяться до графічної збігу і розбіжності слів. Запровадження складніших структур — дійсних чисел, функцій над ними т. буд. -ввозяться конструктивної математиці з урахуванням поняття алгоритму, що грає у ній приблизно ті ж самі роль, яку відіграє в традиційної математиці поняття функції. Вважаючи інтуїтивні уявлення про алгоритми занадто розпливчастими для таких побудов, конструктивна математика робить тут принциповий крок, стандартизируя використовувані алгоритми через ухвалення однієї з сучасних точних визначень цього поняття разом із відповідною гіпотезою типу Чёрча тези, принципу нормалізації тощо., яка каже збіг оперативних можливостей, що доставляються алгоритмами в інтуїтивному і точному буквальному розумінні. Фактично найбільше використання у конструктивної математиці отримали нормальні алгорифмы Маркова. До необхідності уточнення поняття алгоритму наводить ще й конструктивна трактування існування. Наприклад, заперечення судження (x (у ((х, у) є твердження про неможливість деякого алгоритму, тим часом інтуїтивні уявлення, достатні для пізнання як алгоритму тієї чи іншої конкретного розпорядження, в принципі неможливо отримувати скільки-небудь нетривіальні теореми неможливості. За підсумками викладених принципів, і спираючись на сучасну теорію алгоритмів, конструктивна математика будує ряд математичних дисциплін, зокрема і конструктивний математичний аналіз, у тому числі елементи функціонального аналізу, дефференциальные рівняння, теорію функцій комплексного перемінного й т.д. Одержувані в такий спосіб теоретичні моделі, засновані більш скромною ніж обычносистеме абстракцій, хоч і поступаються традиційним в прозорості й елегантності, тим щонайменше, очевидно, здатні обслужити хоча б коло приложений.

Маючи загальний критичний джерело з интуиционимтической математикою Л. Брауэра і запозичивши з неї ряд конмтрукций й ідей, контруктивная математика виявляє певний схожість із останньої. Разом про те, тут є і принципові відмінності як общефилософского, і конкретно математичного характеру. Насамперед констуктивная математика поділяє интуиционизму переконання е початковому характері математичної інтуїції, вважаючи, що ця інтуїція формаируется під впливом практичної діяльності. Відповідно абстрагування в конструктивної математиці іде від розумових побудов як і интуиционизме. А від найпростіших реально можна побачити, конструктивних процесів. У математичному плані конструктивна математика — не приймає що виходить далеко за межі конструктивних процесів та концепцію вільно стає послідовності і засновану у ньому интуиционистскую теорію континууму як середовища вільного становлення. З іншого боку, интуиционистическая математика — не приймає правила конструктивного добору і вважає за необхідне елімінувати інтуїтивні алгоритми з допомогою відповідних точних визначень. Слід зазначити, що останні роки намітилася певна тенденція до зближення конструктивного і інтуїтивного підходів; у деяких конструктивних дослідженнях, в особливості які стосуються семантикою, використовуються індуктивні ухвали і відповідні їм індуктивні докази, схожі на побудови Л. Брауэра при доказі їм так званої бар-теоремы, займаної одне із центральних місць у интуиционистской математике.

2. КОНСТРУКТИВНА СЕМАНИТКА ЯК СУКУПНІСТЬ СПОСОБІВ ПОНИМАНИЯ СУДЖЕНЬ У КОНСТРУКТИВНОЇ МАТЕМАТИКЕ.

Небоходимость особливої семантикою викликана відмінностями загальних принципів, що у основі традиційної (класичної) і створенні конструктивної математики. Особливу увагу конструктивна семантика приділяє судженням про конструктивних об'єктах в мовами першого порядку, тобто, сутнісно, арифметичним судженням. Принципові відмінності з традиційною семантикою у сенсі диз’юнкцій (0((1 сформульовані Л. Брауэром. Контструктивное обгрунтування таких сужднеий вимагає розв’язання завдання: знайти число і (1 таке, що правильне Ai (відповідно знайти число n таке, що А (n)). Загальні принципи описи завдань, відповідних складнішим формулам юыли намічені А. Гейтингом і О. Н. Колмогоровым. Точна формулювання (що стали можлива після появи математичного визначення алгоритму) було дано З. Клини як поняття реалізації замкнутої арифметичній формули. Реалізація вернорго рівності t=r є фиксированнная константа, наприклад число 0, а хибне рівність немає реалізацій. Реалізація конъюнкции А&В -це пара (a, b), где a — реалізація А, а b — реалізація У. Реалізація диз’юнкції (0((1 — це пара (i, a), де і =0,1 і a — реалізація судження (1. Реалізація судження (x ((x) — це пара (n, a), де n — число, a — реалізація судження А (n). Реалізація судження (x ((x) — це загальний метод (, котрий за кожному натуральному n видає реалізацію ((n) судження А (n). Реалізація судження, А (У — це загальний метод (, котрий за будь-якої реалізації а судження, А видає реалізацію ((а) судження У (і може бути визначено для аргументів, а чи не є реализациями А). У цьому загальний метод сприймається як алгоритм (частково рекурсивна функція). Використовуючи кодування алгоритмів числами, можна записати умова «число е є реалізація формули А» як арифметичній формули (erA), не що містить диз’юнкції V і що містить існування (лише перед равенствами. Такі формули називаються майже нормальними. Судження (e (erA) (читане «А реалізована») може бути конструктивним роз’ясненням судження А. При такому розумінні закон исключённого третього (x (((x) ((А (x)) спростовується, наприклад, для A (x) = E y T (x, x, y), де T (e, x, y) означає, що алгоритм (з кодом) е завершує роботу над аргументом x за у кроків. Спростовується і закон подвійного заперечення (x (((У (x) (У (x)), наприклад для У (x)=((x) ((А (x). Наведене визначення пов’язує конструктивну завдання (пошук реалізації) із усіляким судженням A, навіть якщо, А містить (, (. Запропонований Н. А. Шаниным алгоритм виявлення конструктивної завдання не змінює формул без (, ((нормальних формул) і еквівалентний можливості бути реалізованим в формальної интуиционистической арифметиці з бескванторной індукцією. Самовільні формули зводяться до майже нормальним, оскільки підстави для майже нормальних формул, містять (і нетривиальное (.

А.А. Марков визначає істинність для майже нормальних формул з допомогою выводимости зі звичайних правилам для аналізованих логічних зв’язок плюс ефективне (-правило: якщо є загальний метод, дозволяє нічого для будь-якого n встановлювати выводимость А (n) з судження До, то (x ((x) виведено з До. Правдивість визначається поступово. Мова Я (, що з з формул без (,(; мову Яn+1, n (1, включаючи Яn і формули, які можна побудувати з формул мови Яn одним застосуванням імплікації і будь-яким числом застосувань А, &. Правдивість для Я1 — формул — це выводимость зі звичайних правилам для &, (, (. Правдивість для Я2 -формул визначається через допустимість відповідного правила. Наприклад, істинність (x R (x) ((y T (y) означає наявність алгоритму (такого, що R (n) (T (((n)) нічого для будь-якого числа n. Для Яn+1 — формул при n>1 істинність конъюкций і (-формул визначається звичайним чином через істинність компонента, а істинність імплікації А (У означає выводимость У з По деяким правилам Sn, про яких доведено, що вони зберігають істинність Яn — формул. Системи Sn містять (-правило, а ролі аксіом — все істинні Яn — формули. Поняття выводимости в Sn вводиться узагальненим індуктивним визначенням, а як доказ метатеорем застосовується відповідний принцип індукції. Індукцією по S2 — висновку доводиться допустимість правила (((((x R — А ((x R. Воно входить у S3 і дає принцип Маркова (((x R ((x R. Системи Sn+3, n (1, складаються зі звичайних правил для аналізованих зв’язок, включаючи (-правило. Виявляється, що майже нормальна формула, А істинною є по Маркову тоді й тільки тоді, коли примітивно рекурсивне дерево Tа пошуку виведення формули Без перерізу (але з (-правилом і принципом Маркова) є виведенням у сенсі індуктивного визначення. Це еквівалентно (у межах класичної математики) класичної істинності А.

У мажоритальной семантикою Н.А. Шаніна кожної майже нормальної формули, А визначається трансвинитная ієрархія {А (} формул простий структури, причому, А ((А доказово в підходящої формальної системі. Формула, А (називається мажоритарної для А, и, А вважається істинної формулою рангу (, якщо, А (правильна. Точність апроксимації із зростанням (: (< (((А ((А (). Якщо від технічних деталей, то формула, А будується з допомогою (- кратного винесення кванторів, відповідно до эквивалентности.

(((У ((((u (vC (u, v))((u (v (((B ((((u (vC (u, v) (C (u, v)), і згортання ланцюжків кванторів з допомогою алгоритму виявлення конструктивної завдання. Це дає доказуемую в арифметиці з транксфинитной індукцією до (эквивалентность.

А ((u (v ((((((w З ((D () з бесквантовой формулою З (, так что.

А (= (u (v (w З ((u, v, w) виявляється мажорантой для А. Судження виявляється з точністю до технічних деталей, еквівалентним утвердженню про існування виведення висоти.