Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Q1: If $S$ is a set of axioms, and $A$ and $B$ are statements, is it possible that $S+A$ is inconsistent but $S+A+B$ is consistent?

Added.

Q2: If $X+Y$, $Y+Z$ and $X+Z$ are consistent, is $X+Y+Z$ necessarily consistent?

share|improve this question
2  
If from $S$ and $A$ you can derive $P$ and $\neg P$, then from $S$, $A$, and $B$ you can also derive $P$ and $\neg P$ (just use the same deductions and ignore $B$). –  Arturo Magidin Dec 10 '11 at 4:53
    
I have now an additional question –  user20962 Dec 10 '11 at 5:13
4  
Q2: No. Take $X:x=y$, $Y:y\neq z$, and $Z:z=x$. –  Arturo Magidin Dec 10 '11 at 5:14
4  
It is bad form to change a post in such a way that it makes already posted answers incorrect or incomplete. Here, you are doing a disservice to Arthur Fischer, who posted a complete answer to your original question, but whose answer now seems incomplete. If you must add material, it should be clearly marked as an addition to alert readers. –  Arturo Magidin Dec 10 '11 at 5:19

2 Answers 2

up vote 7 down vote accepted

(This answer only deals with the original question by CCCP. The second question seems to be dealt with well in the comments.)

No. What does it mean for $S + A$ to be inconsistent? It means that for every formula $\phi$ there is a formal proof from $S + A$ of $\phi$. However, every formal proof from $S + A$ is also a formal proof from $S + A + B$ (you just never actually use the extra axiom $B$), and so it will follow that $S + A + B$ is also inconsistent.

share|improve this answer
    
The OP has added a second question; you may want to note that you are only addressing the original question. –  Arturo Magidin Dec 10 '11 at 5:18

Allow me to describe an answer to a generalization of Question 2.

What you have is three statements, such that any two of them are consistent, but all three of them are not. How about other patterns? For example, can you have five statements, any three of which are consistent, but never four? What about other combinations?

Theorem. For any finite $k\lt r$, there are $r$ statements $\varphi_1,\varphi_2,\ldots,\varphi_r$, such that any $k$ of them are consistent, but any $k+1$ of them are not.

Proof. Imagine that we intend to choose at most $k$ balls from a collection of $r$ balls. Each $\varphi_i$ asserts that we have chosen ball $i$. Any $k$ of the assertions is consistent, since we can carry $k$ balls, but any $k+1$ is inconsistent, since we cannot carry that many.

(More formally: this can be stated in the language of one unary predicate $U$ and $r$ constant symbols $c_1,\ldots,c_r$. Each $\varphi_i$ asserts that all the constants are different, that at most $k$ of them are in $U$, and that $U(i)$ holds. Any $k$ of these are consistent, and any $k+1$ are inconsistent.) QED

share|improve this answer
    
Even more: Given any collection $A \subseteq {\mathcal P} (\{1,2,\dots,n\})$ closed under taking subsets, there are statements $\phi_1, \phi_2, \dots, \phi_n$ such that $\phi_{i_1}, \phi_{i_2}, \dots, \phi_{i_k}$ is consistent iff $\{i_1, i_2, \dots, i_k\} \in A$. –  sdcvvc Dec 10 '11 at 12:50
    
Yes, I agree with that, and it can be formalized in the same manner as what I indicate: each $\phi_i$ should assert that $U$ is in $\cal A$, that the constants are distinct and that $U(i)$. The version I mentioned arises in some very interesting work in proof theory, in which researchers have established the necessity of very long formal proofs. –  JDH Dec 10 '11 at 12:55
2  
For example, people.cs.uchicago.edu/~razborov/files/php_survey.pdf –  JDH Dec 10 '11 at 13:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.