Model (logika)

Vzhled přesunout do postranního panelu skrýt

Model (také struktura) je matematický pojem z oblasti matematickologické sémantiky. Je to seskupení objektů, na němž jsou definovány nějaké vztahy (relace) a přiřazení (funkce) tak, že vytváří „realizaci“ nějaké formální teorie.

Definice

Model jazyka

Struktura pro jazyk L (také model jazyka L), který obsahuje z mimologických symbolů konstantní symboly c α ; α ∈ I K {\displaystyle c_{\alpha };\alpha \in I_{K}} $c_{\alpha };\alpha \in I_{K}$ , funkční symboly f α {\displaystyle \,f_{\alpha }} $\,f_{\alpha }$ četností n α ; α ∈ I F {\displaystyle n_{\alpha };\alpha \in I_{F}} $n_{\alpha };\alpha \in I_{F}$ a predikátové symboly p α {\displaystyle \,p_{\alpha }} $\,p_{\alpha }$ četností n α ; α ∈ I P {\displaystyle n_{\alpha };\alpha \in I_{P}} $n_{\alpha };\alpha \in I_{P}$ , je množina A {\displaystyle A} $A$ nazývaná nosič struktury spolu s konstantami C α ∈ A ; α ∈ I K {\displaystyle C_{\alpha }\in A;\alpha \in I_{K}} $C_{\alpha }\in A;\alpha \in I_{K}$ , funkcemi F α : A n α → A ; α ∈ I F {\displaystyle F_{\alpha }:A^{n_{\alpha }}\rightarrow A;\alpha \in I_{F}} $F_{\alpha }:A^{n_{\alpha }}\rightarrow A;\alpha \in I_{F}$ a relacemi P α ⊆ A n α ; α ∈ I P {\displaystyle P_{\alpha }\subseteq A^{n_{\alpha }};\alpha \in I_{P}} $P_{\alpha }\subseteq A^{n_{\alpha }};\alpha \in I_{P}$ . Konstanta C α {\displaystyle \,C_{\alpha }} $\,C_{\alpha }$ , resp. funkce F α {\displaystyle \,F_{\alpha }} $\,F_{\alpha }$ , resp. relace P α {\displaystyle \,P_{\alpha }} $\,P_{\alpha }$ se nazývá realizací konstantního symbolu c α {\displaystyle \,c_{\alpha }} $\,c_{\alpha }$ , resp. funkčního symbolu f α {\displaystyle \,f_{\alpha }} $\,f_{\alpha }$ , resp. predikátového symbolu p α {\displaystyle \,p_{\alpha }} $\,p_{\alpha }$ v modelu A {\displaystyle A} $A$ a značí se c α A {\displaystyle \,c_{\alpha }^{A}} $\,c_{\alpha }^{A}$ , resp. f α A {\displaystyle \,f_{\alpha }^{A}} $\,f_{\alpha }^{A}$ , resp. p α A {\displaystyle \,p_{\alpha }^{A}} $\,p_{\alpha }^{A}$ . Struktura s nosičem A {\displaystyle A} $A$ (a příslušnými realizacemi symbolů) se obvykle značí A {\displaystyle {\mathcal {A}}} ${\mathcal {A}}$ .

Méně formálně: Jazyk L obsahuje pouze symboly pro konstanty, funkce a predikáty a arity funkcí a predikátů. Model jazyka L přidává množinu A {\displaystyle A} $A$ (nosič struktury, např. množinu přirozených čísel) a dodává symbolům jazyka L jejich realizace.

Tarského definice pravdy

V tomto odstavci značí A {\displaystyle {\mathcal {A}}} ${\mathcal {A}}$ model jazyka L s mimologickými symboly popsanými výše. Ohodnocení proměnných v modelu A {\displaystyle {\mathcal {A}}} ${\mathcal {A}}$ je každá funkce e {\displaystyle e} $e$ z množiny všech proměnných do nosiče A {\displaystyle A} $A$ . Ohodnocení, které se shoduje s ohodnocením e {\displaystyle e} $e$ na všech proměnných kromě x {\displaystyle x} $x$ a na x {\displaystyle x} $x$ má hodnotu a {\displaystyle a} $a$ , značíme e ( x / a ) {\displaystyle e(x/a)} $e(x/a)$ .

Realizace termu

Realizace termu t {\displaystyle t} $t$ jazyka L při ohodnocení proměnných e {\displaystyle e} $e$ v modelu A {\displaystyle A} $A$ , značíme t A ⟨ e ⟩ {\displaystyle \,t^{A}\langle e\rangle } $\,t^{A}\langle e\rangle$ , se definuje indukcí dle složitosti takto:

