# Construct a deductive system where $1^n$ is provable iff $n$ is prime

I'd appreciate some help or at least a hint for the following exercise:

Construct a (as simple as possible) deductive system where all sequences of the form $$1^n$$ (which means 111... $$n$$-times) is provable if and only if n is prime. (Note: As simple as possible means that the deductive rules and axioms should follow a simple schema. For example the schema "$$1^n$$ is an axiom iff n is prime" isn't a considered simple)

At first I thought this can't be possible because I would have to construct an algorithm which gives me all prime numbers. But then I thought it should be possible to decide for every natural number if it is prime by test division. For deductive system I would take all sequences of the symbols $$1$$,$$*$$,$$+$$ and $$=$$ and with them I would like to somehow construct deductive rules which are the analogy to the test division and giving me the number if the test division only works for the sequence ($$111...$$) itself or the sequence $$1$$.

• Is there a reason you aren't going with a logic with 1 rule of inference $$\dfrac{\emptyset}{1^n} \quad \text{For prime } n$$ Are you saying this is somehow "not simple?" – DanielV Oct 27 '18 at 14:30
• @DanielV Yes. Your example is considered 'not simple' in context of this exercise. I guess 'not simple' is not meant like easy to understand but rather to give only a finite number of axioms and inference rules. – thehardyreader Oct 27 '18 at 14:45
• Is this question from a class or textbook? – DanielV Oct 27 '18 at 15:03
• It is from a class. Maybe I have to point out that there can be impossible exercises in this class but if this is the case I have to explain why they are impossible. – thehardyreader Oct 27 '18 at 18:07
• Btw.: Another exercise would be to write a deduction system where $1^n$ is provable iff $n>1$ is not prime. – thehardyreader Oct 27 '18 at 20:36

1. Construct a subsystem that can prove: $$\operatorname{lt}(1^k, 1^n)$$ iff $$k < n$$, and $$\operatorname{add}(1^k, 1^l, 1^n)$$ iff $$k+l = n$$. This should be straightforward.

2. Extend it to a system that can prove: $$\operatorname{ndiv}(1^k, 1^n)$$ iff $$k$$ does not divide $$n$$. You can do this with two rules:

$$\frac{\operatorname{lt}(y,x)}{\operatorname{ndiv}(x,y)} \text{ and } \frac{\operatorname{ndiv}(x,y),\, \operatorname{add}(x,y,z)}{\operatorname{ndiv}(x,z)}$$

Well, be careful with $$0$$ and all. Also, you can do it with an axiom schema instead of a rule schema and just use modus ponens as the only derivation rule...

1. And finally, extend it with $$\operatorname{ndivsmaller}(1^k, 1^n)$$, which should be provable iff no $$l$$ divides $$n$$ for all $$2 \leq l < k$$. This is a particular case of induction:

$$\frac{\emptyset}{\operatorname{ndivsmaller(11, 1x)}} \text{ and }\frac{\operatorname{ndivsmaller}(y, x), \, \operatorname{ndiv}(y,x)}{\operatorname{ndivsmaller}(1y, x)}$$

1. With this $$n$$ is prime iff you can derive $$\operatorname{ndivsmaller}(1^n, 1^n)$$, so you add this as your final rule:

$$\frac{\operatorname{ndivsmaller}(11x, 11x)}{11x}$$

(The two $$1$$s are there to avoid dealing with $$0$$ and $$1$$.)

Again, there are some details left to fill out and you can do it in many different ways, but I hope that the idea is clear.

• Thank you very much! This is the solution I was looking for! – thehardyreader Oct 28 '18 at 12:47