Глава четвертая. ОСНОВНЫЕ ЧИСЛОВЫЕ СИСТЕМЫ

§ 1. СИСТЕМА НАТУРАЛЬНЫХ ЧИСЕЛ

Алфавит и слова.

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

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

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

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

Пусть символы А и В обозначают слова в каком-либо алфавите. Поставим в соответствие паре А, В слово АВ, которое получается, если сначала написать слово А, а затем справа приписать к нему слово В. Слово А В называется композицией или сочленением слов А и В.

Например, если А обозначает слова а В — слово то АВ есть слово . Композиция любого слова А с пустым словом считается, по определению, равной слову А.

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

Слово В называется обращением (зеркальным образом) слова А, если В состоит из тех вхождений букв, что и А, но записанных в обратном порядке. Например, слово есть обращение слова и наоборот. Слово называется симметричным, если оно совпадает со своим обращением; например, слова шалаш, суть симметричные слова.

Слово А называется подсловом слова В, если найдутся такие слова С и (возможно пустые), что . Если — подслово слова В, то говорят, что входит в В. Для данных слов F и В слово может иметь несколько вхождений в слово В. Ясно, что пустое слово является подсловом любого слова.