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$.

  • $\begingroup$ 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?" $\endgroup$ – DanielV Oct 27 '18 at 14:30
  • 1
    $\begingroup$ @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. $\endgroup$ – thehardyreader Oct 27 '18 at 14:45
  • $\begingroup$ Is this question from a class or textbook? $\endgroup$ – DanielV Oct 27 '18 at 15:03
  • $\begingroup$ 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. $\endgroup$ – thehardyreader Oct 27 '18 at 18:07
  • $\begingroup$ Btw.: Another exercise would be to write a deduction system where $1^n$ is provable iff $n>1$ is not prime. $\endgroup$ – thehardyreader Oct 27 '18 at 20:36

Here how I would go about this:

  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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.