Joc de Ehrenfeucht-Fraïssé

În teoria modelelor, jocurile Ehrenfeucht - Fraïssé sunt o metodă matematică pentru tratarea echivalenței elementare a două structuri.

Organizarea unui joc de către Ehrenfeucht - Fraïssé

Sunt date două structuri ${\mathfrak {A}}$ ${\ displaystyle {\ mathfrak {A}}}$ ${\ mathfrak {A}}$ Și ${\mathfrak {B}}$ ${\ displaystyle {\ mathfrak {B}}}$ $\ mathfrak {B}$ , ambele fără simboluri funcționale și având aceleași simboluri relaționale ^[1] și se dă un număr natural $n$ ${\ displaystyle n}$ $n$ . Jocul Ehrenfeucht-Fraïssé $G_{n}({\mathfrak {A}},{\mathfrak {B}})$ ${\ displaystyle G_ {n} ({\ mathfrak {A}}, {\ mathfrak {B}})}$ ${\ displaystyle G_ {n} ({\ mathfrak {A}}, {\ mathfrak {B}})}$ va fi jucat de doi jucători, un atacant și un apărător . Scopul atacatorului este de a găsi o diferență între cele două structuri; apărătorul trebuie să facă tot posibilul pentru al opri. Jocul se joacă după cum urmează:

Atacatorul alege un element $a_{1}$ ${\ displaystyle a_ {1}}$ $a_1$ din ${\mathfrak {A}}$ ${\ displaystyle {\ mathfrak {A}}}$ ${\ mathfrak {A}}$ sau un articol $b_{1}$ ${\ displaystyle b_ {1}}$ $b_1$ din ${\mathfrak {B}}$ ${\ displaystyle {\ mathfrak {B}}}$ $\ mathfrak {B}$ .
Dacă atacatorul a ales un element în ${\mathfrak {A}}$ ${\ displaystyle {\ mathfrak {A}}}$ ${\ mathfrak {A}}$ , apărătorul alege un element $b_{1}$ ${\ displaystyle b_ {1}}$ $b_1$ din ${\mathfrak {B}}$ ${\ displaystyle {\ mathfrak {B}}}$ $\ mathfrak {B}$ ; invers, dacă atacatorul a ales un element în ${\mathfrak {B}}$ ${\ displaystyle {\ mathfrak {B}}}$ $\ mathfrak {B}$ , apărătorul alege un element $a_{1}$ ${\ displaystyle a_ {1}}$ $a_1$ din ${\mathfrak {A}}$ ${\ displaystyle {\ mathfrak {A}}}$ ${\ mathfrak {A}}$ .
Atacatorul alege din nou un element $a_{2}\neq a_{1}$ ${\ displaystyle a_ {2} \ neq a_ {1}}$ ${\ displaystyle a_ {2} \ neq a_ {1}}$ din ${\mathfrak {A}}$ ${\ displaystyle {\ mathfrak {A}}}$ ${\ mathfrak {A}}$ sau un articol $b_{2}\neq b_{1}$ ${\ displaystyle b_ {2} \ neq b_ {1}}$ ${\ displaystyle b_ {2} \ neq b_ {1}}$ din ${\mathfrak {B}}$ ${\ displaystyle {\ mathfrak {B}}}$ $\ mathfrak {B}$ .
Apărătorul alege din nou un element din cealaltă structură.
Întrebarea și răspunsul se repetă pe tot parcursul $n$ ${\ displaystyle n}$ $n$ ori.
La încheierea jocului, au fost selectați $n$ ${\ displaystyle n}$ $n$ elemente $a_{1},\dots ,a_{n}$ ${\ displaystyle a_ {1}, \ dots, a_ {n}}$ $a_ {1}, \ dots, a_ {n}$ din ${\mathfrak {A}}$ ${\ displaystyle {\ mathfrak {A}}}$ ${\ mathfrak {A}}$ Și $n$ ${\ displaystyle n}$ $n$ elemente $b_{1},\dots ,b_{n}$ ${\ displaystyle b_ {1}, \ dots, b_ {n}}$ ${\ displaystyle b_ {1}, \ dots, b_ {n}}$ din ${\mathfrak {B}}$ ${\ displaystyle {\ mathfrak {B}}}$ $\ mathfrak {B}$ . Putem vedea aceste două colecții ca substructuri ale lui ${\mathfrak {A}}$ ${\ displaystyle {\ mathfrak {A}}}$ ${\ mathfrak {A}}$ Și ${\mathfrak {B}}$ ${\ displaystyle {\ mathfrak {B}}}$ $\ mathfrak {B}$ , cu aceleași relații. ^[2]

