Московский инженерно-физический институт Математический анализ Логинов а.С.

Лекция 1 (1997=>2004)

Глава 1. Введение

§1. Некоторые понятия теории множеств и математической логики

1.Множество, операции над множествами, обозначения

Множество - совокупность некоторых различимых объектов. Задать множество - задать признаки, характеризующие эти объекты.

Примеры:

N - натуральные числа [a,b] - отрезок

Z - целые числа a, b) – интервал, (a,b],[a,b) - полуинтервалы

Q - рациональные числа

R - вещественные числа xE, xE

Подмножество A  E

- пустое множество E, EE

Обозначение множества печислением - {a, b, c}

Обозначение множества указанием характеризующего свойства - { x : x удовлетворет свойству P}. Пример: N={xZ:x>0}

[a,b]={x: ax,xb}

Дополнение (разность) E\A={xE:xA}

Пересечение AB ={x:xA и xB}. Если два множества не пересекаются. то это можно записать в виде AB=.

Объединение AB ={x:xA или xB}.

Произведение множеств AxB ={(x,y):xA и yB}.

Пример R² = R x R - плоскость.2. Отображение, взаимно-однозначное соответствие, счетное и несчетные множества

Даны множества A и B. Отображение A в B (или функция определенная на A со значениями в B) - cоответствие или закон (обозначим его f ), которое каждому a A сопоставляет единственное b  B, A B, f: A B, b = f(a).

a - прообраз, b - образ при отображении f.

Отображение из A в B называется взаимно-однозначным, если

1) разные элементы из A имеют разные образы

2) каждый элемент из B является образом некоторого элемента из A

Эквивалентные множества A  B или множества одинаковой мощности, если существует взаимно-однозначное соответствие между элементами этих множеств.

Счетное множество A  N

Пример: Множество рациональных чисел счетно.

Одно из простейших свойств счетных множеств

Объединение конечного или счетного числа счетных множеств является счетным множеством.

Несчетные множества

Бесконечное множество, не являющееся счетным, называется несчетным. Множество [0,1] имеет большую мощность, чем N. Множество мощности континиума. R - несчетное множество хR  [ 0, 1 ]

3. Некоторые понятия математической логики (Дж. Маллас Пролог)

При описании логики Аристотеля употребляется понятие суждение. Суждение представляет собой законченную мысль, выраженную средствами естественного языка и (согласно Аристотелю) состоит из четырех элементов:

Квантор Субъект Связка Предикат Все числа являются не рациональными

Некоторые натуральные числа - четны

В последнем случае подразумевается связка “являются”. В первом случае обычно говорят также: “Все числа не являются рациональными”. Вместо термина предикат мы будем использовать также термин свойство. Противоположное свойство P или отрицание свойства P обозначается значком или .

В традиционной логике допускаются два типа суждений, каждый из которых характеризует возможные отношения между двумя классами (классом субъектов и классом предикатов):

Все S являются P ( каждый из S удовлетворяет свойству P )

Некоторые из S являются P ( существует представитель из S, удовлетворяющий свойству P )

Здесь S обозначает класс субъектов, а P - класс предикатов ( или некоторое свойство, характеризующее этот класс ). Все, каждый, любой, произвольный называются универсальным кванторам или кванторам общности. Квантор общности обозначается . Некоторые из, существует -экзистенциальные кванторы. Квантор существования обозначается . Таким образом основные типы суждений можно записать в следующей форме ( логической связке соответствует символ двоеточия ):

1. xS:P

2. xS:P

Предикат и субъект в суждении могут быть составными, в частности они сами могут быть суждениями. Например, рассмотрим высказывание:

>0 >0 x,|x-x₀|< : |f(x)-2|<.

Это высказывание следует читать так: Для любого эпсилон больше нуля существует дельта больше нуля, что для всех икс, удовлетворяющих неравеству …, выполнено неравенство …. Это суждение является составным и может быть разложено на простейшие суждения следующим образом:

S₁ : P₁, где S₁-класс, S₁={xR,x>0}, P₁ - предикат,

