Dedukciótétel

Azt gondolom elfogytak a hozzászólások, így összefoglalnám magamnak az eddigieket és visszaterelném a szót az eredeti kérdéshez.

Olybá tűnik, hogy a (valamilyen) dedukciótétel és az (valamilyen) univerzális generalizáció komplementer jellegűek a formális rendszerekben való megvalósulásuk tekintetében. Ahol korlátozatlan feltételű a d.t., ott korlátozásokkal terhelt az u.g. és fordítva. A legmegengedőbb esetben d.t a D1 alakban szerepel, az u.g. pedig ezesetben: Γ |- φ -ból következik Γ |- ∀xφ(x), feltéve, hogy a Γ beli formulák egyikében sem szerepel x szabadon. Ez a megszorítás intuitív annyiban , hogy x-ről amúgy is feltesszük, hogy semmilyen speciális előfeltevéssel nem terhelt, ráadásul ez megakadályozza András p(x)|-∀xp(x)-en alapuló ellenpéldáját. (Persze, ha |-p(x) azt jelenti a szemantika szintjén, hogy minden értékelésre p(x) igaz, akkor ez nem intuitív, akkor viszont igen, ha |-p(x) azt jelenti, hogy p az x betűre(termre) igaz, de mást a helyére téve már nem feltétlenül, mert csak a ∀xp(x) formula ad általános jelleget p-nek.)

Lakatos példát adott arra, hogy egy intuitív tétel a kor szintjén még akár bizonyítható is lehet, miközben később a fogalmváltozással együtt módosul a tétel igazságértéke (Euler-Descartes-féle poliédertétel). Lehet továbbá jó matematikai megérzéseket igazzá tenni oly módon, hogy csűrjük-csavarjuk a feltételeket és leszűkítjük az érvényességi tartományt (folytonos függvények konvergens sorozatának határfüggvénye folytonos ---> folytonos függvények egyenletesen konvergens sorozatának határfüggvénye folytonos).
Most nem azt kérdezem, hogy igazak-e ezek a tételek az eredeti formájukban, hanem, hogy értelmes-e az a kérdés, hogy
-- a természetes nyelv elégtelensége okozza-e a pontosítási kényszert, mert nem "ragadja meg" jól az "objektív" matematikai állításokat vagy
-- a formális nyelv, a formális-axiomatikus-deduktív rendszer nem fejezi-e ki adekvát módon (nem fordítja le helyesen) a természetes nyelvi (érvényes) mondatokat?

Az első "tag-kérdőmondatot" a platonizmus-antirealizmus vitát kedvelőknek ajánlom, a másodikat pedig a formalista-antiformalista vitát kedvelőknek.

Továbbá Simonyi Andrásnak egy *-os példa (mégis ő mindközülünk a szakember ezen a téren :) ha relevánsak a kérdések, hol jön a képbe a strukturalizmus (... és ha nem relevánsak)?

Lényegében megválaszoltátok a zárójeles kérdésemet. Nos, nem voltam biztos a dolgomban, ezért is írtam zárójelbe és ezért is gondoltam, megkérdezem tőletek. A következők miatt gondoltam, hogy a dedukciótételt nem cáfolja az említett példa. Ha T a halmazelmélet, akkor T ∪ {x=y} ellentmondásos, ez OK. Ekkor
T ∪ {x=y} |- x ≠ y
és a (D1) Dedukciótétel értelmében
T |- (x=y) ⊃ (x ≠ y)
ez ugyanazt jelenti, mint
T |- (x ≠ y) v (x ≠ y)
ami viszont ugyanaz mint
T |- x ≠ y
ami az indirekt bizonyítás elve értelmében és szerintem intuitíve is fennáll, mert "a halmazelmélet univerzuma végtelen". Ám, Simonyi András kitűnő diagnózist adott az intuíciók ellentétéről:

András írta:"Viszont elképzelhető egy másik, természetesnek tűnő kiterjesztés is, ami valahogy így szólna:

Γ |= φ pontosan akkor, ha tetsz. olyan modellben és változóértékelés esetén melyek mellett Γ minden eleme igaz, φ is igaz. Nekem úgy tűnik, hogy emellett a definíció mellett teljesül, hogy ha Γ ∪ {ψ} |= φ, akkor Γ |= ψ ⊃ φ, de viszont nyilvánvalóan nem lesz érvényes az univerzális generalizáció szabálya..."

Ebből (is) kiderül, hogy hol hibáztam. Az említett (és nem is ritka) |= -értelmezés esetén csak abban a formában tehető fel a generalizáció, ha φ-ben nem szerepel szabadon x:
|=φ-ből ekkor következik |=∀xφ(x)

Ott hibáztam, hogy használtam az indirekt bizonyítás elvét, mely sajnos a dedukciótételből kapja az érvényességét és (bár ennek nem néztem utána) de biztosan van benne valami feltétel a zártságra vonatkozóan. Érvelésem azonban érvényes, ha az András által leírt következményrelációhoz adekvát levezethetőséget használjuk -- ekkor viszont nincs mit cáfolni.

