Comments 31
это означает, что все множества счётны
Пересчитайте все точки отрезка (0; 1) числовой оси, пожалуйста.
Я лучше перечислю все множества. Берём их описания и начинаем перечислять в лексикографическом порядке. И ничего не пропустим.
Пропустите множества с бесконечным числом элементов. Вот хоть натуральные числа.
Вообще говоря, нет. Натуральные числа описываются описанием "все натуральные числа" :)
Но какие-то пропустит. Думаю, немного поупражнявшись, можно построить канторовский треугольник для описаний.
Перечисление в лексикографическом порядке дает все конечные множества. Единственное бесконечное множество, которое косвенно получится - это множество всех конечных множеств.
Это если перечислять их с помощью списка элементов. Если задавать как в посте, функцией принадлежности, то удастся задать все конструктивные множества, в том числе и бесконечные. Диагонализация не сработает т.к. в списке кроме множеств будут еще штуки способные зависнуть. В целом конструктивная математика имеет право на жизнь, но она слабее классической (не всё что можно доказать в классической математике можно доказать в конструктивной) и в ней все равно неинтуитивных вещей хватает.
нельзя потому что в этом списке кроме множеств будут присутствовать также некорректные описания а отсеять одни от других невозможно.
Упорядочить не значит перечислить. Вы берете первый элемент лексикографический, допустим 0 и начинаете описывать все множества, содержащие 0. Уходите в бесконечность. Когда я спрошу, какой номер у множества {1} - вы не сможете его назвать - у вас перед ним стоит бесконечное количество множеств.
Ну так человек же в рамках C++ мыслит. А там все float или double вполне можно пересчитать. :)
Какая же каша. У вас там то множества множеств, то множества элементов.
И потом, математики же не потому что вредные такие или от скуки понапридумывали всякое. Ваша "теория" неконсистента и противоречива, а значит и бесполезна на практике.
Элемент множества тоже является множеством.
Не всегда. Во множестве натуральных чисел лежат натуральные числа.
Натуральное число - это тоже множество в теории множеств
А почему тогда 2+3=5 а не {2, 3}?
Технически, потому что (там обычно кардиналы, но можно и просто с множествами):
2 = {0, {0}}; 3 = {0, {0}, {0, {0}}}
+ = {((0,0), 0), ((0,1), 1), ..., ((2,3), 5), ...}
2+3 = 5 - поскольку в + есть только одна пара вида ((2, 3), Х), и Х - 5.
(Пара тоже может быть записана как множество, например (2,3) ~ {{2, 3}, 3}.)
Нет
Характеристическая функция должна быть определена для всех входных множеств
"Определена" = "значение должно вычисляться предложенными операциями за конечное время"? "Должно быть доказуемо, что выполнение предложенных операций завершается за конечное время"? Что-то третье?
Множество всех подмножеств множества S:
...в общем случае не является множеством во введённых определениях: вычисление isSubset ни в какой реализации не завершается гарантированно за конечное время. К примеру, множество натуральных чётных, конечно, есть подмножество множества натуральных, но как вы реализуете isSubset, который для этого случая вернёт true?
bool isSubset<Universal> ( Set & s ) { return true; }И?.. Нет, вы можете специализациями задать частные случаи, но вы не можете записать общую логику, которая бы не выдавала иногда "невычислимо".
Ещё в приведённом формализме нельзя построить некоторые штуки которые хочется построить. К примеру, имея Set& x, нельзя построить одноэлементное множество {x}. Имея Set& x, Set& y, нельзя проверить что x есть подмножество y.
Пора брать Coq или Isabelle/HOL, Lean4, автор явно движется в правильном направлении :)
описание из конечного набора символов на каком-то языке
нужно следить за тем, чтобы не было зацикливаний
Однако по теореме останова уследить в общем случае невозможно.
Так что описания из конечного набора символов задают три типа объектов - множества, неверные определения множеств и "мы не знаем множество это или нет".
Ну и да, нет реализаций get_any и isSubset - вполне можно придумать примеры для которых operator() будет вычислимым, а эти две функции - нет.
Какое-то скомканное у вас объяснение концепции. Каша из собственно множества и значений (это из математики), замес из наследования и методов (это из C++).
Технически, если подчистить и взять C++17, то можно сделать так:
#include <iostream>
#include <string>
#include <sstream>
struct SetNatural {
bool Contains(int v) {
return v > 0;
}
template<typename t>
bool Contains(t v) {
return false;
}
std::string Name() { return "Natural"; }
};
struct SetEvenNatural {
bool Contains(int v) {
return v > 0 && v % 2 == 0;
}
template<typename t>
bool Contains(t v) {
return false;
}
std::string Name() { return "EvenNatural"; }
};
struct SetOddNatural {
bool Contains(int v) {
return v > 0 && v % 2 == 1;
}
template<typename t>
bool Contains(t v) {
return false;
}
std::string Name() { return "OddNatural"; }
};
struct SetApple {
bool Contains(std::string v) {
return v == "apple";
}
template<typename t>
bool Contains(t v) {
return false;
}
std::string Name() { return "Apple"; }
};
template<typename a, typename b>
struct SetUnion {
template<typename t>
bool Contains(t v) {
return a().Contains(v) || b().Contains(v);
}
std::string Name() {
std::stringstream s;
s << "Union (" << a().Name() << ", " << b().Name() << ")";
return s.str();
}
};
template<typename a, typename b>
SetUnion<a, b> Union(a arg1, b arg2) { return SetUnion<a, b>(); }
SetNatural Union(SetEvenNatural arg1, SetOddNatural arg2) { return SetNatural(); }
int main()
{
SetNatural n;
std::cout << n.Name() << " contains 5: " << n.Contains(5) << std::endl;
std::cout << n.Name() << " contains apple: " << n.Contains("apple") << std::endl;
std::cout << std::endl;
SetEvenNatural en;
std::cout << en.Name() << " contains 5: " << en.Contains(5) << std::endl;
std::cout << en.Name() << " contains 6: " << en.Contains(6) << std::endl;
std::cout << std::endl;
SetOddNatural on;
std::cout << on.Name() << " contains 5: " << on.Contains(5) << std::endl;
std::cout << on.Name() << " contains 6: " << on.Contains(6) << std::endl;
std::cout << std::endl;
std::cout << "Union natural and apple" << std::endl;
auto uen = Union(SetNatural(), SetApple());
std::cout << uen.Name() << " contains 5: " << uen.Contains(5) << std::endl;
std::cout << uen.Name() << " contains 6: " << uen.Contains(6) << std::endl;
std::cout << std::endl;
std::cout << "Union even and odd" << std::endl;
auto eon = Union(SetEvenNatural(), SetOddNatural());
std::cout << eon.Name() << " contains 5: " << eon.Contains(5) << std::endl;
std::cout << eon.Name() << " contains 6: " << eon.Contains(6) << std::endl;
std::cout << std::endl;
return 0;
}
Пример вывода результатов (обращаем внимание, что объединение even и odd даёт natural):
Natural contains 5: 1
Natural contains apple: 0EvenNatural contains 5: 0
EvenNatural contains 6: 1OddNatural contains 5: 1
OddNatural contains 6: 0Union natural and apple
Union (Natural, Apple) contains 5: 1
Union (Natural, Apple) contains 6: 1Union even and odd
Natural contains 5: 1
Natural contains 6: 1
В сухом остатке:
множества могут хранить разные элементы
можно хранить бесконечные множества, так как хранится "тип" (например, натуральные числа)
приведение результата операции к известному типу (в примере объединяются чётные натуральные числа и нечётные натуральные числа - получаются натуральные числа) - всё ложится на плечи программиста.
В остальном, дело за реализацией.
(обращаем внимание, что объединение even и odd даёт natural)
Есть проблема: несложно задать множество с функцией принадлежности "число нечётное простое". Несложно задать множество с функцией принадлежности "число представимо как сумма двух нечётных простых". Но вот что произойдёт при объединении этого множества с множеством {2}? Мы получим EvenNatural или нет?
Сарказм:
Мы получим EvenNatural или нет?
Очевидно же, что нет!
... утверждение о том, что любое чётное число, начиная с 4, можно представить в виде суммы двух простых чисел ... по состоянию на 2025 год утверждение не доказано. Подробнее здесь: https://ru.wikipedia.org/wiki/Проблема_Гольдбаха
Очевидно, что если не доказано для ЛЮБЫХ двух простых чисел, то оно не доказано и для двух НЕЧЁТНЫХ простых числе.
---
Если без сарказма, то (как и в теории чисел), вся тяжесть деятельности ложится на плечи человека. В данном случае на программиста-математика: если он сделает версию функции Union, где эти множества объединяются - тогда это будет (хотя и спорный результат). А если нет - то нет.
---
Если совсем без сарказма: не нужно ни в этой статье, ни в приведённом куске кода искать "высокий" смысл. Статья написана в стиле "шуточной задачи" - под такую задачу приведено и решение (тоже шуточное).
Зачем это автору - не знаю, использовать это где-то сомнительно.
Зачем это мне - разминка для мозгов, просто для удовольствия.
Моя теория множеств на языке С++