Условие задачи: Сколько различных выражений для множеств можно составить из n переменных с помощью (многократно используемых) операций пересечения, объединения и разности?
Интерес состоит в том, чтобы решить её элементарными методами, она находится в первом пункте Верещагина.
У меня получилось, но слишком громоздко.
Лемма: Если какое-то равенство (содержащее переменные для множеств и операции пересечения, объединения, разности) неверно, то можно подобрать контрпример к нему, в котором все множества равны

или

, где

- некоторый объект.
Доказательство: Т.к. равенство неверно, то как минимум один контрпример существует :

, при подстановке их вместо переменных получаем два множества (в правой и левой частях равенства), которые не равны, то есть существует некоторый объект

, который принадлежит одному из них и не принадлежит другому, рассмотрим множества

. Каждое из них равно либо

, либо

. Этот набор также является контрпримером, т.к. если в левой и правой частях объект

будет тогда и только тогда, когда он был там до этого, поскольку

(не знаю следует ли это доказывать строже, т.к. понятие формулы не как не определялось)
Ч.Т.Д.
Выберем произвольно объект

и рассмотри все возможные наборы длины n состоящие из множеств

и

. Как известно их всего

. Обозначим их произвольным образом через

так, чтобы набор из пустых множеств был обозначен через

. Обозначим

-ое множество

-ого набора через

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

, кроме

сопоставим формулу, которая является пересечением

формул,

-ая из которых равна

, если

и

в противном случае, где

- произвольный элемент набора, отличный от пустого множества и обозначим ее через

. Ясно, что при подстановке в эту формулу любого набора, кроме

в результате получится пустое мно-во, и только при подстановке

в результате получится мно-во

.
Любой формуле сопоставим последовательность из единиц и нулей длины

, у которой на

-ом месте стоит единица, если при подстановке в эту формулу набора

получиться мно-во

, и 0 в противном случае. Ясно, что на первом месте всегда будет стоять 0. Переформулируя, результат леммы, можем сказать, что формулы равны тогда и только тогда, когда равны сопоставленные им последовательности, а их не более

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

из нулей и единиц, на первом месте которой стоит 0, укажем формулу, которой мы сопоставили эту последовательность. Это будет объединение некоторых формул

, а именно для таких

, что в выбранной последовательности на

-ом месте стоит 1. Ясно, что она будет принимать значение

тогда и только тогда, когда мы поставим такой набор

, что в выбранной последовательности на

-ом месте стоит 1, а это и значит, что мы сопоставим ей эту последовательность.
Ч.Т.Д