Дьявольские игры и аксиома выбора
Dec. 1st, 2024 04:21 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
leblon Узнал вчера об одном "практическом" применении аксиомы выбора. Допустим, вы играете с дьяволом в игру "угадай число". Вы загадываете натуральное число, а дьявол угадывает. Причем на каждом шаге игры догадкой может быть не только одно число, но и любое подмножество чисел. А вы отвечаете "да" или "нет" в зависимости от того, принадлежит ли число этому подмножеству или нет. Число догадок неограниченно. Если в какой-то момент дьявол угадывает загаданное вами число, вы проиграли душу и игра заканчивается. С другой стороны, за каждый вопрос дьявол платит вам фиксированную сумму (или продлевает вашу жизнь на фиксированное количество лет, по вашему желанию).
Можно ли придумать такую стратегию игры, чтобы вы гарантировано не проиграли? Ясно, что если задумать любое число, то в конце концов дьявол выиграет и получит вашу душу. То есть, если играть по честному, то в конце концов проиграете. Можно попробовать жульничать: никакого числа не загадывать, а просто придумать какое-нибудь правило, по-которому вы говорите "да" или "нет" в зависимости от того, какое подмножество назвал дьявол. Но правила таковы, что если он поймает вас на жульничестве, то вы тоже проиграли. Например, если он назвал пустое подмножество, а вы ляпнули "да", то вы тут же проиграли. Другой способ поймать вас на жульничестве: если в какой то момент дьявол назвал подмножество А и вы сказали "да", а в другой раз он назвал подмножество Б содержащее А, то если вы скажете "нет", то вы опять проиграли. Наконец, третий способ попасться: если дьявол назвал подмножества А и Б и вы в обоих случаях сказали "да", а в другой раз он назвал подмножество В которое является пересечением А и Б, а вы сказали на этот раз "нет". Ясно, что если вы встали на путь жульничества, то это надо делать с умом. Вопрос: можно ли придумать такую систему жульничества, при которой вы никогда не проиграете?
Ответ, оказывается, зависит от того, выполняется ли в вашей Вселенной аксиома выбора. Если она выполняется, то существует система жульничества (не единственная!), при которой вас никогда не поймают за руку. Она называется "свободный ультрафильтр". С другой стороны, если аксиома выбора не выполняется, то может быть по разному, Например, в некоторых моделях теории множеств Цермело-Френкеля, любая система жульничества имеет "дыры" которые позволят дьяволу вас "поймать". Иначе говоря, в такой Вселенной свободные ультрафильтры на множестве натуральных чисел не существуют.
Можно ли придумать такую стратегию игры, чтобы вы гарантировано не проиграли? Ясно, что если задумать любое число, то в конце концов дьявол выиграет и получит вашу душу. То есть, если играть по честному, то в конце концов проиграете. Можно попробовать жульничать: никакого числа не загадывать, а просто придумать какое-нибудь правило, по-которому вы говорите "да" или "нет" в зависимости от того, какое подмножество назвал дьявол. Но правила таковы, что если он поймает вас на жульничестве, то вы тоже проиграли. Например, если он назвал пустое подмножество, а вы ляпнули "да", то вы тут же проиграли. Другой способ поймать вас на жульничестве: если в какой то момент дьявол назвал подмножество А и вы сказали "да", а в другой раз он назвал подмножество Б содержащее А, то если вы скажете "нет", то вы опять проиграли. Наконец, третий способ попасться: если дьявол назвал подмножества А и Б и вы в обоих случаях сказали "да", а в другой раз он назвал подмножество В которое является пересечением А и Б, а вы сказали на этот раз "нет". Ясно, что если вы встали на путь жульничества, то это надо делать с умом. Вопрос: можно ли придумать такую систему жульничества, при которой вы никогда не проиграете?
Ответ, оказывается, зависит от того, выполняется ли в вашей Вселенной аксиома выбора. Если она выполняется, то существует система жульничества (не единственная!), при которой вас никогда не поймают за руку. Она называется "свободный ультрафильтр". С другой стороны, если аксиома выбора не выполняется, то может быть по разному, Например, в некоторых моделях теории множеств Цермело-Френкеля, любая система жульничества имеет "дыры" которые позволят дьяволу вас "поймать". Иначе говоря, в такой Вселенной свободные ультрафильтры на множестве натуральных чисел не существуют.
(no subject)
Date: 2024-12-02 02:06 am (UTC)Рувим Гуревич этим занимался (и был в восторге от идеи), но Рувим взял да умер, ничего не успев. Он эту задачку подцепил у Револьта Пименова. А вот Револьт откуда её подцепил - тут я могу запутаться. У кого-то из известных логиков, кажется.