Az intuicióra vonatkozó kérdésem viszont méginkább fennáll, hiszen a korlátozatlan univerzális generalizáció legalább annyira intuitív fogalom, mint a Dedukciótétel. Így még "csodálatosabb", hogy mint azt mondtam, egyeseknek sikerült olyan (ellentmondásmentes) nyelvet definiálniuk, melyben mindkét levezetési szabály korlátozás nélkül érvényes. (Azért nem teljesen korlátlan, mert azt teszi fel, hogy Γ |- φ maga után vonja Γ |- ∀xφ(x) -t, de csak ha Γ formulái között nem szerepel x szabadon, ami pont a kritikus levezetéseket gátolja meg.) Az ára az volt, hogy be kellett vezetniük a Hilbert-féle deskriptorokat, amelyekkel kifejezve érvényes például a következő állítás:
|- ∀x A(x) a.cs.a, ha |- A(T)
ahol T az a term, melynek jelentése: "olyan dolog, mely teljesíti ¬ A-t". Azaz
∀x A(x)levezethető, a.cs.a, ha még az a dolog is kieglégíti A-t, ami ¬ A "fogalma alá esik" (tehát a nemlétező).

Vissztérve a konkrét példára

T|-x ≠ y

egyrész lehet nem bizonyítható (hiszen "bármely x, y-ra x ≠ y" biztos nem igaz), másrészt fenn is állhat, de ekkor valami olyan a jelentése, hogy "általában ...", vagy hogy "konkrétan az 'x' és 'y' term nem egyenlő, ha grafikusan is különözők".

Kedves MoZó, (ha én is szólíthatlak így), most már tényleg nagyon fúrja az oldalamat, hogy mi a kifogásod a halmazelméletes példával kapcsolatban :-)

Egy kísérlet az ellentétes intuíciók megvilágítására:

A szemantikai következményrelációt úgy szokták zárt mondatokról tetsz. formulára kiterjeszteni, hogy tetsz formulahalmaznak akkor következménye egy formula, ha a zárt mondatok körében definiált reláció fennáll az univerzális lezártak között. Erre a következményrelációra érvényesek az eddig tárgyalt ellenpéldák, tehát itt intuitíve sem igaz, hogy ha Γ ∪ {ψ} |= φ, akkor Γ |= ψ ⊃ φ

Viszont elképzelhető egy másik, természetesnek tűnő kiterjesztés is, ami valahogy így szólna:

Γ |= φ pontosan akkor, ha tetsz. olyan modellben és változóértékelés esetén melyek mellett Γ minden eleme igaz, φ is igaz. Nekem úgy tűnik, hogy emellett a definíció mellett teljesül, hogy ha Γ ∪ {ψ} |= φ, akkor Γ |= ψ ⊃ φ, de viszont nyilvánvalóan nem lesz érvényes az univerzális generalizáció szabálya...

Zalán példája tetszik a legjobban. András példáját (bocs!) nem értem, Károlyét értem, de nem "hiszem" (nehéz nekem a modális szemantika), Zalánét értem is, hiszem is, de azt nem tudom, hogy az általam említett formális nyelvhez létezik-e adekvát szemantika. Így, a helyzet az, hogy még gondolkodnom kell.

Amúgy, ha ragaszkodunk eleink (Tarski) gondolatvilágához, akkor
|- p(x)
-nek nincs jelentése mint kijelentésnek (mert nem mondat, hanem "nyitott mondat"), csak a
|-?xp(x)
nek. Íly módon a D2 is kifejezi, amit elvárunk tőle mint dedukciótételtől.

Mindenesetre kösz :)

András példájához csatlakozva itt egy másik példa (lényegében ugyanaz más köntösben). S5-ben (meg más rendszerekben is) érvényes a modális generalizálás elve:

Ha ⊢p, akkor ⊢◽p

Ebből nyilván nem szabad arra következtetni, hogy

p → ◽p

S5-tétel lenne.

(x=0) |= (y=0)
|= (x=0) -> (y=0)

(T = ureshalmaz)

Ez jó ellenpédának D1-re: az elsőnek az 1 elemű struktúrák modelljei; míg a második nem teljesül.

Be ke vallanom, hogy nekem nagyjából-egészében jónak tűnik a halmazelméletes példa (bár túlbonyolított) -- kifejtenéd, hogy szerinted miért problémás?

Miután elolvastam ezt a bejegyzést, kutakodtam egy egyszerűbb "ellenpélda" után is, és a következőt találtam (Zaltáék honlapján):

Induljunk ki a P(x) állításból. Ebből univ. generalizálással levezethető ∀xP(x), tehát

P(x) |- ∀xP(x)

igaz. Ha teljesülne D1, akkor

|- P(x) ⊃ ∀xP(x)

is igaz lenne, amiből megint csak generalizálással

|- ∀x[P(x) ⊃ ∀xP(x)]

adódna, vagyis az általános D1 logikai igazságot "varázsolna" abból az állításból, hogy ha tetszőleges individuum P tulajdonságú, akkor mindegyik az.