Symbol funkcyjny - Wikipedia, wolna encyklopedia

Wolna encyklopedia

Symbol funkcyjny – symbol używany w logice matematycznej i pokrewnych dziedzinach matematyki (np. algebrze abstrakcyjnej). Symbole funkcyjne są elementami alfabetów języków pierwszego rzędu (a także innych logik) i charakteryzują się tym, że zastosowane do obiektów zwanych termami produkują nowe termy.

W potocznym języku matematyki, symbole funkcyjne w wyrażeniach matematycznych oznaczają funkcje, np.: w wyrażeniu $f (x)$ symbolem funkcyjnym jest $f$ , w $x + y$ jest nim +, w $f (x) + y - g (z)$ są nimi $f$ , $g$ , + oraz -.

Spis treści

1 Symbole funkcyjne i termy w logikach pierwszego rzędu
- 1.1 Różne ujęcia i oznaczenia
- 1.2 Przykłady
2 Interpretacje termów w modelu
3 Zobacz też

Symbole funkcyjne i termy w logikach pierwszego rzędu

Wprowadzając język pierwszego rzędu najpierw określamy jego alfabet $τ$ czyli zbiór symboli funkcyjnych, symboli relacyjnych i stałych. Każdy z tych symboli ma jednoznacznie określony charakter (tzn wiadomo czy jest to stała, czy symbol funkcyjny czy też predykat) i każdy z symboli funkcyjnych i predykatów ma określoną arność (która jest dodatnią liczbą całkowitą). Ustalmy też nieskończoną listę zmiennych (zwykle $x_0,x_1,\ldots$ ).

Definiujemy termy języka ${\mathcal L}(\tau)$ przez indukcję po ich złożoności w następujący sposób:

wszystkie stałe i zmienne są termami,
jeśli $t_1,\ldots,t_n$ są termami, i $f\in\tau$ jest $n$ -arnym symbolem funkcyjnym, to $f(t_1,\ldots,t_n)$ jest termem.

Różne ujęcia i oznaczenia

W niektórych ujęciach rachunku kwantyfikatorów, stałe języka są traktowane jako 0-argumentowe symbole funkcyjne. Wówczas alfabet języka składa się jedynie z symboli funkcyjnych i symboli relacyjnych, ale arność tych pierwszych może być zero.
W teorii modeli czasami jest wygodniej zakładać, że alfabet rozważanego języka nie zawiera żadnych symboli funkcyjnych. Nie wprowadza to żadnego istotnego ograniczenia, bowiem każdy n-arny symbol funkcyjny f może być zastąpiony przez $n + 1$ -argumentową relację R tak że intuicyjny związek między nimi jest wyrażony przez

$f(x_1,\ldots,x_n)=x_{n+1}$ wtedy i tylko wtedy gdy $R(x_1,\ldots,x_n,x_{n+1})$ .

(Wymaga to dodania do rozważanych teorii zdania wyrażającego własność predykatu R że "pochodzi" on od pewnej funkcji.)

W algebrze, dwuczłonowe symbole funkcyjne są zapisywane pomiędzy termami. Tradycyjnie piszemy więc $x 1 + x 2$ (a nie $+ (x 1, x 2)$ ) itd.

Przykłady

Język teorii grup to ${\mathcal L}(\{*\})$ gdzie $*$ jest binarnym symbolem funkcyjnym. Przykładowe termy w tym języku to

(x 1 * x 2) * (x 1 * x 3)

x 1 * (x 1 * (x 1 * x 1))

Język ciał uporządkowanych to ${\mathcal L}(\{+,\cdot,0,1,\leq\})$ gdzie $+,\cdot$ są binarnymi symbolami funkcyjnymi a $\leq$ jest binarnym symbolem relacyjnym. Przykładowe termy w tym języku to

$(x_1+x_2)+(x_1\cdot x_3)$

$x_1+(x_1\cdot (x_1+x_1))$

0 + (1 + (0 + (1 + 0)))

Interpretacje termów w modelu

Niech $τ$ będzie alfabetem jakiegoś języka pierwszego rzędu i niech $S τ$ będzie zbiorem stałych tego alfabetu, $F τ$ będzie zbiorem symboli funkcyjnych, a $R τ$ będzie zbiorem symboli relacyjnych. modelem języka ${\mathcal L}(\tau)$ nazywamy układ

${\mathcal M} = (M; R^{\mathcal M},\ldots, f^{\mathcal M},\ldots, c^{\mathcal M},\ldots)_{R\in R_\tau, f\in F_\tau, c\in S_\tau}$

gdzie

M jest niepustym zbiorem zwanym dziedziną lub uniwersum modelu ${\mathcal M}$ (często uniwersum modelu ${\mathcal M}$ oznacza się przez $|{\mathcal M}|$ ),
dla n-arnego symbolu relacyjnego $R\in R_\tau$ , $R^{\mathcal M}$ jest n-argumentową relacją na zbiorze M, tzn. $R^{\mathcal M}\subseteq M^n$ ,
dla n-arnego symbolu funkcyjnego $f\in F_\tau$ , $f^{\mathcal M}$ jest n-argumentowym działaniem na zbiorze M, tzn. $f^{\mathcal M}: M^n\longrightarrow M$ ,
dla stałej $c\in S_\tau$ , $c^{\mathcal M}$ jest elementem zbioru M.

Tak więc w modelach danego języka symbole funkcyjne są interpretowane jako funkcje. Przez indukcję po złożoności termów definiujemy też interpretację termu w modelu ${\mathcal M}$ . Dla termu $t$ o zmiennych wolnych zawartych wśród $x_1,\ldots,x_n$ i dla elementów $m_1,\ldots,m_n\in M$ definiujemy $t^{\mathcal M}[m_1,\ldots,m_n]\in M$ następująco.

Jeśli t jest stałą c alfabetu τ, to $t^{\mathcal M}[m_1,\ldots,m_n]=c^{\mathcal M}$ .
Jeśli t jest zmienną $x i$ , to $t^{\mathcal M}[m_1,\ldots,m_n]=m_i$ .
Jeśli $t_1,\ldots,t_k$ są termami i $f\in F_\tau$ jest $k$ -arnym symbolem funkcyjnym, to $t^{\mathcal M}[m_1,\ldots,m_n]=f^{\mathcal M}(t_1^{\mathcal M}[m_1,\ldots,m_n],\ldots,t_k^{\mathcal M}[m_1,\ldots,m_n])$ .

Zobacz też

Źródło: „haslo,Symbol_funkcyjny”

Kategoria: Logika matematyczna