Трансфінітна індукція - раздел Математика, Основи Дискретної математики
Твердження, Що Стосуються Елементів Деякої Повністю Упорядков...
Твердження, що стосуються елементів деякої повністю упорядкованої множини, можна доводити, використовуючи метод трансфінітної індукції, який є узагальненням методу математичної індукції й грунтується на теоремі про трансфінітну індукцію. Далі позначаємо відношення повного порядку через £, а вираз a<b означатиме, що а£b, але а¹b.
Теорема 14 (теорема про трансфінітну індукцію). Нехай <А,£>– повністю упорядкована множина, а0 – найменший елемент А, Р – деяка властивість (унарний предикат) на А. Нехай Р(а0)=1 та для довільного елементу а множини А з того, що Р(х)=1 для усіх х<а, випливає Р(а)=1. Тоді Р(х)=1 для усіх х з А.
Доведення. Припустимо, що твердження теореми не правильне. Тоді існує така непорожня підмножина В множини А (ВÌА), що Р(у)=0 для кожного у з В. Позначимо через b0 найменший елемент множини В. За нашим припущенням Р(b0)=0, тому а0¹b0 й а0<b0. За побудовою множини В Р(х)=1 для усіх тих елементів х множини А, для яких х<b0. Тоді за умовою теореми має бути Р(b0)=1, отже, маємо суперечність. Таким чином, теорему доведено.
Опишемо метод трансфінітної індукції. Нехай є повністю упорядкована множина <А,£> й задана властивість Р на А.
Базис індукції. Перевірити, чи виконується Р(а0)=1 для найменшого елементу а0 множини А. Якщо Р(а0)=1, перейти до наступного кроку, інакше завершити роботу (властивість Р не має місця для усіх елементів множини А).
Індукційний крок. Нехай а (а>а0) – деякий елемент множини А. Перевірити, чи випливає Р(а)=1 з того, що Р(х)=1 для усіх тих елементів х, що х<а (хÎА).
Якщо виконуються умови базису та індукційного кроку, то, спираючись на теорему про трансфінітну індукцію, можна зробити висновок, що Р(х)=1 для будь-якого елементу х множини А.
Метод математичної індукції, що використовується для доведення тверджень, котрі стосуються елементів множини N (або її підмножини), повністю упорядкованої відношенням £ (менше або дорівнює), є спеціальним випадком методу трансфінітної індукції. Суть методу така. Нехай є повністю упорядкована множина <А,£> (АÍN, £ – природний порядок на N) й задана властивість Р на А.
Базис індукції. Переконатися, що для найменшого елементу n0 множини А виконується Р(n0)=1.
Індукційний крок. Нехай k (k>n0) – деякий елемент множини А. Перевірити, чи випливає Р(k+1)=1 з того, що Р(k)=1.
Наведемо приклад застосування методу математичної індукції. Покажемо, що для будь-якого цілого додатного числа n виконується: 1+…+n=n(n+1)/2. У даному випадку розглядається властивість, подана у вигляді рівності, на повністю упорядкованій множині <N+,£>. Найменшим елементом цієї множини є число 1. Отже, маємо.
Базис індукції. Перевіряємо, чи виконується задана рівність для n=1, тобто чи правильна рівність 1=(1(1+1))/2. Легко перевірити, що рівність виконується.
Індукційний крок. Припустимо, що задана рівність виконується для деякого цілого додатного числа k, k>1, тобто 1+…+k=k(k+1)/2. Покажемо, що тоді задана рівність виконується й для числа k+1, тобто 1+…+k+(k+1)=((k+1)((k+1)+1))/2. Маємо:
Київський національний університет технологій та дизайну... М К МОРОХОВЕЦЬ...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Трансфінітна індукція
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
КИЇВ КНУТД 2005
УДК 51.681.3517
Конспект лекцій з курсу “Основи дискретної математики” для студентів спеціальності “Комп’ютерні науки” 6.0402
/ Автор М.К.Мороховец
Лекція 1. Поняття множини. Операції над множинами
Теорія множин як математична дисципліна створена німецьким мате-матиком Г.Кантором. Згідно з його визначенням, множиною є довільне зі-брання певних об’єктів н
Способи подання множин
Множина може бути задана явно або неявно. Якщо об’єктів, що склада-ють множину, небагато, множина задається явно шляхом перерахування цих об’єктів (а точніше, їх імен). На письмі мн
Включення та рівність множин
Нехай А та В – множини. Будемо говорити, що А включається у В, або А є підмножиною В (й позначати АÍВ), якщо кожен елемент множини
Операції над множинами
Об’єднанням множин А та В (позначається АÈВ) називається множина усіх об’єктів, що є елементами множини А або В, тобто
А
Властивості операцій над множинами
Теорема 1. Для будь-яких підмножин А, В, С універсальної множини U наведені нижче рівності є тотожностями (вираз А' слід розуміти як UА
Булеан множини
Кожна непорожня множина Х має принаймні дві різні підмножини: Æ та Х. Крім того, кожен елемент множини Х визначає деяку підмножину множини Х: якщо
Задачі та вправи
І. Описати словами множини:
1) {x| x=2y+1, yÎN}, 2) {x| x=2y-1, yÎN},
Декартів добуток множин
Упорядкованою парою об’єктів х та y (позначається <x,y>) будемо називати сукупність двох об’єктів (не обов’язково різних), які розташовані у
Поняття відношення
Термін «відношення» застосовується у математиці для позначення певного зв’язку між об’єктами. Відношенням R, заданим на множинах А та В, називається довільна підмножина декар
Операції над відношеннями
Нехай R1, R2 – відношення, задані на множинах A1,…,An. Об’єднанням відношень R1 та R2
Види бінарних відношень
Бінарне відношення R на множині А називається симетричним, якщо <x,y>ÎR Þ <y,x>ÎR. Пару
Відношення еквівалентності
Рефлексивне, симетричне та транзитивне відношення на множині А називається відношенням еквівалентності на А.
Прикладом відношення еквівалентності на мн
Фактор-множина
Нехай R – відношення еквівалентності на А. Тоді, як відомо, існує розбиття множини А, яке визначається відношенням R. Позначимо це розбиття через А
Замикання відношень
Рефлексивним замиканням бінарного відношення R, заданого на множині А (позначається Rr), називається відношення Rr=i
Задачі та вправи
І. Чи існують на множині {1,2,3,4} такі два різні відношення R та S, що: 1) Rr=Sr; 2) Rs=Ss; 3)
Відношення часткового порядку
Бінарне відношення R, задане на множині А, називається відношенням часткового порядку (частковим порядком на А), якщо R рефлексивне, антиси
Відношення лінійного та повного порядку
Відношенням лінійного порядку (лінійним порядком) на множині А називається такий частковий порядок на множині А, відносно якого порівнюються будь-які еле
Задачі та вправи
І. Які з відношень завдань XXVIІ-XXІX до попереднього розділу є відношен-нями: 1) часткового порядку, 2) строгого порядку, 3) передпорядку, 4) лінійного порядку, 5) повного порядку.
Поняття відображення
Відношення R, задане на множинах А та В, називається функціональним, якщо для кожного елемента xÎА існує не більше одного елемента
Види відображень
Відображення F множини А у множину В називається відображенням А на В (або сюр’єктивним відображенням, або сюр’єкцією), як
Задачі та вправи
І. Визначити, які з відображень є: а) частковими, б) сюр’єктивними,
в) ін’єктивними, г) взаємно однозначними. А={a,b,c,d}, B={b
Рівнопотужні множини
Множини А та В називаються рівнопотужними (еквівалентними), якщо існує взаємно однозначне відображення А на В.
Наприклад, множини
Потужність множини
Визначимо відношення ~ на множині усіх множин U: A~В Û А та В рівнопотужні. Дане відношення рефлексивне (А~А), симетричне (якщ
Задачі та вправи
І. Навести приклад множини Y, еквівалентної множині X={1,2,3,4,5}. Скільки взаємно однозначних відображень існує між Х та Y?
ІІ. Чи рівнопотужні
СПИСОК ВИКОРИСТАНОЇ ТА РЕКОМЕНДОВАНОЇ ЛІТЕРАТУРИ
1. Биркгоф Г., Барти Т. Современная прикладная алгебра. – М.: Мир, 1976. – 400 с.
2. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра, языки, программировани
СИМВОЛИ ТА ПОЗНАЧЕННЯ
N – множина усіх невід’ємних цілих чисел
N+ – множина усіх додатних цілих чисел
Z – м
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов