1611678155-8e243485e0094ed4164786c6208411db (826629), страница 4
Текст из файла (страница 4)
Обозначим этонасимволической записью |A| = |B|. Это определение — точная формализация того,что в A и B содержится одинаковое количество элементов.Замечание. Равномощность обладает свойствами отношения эквивалентности— для любых множеств A, B, C верно:a) |A| = |A|;b) |A| = |B| ⇒ |B| = |A|;c) |A| = |B| и |B| = |C| ⇒ |A| = |C|.1−1Запись |A| 6 |B| означает, что существует инъекция f : A −−→ B. Это понятие формализует то, что количество элементов в A меньше или равно количестваэлементов в B. Запись |A| < |B| означает, что |A| 6 |B| и |A| =6 |B|.Замечание.
Из |A| 6 |B| и |B| 6 |C| следует, что |A| 6 |C|.Лемма. Если A и B — непустые множества, то равносильно:a) |A| 6 |B|;наb) существует функция g : B −→ A;c) A равномощно некоторому подмножеству B.Если f : A → B и A1 ⊆ A, то через f [A1 ] обозначим множество {f (x) | x ∈ A1 }.Его называют образом A1 относительно f , и иногда обозначают как f (A1 ).Теорема Кантора–Бернштейна. Если |A| 6 |B| и |B| 6 |A|, то |A| = |B|.Теорема (о сравнимости мощностей). Мощности любых двух множествсравнимы, т.е.
|A| 6 |B| или |B| 6 |A| для любых множеств A, B.Теорема Кантора. |A| < |P (A)| для любого множества A.Множество A называется конечным множеством мощности k, если |A| = |Nk |,где k ∈ N, а Nk = {x ∈ N | x < k} = {0, 1, . . . , k − 1}. Множество бесконечно, еслионо не является конечным. Множество A счётно, если |A| = |N|, и континуально,если |A| = |R|, где R — множество вещественных чисел.Мы не будем доказывать некоторые свойства конечных множеств, считая их(почти) очевидными. Например то, что подмножество конечного множества является конечным. Они могут быть доказаны через свойства натуральных чисел.Предложение. Любое бесконечное множество содержит счётное подмножество.Множество A называется не более, чем счётным, если |A| 6 |N|.17Следствие. Множество не более, чем счётно, тогда и только тогда, когда оноконечно или счётно.2.12.
Мощности объединения и произведения множествЛемма. a) Если |A| = |A1 | и |B| = |B1 |, то |A × B| = |A1 × B1 |;b) если при этом A ∩ B = A1 ∩ B1 = ∅, то |A ∪ B| = |A1 ∪ B1 |.Лемма. |N2 | = |N|.Лемма. Если A — бесконечное множество, а B — конечное, то |A ∪ B| = |A|.Если A, B — два множества, то они сравнимы по мощности: |A| 6 |B| или|B| 6 |A|. Обозначим через max{|A|, |B|} бо́льшую из этих мощностей, т.е. |B| впервом случае и |A| во втором.Теорема (о мощности объединения). Если одно из множество A, B бесконечно, то |A ∪ B| = max{|A|, |B|}.Теорема.
Если A — бесконечное множество, то |A2 | = |A|.Теорема (о мощности произведения). Если A, B — непустые множества иодно из них бесконечно, то |A × B| = max{|A|, |B|}.Индексированное семейство {Ai }i∈I — это функция f такая, что dom(f ) = I иf (i) = Ai при i ∈ I.Теорема (об объединении семейства).
Пусть A — бесконечное множество.Если {Ai }i∈I — индексированное семейство множеств, |I| 6 |A| и |Ai | 6 |A| при[всех i ∈ I, то | Ai | 6 |A|.i∈IПредложение. Если ∆ — непустой алфавит, то мощность множества слов вэтом алфавите равна max{|∆|, |N|}.2.13. ОрдиналыОтношение изоморфизма разбивает класс всех в.у.м. на подклассы: каждыйподкласс состоит из всех в.у.м., которые изоморфны некоторому фиксированномув.у.м. Оказывается, что в каждом таком подклассе можно выбрать одно фиксированное в.у.м., которое можно считать его каноническим представителем. Оноявляется множеством специального вида, которое называется ординалом.
Ординалы иногда называют также трансфинитными числами.Замечание. Если n > 1 — натуральное число, то не существует множествx1 , . . . , xn таких, что x1 ∈ x2 ∈ . . . ∈ xn ∈ x1 . В частности, не существует x такого,что x ∈ x.18Множество α называется транзитивным, если из x ∈ α и y ∈ x следует, чтоy ∈ α. Множество α — ординал, если оно транзитивно и любые различные элементыв нём сравнимы относительно ∈. Последнее означает, что один из случаев x ∈ y,x = y, y ∈ x выполняется для любых x, y ∈ α. В дальнейшем ординалы часто будутобозначаться греческими буквами α, β, . .
.Лемма. Если α — ординал и β ∈ α, то β — ординал.Определим на классе ординалов порядок 6 так: α 6 β, если α ∈ β или α = β.Запись α < β, как обычно, обозначает α 6 β и α 6= β.Лемма. Любой ординал α с порядком 6 на его элементах является в.у.м.Далее, говоря об ординале как о в.у.м., мы будем подразумевать, что на егоэлементах задан этот порядок 6 (естественный порядок на ординале).Лемма (о порядке на ординалах).
Для любых ординалов α, β равносильно:a) α 6 β;b) α ⊆ β;c) α — начальный сегмент в β.Теорема (о порядке на ординалах). Класс ординалов с порядком 6 обладает свойствами в.у.м. — для любых ординалов α, β, γ верно:a) α 6 α;b) α 6 β и β 6 α ⇒ α = β;c) α 6 β и β 6 γ ⇒ α 6 γ;d) α 6 β или β 6 α;e) в любом непустом множестве ординалов есть минимальный элемент.Определим α + 1 как α ∪ {α}.Замечание.
Если α — ординал, то α + 1 тоже является ординалом, α < α + 1и не существует ординала β такого, что α < β < α + 1.Предложение (о супремуме множества ординалов). Объединение любогомножества ординалов A вновь является ординалом, который является супремумоммножества A.Обозначим ординал из предыдущего предложения как sup(A).Выше мы определяли натуральные числа так: 0 = ∅ и n+1 = n∪{n}. Поскольку∅ является наименьшим ординалом, ординалами будут и все множества 1, 2, .
. .Они образуют начальный сегмент в классе всех ординалов. Их объединение равномножеству всех натуральных чисел ω = {0, 1, 2, . . .}. Тем самым ω — ординал,следующий за всеми натуральными числами. Далее будут идти ω + 1, (ω + 1) + 1,и т.д.Теорема (о полноте класса ординалов). Для любого в.у.м. существуетединственный изоморфный ему ординал.19Предложение (принцип трансфинитной индукции). Пусть Φ(x) — некоторое условие.
Пусть для любого ординала α из того, что Φ(β) верно для всехβ < α, следует, что верно Φ(α). Тогда Φ(α) верно для всех ординалов α.Как и аксиоме подстановки ZFC, точное определение условия Φ(x) требует использования формул ИП. Тем самым предложение сформулировано пока не совсемформальной. Приведём в ещё более неформальном виде другой важный факт.Предложение (принцип трансфинитной рекурсии).
Пусть существуетусловие, которое для каждого ординала α однозначно задаёт некоторое множествоfα в предположении, что при β < α множества fβ уже определены. Тогда каждомуординалу α действительно можно сопоставить множество fα так, чтобы указаннаясвязь между fα и fβ , β < α, выполнялась. При этом fα определено однозначно.Ординал α — предельный, если α 6= 0 и его нельзя представить в виде β + 1 длянекоторого ординала β.Пример. Для любых двух ординалов α, β существует ординалы α + β и α · β,обладающие свойствами:a) α + 0 = α и α · 0 = 0;b) α + (β + 1) = (α + β) + 1 и α · (β + 1) = (α · β) + α;c) α + λ = sup{α + β | β < λ} и α · λ = sup{α · β | β < λ}, если λ — предельныйординал.Отметим, что на языке ординалов определение натурального числа звучит так:α — натуральное число, если α — непредельный ординал и любой β ∈ α — тоженепредельный ординал.2.14.
КардиналыОрдинал µ называется кардиналом, если он неравномощен никакому меньшемуординалу.Теорема (основное свойство кардиналов). Для любого множества A существует единственный кардинал µA такой, что |µA | = |A|.Предложение. Если A, B — множества, тоa) |A| = |B| ⇔ µA = µB ;b) |A| 6 |B| ⇔ µA 6 µB .Определим теперь понятие мощности: |A|, мощность множества A — это кардинал, равномощный A, то есть µA . Последнее предложение показывает, что этоопределение согласуется с нашей прошлой системой обозначений.Пример.
Ординал ω и все натуральные числа n ∈ ω являются кардиналами.203. ЯЗЫК ИСЧИСЛЕНИЯ ПРЕДИКАТОВИ ЕГО СЕМАНТИКА3.1 Формулы исчисления предикатов (ИП)Чтобы определить понятие формулы ИП, нужно в первую очередь зафиксировать некоторое множество символов, которое называется сигнатурой (или языком).Это множество соответствует тому набору исходных понятий, о которых мы собираемся говорить на языке формул. Оно состоит из трёх частей — из предикатных,функциональных и константных символов.Формально определим сигнатуру Σ как четвёрку вида (PrΣ , FnΣ , CnΣ , ν), гдеν : PrΣ ∪ FnΣ → N \ {0}, а множества PrΣ , FnΣ , CnΣ попарно не пересекаются.
Элементы множества PrΣ называются предикатными символами, элементыFnΣ — функциональными символами, а элементы CnΣ — константными символами. Функция ν каждому предикатному и функциональному символу сопоставляетненулевое натуральное число, которое называется местностью этого символа.Поскольку сигнатура — всего лишь набор символов, её строгое определение неочень существенно. Если, например, PrΣ = {P1 , . . . , Pt }, FnΣ = {f1 , .
. . , fs }, CnΣ ={c1 , . . . , cr }, то сигнатуру Σ будем иногда обозначать так:Σ = (P1n1 , . . . , Ptnt ; f1m1 , . . . , fsms ; c1 , . . . , cr ),где ni — местность символа Pi , а mj — местность fj .Выбрав сигнатуру Σ, можно определить исчисление ИПΣ . Определим сначалатермы и формулы ИПΣ . Алфавит ИПΣ состоит из четырёх непересекающихся частей:1) символы из Σ2) предметные переменные: v0 , v1 , v2 , . . .3) логические символы: &, ∨, →, ¬, ∃, ∀, =4) вспомогательные символы: запятая и две скобки, левая и правая.Символ ∃ называется квантором существования, а ∀ — квантором всеобщности. Предметные переменные в этом разделе часто будут называться простопеременными и обозначаться символами x, y, z и производными от них.Терм ИПΣ — слово в этом алфавите, которое строится по правилам:1) любая переменная x — терм;2) любой константный символ c из Σ — терм;3) если f — функциональный символ из Σ местности m, а t1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