Fundașul a câștigat dacă $a_{i}\mapsto b_{i}$ ${\ displaystyle a_ {i} \ mapsto b_ {i}}$ ${\ displaystyle a_ {i} \ mapsto b_ {i}}$ este un izomorfism. În caz contrar, atacatorul a câștigat.

Analiza pas cu pas

Cel prezentat mai sus este cel mai simplu mod de a defini victoria într-un joc Ehrenfeucht - Fraïssé.

Alternativ, se poate observa că apărătorul câștigă dacă, la fiecare mișcare, elementul pe care îl alege verifică cu elementele alese anterior în structura sa toate și numai relațiile pe care elementul tocmai ales de atacator le verifică cu elementele alese anterior. celălalt.

Prin urmare, va fi această a doua definiție a victoriei pe care o vom lua în considerare atunci când vom analiza câteva exemple de Ehrenfeucht - jocul lui Fraïssé.

Interpretarea jocurilor

Două structuri ${\mathfrak {A}}$ ${\ displaystyle {\ mathfrak {A}}}$ ${\ displaystyle {\ mathfrak {A}}}$ Și ${\mathfrak {B}}$ ${\ displaystyle {\ mathfrak {B}}}$ ${\ displaystyle {\ mathfrak {B}}}$ vor spune ei $m$ ${\ displaystyle m}$ $m$ -echivalenți (această relație este indicată cu simbolul ${\underset {k}{\equiv }}$ ${\ displaystyle {\ underset {k} {\ equiv}}}$ ${\ displaystyle {\ underset {k} {\ equiv}}}$ ) dacă fundașul are o strategie câștigătoare pentru joc $G_{m}({\mathfrak {A}},{\mathfrak {B}})$ ${\ displaystyle G_ {m} ({\ mathfrak {A}}, {\ mathfrak {B}})}$ ${\ displaystyle G_ {m} ({\ mathfrak {A}}, {\ mathfrak {B}})}$ .

Este ușor de verificat că două structuri în esență echivalente sunt $m$ ${\ displaystyle m}$ $m$ -echivalenți pentru orice număr natural $m$ ${\ displaystyle m}$ $m$ (cu condiția ca simbolurile relației de pe structuri să fie finite) și invers.

Exemple

Structuri finite

De sine ${\mathfrak {A}}$ ${\ displaystyle {\ mathfrak {A}}}$ ${\ mathfrak {A}}$ Și ${\mathfrak {B}}$ ${\ displaystyle {\ mathfrak {B}}}$ $\ mathfrak {B}$ sunt două structuri finite ale respectiv $\alpha$ ${\ displaystyle \ alpha}$ $\ alfa$ Și $\beta$ ${\ displaystyle \ beta}$ $\ beta$ elemente, cu $\alpha >\beta$ ${\ displaystyle \ alpha> \ beta}$ ${\ displaystyle \ alpha> \ beta}$ (de sine $\beta >\alpha$ ${\ displaystyle \ beta> \ alpha}$ $\ beta> \ alfa$ , discursul este analog), fundașul pierde fiecare joc $G_{n}({\mathfrak {A}},{\mathfrak {B}})$ ${\ displaystyle G_ {n} ({\ mathfrak {A}}, {\ mathfrak {B}})}$ ${\ displaystyle G_ {n} ({\ mathfrak {A}}, {\ mathfrak {B}})}$ cu $n>\alpha$ ${\ displaystyle n> \ alpha}$ ${\ displaystyle n> \ alpha}$ . De fapt, va fi suficient ca atacatorul să aleagă câte un element la un moment dat ${\mathfrak {A}}$ ${\ displaystyle {\ mathfrak {A}}}$ ${\ mathfrak {A}}$ : chiar dacă apărătorul este capabil să reziste $\beta$ ${\ displaystyle \ beta}$ $\ beta$ se mută, nu va putea găsi un element diferit de cele anterioare din ${\mathfrak {B}}$ ${\ displaystyle {\ mathfrak {B}}}$ $\ mathfrak {B}$ la $\beta +1$ ${\ displaystyle \ beta +1}$ ${\ displaystyle \ beta +1}$ -a mutare.

De fapt, două structuri finite cu cardinalitate diferită nu sunt niciodată elementar echivalente.

