What's given?

There is a statement "The n is prime", that we need to express with $\forall$ quantifier. I solved it one way and teacher (because one statement can be expressed not only by one formula) another.

Teacher's formula: $(\forall q \in \mathbb{N})(\forall p \in \mathbb{N})[(n=pq) \Rightarrow (p=1 \lor q=1)]$ (0)

What's the problem?

I think, teacher's solution is not right, because his formula (0) doesn't express the statement "The n is prime".

Explaining, why it is not right.

  1. Let p = 3 and q = 5. $3 \in N$ is True, $5 \in N$ is True.
  2. Then n = pq = 3*5 = 15. It is True.
  3. n = pq is left part of the expression $(n=pq) \Rightarrow (p=1 \lor q=1)$ (1)
  4. $p \neq 1, q \neq 1$ then $(p=1 \lor q=1)$ (2) is False.
  5. So, for expression (1) we got $True \rightarrow False$, that is $False$.
  6. Thus (1) is not True for all q and p.
  7. Thus, formula (0) is False.
  8. So, lets read formula (0), knowing that it is false: Not for all natural q and p true, that, if q*p gives us some n, then either q or p equals 1.
  9. Thus:

    • For some n its q and p are not equal one, then we know that n consist of two numbers, then it is composite.
    • For another n either q or p can be 1, then we don't know if n is prime or composite, cause another number (q or p) can be either composite or prime.
  10. Thus, (0) doesn't say us about nature of n (prime or composite).

My question is:

What do you think, is (0) express state The n is prime? If so, where in my reasoning i am wrong?

Is it a homework?

No, this is a part of an assignment from MOOC course. I already solved it my way, Professor already solved it. Problem is just that i can't accept that his solution is right.

New details of task. Answer to the PJTraill's answer.

First of all: thank you, i absolutely agree about your conclusion on "Your “gives us some n” makes me feel...". In this case (0) really would have no mistake and would seem for me unambiguous. BUT! For past 4 days i was looking the lectures again and again and found more details about task itself and how was constructed (0) in particular. I ll try to explain it below.

1) (0) was a result of negation of another task's formula that expressed statement "The natural number n is not prime".

2) That previous task was about expressing with existence quantifier, so as a result for "The natural number n is not prime" we had:

$(\exists p \in N)(\exists q \in N)$( p>1 $\land$ q>1 $\land$ n=pq) (3)

That, if i read it properly of course, is:

"There are such natural q and p, that both bigger than 1 and by multiplying giving us product n".

^About product n - it is how teacher was reading it.

3) Before start with problem, this topic is about ,teacher said, that "The n is prime" is a negation of previous " The n is not prime", so we can just negate (3) and get the proper formula for "The n is prime", which is (0).

4) So, i checked and (0) is really a negation of (3).

5) But, negation of existence quantifier is a universal quantifier, so "There are such q and p, that", so (0) became into "For all natural q and p it is not that..." .

6) So, where the first case was, according to its formula, "There is n that is not a prime", the second one, by negating, became "There isn't n that is prime". That is, according to n is a product for all natural q and p, is not true. Because we know, that there are natural primes.

7) But it is not the case. The case is whether (0) express statement "The n is prime" or not? Well, we can say yes, because if there isn't n, that is not prime, then all n is prime. Despite we know that it is not true, however.

8) Thus, false formula express false statement or true formula express true statement (if "non rationally" assume, that first statement was false) . We are good with both cases, because the task is not about truth.

But! The next will be about why i am not agree that (0) express its statement.

1) Though (3) is sufficient to say "The n is not a prime", it doesn't talk about primes, that have factors q and p, that are not both bigger then 1, but one equals 1 and second is composite, so n=qp = (composite*1) or (1*composite).

2) Thus, its negation is talking "There are no composite numbers, that have two factors q and p both bigger then one", but not talking about composite of "my kind" that are composite*1.

