Matematické Fórum

CzechMan

Zdravím, na prázdniny jsem si sehnal učebnici Logika - neúplnost, složitost a nutnost od Vítězslava Švejdara, abych trochu pohnul s těmito schopnostmi, ale zasekl jsem se hned na první ukázce logiky v Úvodu.

Je zde pětice axiomů (se procvičím v TeXu):
(1) $\forall{x}\forall{y}(x\le y \leftrightarrow \exists{v}(v+x=y))$ ,
(2) $\forall{x}\forall{y}\forall{z}(x+z\le y+z \to x\le y)$ ,
(3) $\forall{x}\forall{y}\forall{z}((x+y)+z=x+(y+z))$ ,
(4) $\forall{x}\forall{y}(x\cdot y\le x \ \wedge \ x\cdot y \le y)$ ,
(5) $\forall{x}\forall{y}\forall{z}(z\le x \ \wedge \ z\le y \to z\le x\cdot y)$ .

Bez ohledu na to, k čemu se axiomy vztahují, mám rozhodnout, zda z nich vyplývá formule D:
$\forall{a}\forall{b}\forall{c}((a+c)\cdot (b+c) \le (a\cdot b)+c)$

Vzápětí D dokazuje. Ale mi se povedlo dokázat non D. Což by teoreticky možné bylo, ale určitě by to panu doktoru neuniklo:)

Můj postup:
$d:=a\cdot b$ (*)
z (4) plyne $d\le a \wedge d\le b$
Dále předpokládám $a+c \le d+c$ (**). Z toho podle (2) plyne, že $a\le d$ , což je ve sporu s pravdivým tvrzením (*). Tedy předpoklad (**) byl chybný, správně je non(**) - $d+c \le a+c$ . Pokud v předešlé úvaze zaměním a za b, získám nerovnost $d+c\le b+c$ .
Pro formální správnost si nadefinuji:
$f:=d+c \nl g:=a+c \nl h:=b+c$
Po substituci platí $f\le g \wedge f\le h$ , z čehož podle (5) vyplývá $g\le g\cdot h$ .
Návrat zpět v substitucích:
$g\le g\cdot h \to d+c\le (a+c)\cdot (b+c) \to (a\cdot b)+c\le (a+c)\cdot (b+c)$

Pak můžu psát:
$(a\cdot b)+c\le (a+c)\cdot (b+c) \leftrightarrow \neg{D}$

Tedy, dokázal jsem spornost axiomů, nebo jsem udělal chyby? Mám dva kandidáty:
1. Ten spor nebyl úplně čistý anebo spíš
2. tvrzení, které jsem dokázal, není negace.

\\EDIT: jasně, nedokázal jsem negaci. Není vůbec důvod si to myslet. (dokonce má formule je na další straně jako cvičení)
Dále se píše, že axiomy platí pro množinu přirozených čísel, kde $+,\cdot ,\le$ znamenají po řadě násobení, největší společný dělitel, relace "být dělitelem"
To jsme vlastně společně s panem Švejdarem formálně dokázali jednoduchou rovnost z teorie čísel.

Zodpovězená otázka determinuje novou otázku:
Kdybych měl axiomy a neměl je k ničemu přířazené, mohl bych dokázat, že jsem dokázal rovnost?
Jinými slovy, $\forall{x}\forall{y}(x\le y\ \wedge \ y\le x \to x=y)$ , tedy antisymetričnost relace (tuším)?

Kondr · 04. 08. 2009 15:55

Trochu staré téma, ale snad si to ještě autor přečte:
axiomy fungují i pro celá čísla, kde
+ je násobení
. absolutní hodnota největších společných dělitelů
<= relace být dělitelem
V celých číslech platí, že 42 dělí -42 a -42 dělí 42, ale zřejmě 42 není rovno -42, proto to antisymetrické být nemusí.

A taky se mi nezdá ten důkaz -- z toho, že neplatí ** neplyne, že by platilo d+c<=a+c. Navíc a<=d a d<=a nejsou ve sporu ...

Matematické Fórum

#1 15. 07. 2009 16:59 — Editoval CzechMan (15. 07. 2009 18:01)

Logika - dokazatelnost formule z axiomů

#2 04. 08. 2009 15:55

Re: Logika - dokazatelnost formule z axiomů

Zápatí