We have a proof system: $(S,P,\tau,\phi)$ with $S = P = \mathbb N$. Let $\tau: S \to \{0,1\}$ be a truth function with $\tau(n) = 1$ exactly when $n$ has at least four prime factors.(not necessarily distinct). Now I want to find a verification function $\phi:S \times P \to \{0,1\}$, s.t our proof system becomes sound and complete. I need your help and advice to complete this.

First some definitions:

$S$ is the set of all statements. Every statement $s \in S$ is either true or false.

The truth function $\tau: S \to \{0,1\}$ assigns to each statement $s$ whether it's true or not.

$P$ is the set of all proofs. A proof for a statement is relative to a verification function $\phi$, where $\phi(s,p) = 1$ means that $p$ is a valid proof for the statement $s$ in the proof system $(S,P,\tau,\phi)$.

A proof system is sound if no false statement has a proof and complete if all true statements have a proof.

Here is my first try:

We assume that we can efficiently test whether or not a number is prime. A statement $s$ is true when $ s = p_{0}^{a}p_{1}^{b}...p_{n}^{m}$ for $p_{0}$ to $p_{n}$ prime numbers and $a+b+...+m \geq 4$.

We want to find a verification function that is complete and sound, meaning that all true statements have a proof and no false statement has a proof.

Here is where I struggle. Isn't checking whether a statement has at least four prime factors already the verification function we need? I really need some help understanding this since I'm stuck.

in general how do I approach such problems?

Thanks in advance

  • 1
    $\begingroup$ Can you explain what the components of $(S,P,\tau,\phi)$ are? Textbook authors make up such tuple notations for their formalizations out of whole cloth; you cannot expect people here to already be familiar with the particular components and sequence of them your textbook happen to use. $\endgroup$ – hmakholm left over Monica Aug 12 '17 at 10:39
  • $\begingroup$ my bad, I didn't realize that it wasn't clear from the question. I edited it in. Thanks $\endgroup$ – DariusTheGreat Aug 12 '17 at 10:56

As you present it you're right: You can just set $$ \phi(s,p) = \begin{cases} 1 & \text{if $s=p$ and $s$ has at least four prime factors} \\ 0 & \text{otherwise} \end{cases} $$ and that will obviously be sound and complete.

If that is not a sufficient answer, it must be because there are additional conditions of $\phi$ that you have not reproduced in your question. What they might be is anyone's guess, though.

It is common to require that $\phi$ is computable, but that is obviously the case here -- we can easily check whether $s$ equals $p$, and we can also compute the prime factorization of $s$ and sum the exponents.

One also sometimes sees the stronger requirement that $\phi$ is primitive recursive, but that too is the case here (it takes a slight bit of ingenuity to show this, but not much).

Other than that we get into guesswork territory. One hypothesis could be that the textbook you get the exercise from might want to be able to verify proofs in polynomial time, in which case the above function won't do unless $s$ is given in unary notation. Then it would make some sense as an exercise, because $p$ would need to encode data about the factorization that cannt quickly be extracted from $s$ itself. (One option would be to let $p$ be an encoding of four factors $>2$ that multiply together to yields $s$).

Alternatively there may be a hidden requirement that $\phi$ be specified in a particular formalism or notation.

  • $\begingroup$ Thanks for the elaborate answer. As far as I can see, it is not said that we need to verify in polynomial time or anything else. The exercise is more about intuitive understanding of a proof system. Again thank you since before this I wasn't able to find any solutions to this exercise. $\endgroup$ – DariusTheGreat Aug 12 '17 at 11:38

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.