Математическая логика и теория алгоритмов

ф (т~ф), и непротиворечивой в противном случае ( (Гс ф) & (тч^ф)). Будем считать это первым определением (не) противоречивости. Второе определение (не) противоречивости. Дедуктивная теория называется противоречивой, если существует формула а такая, что в этой теории выводимо а и выводимо 1 а-, если такой формулы не существует, то теория называется непротиворечивой. Теорема 4.2. Для теорий, содержащих исчисление высказыва­ ний, приведенные определения (не) противоречивости эквивалентньь Доказательство. Покажем, что из второго определения следует первое. Пусть существует формулатакая, что выводима а nl а: [•а, (4.5) 1-1^. (4.6) В п. в) леммы 4.2 доказано, что для любых формул акв имеет место; [-'U=>(yi=>5). (4.7) Из (4.6) и (4.7) по mp получаем (4.8) а из (4,8) и (4.5) снова по mp имеем: |- в. Последнее и означает, что доказуема любая формула в, т.е. множество теорем совпадает с мно­ жество формул. Если примем первое определение, то в противоречивой теории доказуема любая формула, т. е. для любой формулы а получим, что а и 1А являются теоремами, следовательно, теория противоречива согласно второму определению. 15.5