P₁=(S₂ : P₂), где S₂=S₁, P₂ - предикат,

P₂=(xS₃: P₃), S₃= S₃()={xR:|x-x₀|<}, P₃ - предикат,

Прямая и обратная теоремы, эквивалентность, метод математической индукции

Структура простейшей теоремы выглядит следующем образом: дано свойство (условие) A, из него выводится свойство (заключение) B.

В этом случае говорят A влечет B . A B ( последняя запись подразумевает на самом деле истинность выражения A B).

Если к томе же B A, то говорят, что верна и обратная теорема и пишут AB, при этом A и B называются эквивалентными.

Теорема. Отрицание суждения должно строится по следующим формальным правилам:

1. квантор  заменяется на квантор 

2. квантор  заменяется на квантор 

3. предикат P заменяется на свое отрицание.

Пример:

>0 >0 x,|x-x₀|< : |f(x)-2|<.

его отрицание

>0 >0 x,|x-x₀|< : |f(x)-2|.

Для доказательства отметим, что любое высказывание (составное суждение) может быть сведено к двум типам простейших суждений:

1. x: P

2. x: P,

где P некоторое суждение, поэтому требуемое утверждение достаточно доказать для двух этих суждений, но для простейших суждений сформулированная теорема очевидна.

Метод математической индукции

Есть последовательность свойств P_n. Если доказано свойство P₁ и P_k P_k+1, то P_n справедливы для nN.

Пример: Доказать индукцией равенство C_n^k + C_n^k+1=C_n+1^k+1, .

Лекция 2

4.Вещественные числа

1. Свойство упорядоченности

a, b либо a < b либо a = b либо a > b

1.1 a < b, b < c  a < c ( свойство транзитивности )

( a < b ) или ( a = b ) , то пишут a  b

2. Свойства операции сложения (a,b  a+b)

1. a + b = b + a (коммутативность)

( точнее было бы написать a:( b: a + b = b + a) )

2.2 a + ( b + c ) = ( a + b ) + c (ассоциативность)

2.3 0, a  R : a + 0 = a

2.4 a  противоположный - a : a + (-a) = 0

2.5 a < b  a + c < b + c ,( c )

3. Свойства операций умножения (a,b  ab)

3.1 a b = b a (коммутативность)

3.2 a ( b c ) = ( a b ) c (ассоциативность)

3.3 1, a  R : 1 a = a 3.4 a0a^-1(обратный ): a a^-1 = 1

3.5 a < b и c > 0 a c < b c

a < b и c < 0 a c > b c

4. Связь операций

4.1 ( a + b ) c = a c + b c ( дистрибутивность )

Определение

| a| =

Свойства | a + b |  | a | + | b |, | | a | - | b | |  | a – b |

5. Свойство Архимеда a nN: n > a. Следствие: a>0 b nZ: na > b

6. Свойство непрерывности вещественных чисел или Принцип вложенных отрезков.

Вначале некоторые определения.

Отрезок или сегмент - [a,b]={x:axb}, b-a - длина

Система вложенных отрезков. Система отрезков {[a_j,b_j]} называется системой вложенных отрезков, если  j: [a_j+1,b_j+1][a_j,b_j] .

Принцип вложенных отрезков. Для всякой системы вложенных отрезков существует хотя бы одно число, общее для всех отрезков. Множество элементов, удовлетворяющее свойствам 1 - 6 называется множеством вещественных чисел и обозначается R. Числовая ось - изображение действительных чисел. Терминология “Точки”

Определение. Система отрезков стягивается к 0, если

>0 N n>N: b_n-a_n < 

Лемма Кантора. Для всякой системы вложенных стягивающихся к нулю отрезков [a_j,b_j] существует единственное число, принадлежащее всем отрезкам данной системы.

Доказательство. Одно существует, например, x. Пусть есть другое, например, y и x < y. Тогда

a_n  x < y  b_n  y – x  b_n - a_n.

Возмем  = y – x,  N, n > N: b_n - a_n < , что противоречит предыдущему неравенству.