Dacă în schimb $\alpha =\beta$ ${\ displaystyle \ alpha = \ beta}$ $\ alpha = \ beta$ , cele două structuri sunt practic echivalente dacă și numai dacă sunt izomorfe și, în acest caz, date $\phi :{\mathfrak {A}}\rightarrow {\mathfrak {B}}$ ${\ displaystyle \ phi: {\ mathfrak {A}} \ rightarrow {\ mathfrak {B}}}$ ${\ displaystyle \ phi: {\ mathfrak {A}} \ rightarrow {\ mathfrak {B}}}$ un izomorfism, mișcările pe care trebuie să le facă apărătorul sunt simple: la fiecare alegere a unui element $a_{i}\in {\mathfrak {A}}$ ${\ displaystyle a_ {i} \ in {\ mathfrak {A}}}$ ${\ displaystyle a_ {i} \ in {\ mathfrak {A}}}$ din partea atacatorului, el va răspunde cu $\phi (a_{i})$ ${\ displaystyle \ phi (a_ {i})}$ ${\ displaystyle \ phi (a_ {i})}$ , la fiecare alegere de $b_{i}$ ${\ displaystyle b_ {i}}$ $bi}$ va răspunde cu $\phi ^{-1}(b_{i})$ ${\ displaystyle \ phi ^ {- 1} (b_ {i})}$ ${\ displaystyle \ phi ^ {- 1} (b_ {i})}$ .

Numere reale și numere raționale

Să luăm în considerare structurile $(\mathbb {Q} ,<)$ ${\ displaystyle (\ mathbb {Q}, <)}$ ${\ displaystyle (\ mathbb {Q}, <)}$ Și $(\mathbb {R} ,<)$ ${\ displaystyle (\ mathbb {R}, <)}$ ${\ displaystyle (\ mathbb {R}, <)}$ , adică numere reale și numere raționale văzute doar ca mulțimi dense ordonate liniar . Aceste două structuri sunt în esență echivalente: de fapt, completitudinea (care distinge tipul de ordine al uneia de cea a celeilalte) este o proprietate de ordinul al doilea, în sensul că nu poate fi definită fără cuantificarea pe seturi („ pentru fiecare împreună $I\subset \mathbb {R}$ ${\ displaystyle I \ subset \ mathbb {R}}$ ${\ displaystyle I \ subset \ mathbb {R}}$ , există un element $X$ ${\ displaystyle x}$ $X$ care este extremul său superior "). Aceasta înseamnă că într-o piesă de teatru a lui Ehrenfeucht - Fraïssé $G_{n}({\mathfrak {A}},{\mathfrak {B}})$ ${\ displaystyle G_ {n} ({\ mathfrak {A}}, {\ mathfrak {B}})}$ ${\ displaystyle G_ {n} ({\ mathfrak {A}}, {\ mathfrak {B}})}$ , cu $n$ ${\ displaystyle n}$ $n$ oricum, fundașul are întotdeauna o strategie câștigătoare.

După $k$ ${\ displaystyle k}$ $k$ de fapt, elementele au fost alese $a_{1}\dots a_{k}$ ${\ displaystyle a_ {1} \ dots a_ {k}}$ ${\ displaystyle a_ {1} \ dots a_ {k}}$ într-una din cele două structuri e $b_{1}\dots b_{k}$ ${\ displaystyle b_ {1} \ dots b_ {k}}$ ${\ displaystyle b_ {1} \ dots b_ {k}}$ in cealalta. Să presupunem că $k+1$ ${\ displaystyle k + 1}$ $k + 1$ -a mutare, atacatorul alege un element $a_{k+1}$ ${\ displaystyle a_ {k + 1}}$ ${\ displaystyle a_ {k + 1}}$ . Desigur $a_{1}\dots a_{k+1}$ ${\ displaystyle a_ {1} \ dots a_ {k + 1}}$ ${\ displaystyle a_ {1} \ dots a_ {k + 1}}$ este un lanț , deoarece este un subset al unui set ordonat liniar. Atunci $a_{k+1}$ ${\ displaystyle a_ {k + 1}}$ ${\ displaystyle a_ {k + 1}}$ Sara:

mai mare decât fiecare $a_{i}$ ${\ displaystyle a_ {i}}$ $la}$ cu $i<k$ ${\ displaystyle i <k}$ ${\ displaystyle i <k}$ : în acest caz apărătorul trebuie doar să ia $b_{k+1}$ ${\ displaystyle b_ {k + 1}}$ ${\ displaystyle b_ {k + 1}}$ mai mare decât fiecare $b_{i}$ ${\ displaystyle b_ {i}}$ $bi}$ cu $i<k$ ${\ displaystyle i <k}$ ${\ displaystyle i <k}$
mai puțin decât fiecare $a_{i}$ ${\ displaystyle a_ {i}}$ $la}$ cu $i<k$ ${\ displaystyle i <k}$ ${\ displaystyle i <k}$ : apărătorul trebuie doar să ia $b_{k+1}$ ${\ displaystyle b_ {k + 1}}$ ${\ displaystyle b_ {k + 1}}$ mai puțin decât fiecare $b_{i}$ ${\ displaystyle b_ {i}}$ $bi}$ cu $i<k$ ${\ displaystyle i <k}$ ${\ displaystyle i <k}$
între a $a_{i}$ ${\ displaystyle a_ {i}}$ $la}$ e o $a_{j}$ ${\ displaystyle a_ {j}}$ ${\ displaystyle a_ {j}}$ (astfel încât între $a_{i}$ ${\ displaystyle a_ {i}}$ $la}$ Și $a_{j}$ ${\ displaystyle a_ {j}}$ ${\ displaystyle a_ {j}}$ nu există alte elemente în colecție): în acest caz apărătorul poate lua $b_{k+1}={\frac {b_{i}+b_{j}}{2}}$ ${\ displaystyle b_ {k + 1} = {\ frac {b_ {i} + b_ {j}} {2}}}$ ${\ displaystyle b_ {k + 1} = {\ frac {b_ {i} + b_ {j}} {2}}}$

Situația este identică (înlocuiți „a” cu „b” peste tot) dacă atacatorul alege un element $b_{k+1}$ ${\ displaystyle b_ {k + 1}}$ ${\ displaystyle b_ {k + 1}}$ .

Să analizăm acum $(\mathbb {Q} ,<,0,+)$ ${\ displaystyle (\ mathbb {Q}, <, 0, +)}$ ${\ displaystyle (\ mathbb {Q}, <, 0, +)}$ Și $(\mathbb {R} ,<,0,+)$ ${\ displaystyle (\ mathbb {R}, <, 0, +)}$ ${\ displaystyle (\ mathbb {R}, <, 0, +)}$ , adică numerele raționale și numerele reale văzute ca grupuri ordonate cu operația de adunare. Aceste două structuri nu mai sunt practic echivalente și, într-adevăr, atacatorul are o strategie câștigătoare pentru fiecare joc de cel puțin 3 mutări:

Mutarea atacatorului

Mișcarea apărătorului

Motivație

1

a_{1}=0\in \mathbb {Q}

{\ displaystyle a_ {1} = 0 \ in \ mathbb {Q}}

{\ displaystyle a_ {1} = 0 \ in \ mathbb {Q}}

b_{1}=0\in \mathbb {R}

{\ displaystyle b_ {1} = 0 \ in \ mathbb {R}}

{\ displaystyle b_ {1} = 0 \ in \ mathbb {R}}

Un izomorfism al grupurilor poate trimite doar elementul neutru al unui grup în elementul neutru al celuilalt.

2

b_{2}=1\in \mathbb {R}

{\ displaystyle b_ {2} = 1 \ in \ mathbb {R}}

{\ displaystyle b_ {2} = 1 \ in \ mathbb {R}}

a_{2}={\frac {c}{d}}\in \mathbb {Q} {\text{, con }}{\frac {c}{d}}>0

{\ displaystyle a_ {2} = {\ frac {c} {d}} \ in \ mathbb {Q} {\ text {, cu}} {\ frac {c} {d}}> 0}

{\ displaystyle a_ {2} = {\ frac {c} {d}} \ in \ mathbb {Q} {\ text {, cu}} {\ frac {c} {d}}> 0}

b_{2}>b_{1}

{\ displaystyle b_ {2}> b_ {1}}

{\ displaystyle b_ {2}> b_ {1}}

, așa trebuie să fie

a_{2}>a_{1}

{\ displaystyle a_ {2}> a_ {1}}

{\ displaystyle a_ {2}> a_ {1}}

în caz contrar, alegerea este gratuită.

3

b_{3}=\pi \in \mathbb {R}

{\ displaystyle b_ {3} = \ pi \ in \ mathbb {R}}