t A ⟨ e ⟩ = e ( x ) {\displaystyle \,t^{A}\langle e\rangle =e(x)} $\,t^{A}\langle e\rangle =e(x)$ , je-li t {\displaystyle t} $t$ proměnná x {\displaystyle x} $x$
t A ⟨ e ⟩ = c α A {\displaystyle \,t^{A}\langle e\rangle =c_{\alpha }^{A}} $\,t^{A}\langle e\rangle =c_{\alpha }^{A}$ , je-li t {\displaystyle t} $t$ konstantní symbol c α {\displaystyle \,c_{\alpha }} $\,c_{\alpha }$
t A ⟨ e ⟩ = f α A ( t 0 A ⟨ e ⟩ , … , t n α − 1 A ⟨ e ⟩ ) {\displaystyle t^{A}\langle e\rangle =f_{\alpha }^{A}(t_{0}^{A}\langle e\rangle ,\ldots ,t_{n_{\alpha }-1}^{A}\langle e\rangle )} $t^{A}\langle e\rangle =f_{\alpha }^{A}(t_{0}^{A}\langle e\rangle ,\ldots ,t_{n_{\alpha }-1}^{A}\langle e\rangle )$ , je-li t = f α ( t 0 , … , t n α − 1 ) {\displaystyle t=f_{\alpha }(t_{0},\ldots ,t_{n_{\alpha }-1})} $t=f_{\alpha }(t_{0},\ldots ,t_{n_{\alpha }-1})$ a t 0 , … , t n α − 1 {\displaystyle t_{0},\ldots ,t_{n_{\alpha }-1}} $t_{0},\ldots ,t_{n_{\alpha }-1}$ jsou termy

Platnost formule

Platnost formule φ {\displaystyle \,\varphi } $\,\varphi$ jazyka L při ohodnocení proměnných e {\displaystyle e} $e$ v modelu A {\displaystyle {\mathcal {A}}} ${\mathcal {A}}$ definujeme indukcí dle složitosti takto ( φ {\displaystyle \,\varphi } $\,\varphi$ platí v A {\displaystyle {\mathcal {A}}} ${\mathcal {A}}$ při ohodnocení e {\displaystyle e} $e$ značíme A ⊨ φ ⟨ e ⟩ {\displaystyle {\mathcal {A}}\models \varphi \langle e\rangle } ${\mathcal {A}}\models \varphi \langle e\rangle$ , φ {\displaystyle \,\varphi } $\,\varphi$ neplatí v A {\displaystyle {\mathcal {A}}} ${\mathcal {A}}$ při ohodnocení e {\displaystyle e} $e$ značíme A ⊭ φ ⟨ e ⟩ {\displaystyle {\mathcal {A}}\not \models \varphi \langle e\rangle } ${\mathcal {A}}\not \models \varphi \langle e\rangle$ ):

Je-li φ {\displaystyle \,\varphi } $\,\varphi$ atomická formule tvaru p α ( t 0 , … , t n α − 1 ) {\displaystyle p_{\alpha }(t_{0},\ldots ,t_{n_{\alpha }-1})} $p_{\alpha }(t_{0},\ldots ,t_{n_{\alpha }-1})$ , pak A ⊨ φ ⟨ e ⟩ {\displaystyle {\mathcal {A}}\models \varphi \langle e\rangle } ${\mathcal {A}}\models \varphi \langle e\rangle$ , pokud ( t 0 A ⟨ e ⟩ , … , t n α − 1 A ⟨ e ⟩ ) ∈ p α A {\displaystyle (t_{0}^{A}\langle e\rangle ,\ldots ,t_{n_{\alpha }-1}^{A}\langle e\rangle )\in p_{\alpha }^{A}} $(t_{0}^{A}\langle e\rangle ,\ldots ,t_{n_{\alpha }-1}^{A}\langle e\rangle )\in p_{\alpha }^{A}$ .
Je-li φ {\displaystyle \,\varphi } $\,\varphi$ atomická formule tvaru t 0 = t 1 {\displaystyle \,t_{0}=t_{1}} $\,t_{0}=t_{1}$ , pak A ⊨ φ ⟨ e ⟩ {\displaystyle {\mathcal {A}}\models \varphi \langle e\rangle } ${\mathcal {A}}\models \varphi \langle e\rangle$ , pokud t 0 A ⟨ e ⟩ = t 1 A ⟨ e ⟩ {\displaystyle t_{0}^{A}\langle e\rangle =t_{1}^{A}\langle e\rangle } $t_{0}^{A}\langle e\rangle =t_{1}^{A}\langle e\rangle$ .
Je-li φ {\displaystyle \,\varphi } $\,\varphi$ formule tvaru ¬ ψ {\displaystyle \neg \psi } $\neg \psi$ , pak A ⊨ φ ⟨ e ⟩ {\displaystyle {\mathcal {A}}\models \varphi \langle e\rangle } ${\mathcal {A}}\models \varphi \langle e\rangle$ pokud A ⊭ ψ ⟨ e ⟩ {\displaystyle {\mathcal {A}}\not \models \psi \langle e\rangle } ${\mathcal {A}}\not \models \psi \langle e\rangle$
Je-li φ {\displaystyle \,\varphi } $\,\varphi$ formule tvaru ψ ⇒ χ {\displaystyle \psi \Rightarrow \chi } $\psi \Rightarrow \chi$ , pak A ⊨ φ ⟨ e ⟩ {\displaystyle {\mathcal {A}}\models \varphi \langle e\rangle } ${\mathcal {A}}\models \varphi \langle e\rangle$ pokud buďto A ⊭ ψ ⟨ e ⟩ {\displaystyle {\mathcal {A}}\not \models \psi \langle e\rangle } ${\mathcal {A}}\not \models \psi \langle e\rangle$ nebo A ⊨ χ ⟨ e ⟩ {\displaystyle {\mathcal {A}}\models \chi \langle e\rangle } ${\mathcal {A}}\models \chi \langle e\rangle$ .
Je-li φ {\displaystyle \,\varphi } $\,\varphi$ formule tvaru ( ∀ x ) ψ {\displaystyle (\forall x)\psi } $(\forall x)\psi$ , pak A ⊨ φ ⟨ e ⟩ {\displaystyle {\mathcal {A}}\models \varphi \langle e\rangle } ${\mathcal {A}}\models \varphi \langle e\rangle$ , pokud A ⊨ ψ ⟨ e ( x / a ) ⟩ {\displaystyle {\mathcal {A}}\models \psi \langle e(x/a)\rangle } ${\mathcal {A}}\models \psi \langle e(x/a)\rangle$ pro všechna a ∈ A {\displaystyle a\in A} $a\in A$ .

