Prädikatenlogik/Maximal widerspruchsfrei/Beispiele/Folgerungen/Fakt/Beweis

Beweis

(1). Wegen der Widerspruchsfreiheit kann nicht sowohl als auch zu gehören. Wenn weder noch zu gehören, so ist entweder oder widerspruchsfrei. Wären nämlich beide widersprüchlich, so würde für einen beliebigen Ausdruck sowohl

als auch

gelten. Dies bedeutet

und

woraus aufgrund der Fallunterscheidungsregel

folgt. Dies bedeutet aber, dass widersprüchlich ist.
(2). Es sei . Nach (1) ist oder . Das zweite kann nicht sein, da sich daraus sofort ein Widerspruch ergeben würde. Also ist .
(3). Die Richtung von links nach rechts folgt aus (2). Es seien also . Da nach Aufgabe eine Tautologie ist, folgt nach Teil (2).