Научная литература
booksshare.net -> Добавить материал -> Математика -> Яблонский С.В. -> "Введение в дискретную математику " -> 21

Введение в дискретную математику - Яблонский С.В.

Яблонский С.В. Введение в дискретную математику — Наука , 1986. — 384 c.
Скачать (прямая ссылка): vvedenievdiskretnuyum1986.djvu
Предыдущая << 1 .. 15 16 17 18 19 20 < 21 > 22 23 24 25 26 27 .. 104 >> Следующая

Непосредственно к доказанному примыкает следующая теорема.
Теорема 13. Для всякого к {к 5* 3) Рк содержит континуум различных замкнутых классов.
Доказательство. Число замкнутых классов в Рк можно оценить сверху числом всех подмножеств функций из Рк. Так как Рк содержит счетное число функций, то число подмножеств РК равно континууму.
Для завершения доказательства нужно оценить снизу число замкнутых классов в Рк. С этой целью рассмотрим замкнутый класс ЗЯь, построенный при доказательстве предыдущей теоремы. Этот класс имеет базис
Образуем для каждой последовательности (р1в р2, ..где 2 р! < рг < ..., класс йМрп Рг, .. •) как класс, порожденный системой функций{/Р1, /р2, .. .}.Легко видеть, что
Следовательно, семейство рг, ...)} является кон-
тинуальным семейством. Теорема доказана.
Теорема 14. Система полиномов по mod к полна в Ph тогда и только тогдау когда к = р, где р — простое число.
Доказательство. Легко видеть, что для любой функции / (^1, ..., хя) из Pk имеет место представление
f(xu ..., X„)=i
если
И • * *1
an) (mod к).
70 Ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
Поэтому вопрос о представимости функции / полиномами по mod к сводится к вопросу о представимости в виде полиномов функций
U (х), ..Д-i (z) .
В силу того, что
ja{x) = ja(x — о),
мы можем утверждать, что система полиномов по mod к полна тогда и только тогда, когда представима в виде полинома функция /о(д’).
1. Пусть к = р. В этом случае, опираясь на малую теорему Ферма aT~i ^ 1 (modр) (1 а < р — 1), получаем
/о (х) — 1 — хр-* (mod р),
т. е. система полиномов полна в /У).
Монсйо указать другой способ решения этой же задачи. Будем искать представление функции g(^), зависящей от одной переменной, в виде полпнома, пользуясь методом неопределенных коэффициентов
g (х) = По + а^Х + . . . + Clp-tXp~l.
Мы получаем систему уравнений
а0 + а, • О1 4- а2 • О2 + ... + aP-i • 0Р-1 = g(0)r
йо + «i * + «2 ’ I2 + . . . + dp-1 • 1р-! = g('l),
йо + av ? 21 + az * 22 + ... + ffp_i • 2p~l ~ g(2),
a0-hai(p — l)1 + a2(p — 1)й + ... + op_i(p — I)?-1 =
= g(p — i).
Определитель этой системы
і 0 0 0
1 і I2 ip~1
д = 1 2 23 2V~X
1 Р~ 1 (р —lja . • • (Р-Dp
есть определитель Вандермонда. Как известно,
Д =? II о-о.
*) Малая теорема Ферма обосновывается так. Пусть 1 ^ а ^ ^ р— 1, тогда числа Г! = я-1, ..., гр_і = а(р — 1) не сравнимы по mod р. Поэтому г( ... гр_і еэ (р — 1)! (modp) и (р — 1)! гэ ее av~l(p — 1)1 (mod р) или 1 ез a?-1 (mod р).
ГЛ. 2. fe-ЗНАЧИЛ Я ЛОГИКА
71
Так как р — простое число, то A^0(mod р). Пользуясь правилом Крамера и учитывая, что A^O(modp), мы сможем решить в целых числах сравнения
а*Д 153 А,-(mod р) (i ?=* 0, — 1),
где Д( — соответствующий минор. Итак, мы приходим к единственному решению исходной системы и, следовательно, к полиному, изображающему g(.r).
2. Пусть к Фр. Тогда к = к1кг, где к > къ > 1. Допустим, что
U(^) — Ьо 4- Ъух + ... + b,x' (mod к).
При х = 0 получаем Ь0 = 1. При .г = к{ получаем 0 = 1+ bJcL + ... + bbk\ (mod к)
или
к — 1 = Ь1кх + ... +Ъьк\ (modfc),
т. е. к — 1 делится на кл. Таким образом, к и к — 1 делятся на ки что возможно только при — 1. Мы пришли к противоречию. Следовательно, при кФ р функция }0(.г) не представима полиномом до mod к.
Доказанная теорема может быть легко обобщена на случай, когда на Ек возможно определить две операция: © и X — сложение и умножение, относительно коюрых Eh образует ноле. Как показывается в алгебре, конечное поле пли поле Галуа, существует тогда и только тогда, когда к = ртп: В этом случае оно определяется с точностью до изоморфизма однозначным образом. При этом относительно сложения оно образует абелеву группу характеристики р, т. е. для любого элемента а выполняется соотношение
« Ф .. ? ф а = 0,
р
где 0 — нуль группы. Эту группу можно определить, рассматривая числа а, как числа в /кичной системе счисления, т. е. в виде наборов (ah ..ат), и операцию а © (} =(<2! Т (Jj, ..., ат + j}m) (+ обозначает сложение по modp). Все элементы поля Галуа, кроме 0, образуют относительно второй операции циклическую группу.
Пример 5. Пусть к = 23. Тогда операция © имеет вид как в табл. 4. Для построения таблицы для операции X заметим, что числа I, 2, 3 могут быть выражены
72 Ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
как степени некоторого элемента а (следует из цикличности мультипликативной группы). Это число а удовлетворяет уравнению
а3 = 1
или, так как а ?= 1,
а!®а® 1 = 0.
Взяв за а элемент 2 получим а2 = © (а® 1) = 3. Мы получаем таблицу для X (табл. 5), поскольку
2 • 2 = а ? а = 3,
2 • 3 = а ? а2 = а3 = 1,
3 • 3 = а2 • аг = а} = а = 2.
Мы можем, повторяя первую часть доказательства предыдущей теоремы, показать, что каждая функция Цхи ...
.. дгп) из Рк при к = рт представима полиномом над со-
ответствующим полем Галуа.
Таблица 4 Т а б л п ц а 5
ф 0 1 2 3
0 0 1 2 3
1 1 0 3 2
2 2 3 0 1
3 3 2 1 0
X 0 1 2 3
0 0 0 0 0
1 0 1 2 3
2 0 2 3 i
3 0 3 1 2
В частности, в Pt возможно представление функций полиномами, но не по mod 4, а полиномами над полем Галуа.
Предыдущая << 1 .. 15 16 17 18 19 20 < 21 > 22 23 24 25 26 27 .. 104 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed