01_-_mnozhestva_otobrazhenia_logika

Доказательство

Предположим противное. Пусть для некоторого множества A существует взаимно однозначное соответствие элементов этого множества и множества 2A .

Обозначим как Bx множество, соответствующее элементу x A.

Рассмотрим множество D = {x | x Bx }. То есть это все такие элементы из A, которым соответствуют подмножества A, не содержащие эти элементы. Если для некоторого элемента - y A

справедливо равенство By = , то y D.					Следовательно,			D .
Возьмем y A такое что D = By .
Возможен лишь один из следующих случаев:
а) y By ;
b) y By.
В первом	случае	имеем:	если	y	By ,	то y	D, т.е.
y By.
Во втором случае:		если y By ,		то y D.		Поэтому y By ,
т.е. в обоих случаях получаем противоречие.
Поэтому	предположение		о	существовании				взаимно
однозначного соответствия между элементами						A и 2	A	является

неверным.

Доказательство окончено.

1.2. ОТОБРАЖЕНИЯ И ФУНКЦИИ

Понятие отображения является фундаментальным для современной математики, поскольку всякий ее раздел связан с исследованием специальных множеств объектов вместе с системой операций над элементами множеств. Отображения являются важным случаем таких операций.

1.2.1. ОСНОВНЫЕ ПОНЯТИЯ

Пусть A и B непустые множества. Отображением множества A во множество B называется всякое соотнесение каждому элементу множества A единственного элемента множества B.

15

При этом множество A называется областью определения, а

B множеством значений отображения.

Для обозначения отображений будем использовать малые символы латинского алфавита.

Если f отображение множества A во множество B, то для представления этого факта применяется специальное обозначение f : A B.

Пусть отображение f: A B ставит в соответствие элементу

a A элемент b	B. В этом случае будем говорить, что f
переводит a в b, и использовать запись f(a) = b.
Если f: A	B, то запись f(A) обозначает множество

элементов, в которые f переводит элементы A.

Отображение f: A B называется отображением множества A на множество B (или сюръекцией), если f(A) = B. В противном

случае отображение называется отображением множества A во множество B.

Отображение f называется инъективным, если оно переводит разные элементы A в разные элементы B.

Замечание. Содержательно отображение f является сюръективным, если в каждый элемент B отображается хотя бы один элемент множества A. Отображение f инъективно, если в каждый элемент множества B отображается не более одного

элемента из A.

Наглядным способом представления произвольных отображений являются диаграммы, имеющие вид (рис. 1.1):

A B

a	f	3
b		1
c		2
d

Рис. 1.1

Здесь элементы множеств A и B замкнутых областей на плоскости,

изображаются точками а отображение f,

16

сопоставляющее элементам A элементы B, ориентированными дугами, соединяющими элементы A с соответствующими им

элементами B.

Рассмотрим пример диаграммы (рис. 1.2), на которой изображено неинъективное и несюръективное отображени е.

A	B
a	f
b	x
c	y
d	z
	Рис. 1.2

Отображение f неинъективно, поскольку f(a) = f(c). Кроме того, f это несюръективное отображение, так как элементу y не соответствует ни один элемент A.

Пусть f: A B. Обозначим как f 1 соответствие элементам множества B совокупностей элементов A, определяемое по следующему правилу: если b B, то f 1 ставит в соответствие b те элементы множества A, которые отображением f переводятся в элемент b.

Обозначим совокупность таких элементов как f 1 (b). Для

приведенной ранее диаграммы соответствие f 1 имеет следующий вид :

f 1 (x) = {a, c, d}, f 1 (y) = , f 1 (z) = {b}.

Если f 1 сопоставляет каждый элемент B с одноэлементным множеством, то это соответствие порождает отображение, переводящее каждый элемент B в единственный элемент множества, соответствующего этому элементу. Такое отображение

называется отображением (или функцией), обратным к f, и обозначается тем же символом, что и определяющее его соответствие элементов B и подмножеств A. Очевидно, что в

приведенном примере отображение f не имеет обратного к нему отображения.

17

ТЕОРЕМА 1.4

Отображение f имеет обратное отображение тогда и только тогда, когда f является инъективным и сюръективным.

Доказательство

Необходимость. Пусть отображение f : A B имеет обратное отображение. По определению обратной функции это означает, что в каждый элемент множества B отображение f

переводит хотя бы	один элемент	A. Поэтому f(A) = B, т.е.
f это сюръективное отображение.
Поскольку f 1	отображение,	то отображение f переводит в

каждый элемент b B ровно один элемент a A. Следовательно, f это инъективное отображение.

Достаточность. Пусть отображение f - инъективное и сюръективное. Тогда в каждый элемент b B отображение f

