Да куда уж мне в этот мир с моими ограниченными знаниями!
Ваша статья (https://page.hyoo.ru/#!=ixy44o_3oga48 ) мне понравилась. Кое о чем я бы поспорил, но вот с Вашей трактовкой ограниченности классической логики согласен. Только хотел бы напомнить, что с помощью этой логики получено немало замечательных результатов, без которых невозможно представить математику. Предлагаю пообщаться за пределами этой тусовки.
В постановке задачи я предполагал, что существует какое-то разделение труда между разработчиком алгоритмов и системным программистом. Или я отстал от жизни?
А Вы, наверное, обиделись на меня и решили увести разговор в сторону от основной темы. Ну что ж, неплохо придумано! А я приношу извинения за свое резковатое и не совсем справедливое суждение.
Вот теперь у меня проблема. Дано множество S={a, c} в универсуме U = {a, b, c, d}. В ЭВМ множество S можно представить как битовый вектор 1010. Мне нужно вычислить дополнение S. Тогда я просто даю команду инвертировать вектор. Получаю 0101. А если мне нужно вычислить дополнение дополнения S? Тогда непонятно что делать: то ли инвертировать вновь полученный вектор, то ли искать конструктивного математика и просить помощи у него?
Имеется огромный класс (десятки тысяч) практически значимых задач, которые в общем случае не решаются алгоритмами полиномиальной сложности (речь идет о некоторых классах NP-полных задач)). О них можно почитать в широко известной и доступной в Интернете книге Гэри и Джонсона. Все они обладают одним замечательным свойством: с помощью полиномиальных по сложности алгоритмов сводятся к одной задаче «Выполнимость КНФ» в булевом базисе. Для этой задачи даже проводятся соревнования по скорости решения. Все известные алгоритмы их решения не выходят за пределы неконструктивной математики. Хотелось бы знать, как конструктивная математика может помочь в решении этой проблемы, т.е. найти общий полиномиальный алгоритм решения этой задачи или доказать, что такой алгоритм невозможен?
Интересно, что в теоретическом обосновании проблем, связанных с вычислительной сложностью, часто используется машина Тьюринга. Та же машина используется при определении понятия «вычислимость». Только вот почему-то эта машина, насколько мне известно, не используется в алгоритмах решения NP-полных задач и в ЭВМ, которые решают эти задачи.
Там, кстати в алгоритме решения использовалось мое детище: алгебра кортежей, которая основана на ругаемой тут многими алгебре множеств. Даже сделал программу, которая сравнительно быстро решала эти задачи. Недавно захотел с этой программой поучаствовать в соревнованиях, но оказалось, что моя программа не работает в новых Windows. Хотел ее переделать, но не вышло - грамотности не хватило. С алгоритмами бы справился, а вот с интерфейсом никак. Учиться поздно, да и некогда.
Кстати, нашел оригинал книги Голдблатта (прошу прощения за опечатку фамилии в прошлом письме). Вот точная цитата (стр.. 15):
It may be the case that the objects of mathematical study can be thought of as sets, but it is not certain that in the future they will be so regarded. No doubt the basic language of set theory will continue to be an important tool whenever collections of things are to be dealt with. But the conception of the things themselves as sets has lost some of its prominence through the development of a natural and attractive alternative.
Насчет цитаты спорить трудно, может быть, перевод книги Голденблатта не совсем удачный. Оригинала у меня, к сожалению, нет.
Что касается закона исключенного третьего и двойного отрицания, то это законы не только алгебры множеств, но и булевой алгебры. А законы булевой алгебры соблюдаются в элементной базе многих ЭВМ, в частности, в цифровых. По Вашему же, выходит, что булева алгебра неконструктивна? А, по-моему, это терминологическая несообразность: интуиционистскую математику, в которой не соблюдаются эти законы, назвали «конструктивной». Тогда получается, что булева алгебра неконструктивна и ее можно на свалку выкинуть. И исчисление высказываний туда же. Ах, язык, язык!
Пока нет. Простите, но в ходе нашего диалога у меня сложилось впечатление, что у Вас еще не достаточно навыков обоснованно аргументировать свою точку зрения. Может быть, поэтому и не тороплюсь. Хотя свободного времени тоже недостаточно.
Вообще-то в публичной дискуссии не принято обзывать оппонента нелестными эпитетами.
ЭВМ состоит из многих деталей, в том числе микропроцессоров, а в них соблюдаются все законы булевой алгебры, в том числе и закон двойного отрицания. Что касается языка, на котором работает ЭВМ, то можно ввести много языков, правда, не во всех случаях результат получится удачный – в ЭВМ он просто не будет работать. Ваши доводы относятся к языку, а не к элементной базе ЭВМ.
Для доказательства не нужно, но для частных случаев применения закона контрапозиции без двойного отрицания не обойтись. Что мы будем делать с этим «не не B» если, допустим, речь идет о простых конечных множествах?
Мне кажется, многие утверждения участников дискуссии, представляемые как безусловные истины, на самом деле не более, чем мнения. В качестве подтверждения приведу цитату из книги Р. Голдблатта «Топосы. Категорный анализ логики».
«Конечно, можно мыслить объекты математического изучения как множества, однако уже нет уверенности, что в будущем их будут рассматривать так». Так что алгебра множеств с этой точки зрения тоже под вопросом.
Но есть и ошибочные утверждения. Вы пишете
"В ЭВМ работает конструктивное её (т.е. алгебры множеств - AntiLogik) подмножество. Аксиома (или как там у вас это называется во внеаксиоматическом мире) (называется закон - AntiLogik) исключенного третьего (или снятия двойного отрицания) там не работает".
Может ли кто-нибудь обосновать, что принципы действия ЭВМ основаны на интуиционистской логике?
Почему же снятие двойного отрицания в ЭВМ не работает. Как раз работает. Иначе закон контрапозиции тоже не будет работать, а как без него можно? Это в интуиционистской логике этот закон не работает. Не надо меня и читателя в заблуждение вводить.
Что касается лирики, то это всего лишь необоснованный ярлык.
Во-первых, конечное – не так уж и плохо. Конечно множество слов, произнесенных всеми людьми во все времена со дня появления Гомо Сапиенс, также конечно множество атомов во Вселенной (по современным представлениям). Также не будет проблем, если мы воспользуемся потенциальной бесконечностью (метод математической индукции, сходимость в анализе и др.). С актуальной бесконечностью сложнее, тут уже алгебра множеств пока не тянет.
Вы спрашиваете, как работать с такой теорией? Так она же уже работает в ЭВМ с фон Неймановской архитектурой. Только многим это неприятно признать. С нейросетями – мне трудно судить – плохо знаю. Но, по-моему и у них в микропроцессорах конечный базис с булевой (троичной и т.д.) логикой.
На алгебре множеств основана алгебра кортежей. В ней разработаны методы логического анализа, которые закрывают некоторые бреши в математической логике (трудности с моделированием и анализом неопределенностей, выводом следствий с заранее заданными свойствами, распознаванием ошибок в рассуждении и т.д.).
И еще одно. Мне кажется, что во многих отношениях любую науку лучше начинать с простого и посмотреть, что из этого простого может получиться. А потом уже усложнять. Алгебру множеств можно усложнить, добавив аксиомы теории множеств (те, которые есть, или новые, усовершенствованные). И работы всем хватит и удовлетворения.
Почти убедили по поводу дат. Но, я думаю, во времена Кантора никто не употреблял слово Наивный. А я говорил лишь о термине.
Что касается «могут сгенерировать противоречие» то это обоснование по аналогии («История научила…»). В алгебре множеств можно обойтись без признания множества элементом другого множества. А именно это лежит в основе парадоксов теории множеств + самоприменимость отношения принадлежности. И еще: известны ли парадоксы в рамках такой алгебры множеств?
В Англоязычной Вики говорится о 40-х годах 20 века (имеется в виду термин НАИВНАЯ теория множеств, а не просто теория множеств).
Что касается «лирики», то ей почему-то не побрезговали заняться известные математики (имею в виду Куранта и Роббинса). Другое дело, что эта «лирика» мало кого из математиков заинтересовала. Но попытаться развить эту тему никто не запретил.
Высокий рейтинг в Хабре не дает вам права принижать собеседника, тем более без достаточных оснований.
Что касается "наивной теории множеств" (Naive set theory), то появилась она в 1960-м году после публикации одноименной книги Халмоша. Сам Халмош называл наивную теорию множеств «аксиоматической теорией множеств с наивной точки зрения». В моей статье речь идет об алгебре множеств (algebra of sets), которая была описана в книге Куранта и Роббинса «Что такое математика?», впервые изданной в 1941 году. Там, кстати было высказано предположение, что законы алгебры множеств можно обосновать без аксиом.
Что касается заведомой противоречивости алгебры множеств (не «наивной теории множеств»!), то об этом, насколько я знаю, в публикациях по математике ничего нет.
Вы затронули интересную и важную для меня тему, поэтому я решил отменить свой запрет на свое участие в дискуссии с вами. Но прошу не рассказывать мне про благородных и беспечных мушкетеров и рассуждающих брадобреев, а то у меня создается впечатление, что вы с помощью словесной эквилибристики стремитесь сбить меня с толку. Если ошибся, извините.
Вы пишете:
То, что невозможно выразить замкнутой формулой исчисления предикатов, не имеет значения истинности, и из него нельзя выводить следствия. Математическая логика – это набор чисто синтаксических преобразований предикатов друг в друга.
Вот это, по-моему, и есть слабое место математической логики, из-за чего при ее использовании возникают трудности с прикладным логическим анализом (трудности с моделированием и анализом неопределенностей, выводом следствий с заранее заданными свойствами, распознаванием ошибок в рассуждении и т.д.).
Но предложена система логического анализа, с помощью которой некоторые из этих проблем решаются. Это алгебра кортежей. Если найдете время, посмотрите статью Как вычислять интересные следствия.
Извините, но мне трудно вас понять. На некоторые мои вопросы я так и не получил внятного ответа. Покажу только на примере вопроса «Почему отношение возврата долга третьему лицу рефлексивно?»
Ваша первая фраза «Все мушкетёры должны одному лицу – трактирщику, это константа». Вы приводите частный случай, выраженный замкнутой формулой (потому и константа), но для естественных рассуждений отношение между должниками и заимодавцами – это просто бинарное отношение, которое не всегда можно выразить замкнутой формулой исчисления предикатов. И мушкетеры у вас по характеру такие, какие вам нужны для обоснования вашей точки зрения: «Нет никакой разницы для мушкетёра, возвращать свой долг или чужой». Но должниками могут быть не только благородные мушкетеры! А я спрашивал про возврат долга вообще, а не только применительно к придуманным вами мушкетерам, которые выплачивают свои или чужие долги, даже не удосужившись узнать, получил ли трактирщик все, что ему причитается.
С другими ответами и рассуждениями картина аналогичная.
Поэтому в силу трудностей понимания, я вынужден прервать СВОЕ участие в дискуссии с вами по данной теме. Спасибо за замечания.
Да куда уж мне в этот мир с моими ограниченными знаниями!
Ваша статья (https://page.hyoo.ru/#!=ixy44o_3oga48 ) мне понравилась. Кое о чем я бы поспорил, но вот с Вашей трактовкой ограниченности классической логики согласен. Только хотел бы напомнить, что с помощью этой логики получено немало замечательных результатов, без которых невозможно представить математику. Предлагаю пообщаться за пределами этой тусовки.
В постановке задачи я предполагал, что существует какое-то разделение труда между разработчиком алгоритмов и системным программистом. Или я отстал от жизни?
А Вы, наверное, обиделись на меня и решили увести разговор в сторону от основной темы. Ну что ж, неплохо придумано! А я приношу извинения за свое резковатое и не совсем справедливое суждение.
Вот теперь у меня проблема. Дано множество S={a, c} в универсуме U = {a, b, c, d}. В ЭВМ множество S можно представить как битовый вектор 1010. Мне нужно вычислить дополнение S. Тогда я просто даю команду инвертировать вектор. Получаю 0101. А если мне нужно вычислить дополнение дополнения S? Тогда непонятно что делать: то ли инвертировать вновь полученный вектор, то ли искать конструктивного математика и просить помощи у него?
Имеется огромный класс (десятки тысяч) практически значимых задач, которые в общем случае не решаются алгоритмами полиномиальной сложности (речь идет о некоторых классах NP-полных задач)). О них можно почитать в широко известной и доступной в Интернете книге Гэри и Джонсона. Все они обладают одним замечательным свойством: с помощью полиномиальных по сложности алгоритмов сводятся к одной задаче «Выполнимость КНФ» в булевом базисе. Для этой задачи даже проводятся соревнования по скорости решения. Все известные алгоритмы их решения не выходят за пределы неконструктивной математики. Хотелось бы знать, как конструктивная математика может помочь в решении этой проблемы, т.е. найти общий полиномиальный алгоритм решения этой задачи или доказать, что такой алгоритм невозможен?
Интересно, что в теоретическом обосновании проблем, связанных с вычислительной сложностью, часто используется машина Тьюринга. Та же машина используется при определении понятия «вычислимость». Только вот почему-то эта машина, насколько мне известно, не используется в алгоритмах решения NP-полных задач и в ЭВМ, которые решают эти задачи.
Я этим делом когда-то давно занимался, даже придумал новый класс полиномиально решаемых задач «Выполнимость КНФ» .
Там, кстати в алгоритме решения использовалось мое детище: алгебра кортежей, которая основана на ругаемой тут многими алгебре множеств. Даже сделал программу, которая сравнительно быстро решала эти задачи. Недавно захотел с этой программой поучаствовать в соревнованиях, но оказалось, что моя программа не работает в новых Windows. Хотел ее переделать, но не вышло - грамотности не хватило. С алгоритмами бы справился, а вот с интерфейсом никак. Учиться поздно, да и некогда.
Кстати, нашел оригинал книги Голдблатта (прошу прощения за опечатку фамилии в прошлом письме). Вот точная цитата (стр.. 15):
It may be the case that the objects of mathematical study can be thought of as sets, but it is not certain that in the future they will be so regarded. No doubt the basic language of set theory will continue to be an important tool whenever collections of things are to be dealt with. But the conception of the things themselves as sets has lost some of its prominence through the development of a natural and attractive alternative.
Насчет цитаты спорить трудно, может быть, перевод книги Голденблатта не совсем удачный. Оригинала у меня, к сожалению, нет.
Что касается закона исключенного третьего и двойного отрицания, то это законы не только алгебры множеств, но и булевой алгебры. А законы булевой алгебры соблюдаются в элементной базе многих ЭВМ, в частности, в цифровых. По Вашему же, выходит, что булева алгебра неконструктивна? А, по-моему, это терминологическая несообразность: интуиционистскую математику, в которой не соблюдаются эти законы, назвали «конструктивной». Тогда получается, что булева алгебра неконструктивна и ее можно на свалку выкинуть. И исчисление высказываний туда же. Ах, язык, язык!
Пока нет. Простите, но в ходе нашего диалога у меня сложилось впечатление, что у Вас еще не достаточно навыков обоснованно аргументировать свою точку зрения. Может быть, поэтому и не тороплюсь. Хотя свободного времени тоже недостаточно.
Вообще-то в публичной дискуссии не принято обзывать оппонента нелестными эпитетами.
ЭВМ состоит из многих деталей, в том числе микропроцессоров, а в них соблюдаются все законы булевой алгебры, в том числе и закон двойного отрицания. Что касается языка, на котором работает ЭВМ, то можно ввести много языков, правда, не во всех случаях результат получится удачный – в ЭВМ он просто не будет работать. Ваши доводы относятся к языку, а не к элементной базе ЭВМ.
Для доказательства не нужно, но для частных случаев применения закона контрапозиции без двойного отрицания не обойтись. Что мы будем делать с этим «не не B» если, допустим, речь идет о простых конечных множествах?
Возможно, знаю кое-что еще кроме этого. А что Вы этим хотите сказать?
Как же не связана? Из утверждения «Если A то не B» получаем «Если B то не A», а не только «Если не не B то не A»
Мне кажется, многие утверждения участников дискуссии, представляемые как безусловные истины, на самом деле не более, чем мнения. В качестве подтверждения приведу цитату из книги Р. Голдблатта «Топосы. Категорный анализ логики».
«Конечно, можно мыслить объекты математического изучения как множества, однако уже нет уверенности, что в будущем их будут рассматривать так». Так что алгебра множеств с этой точки зрения тоже под вопросом.
Но есть и ошибочные утверждения. Вы пишете
"В ЭВМ работает конструктивное её (т.е. алгебры множеств - AntiLogik) подмножество. Аксиома (или как там у вас это называется во внеаксиоматическом мире) (называется закон - AntiLogik) исключенного третьего (или снятия двойного отрицания) там не работает".
Может ли кто-нибудь обосновать, что принципы действия ЭВМ основаны на интуиционистской логике?
Почему же снятие двойного отрицания в ЭВМ не работает. Как раз работает. Иначе закон контрапозиции тоже не будет работать, а как без него можно? Это в интуиционистской логике этот закон не работает. Не надо меня и читателя в заблуждение вводить.
Что касается лирики, то это всего лишь необоснованный ярлык.
А почему аксиоматику Пеано не рассматриваете? Там все более прозрачно, чем эти пустые скобки.
Во-первых, конечное – не так уж и плохо. Конечно множество слов, произнесенных всеми людьми во все времена со дня появления Гомо Сапиенс, также конечно множество атомов во Вселенной (по современным представлениям). Также не будет проблем, если мы воспользуемся потенциальной бесконечностью (метод математической индукции, сходимость в анализе и др.). С актуальной бесконечностью сложнее, тут уже алгебра множеств пока не тянет.
Вы спрашиваете, как работать с такой теорией? Так она же уже работает в ЭВМ с фон Неймановской архитектурой. Только многим это неприятно признать. С нейросетями – мне трудно судить – плохо знаю. Но, по-моему и у них в микропроцессорах конечный базис с булевой (троичной и т.д.) логикой.
На алгебре множеств основана алгебра кортежей. В ней разработаны методы логического анализа, которые закрывают некоторые бреши в математической логике (трудности с моделированием и анализом неопределенностей, выводом следствий с заранее заданными свойствами, распознаванием ошибок в рассуждении и т.д.).
И еще одно. Мне кажется, что во многих отношениях любую науку лучше начинать с простого и посмотреть, что из этого простого может получиться. А потом уже усложнять. Алгебру множеств можно усложнить, добавив аксиомы теории множеств (те, которые есть, или новые, усовершенствованные). И работы всем хватит и удовлетворения.
Почти убедили по поводу дат. Но, я думаю, во времена Кантора никто не употреблял слово Наивный. А я говорил лишь о термине.
Что касается «могут сгенерировать противоречие» то это обоснование по аналогии («История научила…»). В алгебре множеств можно обойтись без признания множества элементом другого множества. А именно это лежит в основе парадоксов теории множеств + самоприменимость отношения принадлежности. И еще: известны ли парадоксы в рамках такой алгебры множеств?
В Англоязычной Вики говорится о 40-х годах 20 века (имеется в виду термин НАИВНАЯ теория множеств, а не просто теория множеств).
Что касается «лирики», то ей почему-то не побрезговали заняться известные математики (имею в виду Куранта и Роббинса). Другое дело, что эта «лирика» мало кого из математиков заинтересовала. Но попытаться развить эту тему никто не запретил.
Уважаемый, Tzimie !
Высокий рейтинг в Хабре не дает вам права принижать собеседника, тем более без достаточных оснований.
Что касается "наивной теории множеств" (Naive set theory), то появилась она в 1960-м году после публикации одноименной книги Халмоша. Сам Халмош называл наивную теорию множеств «аксиоматической теорией множеств с наивной точки зрения». В моей статье речь идет об алгебре множеств (algebra of sets), которая была описана в книге Куранта и Роббинса «Что такое математика?», впервые изданной в 1941 году. Там, кстати было высказано предположение, что законы алгебры множеств можно обосновать без аксиом.
Что касается заведомой противоречивости алгебры множеств (не «наивной теории множеств»!), то об этом, насколько я знаю, в публикациях по математике ничего нет.
Согласен, можно и одним правилом, но мне показалось, что так удобнее
Вы затронули интересную и важную для меня тему, поэтому я решил отменить свой запрет на свое участие в дискуссии с вами. Но прошу не рассказывать мне про благородных и беспечных мушкетеров и рассуждающих брадобреев, а то у меня создается впечатление, что вы с помощью словесной эквилибристики стремитесь сбить меня с толку. Если ошибся, извините.
Вы пишете:
То, что невозможно выразить замкнутой формулой исчисления предикатов, не имеет значения истинности, и из него нельзя выводить следствия. Математическая логика – это набор чисто синтаксических преобразований предикатов друг в друга.
Вот это, по-моему, и есть слабое место математической логики, из-за чего при ее использовании возникают трудности с прикладным логическим анализом (трудности с моделированием и анализом неопределенностей, выводом следствий с заранее заданными свойствами, распознаванием ошибок в рассуждении и т.д.).
Но предложена система логического анализа, с помощью которой некоторые из этих проблем решаются. Это алгебра кортежей. Если найдете время, посмотрите статью Как вычислять интересные следствия.
Извините, но мне трудно вас понять. На некоторые мои вопросы я так и не получил внятного ответа. Покажу только на примере вопроса «Почему отношение возврата долга третьему лицу рефлексивно?»
Ваша первая фраза «Все мушкетёры должны одному лицу – трактирщику, это константа». Вы приводите частный случай, выраженный замкнутой формулой (потому и константа), но для естественных рассуждений отношение между должниками и заимодавцами – это просто бинарное отношение, которое не всегда можно выразить замкнутой формулой исчисления предикатов. И мушкетеры у вас по характеру такие, какие вам нужны для обоснования вашей точки зрения: «Нет никакой разницы для мушкетёра, возвращать свой долг или чужой». Но должниками могут быть не только благородные мушкетеры! А я спрашивал про возврат долга вообще, а не только применительно к придуманным вами мушкетерам, которые выплачивают свои или чужие долги, даже не удосужившись узнать, получил ли трактирщик все, что ему причитается.
С другими ответами и рассуждениями картина аналогичная.
Поэтому в силу трудностей понимания, я вынужден прервать СВОЕ участие в дискуссии с вами по данной теме. Спасибо за замечания.