Axioms independence in Rosser system

Question

In textbook, I see a method to judge axiom independence: Axiom Systems. One example is in the link, and in this interpretation, R.S1 is not always A, while the other two are A-tautology, so R.S 1 is independence. And I hope to know if there is some method to find the specific interpretation to make an axiom not always A. I tried to make it for R.S.3 but failed, there are too many choices and when I change one, I need to change many other items.

Answer 1

Before I answer your actual question, I first would like to point out that having R.S.1 not being an A-tautology, while the others are, does not immediately make R.S.1 independent from the others: you also need to verify that using the inference rule(s) as provided by the axiom system under consideration, you can only infer A-tautologies from other A-tautologies. For example, if your only inference rules is Modus Ponens, then you need to verify that whenever $P \rightarrow Q$ and $P$ have the value of $A$, then $Q$ has the value of $A$ as well.

Ok, now to your question: Unfortunately, it is indeed not always easy to find an interpretation that works for your purposes, and often you have to do a good bit of trial and error. After you have tried a few things, though, you typically do get a sense of direction as to what such an interpretation would have to look like (and, some values of the interpretation will have to be forced, especially given the necessary nature of the inference rules as I stated in the first point). And, when you get close, you know where it still fails, and sometimes you can just make a small correction to make it fully work.

But no, I don't know of any algorithm that will automatically and quickly generate an interpretation that will work. However, if you have some programming skills, you could write a program to just brute-force the whole space of possible interpretations.

One more thing to note, though. It is possible to find a 'non-standard' interpretations that is still only $2$-valued ... but in my experience that doesn't happen too often. So, typically you'll have to work with a $3$-valued system, and typically there is one of those. However, it is also possible that the only interpretations that will work need more than $3$ values, so now you'll need $4$ or $5$ or ... And again, as far as I can tell, there is really nothing that would systematically be able to predict for you how many values you need.

Hope this helps. Good luck!