{\ displaystyle b_ {3} = \ pi \ in \ mathbb {R}}

Apărătorul a pierdut

Dacă apărătorul a ales un număr

a_{3}={\frac {e}{f}}\in \mathbb {Q}

{\ displaystyle a_ {3} = {\ frac {e} {f}} \ in \ mathbb {Q}}

{\ displaystyle a_ {3} = {\ frac {e} {f}} \ in \ mathbb {Q}}

, am avea asta:

{\begin{matrix}\underbrace {a_{2}+a_{2}+\dots a_{2}} &={\frac {c}{d}}*d*e=c*e={\frac {e}{f}}*f*c=&\underbrace {a_{3}+a_{3}+\dots a_{3}} \\d*e{\text{ volte}}&&f*c{\text{ volte}}\end{matrix}}

{\ displaystyle {\ begin {matrix} \ underbrace {a_ {2} + a_ {2} + \ dots a_ {2}} & = {\ frac {c} {d}} * d * e = c * e = {\ frac {e} {f}} * f * c = & \ underbrace {a_ {3} + a_ {3} + \ dots a_ {3}} \\ d * e {\ text {times}} && f * c {\ text {times}} \ end {matrix}}}

{\ displaystyle {\ begin {matrix} \ underbrace {a_ {2} + a_ {2} + \ dots a_ {2}} & = {\ frac {c} {d}} * d * e = c * e = {\ frac {e} {f}} * f * c = & \ underbrace {a_ {3} + a_ {3} + \ dots a_ {3}} \\ d * e {\ text {times}} && f * c {\ text {times}} \ end {matrix}}}

dar:

{\begin{matrix}\underbrace {b_{2}+b_{2}+\dots b_{2}} &=1*d*e=d*e\not =\pi f*c=&\underbrace {a_{3}+a_{3}+\dots a_{3}} \\d*e{\text{ volte}}&&f*c{\text{ volte}}\end{matrix}}

{\ displaystyle {\ begin {matrix} \ underbrace {b_ {2} + b_ {2} + \ dots b_ {2}} & = 1 * d * e = d * e \ not = \ pi f * c = & \ underbrace {a_ {3} + a_ {3} + \ dots a_ {3}} \\ d * e {\ text {times}} && f * c {\ text {times}} \ end {matrix}}}

{\ displaystyle {\ begin {matrix} \ underbrace {b_ {2} + b_ {2} + \ dots b_ {2}} & = 1 * d * e = d * e \ not = \ pi f * c = & \ underbrace {a_ {3} + a_ {3} + \ dots a_ {3}} \\ d * e {\ text {times}} && f * c {\ text {times}} \ end {matrix}}}

deoarece

\pi

{\ displaystyle \ pi}

\ pi

este irațional și, prin urmare, nu poate fi

={\frac {d*e}{f*c}}

{\ displaystyle = {\ frac {d * e} {f * c}}}

{\ displaystyle = {\ frac {d * e} {f * c}}}

.

Deci, am avea o formulă verificată într-un subarbore, dar nu în celălalt, adică mutarea nu ar fi validă.

Numere relative

