Арифметика на тривиальных множествах

[codedot]

Если обозначить через {} пустое множество, а через {x} - одноэлементное множество с элементом x, то с помощью операции "U" объединения множеств можно построить структуры, назвав их тривиальными множествами, являющиеся по сути множествами и эквивалентные неориентированным деревьям. Формально, множество таких структур T вводится индуктивным способом (отношение "@" здесь и далее означает принадлежность элемента множеству):

{} @ T;
x @ T => {x} @ T;
x @ T & y @ T => x U y @ T.

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

Множество натуральных чисел N вводится также индуктивным способом:

0 = {} @ N;
n = {n - 1} @ N, если n > 1.

Так, например, 1 = {0} = {{}}, 2 = {1} = {{0}} = {{{}}}, и так далее.

Поддаются определению и обычные арифметические операции при рассмотрении их как рекурсивных функций (здесь и далее выражение вида a ? b : c возращает значение b, если a истинно, и c - в противном случае):

m + n := m = {x} ? {x + n} : n;
m - n := m = {x} & n = {y} ? x - y : m;
m * n := m = {x} ? n + x * n : {};
m / n := m = {x} ? {(m - n) / n} : {}.

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

пустой список [] = {} @ L;
список с головой h и хвостом t [h / t] = {{h}} U {{{}} U {{t}}} @ L.