Лемма мощовакиса о кодировании - Moschovakis coding lemma

В Лемма мощовакиса о кодировании это лемма из описательных теория множеств включая наборы действительные числа под аксиома детерминированности (принцип - несовместим с выбор - что каждая целочисленная игра двух игроков определена). Лемма разработана и названа в честь математика Яннис Н. Мощовакис.

В общем виде лемму можно выразить следующим образом:

Позволять Γ быть несамостоятельным pointclass закрыт под реальная количественная оценка и ∧, и ≺ а Γ-основательное отношение к ωω ранга θ ∈ ON. Позволять R ⊆ dom (≺) × ωω быть таким, чтобы (∀Икс∈dom (≺)) (∃у)(Икс р у). Тогда есть Γ-набор A ⊆ dom (≺) × ωω который является набор выбора для R, то есть:
  1. (∀α<θ)(∃Икс∈dom (≺),у)(|Икс|≺=α ∧ Икс А у).
  2. (∀Икс,у)(Икс А у → Икс р у).

Доказательство таково: предположим от противоречия θ - минимальный контрпример, и зафиксируем ≺, р, и хороший универсальный набор U ⊆ (ωω)3 для Γ-подмножества (ωω)2. С легкостью, θ должен быть предельным порядковым номером.[1] За δ < θ, мы говорим ты ∈ ωω кодирует δ-выборочный набор при условии, что свойство (1) выполняется для α ≤ δ с помощью А = U u и свойство (2) выполнено для А = U u где мы заменяем Икс ∈ dom (≺) с Икс ∈ dom (≺) ∧ |Икс| ≺ [≤δ]. По минимальности θ, для всех δ < θ, Существуют δ-выборные наборы.

Теперь сыграйте в игру, в которой игроки I, II выбирают очки. ты,v ∈ ωω и II побеждает, когда ты кодирование δ1-выборный набор для некоторых δ1 < θ подразумевает v кодирует δ2-выборный набор для некоторых δ2 > δ1. Стратегия победы для I определяет Σ1
1 набор B кодирования вещественных чисел δ-выборные наборы для произвольно больших δ < θ. Определите тогда

Икс А у ↔ (∃ш∈B)U(ш,Икс,у),

который легко работает. С другой стороны, предположим τ является выигрышной стратегией для II. От s-m-n теорема, позволять s:(ωω)2 → ωω быть непрерывным таким, что для всех ϵ, Икс, т, и ш,

U(s(ϵ,Икс),т,ш) ↔ (∃у,z)(у ≺ Икс ∧ U(ϵ,у,z) ∧ U(z,т,ш)).

По теореме рекурсии существует ϵ0 такой, что U(ϵ0,Икс,z) ↔ z = τ(s(ϵ0,Икс)). Непосредственный вводный курс по |Икс|≺ за Икс ∈ dom (≺) показывает, что

(∀Икс∈dom (≺)) (∃!z)U(ϵ0,Икс,z),

и

(∀Икс∈dom (≺),z)(U(ϵ0,Икс,z) → z кодирует выбор набора порядковых номеров ≥ |Икс|≺).

Так что давайте

Икс А у ↔ (∃z∈dom (≺),ш)(U(ϵ0,z,ш) ∧ U(ш,Икс,у)).[2][3][4]

Рекомендации

  1. ^ Пользователь 16278263789; Швебер, Ноа (9 октября 2011 г.). "дескриптивная теория множеств - лемма Мошовакиса о кодировании". MathOverflow. Получено 2020-04-06.
  2. ^ Бабинкостова, Лиляна (2011). Теория множеств и ее приложения. Американское математическое общество. ISBN  978-0821848128.
  3. ^ Форман, Мэтью; Канамори, Акихиро (27 октября 2005 г.). Справочник по теории множеств (PDF). Springer. п. 2230. ISBN  978-1402048432.
  4. ^ Мощовакис, Яннис (4 октября 2006 г.). «Обыкновенные игры и игривые модели». В Александре С. Кечрисе; Дональд А. Мартин; Яннис Н. Мощовакис (ред.). Семинар Кабала 77 - 79: Труды, Логический семинар Калифорнийского технологического института и Калифорнийского технологического института 1977 - 79. Конспект лекций по математике. 839. Берлин: Springer. С. 169–201. Дои:10.1007 / BFb0090241. ISBN  978-3-540-38422-9.