3) And, like i said earlier, in this case (0) will have opposite value than its statement. The statement "There are no composite" is false, whether (0) gives us true value with {q;p} {composite;1}.


I absolutely agree with you, that if there was a case ∃n∈ℕ, then no ambiguity, teacher's (0) express its statement. However, data, that i found and introduced to you above (how 0 was constructed) talks, that we should read formula, like we read all formulas: "For all q and p, if they give us the product n, then either q or p equals 1". In this case it doesn't express statement "The n is prime", because, again, according to data (0) is a negation of (3), that is "There is n that has two factors bigger than 1" . So (0) has a form of "There are no n, that has two factors bigger than 1", which is necessary, but not sufficient to say "The n is prime", because there are "not primes", that have only one factor bigger than one.

Of course, it can be, that i don't understand at all nature of free variables, but we haven't learn or even heard about them yet, so i don't think it is the case.

  • 1
    $\begingroup$ Simply put, (0) means: $n\in\mathbb{N}_+$ is prime if and only if whenever $n=pq$, where $p,q\in\mathbb{N}_+$, we have $p=1$ or $q=1$. I don't quite understand your reasoning; about which part are you in doubt? $\endgroup$ – Colescu Apr 21 '17 at 14:11
  • 1
    $\begingroup$ Your $n = 15$ is not prime. Therefore it does not pass the "test" given by your teacher. If your $n$ was prime, then indeed one of its factors is forced to be 1. $\endgroup$ – Kaynex Apr 21 '17 at 14:12
  • 1
    $\begingroup$ Cooking them together (and using equivalences) we have: $\forall x \ \forall y \ [(n=xy) \to (x=1 \lor x=n)]$. $\endgroup$ – Mauro ALLEGRANZA Apr 21 '17 at 14:30
  • 1
    $\begingroup$ You have written “complex” when you presumably meant “composite”! $\endgroup$ – PJTraill May 1 '17 at 22:37
  • 1
    $\begingroup$ (3) does not say “There is $n$ that has two factors bigger than $1$” but “The $n$ in question has two factors bigger than $1$”. Similarly (0) does not say “There is no $n$, …” but “The $n$ in question cannot be wriiten as a product of two factors both $>1$”. $\endgroup$ – PJTraill May 1 '17 at 23:37

Your teacher’s formula is correct except when $n=1$, which it says is prime (see the final section); for consistency with their terminology I shall use “prime” in this answer to mean “non-composite”. Your problem seems to be that you do not realise that $n$ is a “free variable” in formula (0), which we ought to call $P(n)$ to emphasise that it says something about $n$, some natural whose primality interests us.

A free variable (in a given formula) is one that is not a “bound variable”, where a bound variable is one introduced by a quantifier, in the way that $p$ and $q$ are. A free variable refers to something outside the formula, while a bound variable does not refer to anything outside the formula: replacing $q$ by $r$ would not affect the meaning of $P(n)$.

Where you write “Not for all natural $q$ and $p$ true, that, if $q*p$ gives us some $n$, then either $q$ or $p$ equals $1$.” it would be more accurate to say “…if $qp$ gives us the particular $n$ we are interested in, …”. That is to say, in your example we are only interested in the case $P(15)$, i.e. your (0) with $n$ replaced by $15$; as you correctly observed, $P(15)$ is false, so $15$ is not prime. If you try it out, you should find that $P(5)$ is true.

Your “gives us some $n$” makes me feel that you may be thinking of (0) as: $$ (\forall q \in \mathbb N)(\forall p \in \mathbb N)(\exists n \in \mathbb N)[(n=pq) \Rightarrow (p=1 \lor q=1)] $$ i.e. “every product of naturals is $1$ or prime” (or even “given two naturals, one is $1$”!), which is of course false. If you rearrange it as $$ (\exists n \in \mathbb N)(\forall q \in \mathbb N)(\forall p \in \mathbb N)[(n=pq) \Rightarrow (p=1 \lor q=1)] $$ it says “some natural is $1$ or prime”, which is trivially true. Both these formulæ have $n$ as a bound variable, i.e. they are not statements about a particular $n$ but about $\mathbb N$ as a whole.

