pokazać nietatutologię, liczba skończonych modeli dla formuł

[matinf]

Pokaż, że zdanie \(\displaystyle{ \exists_x\exists_y\exists_u\exists_v ((\neg(u=x)\vee\neg (v=y))\wedge (f(x,y)=f(u,v))}\) nie jest tautologią. Ile nieizomorficznych modeli skończonych ma to zdanie ?

Nie jest to tautologia, bo:
\(\displaystyle{ f(x,y)=x+y}\).
\(\displaystyle{ x=1,y=2,u=3,v=4}\).

Natomiast co do modeli skończonych nieizomorficznych - ile ich jest ?
Co to jest model ? Model jest "czymś". W każdym bądź razie jakbyśmy to "coś" nie powartościowali, to i tak dostaniemy prawdę. W tym przypadku chyba modelem jest jakaś funkcja i jej dziedzina. Tak mi się wydaje, ale wciąż nie rozumiem tych pojęć.
Możecie pomóc ?

[Jan Kraszewski]

Co to jest model ?

Model to struktura algebraiczna, w której interpretujesz formułę.

JK

[matinf]

A do innych kwestii się nie odniesiesz ?

[krl]

Najpierw język.... Język \(\displaystyle{ L}\) to zestaw symboli funkcyjnych, relacyjnych i stałych. (czyli tak naprawdę alfabet określonego języka).

Teraz model... MOdel dla języka \(\displaystyle{ L}\) to układ \(\displaystyle{ M=(X,\dots)}\), gdzie \(\displaystyle{ X\neq\emptyset}\) to tzw. uniwersum (dziedzina) modelu \(\displaystyle{ M}\), zaś \(\displaystyle{ \dots}\) oznacza konretne funkcje i relacje określone na uniwersum \(\displaystyle{ X}\) i stałe z tego uniwersum - interpretacje symboli języka \(\displaystyle{ L}\).

W tym konkretnym przypadku nasz język składa się z symbolu funkcji binarnej. Model dla tego języka do zbiór \(\displaystyle{ X\neq\emptyset}\) z określoną na nim funkcją binarną \(\displaystyle{ f:X\times X\to X}\). Czyli \(\displaystyle{ M=(X,f)}\) (o \(\displaystyle{ f}\) możemy tu myśleć jak o działaniu algebraicznym).

Ile jest modeli skończonych? Hmm, trochę bez sensu to pytanie. Bardziej sensowne: Ile jest modeli skończonych \(\displaystyle{ k}\)-elementowych (tzn z uniwersum \(\displaystyle{ k}\)-elementowym), z dokładnością do izomorfizmu.

[matinf]

Najpierw język.... Język \(\displaystyle{ L}\) to zestaw symboli funkcyjnych, relacyjnych i stałych. (czyli tak naprawdę alfabet określonego języka).

Teraz model... MOdel dla języka \(\displaystyle{ L}\) to układ \(\displaystyle{ M=(X,\dots)}\), gdzie \(\displaystyle{ X\neq\emptyset}\) to tzw. uniwersum (dziedzina) modelu \(\displaystyle{ M}\), zaś \(\displaystyle{ \dots}\) oznacza konretne funkcje i relacje określone na uniwersum \(\displaystyle{ X}\) i stałe z tego uniwersum - interpretacje symboli języka \(\displaystyle{ L}\).

W tym konkretnym przypadku nasz język składa się z symbolu funkcji binarnej. Model dla tego języka do zbiór \(\displaystyle{ X\neq\emptyset}\) z określoną na nim funkcją binarną \(\displaystyle{ f:X\times X\to X}\). Czyli \(\displaystyle{ M=(X,f)}\) (o \(\displaystyle{ f}\) możemy tu myśleć jak o działaniu algebraicznym).

Ile jest modeli skończonych? Hmm, trochę bez sensu to pytanie. Bardziej sensowne: Ile jest modeli skończonych \(\displaystyle{ k}\)-elementowych (tzn z uniwersum \(\displaystyle{ k}\)-elementowym), z dokładnością do izomorfizmu.

Wiem z czego może wynikać nieporozumienie. U mnie Twój model nazywa się strukturą natomiast, model to taka struktura, która niezależnie od wartościowania spełnia formułę - czyli model jest dla pewnej formuły strukturą.

U nas jest formułą:
\(\displaystyle{ \exists_x\exists_y\exists_u\exists_v ((\neg(u=x)\vee\neg (v=y))\wedge (f(x,y)=f(u,v))}\)
Jak sam powiedziałeś, strukturą (Ty nazywasz to modelem) jest \(\displaystyle{ \langle X, f:X\times X\to X\rangle}\).

Czyli poszukujemy skończonych modeli. Czym mogą tu być modele ? No musi to być dziedzina i jakaś funkcja. Ale taka, że niezależnie od wartościowań formuła będzie zawsze prawdziwa. Co więcej, ten model ma być skończony.
Trochę nie rozumiem co ma tu znaczyć model skończony...., dlatego pozwolę sobie poprosić jeszcze o pomoc.

Bo ogólnie, to wydaje sie, że takim modelem dla tej formuły jest np:
\(\displaystyle{ X=\NN}\), \(\displaystyle{ f(x,y)=1}\) - po prostu funkcja stała. Co o tym myślisz ?

[krl]

Przepraszam za zamieszanie... W logice nazwy "model" i "struktura" używa się często zamiennie. Choć istotnie, być może bardziej poprawnie jest mówić o "modelu", gdy mamy na myśli model jakiegoś zdania lub teorii.
Moc modelu (struktury) to po prostu moc (liczba elementów) jego uniwersum. Model skończony to model, którego dziedzina (uniwersum) jest zbiorem skończonym.
Twój przykład na końcu istotnie spełnia zdanie, ale jest nieskończony.

[matinf]

Tak, wiem, że ten przykład spełnia zadanie, ale jest nieskończony.
Nie za bardzo potrafię sobie z tym poradzić. Nie wiem dokładnie kiedy dwa modele są izomorficzne.
Szczerze powiedziawszy to widać, że każda funkcja stała o skończonej dziedzinie to spełnia. Ale to tylko jakiś tam zbiór. Nawet nie wiem czy w obrębie tego zbioru te modele są izomorficzne, pewnie tak.

Poza tym skąd wiedzieć ile jest ogólnie tych funkcji ? Najpierw muszę zrozumieć które modele są izomorficzne...
Proszę o pomoc "mocniejszą".

[krl]

Może lepiej pozostać z wersją początkową pytania: "ile jest modeli skończonych, z dokładnością do izomorfizmu": to jest nie tyle "trochę bez sensu" (jak wyżej napisałem), tylko po prostu banalne. Bo modele skończone różnych mocy są oczywiście nieizomorficzne.
Natomiast badanie izomorficzności modeli skończonych tej samej mocy (czy ogólniej dowolnych modeli tej samej mocy) to często zadanie wysoce niebanalne. Tak jest właśnie w przypadku zdania z pierwszego postu, które mówi, że funkcja \(\displaystyle{ f}\) (o której możemy myśleć jak o działaniu) nie jest różnowartościowa. Jak słusznie zauważyłeś, w dziedzinie skończonej żadna funkcja binarna nie jest różnowartościowa. Wobec tego pytanie o liczbę nieizomorficznych modeli naszego zdania, o danej skończonej liczbie elementów, sprowadza się do pytania o liczbę nieizomorficznych struktur algebraicznych o tej liczbie elementów, z jednym działaniem binarnym. Ta liczba jest skończona, ale nie da się jej zapisać sensownym wzorem.

[matinf]

Chyba rozumiem co postulujesz.

1. To prawda, jeśli funkcja ma skończoną dziedzinę i jest binarna to nie może być różnowartościowa - zasada szufladkowa - zabraknie elementów w przeciwdziedzinie.
2. Tak właściwie dlaczego zakładamy, że ta funkcja jest binarna ? Wiem, że nie powiedziałem nic na ten temat, ale ja też nic w treści nie mam. Takie założenie wydaje się być słuszne. Zakładajmy to więc.
3. Modelem są zatem tutaj wszystkie funkcje binarne o skończonej dziedzinie. Dlaczego ? Bo każda taka funkcja nie jest różnowartościowa, czyli spełnia nasze zdanie dla każdego wartościowania \(\displaystyle{ u,v,x,y}\).
Zatem skoro modele o różnych rozmiarach dziedziny są nieizomorficzne, więc biorąc dziedziny rozmiaru \(\displaystyle{ k}\) dla każdego \(\displaystyle{ k\in\NN}\) mamy, że jest tego przeliczalnie wiele. Pytanie tylko jeszcze o nieizomorficzne funkcje dla ustalonego rozmiaru dziedziny \(\displaystyle{ k}\) - ile jest funkcji binarnych, które nie są parami izomorficzne ? Powiedziałeś, że trudno to policzyć, ale ta liczba jest skończona. Wystarczyłoby, żeby była przeliczalna nawet. Wówczas odpowiedzią w naszym zadaniu jest: przeliczalnie wiele.

Czy te wnioski są poprawne ?

[Jan Kraszewski]

2. Tak właściwie dlaczego zakładamy, że ta funkcja jest binarna ? Wiem, że nie powiedziałem nic na ten temat, ale ja też nic w treści nie mam.

Ależ masz. Funkcja binarna = funkcja dwuargumentowa.

JK

[matinf]

No dobrze, ale może ona wygląda tak:
\(\displaystyle{ f:X\times X\to X\times X\times X}\) a nie konkretnie \(\displaystyle{ X\times X\to X}\)

[Jan Kraszewski]

Nie. W strukturze funkcje mają zawsze wartości z \(\displaystyle{ X}\).

JK

[matinf]

A czy odniesiesz się do tego jeszcze: ?

1. To prawda, jeśli funkcja ma skończoną dziedzinę i jest binarna to nie może być różnowartościowa - zasada szufladkowa - zabraknie elementów w przeciwdziedzinie.
3. Modelem są zatem tutaj wszystkie funkcje binarne o skończonej dziedzinie. Dlaczego ? Bo każda taka funkcja nie jest różnowartościowa, czyli spełnia nasze zdanie dla każdego wartościowania u,v,x,y.
Zatem skoro modele o różnych rozmiarach dziedziny są nieizomorficzne, więc biorąc dziedziny rozmiaru k dla każdego kinNN mamy, że jest tego przeliczalnie wiele. Pytanie tylko jeszcze o nieizomorficzne funkcje dla ustalonego rozmiaru dziedziny k - ile jest funkcji binarnych, które nie są parami izomorficzne ? Powiedziałeś, że trudno to policzyć, ale ta liczba jest skończona. Wystarczyłoby, żeby była przeliczalna nawet. Wówczas odpowiedzią w naszym zadaniu jest: przeliczalnie wiele.