переводит единст венный элемент a A, т.е. f 1 является отображением.

Теорема доказана.

1.2.2. ПРОИЗВЕДЕНИЕ ОТОБРАЖЕНИЙ

Пусть f: A B и g: B C. Тогда отображение h: A C, для которого h(a) = c тогда и только тогда, когда из того что

f(a) = b следует, что g(b) = c, называется произведением или композицией этих отображений. Произведение отображений f и g записывается в виде h = g o f .

Содержательно отображение h получается последовательным

применением отображений f и g. Наглядное представление произведения отображений приведено на рис. 1.3.

A		B		C
			h
a	f	b	g	c
			Рис. 1.3

18

f(x1 , ... ,

Упражнение. Доказать, что произведение отображений обладает свойством ассоциативности, т.е. для любых отображений f, g, h, для которых определено произведение h (g f ) ,

справедливо равенство: h o( g o f ) = (h o g) o f .

Обобщением операции композиции отображений является операция суперпозиции. Такая операция применяется тогда, когда области определений представляют собой произведения систем множеств или части таких произведений. Суперпозиция отображений связана с подстановкой вместо отдельных компонент наборов элементов из области определения заданной функции других функций, области значений которых содержатся во множествах значений заменяемых компонент.

Пусть f: A B и A = A1 ... An . Для работы с компонентами элементов области определения такой функции

используют представление f в виде xn ). В этой записи символы переменных x1 , ... , xn обозначают компоненты элементов множества A.

Пусть i это некоторое число из множества { 1, ... , k}, и задана еще одна функция: g: D1 ... Dk Ai , представляемая в виде g(v1 , ... , vk). Обозначим как { w1 , ... , wm} множество из всех переменных f, за исключением xi и всех переменных g.

Тогда суперпозицией f и g, в которой функция g(v1 , ... , vk)

подставляется в		f	вместо		xi ,	называется	такое		отображение
h(w1 , ... , wm), когда для каждого набора ( 1 , ...								,	m) значений
переменных w1 , ... , wm выполнено соотношение
	h( 1 ,		... , m)= f ( 1 , ... i 1, , i + 1					, …, n ).
В последнем соотношении 1 , ... i 1,							i+1	,	…, n	это
значения	переменных			x1 ,	...	xi 1, xi+1 ,	…,	xn	в	наборе
( 1 , ... ,	m), а =	g( 1 ,		... ,	k),	где 1 , ... ,	k	значения v1 , ... ,

vk, выбираемые из того же набора.

Для обозначения суперпозиции функций f и g применяется специальная запись f(x1 , ... xi 1, g(v1 , ... , vk), xi+1, …, xn ).

19

Если к некоторой функции f операция суперпозиции применяется несколько раз по различным переменным, то

получаемое в результате отображен ие называется суперпозицией f и отображений, подставляемых вместо переменных f.

Если все переменные отображения f(x1 , ... , xn ) заменяются

на g1 (v1 , 1 , ... , v1, k1 ), ... , gn(vn, 1 , ... , vn, kn ) соответственно, то такая суперпозиция представляется записью:

f(g1 (v1 ,1 , ... , v1, k1 ),., ... , gn(vn, 1 , ... , vn, kn ).

1.3. ЛОГИКА ДОКАЗУЕМОСТИ И ИСТИННОСТИ

1.3.1. ВЫСКАЗЫВАНИЯ

ОПРЕДЕЛЕНИЕ

Высказыванием называется всякое предложение, о котором можно сказать, что оно является истинным или ложным.

Истинностные знач ения высказываний “ истина“ и “ложь“ сокращенно будем записывать с помощью символов “ t“ и “f“.

Например, предложение “ Новороссийск приморский город“ образует высказывание, которое является истинным и принимает истинностное значение “ t“.

Утверждение “Солнце восходит на западе “ образует ложное высказывание, истинностное значение его равно “ f“.

Некоторые предложения не принимают никакого конкретного истинностного значения и не являются высказываниями. Например, предложение “ В январе дни короче, чем в июне“ не может быть истинным или ложным, так как для северного полушария оно истинно, а для южного ложно. Приведенное предложение можно рассматривать как неточное или неправильное, которое можно уточнить так, чтобы получить высказывание. Например, “В январе в северном полушарии дни короче, чем в июне “ это истинное высказывание, а “ В январе в Аргентине дни короче, чем в июне “ ложное высказывание.

Содержательно высказывание указывает на наличие свойства предмета или предметов, о котором говорится в соответствую щем

20

предложении. В первом	примере говорится	о свойстве	объекта
(города Новороссийск)	располагаться в	определенном	месте

(являться приморским городом). Об аналогичном свойстве идет речь и в другом высказывании: “ Одесса - приморский город“. В обоих случаях высказывания являются конкретизациями одной и той же конструкции, различаются только именем объекта населенного пункта. На основе этой и других подобных

конструкции	можно	строить	многочисленные	примеры
высказываний.
1.3.2. ПАРАДОКСЫ
Парадоксы это		утверждения, которые		интуитивно

представляются осмысленными и указывают на конкретные свойства предметов, но не являются ни истинными, ни ложными. Широко известен пример такого предложения, называемый парадоксом лжеца.

Рассмотрим высказывание некоторого человека , который говорит о себе: "Я лжец". Для простоты будем считать, что всякий человек может быть либо лжецом, т.е. всегда лгать, либо не быть лжецом и всегда говорить правду. Поэтому мы будем понимать смысл произнесенной фразы как признание в том, что этот человек всегда лжет.

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

Предположим, что предложение является истинным, и построим следующую цепочку рассуждений:

1)поскольку сказанное человеком истинно, то данный человек всегда лжет;