Să luăm în considerare structurile ${\mathfrak {A}}=(\mathbb {N} ,<)$ ${\ displaystyle {\ mathfrak {A}} = (\ mathbb {N}, <)}$ ${\ displaystyle {\ mathfrak {A}} = (\ mathbb {N}, <)}$ Și ${\mathfrak {B}}=(\mathbb {N} +\mathbb {Z} ,<')$ ${\ displaystyle {\ mathfrak {B}} = (\ mathbb {N} + \ mathbb {Z}, <')}$ ${\ displaystyle {\ mathfrak {B}} = (\ mathbb {N} + \ mathbb {Z}, <')}$ , unde cu $\mathbb {N} +\mathbb {Z}$ ${\ displaystyle \ mathbb {N} + \ mathbb {Z}}$ ${\ displaystyle \ mathbb {N} + \ mathbb {Z}}$ mijloace $\mathbb {N} \times {0}\cup \mathbb {Z} \times 1$ ${\ displaystyle \ mathbb {N} \ times {0} \ cup \ mathbb {Z} \ times 1}$ ${\ displaystyle \ mathbb {N} \ times {0} \ cup \ mathbb {Z} \ times 1}$ Și $<'$ ${\ displaystyle <'}$ ${\ displaystyle <'}$ este ordinea antilexicografică.

Cele două structuri sunt $m$ ${\ displaystyle m}$ $m$ -echivalenți pentru orice număr natural $m$ ${\ displaystyle m}$ $m$ ; de fapt, următoarea este o strategie câștigătoare pentru fundaș:

dacă atacatorul alege un element mai mare (sau mai mic) dintre toți cei deja aleși de aceeași structură (sau în orice caz în aceeași „copie” a $\mathbb {N}$ ${\ displaystyle \ mathbb {N}}$ $\ mathbb N$ sau $\mathbb {Z}$ ${\ displaystyle \ mathbb {Z}}$ $\ mathbb Z$ ), apărătorul alege din cealaltă structură un element egal cu cel mai mare (respectiv mai mic) element adăugat (respectiv scăzut) $2^{k}$ ${\ displaystyle 2 ^ {k}}$ $2 ^ {k}$ , unde este $k$ ${\ displaystyle k}$ $k$ este numărul de mișcări lipsă la sfârșitul jocului
în caz contrar, dacă atacatorul alege un element care este $n$ ${\ displaystyle n}$ $n$ -Altul cel mai mare dintre cei deja aleși în aceeași structură, apărătorul alege din cealaltă structură media aritmetică ^[3] între $n-1$ ${\ displaystyle n-1}$ $n-1$ -alea și $n$ ${\ displaystyle n}$ $n$ -el mai mare element dintre cele deja alese

Este ușor verificat prin inducție că media aritmetică a două elemente este întotdeauna întreagă și că într-adevăr cea dată este o strategie câștigătoare pentru apărător.

Acest rezultat implică faptul că $(\mathbb {N} ,<)$ ${\ displaystyle (\ mathbb {N}, <)}$ ${\ displaystyle (\ mathbb {N}, <)}$ Și $(\mathbb {N} +\mathbb {Z} ,<')$ ${\ displaystyle (\ mathbb {N} + \ mathbb {Z}, <')}$ ${\ displaystyle (\ mathbb {N} + \ mathbb {Z}, <')}$ (un model nestandard de numere naturale ) sunt practic echivalente. Într - adevăr, acest lucru este confirmat de faptul că pentru a formula principiul inducției asupra numerelor naturale (care este valabil în $\mathbb {N}$ ${\ displaystyle \ mathbb {N}}$ $\ mathbb N$ dar nu în modelul non-standard dat), o formulă de prim ordin nu este suficientă.

Istorie

Metoda „vino și pleacă” folosită în jocurile lui Ehrenfeucht-Fraïssé pentru a verifica echivalența elementară a fost furnizată de Roland Fraïssé în teza sa ^[4] , ^[5] ; a fost reformulat sub forma unui joc de Andrzej Ehrenfeucht . ^[6] În literatura de limbă engleză, atacatorul este adesea numit Spoiler și apărătorul Duplicator , datorită unui obicei început de Joel Spencer . ^[7]

Generalizare

Jocurile lui Ehrenfeucht - Fraïssé, terminologia $m$ ${\ displaystyle m}$ $m$ -echivalența și notația asociată pot fi generalizate la orice numere ordinale prin formalizarea următoarei intuiții:

de sine $\alpha =\beta +1$ ${\ displaystyle \ alpha = \ beta +1}$ ${\ displaystyle \ alpha = \ beta +1}$ , atunci „apărătorul are o strategie câștigătoare pentru $G_{\alpha }({\mathfrak {A}},{\mathfrak {B}})$ ${\ displaystyle G _ {\ alpha} ({\ mathfrak {A}}, {\ mathfrak {B}})}$ ${\ displaystyle G _ {\ alpha} ({\ mathfrak {A}}, {\ mathfrak {B}})}$ „înseamnă” apărătorul are o strategie câștigătoare pentru $G_{\beta }({\mathfrak {A}},{\mathfrak {B}})$ ${\ displaystyle G _ {\ beta} ({\ mathfrak {A}}, {\ mathfrak {B}})}$ ${\ displaystyle G _ {\ beta} ({\ mathfrak {A}}, {\ mathfrak {B}})}$ , la finalul căruia este capabil să reziste încă o mișcare ";
de sine $\alpha =\sup\{\beta <\alpha \}$ ${\ displaystyle \ alpha = \ sup \ {\ beta <\ alpha \}}$ ${\ displaystyle \ alpha = \ sup \ {\ beta <\ alpha \}}$ , atunci „apărătorul are o strategie câștigătoare pentru $G_{\alpha }({\mathfrak {A}},{\mathfrak {B}})$ ${\ displaystyle G _ {\ alpha} ({\ mathfrak {A}}, {\ mathfrak {B}})}$ ${\ displaystyle G _ {\ alpha} ({\ mathfrak {A}}, {\ mathfrak {B}})}$ „înseamnă” apărătorul are o strategie câștigătoare pentru fiecare $G_{\beta }({\mathfrak {A}},{\mathfrak {B}})$ ${\ displaystyle G _ {\ beta} ({\ mathfrak {A}}, {\ mathfrak {B}})}$ ${\ displaystyle G _ {\ beta} ({\ mathfrak {A}}, {\ mathfrak {B}})}$ cu $\beta <\alpha$ ${\ displaystyle \ beta <\ alpha}$ ${\ displaystyle \ beta <\ alpha}$ ".

Rețineți că generalizarea în acest mod nu înseamnă introducerea „mișcărilor infinite” jocuri Ehrenfeucht - Fraïssé. De exemplu:

${\mathfrak {A}}{\underset {\omega }{\equiv }}{\mathfrak {B}}$ ${\ displaystyle {\ mathfrak {A}} {\ underset {\ omega} {\ equiv}} {\ mathfrak {B}}}$ ${\ displaystyle {\ mathfrak {A}} {\ underset {\ omega} {\ equiv}} {\ mathfrak {B}}}$ va însemna pur și simplu $\forall m\in \mathbb {N} ,{\mathfrak {A}}{\underset {m}{\equiv }}{\mathfrak {B}}$ ${\ displaystyle \ forall m \ in \ mathbb {N}, {\ mathfrak {A}} {\ underset {m} {\ equiv}} {\ mathfrak {B}}}$ ${\ displaystyle \ forall m \ in \ mathbb {N}, {\ mathfrak {A}} {\ underset {m} {\ equiv}} {\ mathfrak {B}}}$ , adică "apărătorul poate câștiga un joc de $m$ ${\ displaystyle m}$ $m$ se mișcă cu $m$ ${\ displaystyle m}$ $m$ număr natural ales arbitrar de atacator.
${\mathfrak {A}}{\underset {\omega +1}{\equiv }}{\mathfrak {B}}$ ${\ displaystyle {\ mathfrak {A}} {\ underset {\ omega +1} {\ equiv}} {\ mathfrak {B}}}$ ${\ displaystyle {\ mathfrak {A}} {\ underset {\ omega +1} {\ equiv}} {\ mathfrak {B}}}$ va însemna „apărătorul poate câștiga $G_{\omega }({\mathfrak {A}},{\mathfrak {B}})$ ${\ displaystyle G _ {\ omega} ({\ mathfrak {A}}, {\ mathfrak {B}})}$ ${\ displaystyle G _ {\ omega} ({\ mathfrak {A}}, {\ mathfrak {B}})}$ (care constă dintr-un meci $G_{m}({\mathfrak {A}},{\mathfrak {B}})$ ${\ displaystyle G_ {m} ({\ mathfrak {A}}, {\ mathfrak {B}})}$ ${\ displaystyle G_ {m} ({\ mathfrak {A}}, {\ mathfrak {B}})}$ cu $m\in \mathbb {N}$ ${\ displaystyle m \ in \ mathbb {N}}$ ${\ displaystyle m \ in \ mathbb {N}}$ ales de atacator) și rezista unei alte mișcări
$A{\underset {\omega ^{2}}{\equiv }}B$ ${\ displaystyle A {\ underset {\ omega ^ {2}} {\ equiv}} B}$ ${\ displaystyle A {\ underset {\ omega ^ {2}} {\ equiv}} B}$ va însemna „apărătorul este capabil să reziste $n$ ${\ displaystyle n}$ $n$ (număr natural ales de atacator) jocuri consecutive, fiecare dintr-un număr finit de mișcări alese de fiecare dată în mod arbitrar de atacator.

Din acest motiv, a fost adăugată o altă notație, ${\mathfrak {A}}{\underset {\infty }{\equiv }}{\mathfrak {B}}$ ${\ displaystyle {\ mathfrak {A}} {\ underset {\ infty} {\ equiv}} {\ mathfrak {B}}}$ ${\ displaystyle {\ mathfrak {A}} {\ underset {\ infty} {\ equiv}} {\ mathfrak {B}}}$ , Ceea ce înseamnă „apărătorul este capabil să reziste la un număr arbitrar de mare și nu este fixat la începutul mișcărilor”.

Lectură recomandată

Primul capitol al textului model al teoriei lui Poizat ^[8] conține o introducere în jocurile lui Ehrenfeucht-Fraïssé, precum și capitolele 6, 7 și 13 din cartea lui Rosenstein despre ordine liniare. ^[9]

Notă

^ Se înțelege exact că au aceleași simboluri și că același simbol are aceeași ariete în ambele structuri; nu înseamnă că există o asemănare suplimentară între relațiile pe care le reprezintă (deși acest lucru se întâmplă de obicei, deoarece în matematică fiecare simbol este utilizat în mod convențional pentru a indica relații particulare și pentru că compararea relațiilor care nu au nimic în comun este de obicei neinteresant).
^ Sau mai precis cu restricțiile relațiilor definite pe structurile respective.
^ Conceptul de medie aritmetică este extins în mod natural la ${\mathfrak {B}}$ ${\ displaystyle {\ mathfrak {B}}}$ ${\ displaystyle {\ mathfrak {B}}}$ : media $(1,a)$ ${\ displaystyle (1, a)}$ ${\ displaystyle (1, a)}$ Și $(1,b)$ ${\ displaystyle (1, b)}$ ${\ displaystyle (1, b)}$ Sara $\left(1,{\frac {a+b}{2}}\right)$ ${\ displaystyle \ left (1, {\ frac {a + b} {2}} \ right)}$ ${\ displaystyle \ left (1, {\ frac {a + b} {2}} \ right)}$
^ Sur une nouvelle classification des systèmes de relations , Roland Fraïssé, Comptes Rendus 230 (1950), 1022–1024.
^ Sur quelques classifications des systèmes de relations , Roland Fraïssé, teză, Paris, 1953; publicat în Publications Scientifiques de l'Université d'Alger , seria A 1 (1954), 35–182.
^ O aplicație a jocurilor la problema completitudinii pentru teoriile formalizate, A. Ehrenfeucht, Fundamenta Mathematicae 49 (1961), 129-141.
^(EN) Encyclopedia of Philosophy Stanford, secțiunea despre logică și jocuri
^ Un curs în teoria modelelor , Bruno Poizat, tr. Moses Klein, New York: Springer-Verlag, 2000.
^ Linear Orderings , Joseph G. Rosenstein, New York: Academic Press, 1982.

[1] Se înțelege exact că au aceleași simboluri și că același simbol are aceeași ariete în ambele structuri; nu înseamnă că există o asemănare suplimentară între relațiile pe care le reprezintă (deși acest lucru se întâmplă de obicei, deoarece în matematică fiecare simbol este utilizat în mod convențional pentru a indica relații particulare și pentru că compararea relațiilor care nu au nimic în comun este de obicei neinteresant).

[2] Sau mai precis cu restricțiile relațiilor definite pe structurile respective.

[3] Conceptul de medie aritmetică este extins în mod natural la ${\mathfrak {B}}$ ${\ displaystyle {\ mathfrak {B}}}$ ${\ displaystyle {\ mathfrak {B}}}$ : media $(1,a)$ ${\ displaystyle (1, a)}$ ${\ displaystyle (1, a)}$ Și $(1,b)$ ${\ displaystyle (1, b)}$ ${\ displaystyle (1, b)}$ Sara $\left(1,{\frac {a+b}{2}}\right)$ ${\ displaystyle \ left (1, {\ frac {a + b} {2}} \ right)}$ ${\ displaystyle \ left (1, {\ frac {a + b} {2}} \ right)}$

[4] Sur une nouvelle classification des systèmes de relations , Roland Fraïssé, Comptes Rendus 230 (1950), 1022–1024.

[5] Sur quelques classifications des systèmes de relations , Roland Fraïssé, teză, Paris, 1953; publicat în Publications Scientifiques de l'Université d'Alger , seria A 1 (1954), 35–182.

[6] O aplicație a jocurilor la problema completitudinii pentru teoriile formalizate, A. Ehrenfeucht, Fundamenta Mathematicae 49 (1961), 129-141.

[7] (EN) Encyclopedia of Philosophy Stanford, secțiunea despre logică și jocuri

[8] Un curs în teoria modelelor , Bruno Poizat, tr. Moses Klein, New York: Springer-Verlag, 2000.

[9] Linear Orderings , Joseph G. Rosenstein, New York: Academic Press, 1982.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]