In step (9) you write (with “complex” replaced by “composite”):

• For some $n$ its $q$ and $p$ are not equal one, then we know that $n$ consist of two numbers, then it is composite.
• For another $n$ either $q$ or $p$ can be $1$, then we don't know if n is prime or composite, cause another number ($q$ or $p$) can be either composite or prime.

The first part is more or less right, though “its $p$ and $q$” is a bit odd, as $p$ and $q$ are not determined by $n$, but are just some naturals that may need to be checked to see if $n$ is prime. The second part is wrong: you are right that the case when either $p$ or $q$ is $1$ does not (on its own) settle the primality of $n$, but if all such $p$ and $q$ satisfy $ (n=pq) \Rightarrow (p=1 \lor q=1) $ that makes $P(n)$ true – that is what the universal quantifiers in $P(n)$ mean!

The case $n=1$

As pointed out the answer in the answer by Dan Brumleve, your teacher’s expression breaks down when $n=1$, though this seems to have nothing to do with your problems in understanding it.

Their expression $P(1)$ says $$ (\forall q \in \mathbb N)(\forall p \in \mathbb N)[(1=pq) \Rightarrow (p=1 \lor q=1)] $$ which is true: when the product of two naturals is $1$, then one of them is $1$ – indeed both are! But the conventional definition of a prime is that it should not be a “unit”, i.e. should not have a multiplicative inverse in $\mathbb N$. We can fix this by defining “$n$ is prime” as $n\neq 1 \land P(n)$. This is useful, as the primes are then the smallest set of naturals that generate $\mathbb N$ by multiplication. For $\mathbb Z$ there is no unique set of generators, but the sets are unique up to multiplying each element by one of the units $\{1,-1\}$.

Equally, their expression for “$1$ is not prime” becomes $$ (\exists q \in \mathbb N)(\exists p \in \mathbb N)(p > 1 \land q > 1 \land 1=pq) $$ which is false, again meaning that $1$ is prime.

  • $\begingroup$ Thank you for your answer! My comment would be too long, so i wrote it as an updated info in topic itself. Please, check it, if it won't be a big deal for you. $\endgroup$ – Djon Smith Apr 27 '17 at 9:09
  • $\begingroup$ So, if n is unbound and both bound cases you have written about, are not our case, then... how do you read (0)? $\endgroup$ – Djon Smith May 3 '17 at 0:20
  • 1
    $\begingroup$ As “of any two naturals whose product is $n$, at least one must be $1$”, which is a statement about $n$, and not about any $p$ or $q$. $\endgroup$ – PJTraill May 4 '17 at 18:27
  • $\begingroup$ Wow, seems fine! However, teacher didn't read (0) exactly your way, but read it that way: i found transcript from video lecture, where he was explaining his solving. I ll put it below this commentary--> $\endgroup$ – Djon Smith May 5 '17 at 21:10
  • 1
    $\begingroup$ They were motivating and explaining, so what they said is longer, and the English is a bit odd, but at a glance I would say the intention is the same. $\endgroup$ – PJTraill May 6 '17 at 10:12

The teacher's formula

$(\forall q \in \mathbb{N})(\forall p \in \mathbb{N})[(n=pq) \Rightarrow (p=1 \lor q=1)]$

is not a correct definition of "$n$ is prime" because it claims $1$ is prime, that is, the formula

$(\forall q \in \mathbb{N})(\forall p \in \mathbb{N})[(1=pq) \Rightarrow (p=1 \lor q=1)]$

is true. There is a sense in which $1$ not being prime is just an arbitrary convention but as far as I know it is universally held, like $0$ not being called positive.

  • $\begingroup$ You are of course right; I was fixated on trying to see where the OP went wrong in his thinking, and so overlooked this obvious point. $\endgroup$ – PJTraill Apr 28 '17 at 19:33

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.