Říkáme, že φ {\displaystyle \,\varphi } $\,\varphi$ platí v modelu A {\displaystyle {\mathcal {A}}} ${\mathcal {A}}$ , značíme A ⊨ φ {\displaystyle {\mathcal {A}}\models \varphi } ${\mathcal {A}}\models \varphi$ , pokud A ⊨ φ ⟨ e ⟩ {\displaystyle {\mathcal {A}}\models \varphi \langle e\rangle } ${\mathcal {A}}\models \varphi \langle e\rangle$ pro každé ohodnocení proměnných e {\displaystyle e} $e$ .

Model teorie

Je-li T teorie v jazyce L a A {\displaystyle {\mathcal {A}}} ${\mathcal {A}}$ struktura pro tento jazyk, pak říkáme, že A {\displaystyle {\mathcal {A}}} ${\mathcal {A}}$ je modelem T, značíme A ⊨ T {\displaystyle {\mathcal {A}}\models T} ${\mathcal {A}}\models T$ , pokud A ⊨ φ {\displaystyle {\mathcal {A}}\models \varphi } ${\mathcal {A}}\models \varphi$ pro každý axiom φ {\displaystyle \,\varphi } $\,\varphi$ teorie T.

Příklady

Množina přirozených čísel spolu s konstantou 0 {\displaystyle \,0} $\,0$ , binární relací ≤ {\displaystyle \,\leq } $\,\leq$ a funkcemi + {\displaystyle \,+} $\,+$ , ⋅ {\displaystyle \,\cdot } $\,\cdot$ a S {\displaystyle \,S} $\,S$ ( S ( n ) = n + 1 {\displaystyle \,S(n)=n+1} $\,S(n)=n+1$ ) tvoří model Peanovy aritmetiky. Tento model se nazývá standardní model.
Libovolná grupa je modelem axiomatické teorie grup.

Izomorfismus modelů

Izomorfismem modelů (struktur) A , B {\displaystyle {\mathcal {A}},\,{\mathcal {B}}} ${\mathcal {A}},\,{\mathcal {B}}$ téhož jazyka L je taková bijekce i : A → B {\displaystyle i:A\rightarrow B} $i:A\rightarrow B$ , která zachovává všechny symboly jazyka L, tj. splňuje:

i ( c A ) = c B {\displaystyle \,i(c^{A})=c^{B}} $\,i(c^{A})=c^{B}$ pro každý konstantní symbol c jazyka L
i ( f A ( a 1 , … , a n ) ) = f B ( i ( a 1 ) , … , i ( a n ) ) {\displaystyle i(f^{A}(a_{1},\ldots ,a_{n}))=f^{B}(i(a_{1}),\ldots ,i(a_{n}))} $i(f^{A}(a_{1},\ldots ,a_{n}))=f^{B}(i(a_{1}),\ldots ,i(a_{n}))$ pro každý funkční symbol f jazyka L četnosti n.
p A ( a 1 , … , a n ) ⇔ p B ( i ( a 1 ) , … , i ( a n ) ) {\displaystyle p^{A}(a_{1},\ldots ,a_{n})\Leftrightarrow p^{B}(i(a_{1}),\ldots ,i(a_{n}))} $p^{A}(a_{1},\ldots ,a_{n})\Leftrightarrow p^{B}(i(a_{1}),\ldots ,i(a_{n}))$

Existuje-li izomorfismus modelů A , B {\displaystyle {\mathcal {A}},\,{\mathcal {B}}} ${\mathcal {A}},\,{\mathcal {B}}$ , říkáme, že jsou tyto modely izomorfní.

Související články

Portály: Matematika