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

   
На этом шаге мы дадим определение и приведем примеры таких множеств.

Определение.
Вполне упорядоченным множеством называется множество X, на котором определено бинарное отношение <, обладающее следующими свойствами:

  • если х,y,z ∈ Х, а х<y и y<z, то х<z;
  • для х,y ∈ Х справедлива одна и только одна из трёх возможностей: либо х<y, либо y<х, либо х=y;
  • любое непустое подмножество Х содержит наименьший элемент, т.е. если А - любое непустое подмножество Х, то в множестве А существует некоторый элемент х,
    такой, что для любого y ∈ А либо х=y, либо x<y.
  • Определение.

     Будем говорить, что бинарное отношение < вполне упорядочивает множество Х, если X является вполне упорядоченным множеством.
    Теорема.

    Для любого частично упорядоченного множества X перечисленные ниже условия эквивалентны.

  • Условие минимальности. Всякое непустое подмножество множества X обладает хотя бы одним минимальным элементом.
  • Условие обрыва убывающих цепей. Всякая строго убывающая последовательность a1 > a2... >an > ... элементов из
    X (называемая  цепочкой) не может быть бесконечной.
  • Условие индуктивности. Пусть для всякого x ∈ X задано некоторое высказывание S(x). Все высказывания S(x), x ∈ X, справедливы, если будут выполнены два
    требования: (а) если x0 - минимальный элемент в X, то высказывание S(x0) справедливо; (б) если x не минимальный элемент в X и для всякого у<х (у ∈ X) высказывание
    S(у) справедливо, то справедливо и S(x).
  • Доказательство.

    (1) Пусть множество X удовлетворяет условию (1); покажем, что тогда выполнено (3). Предположим, что это не так.

    Пусть А ⇔ {х¦х ∈ Х, S(x)  ложно}. Если S(x) не справедливо для всех х в Х, то А - непустое подмножество Х. Т.к. X вполне упорядочено, то
    известно, что А содержит наименьший элемент а0. По определению, это наименьший элемент Х, для которого S(x) не справедливо. Таким образом, S(y) справедливо
    для всех у (если они есть), удовлетворяющих условию у<а0. Если а0 - наименьший элемент в Х, то S(a0) справедливо, что следует из
    первого положения. В противном случае из справедливости S(y) для всех у<а0 и второго положения вытекает, что S(а0) справедливо. Но это противоречит
    предположению, состоящему в том, что а0  принадлежит А и S(а0) ложно. Единственный способ устранить это противоречие - считать А пустым множеством,
    т.е. в Х нет элементов, для которых высказывание S(x) ложно.

    (2) Пусть выполнено (3), покажем выполнение (2). Условие индуктивности применим к высказываниям S(x) (x ∈ Х): "всякая строго убывающая цепочка элементов из S, начинающая с элемента x, конечна".
    Высказывание S(x) справедливо для всякого минимального элемента x0 ∈ Х, т.к. любая строго убывающая цепочка указанного вида состоит из одного элемента x0.
    Пусть x - не минимальный элемент в Х, а для всех у<x (у ∈ Х) высказывания S(у) справедливы. Тогда для произвольной строго убывающей цепочки x>a2>a3>...,
    ввиду справедливости S(a2), получаем, что цепочка a2>a3>... конечна, а потому конечна и вся цепочка, т.е. высказывание S(x) справедливо. Согласно (3), высказывания
    S(x) справедливы для всех x ∈ Х.

    (3) Пусть выполнено (2), покажем, что выполнено и (1). Предположим противное, т.е. некоторое непустое подмножество A множества Х не имеет минимальных элементов. Тогда для произвольного
    a1 ∈ A существует a2 ∈ A, такой, что a1 > a2, и т.к. a2 - не минимальный, то существует a3 ∈ A,
    такой что a1 > a2 > a3 и т.д. Этот процесс бесконечен, т.к. ни один элемент из A по предположению не минимальный. Но тогда построена бесконечная цепочка
    a1 > a2 > a3..., что противоречит (2).

    Теорема доказана.
    Определение (по [1, с.62]).

    Фундированными множествами называются множества, удовлетворяющие свойствам (1)-(3) предыдущей теоремы.

       
    Примеры фундированных множеств (по [1, с.62-64]).

  • Множество натуральных чисел  N.
  • Множество  N×N  пар натуральных чисел (меньше та пара, у которой второй член меньше; в случае равенства сравниваем первые).
  • Множество  N×N×...×N (повторено k раз).
  • Множество всех слов русского алфавита (точнее, всех конечных последовательностей русских букв, независимо от смысла) с  лексикографическим порядком.
  •    
    Формально лексикографический порядок можно определить так: если слово x является началом слова y, то x ≤ y (например, кант ≤ кантор).
    Если ни одно из слов не является началом другого, посмотрим на первую по порядку букву, в которой слова отличаются: то слово, где эта буква меньше в алфавитном порядке и будет меньше.

    Определение (по [1, с.64]).
    Вполне упорядоченными множествами называются фундированные линейно упорядоченные множества.

    (1)Н.К.Верещагин, А.Шень. Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств. 2-е изд., исправленное. М.:МЦНМО, 2002. - 128 с.

       
    На следующем шаге мы рассмотрим рекурсивные определения функций.



    Вы можете оставить комментарий, или Трекбэк с вашего сайта.

    Оставить комментарий