2)так как человек всегда лжет, то он лжет и в данном

случае;

3)поскольку человек лжет, то предложение "Я лжец"

ложно.

Следовательно, предложение "Я лжец" не является

истинным.

21

Рассмотрим второй возможный случай. Предположим, что данное предложение является ложным. Тогда построим следующую цепочку рассуждений:

1)поскольку данное предложение ложно, то человек не является лжецом;

2)так как человек не лжец, то сказанное в предложении является истинным;

3)следовательно, приведенное предложение должно быть истинным, а значит, предложение " Я лжец" не является ложным.

Окончательно получаем, что интуитивно понятное и допускаемое в качестве высказывания предложение не имеет никакого истинностного значения, или не имеет смысла.

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

и деятельности. Последнее замечание связано с тем, что традиционные схемы рассуждений и решения задач основаны на использовании понятия истинности исходных данных утверждений, получаемых в процессе рассуждений, и делаемых в процессе вывода заключений.

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

В частности, для парадокса лжеца попытка доказательства истинности соответствующег о предложения приводит к установлению его ложности. Верно и обратное, на основе ложности предложения с помощью приведенных ранее рассуждений устанавливается его истинность.

Противоречие, аналогичное парадоксу лжеца, может содержаться и в совокупностях свя занных и интуитивно осмысленных предложений.

Например, рассмотрим факты, сообщенные в качестве начальной информации двумя лицами А и В:

22

А: "То, что говорит В ложно"; В: "То, что сказал А истинно".

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

Естественный способ, позволяющий избежать использования внутренне противоречивой информации, состоит в применении ограниченных языковых средств, позволяющих формировать высказывания.

Например, в приведенных примерах речь фактически идет об утверждениях, содержащих не столько информацию об окружающем мире, сколько говорящих об истинности утверждений об этом мире (в частности, о своем истинностном значении).

К логическим парадоксам близки так называемые семантические или смысловые парадоксы, представляемые предложениями, которые интуитивно имеют смысл, но в действительности та ковыми не являются.

Вкачестве примера рассмотрим парадокс брадобрея или парадокс парикмахера, который содержится в следующем предложении:

"В городе живет брадобрей, который бреет всех мужчин города, которые не бреются сами ".

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

Взаключение рассмотрим пример парадокса, связанного с неточным определением множества, данным в предыдущем разделе. Для этого введем такое понятие, как множество всех множеств.

С точки зрения использованного ранее интуитивного

понятия множества, множество всех м ножеств это совокупность, элементами которой являются любые множества. Поэтому интуитивно эта совокупность множеств также является множеством множеств. Общее свойство элементов множества всех множеств быть множеством.

23

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

Последний пример свидетельствует о некорректности интуитивного понятия множества и указывает на необходимость аккуратного применения этого понятия при проведении рассуждений, чтобы избежать противоречивых конструкций и выводов из-за использования некорректных объектов.

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

1.3.3. ПРЕДИКАТЫ

Ранее приводились примеры высказываний, являющихся уточнениями некоторого общего утверждения, не явля ющегося высказыванием. Такие общие утверждения носят название высказывательных форм и используются как обобщение понятия высказывания, в котором представлено несколько отдельных высказывания или групп отдельных высказываний.

ОПРЕДЕЛЕНИЕ

Высказывательной ф ормой или предикатом называется всякое предложение, содержащее наименования неопределенных объектов или неизвестных, которое превращается в высказывание после подстановки в него конкретных объектов вместо имен неопределенных объектов.

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

Например, к высказывательным формам относится предложение “x учится в школе с номером y“. Здесь x обозначает

24