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.
- Let p = 3 and q = 5. $3 \in N$ is True, $5 \in N$ is True.
- Then n = pq = 3*5 = 15. It is True.
- n = pq is left part of the expression $(n=pq) \Rightarrow (p=1 \lor q=1)$ (1)
- $p \neq 1, q \neq 1$ then $(p=1 \lor q=1)$ (2) is False.
- So, for expression (1) we got $True \rightarrow False$, that is $False$.
- Thus (1) is not True for all q and p.
- Thus, formula (0) is False.
- 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. -
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.
-
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}.
Result.
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.
Best Answer
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”):
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.