Logical representation of prime numbers

[lys04]

One of the discussion questions for my class this week was to express the condition "p is a prime number" using formal logic.
The answer my uni's got is (∀d∈N)[(d>=1∧p≠1)∧(d|p⇒((d=1)∨(d=p))]. My interpretation of this is all the natural number d that (satisfy d>=1 and prime number is not equal to 1) AND (if d is a divisor of p then d is either equal to 1 or d is equal to p).
Just to make sure, p represents the prime number here right?
If so, then doesn't (∀d∈N)[(d>=1∧p≠1)∧(d|p⇒(d=1)∨d=p)] just describe all the divisors of the prime number? How does this become a condition that p is a prime number?

 

[Hornbein]

One of the discussion questions for my class this week was to express the condition "p is a prime number" using formal logic.
The answer my uni's got is (∀d∈N)[(d>=1∧p≠1)∧(d|p⇒((d=1)∨(d=p))]. My interpretation of this is all the natural number d that (satisfy d>=1 and prime number is not equal to 1) AND (if d is a divisor of p then d is either equal to 1 or d is equal to p).
Just to make sure, p represents the prime number here right?
If so, then doesn't (∀d∈N)[(d>=1∧p≠1)∧(d|p⇒(d=1)∨d=p)] just describe all the divisors of the prime number? How does this become a condition that p is a prime number?

They didn't define p but it seems safe to assume that it is a natural number. It appears that d|p = true means that d is a divisor of p. They are saying that if "for all d, if d is a divisor of p then either d=1 or d=p" is a true statement then p is prime. If there were a divisor of p that was neither 1 nor p then that would be a false statement so p would not be prime.

 

[PeroK]

One of the discussion questions for my class this week was to express the condition "p is a prime number" using formal logic.
The answer my uni's got is (∀d∈N)[(d>=1∧p≠1)∧(d|p⇒((d=1)∨(d=p))]. My interpretation of this is all the natural number d that (satisfy d>=1 and prime number is not equal to 1) AND (if d is a divisor of p then d is either equal to 1 or d is equal to p).
Just to make sure, p represents the prime number here right?
If so, then doesn't (∀d∈N)[(d>=1∧p≠1)∧(d|p⇒(d=1)∨d=p)] just describe all the divisors of the prime number? How does this become a condition that p is a prime number?

I must confess I've never studied formal logic, but why include $d=1$ only to exclude it later? Why not:
$$(d \ge 2 \wedge p \ge 2) \wedge (d|p \Rightarrow (d = p))$$

 

[PeroK]

Or (you might have to translate this in to those symbols properly):
$$(p \ge 2) \wedge (\forall 2 \le d < p: \neg(d| p))$$Or:
$$(p \ge 2) \wedge (\forall 2 \le d \le \sqrt p: \neg(d | p))$$

 

[PeroK]

If so, then doesn't (∀d∈N)[(d>=1∧p≠1)∧(d|p⇒(d=1)∨d=p)] just describe all the divisors of the prime number? How does this become a condition that p is a prime number?

This is effectively a test for primeness. You don't know that the $p$ you put in is prime. $p$ is only prime if it passes that test. The test says:

The only natural numbers that divide $p$ are $1$ and $p$.

Then, you could also say:

The only natural number greater than 1 that divides $p$ is $p$

No natural numbers greater than 1 and less than $p$ divide $p$.

Or, no natural numbers greater than 1 and less than or equal to the square root of $p$ divide $p$.

 

[lys04]

They didn't define p but it seems safe to assume that it is a natural number. It appears that d|p = true means that d is a divisor of p. They are saying that if "for all d, if d is a divisor of p then either d=1 or d=p" is a true statement then p is prime. If there were a divisor of p that was neither 1 nor p then that would be a false statement so p would not be prime.

Oh so maybe if add say p(x) = “x is prime”, x is in the domain of natural numbers, then p(x) is equivalent to (double arrow symbol) to the statement (for all d if d is a divisor then either d is 1 or the prime number itself)?

 

[lys04]

This is effectively a test for primeness. You don't know that the $p$ you put in is prime. $p$ is only prime if it passes that test. The test says:

The only natural numbers that divide $p$ are $1$ and $p$.

Then, you could also say:

The only natural number greater than 1 that divides $p$ is $p$

No natural numbers greater than 1 and less than $p$ divide $p$.

Or, no natural numbers greater than 1 and less than or equal to the square root of $p$ divide $p$.

So could I interpret it like iteration?
For every p I test for primeness I go through all the d’s in the natural number and if it passes the test then it’s a prime number

 

[lys04]

I must confess I've never studied formal logic, but why include $d=1$ only to exclude it later? Why not:
$$(d \ge 2 \wedge p \ge 2) \wedge (d|p \Rightarrow (d = p))$$

Dw I’ve also just started, so not much better than you are at this.
Hmm not sure what you mean by exclude it later, where is that?

 

[PeroK]

Dw I’ve also just started, so not much better than you are at this.
Hmm not sure what you mean by exclude it later, where is that?

I meant that we started looking for divisors from $d = 1$. But, $d = 1$ is always a divisor, so it's a waste of time (*). It's the same with checking $d = p$.

(*) By waste of time, I mean that it makes the formal definition more complicated than it need be. This isn't important, other than to encourage you to think logically about why the definition is the way it is. This was just something I noticed.

You seem to have two problems: 1) understanding basic mathematical logic; 2) knowing how to interpret statements in formal logic. What I was doing was playing around with all the options that were logically available.

You should be able to play about with all the different ways of defining a prime number. Hopefully, that should make sense.

 

[Hill]

The answer my uni's got is (∀d∈N)[(d>=1∧p≠1)∧(d|p⇒((d=1)∨(d=p))]. My interpretation of this is all the natural number d that (satisfy d>=1 and prime number is not equal to 1) AND (if d is a divisor of p then d is either equal to 1 or d is equal to p).

This expression in words says,
p is a prime number iff it is not 1 and for every natural number d>=1 if d is a divisor of p then either d=1 or d=p.

 

[Hornbein]

Oh so maybe if add say p(x) = “x is prime”, x is in the domain of natural numbers, then p(x) is equivalent to (double arrow symbol) to the statement (for all d if d is a divisor then either d is 1 or the prime number itself)?

Yes but in this formal language "x is prime" has no meaning.

 

[lys04]

I meant that we started looking for divisors from $d = 1$. But, $d = 1$ is always a divisor, so it's a waste of time (*). It's the same with checking $d = p$.

(*) By waste of time, I mean that it makes the formal definition more complicated than it need be. This isn't important, other than to encourage you to think logically about why the definition is the way it is. This was just something I noticed.

You seem to have two problems: 1) understanding basic mathematical logic; 2) knowing how to interpret statements in formal logic. What I was doing was playing around with all the options that were logically available.

You should be able to play about with all the different ways of defining a prime number. Hopefully, that should make sense.

Thats true, I think I kind of get it now,
The statement (∀d∈N)[(d>=1∧p≠1)∧(d|p⇒((d=1)∨(d=p))] can be simplified then, into (p≠1)∧(∀d∈N)(d|p⇒((d=1)∨(d=p)) right?
And if both is true then p is prime, and if one is false then p is not prime.

 

[lys04]

Thats true, I think I kind of get it now,
The statement (∀d∈N)[(d>=1∧p≠1)∧(d|p⇒((d=1)∨(d=p))] can be simplified then, into (p≠1)∧(∀d∈N)(d|p⇒((d=1)∨(d=p)) right?
And if both is true then p is prime, and if one is false then p is not prime.

actually to be precise the first part is a condition on p and the second is a condition of both p and d?

 

[PeroK]

Thats true, I think I kind of get it now,
The statement (∀d∈N)[(d>=1∧p≠1)∧(d|p⇒((d=1)∨(d=p))] can be simplified then, into (p≠1)∧(∀d∈N)(d|p⇒((d=1)∨(d=p)) right?
And if both is true then p is prime, and if one is false then p is not prime.

The second one looks good to me, but as I said, I don't fully understand the syntax of these formal statements. Note that the whole thing is a statement that says "$p$ is prime".

 

[Hornbein]

So could I interpret it like iteration?
For every p I test for primeness I go through all the d’s in the natural number and if it passes the test then it’s a prime number

This formal language is non-procedural. Statements are either true or false. (Then there's undecidability, but you don't need to know about that.)

 

[Evgeny.Makarov]

Here is a couple of formulas saying that a natural number $p$ is prime.
$$\begin{align*}&p>1\land \forall d\,(d\mid p\to d=1\lor d=p)\\ &p>1\land \forall d\,(1<d\land d<p\to \neg(d\mid p))\end{align*}$$The original variant (∀d∈N)[(d>=1∧p≠1)∧(d|p⇒((d=1)∨(d=p))] is incorrect because it says in particular that every number $d$ is $\ge 1$.

 

[SSequence]

Suppose we want to express the predicate $Prime:\mathbb{N} \rightarrow \{0,1\}$. We are assuming the set $\mathbb {N}$ to be:
$\mathbb{N}=\{0,1,2,3,4,.....\}$

Assuming that the domain of quantification is understood to be $\mathbb{N}$, here is one way of expressing the formula $Prime(x)$:
$(x \neq 0,1) \land \neg \, \exists k \in \mathbb{N} \, [(1<k<x) \land \exists n \in \mathbb{N} \, ( k \cdot n=x) ]$
We can just write:
$(x \neq 0,1) \land \neg \, \exists k \, [(1<k<x) \land \exists n \, ( k \cdot n=x) ]$

The idea here is that the formula:
$\exists k \, [(1<k<x) \land \exists n \, ( k \cdot n=x) ]$
should only be satisfied by the following set of numbers $x$:
$\{4,6,8,9,10,...\}$
In other words, the composite numbers. So when we take the negation and exclude the numbers $0,1$ we should get the set of prime numbers.

 

[Sargon38]

I think one of the difficulties the TS has, is to understand the concept of "predicate".
A predicate is grossly a logical proposition with free variables in it, as opposed to a closed logical proposition.

A logical proposition is a statement that is true, or that is false.
5 = 6 is a logical proposition that is false. 2 = 1 + 1 is a logical proposition that is true.

These logical propositions are not depending on any "variable".

Next, we have logical propositions containing bound variables. In these propositions, there appear letters that are "variables", which are introduced with a quantifier (for all, or "there exist"). As a whole, the proposition is still true, or false.
For instance:
$$ \forall x \in \mathbb{R}: x > 2 \implies x > 1$$
is a true statement. The x is a bound variable, and the statement is something that says that every real number that is larger than 2, is also larger than 1.

$$ \forall x \in \mathbb{R}: x > 2 \implies x > 3$$
is a false statement. It claims that any real number that is larger than 2, is also larger than 3. That's a false statement.

However, if we "free up" x, by removing the quantifier clause, we have a predicate, with a free variable x:

T(x) is the predicate: $$x > 2 \implies x > 3 $$

Now, that is not a logical proposition anymore. It is not a false statement, nor is it a true statement. Its truth value depends on the choice of x.
T(1) is a true statement.
T(2.5) is a false statement.
T(4) is a true statement.

So you can say that the predicate T is something that tells us something about x.

Well, in the same way, the logical expression that was written by the OP, was a predicate P(p).

The predicate tells us something about p, in this case, whether p is a prime number or not.

P(8) is false. Which means: 8 is not a prime number.
P(7) is true. Which means: 7 is a prime number.

 

[SSequence]

I was thinking about expressing the formula $Prime:\mathbb{N} \rightarrow \{0,1\}$ using $\forall$ instead of $\exists$ (although post#16 already does it). Continuing from post#17, I will again assume quantification over $\mathbb{N}$ in this post.

One way just seems to be using the following formula for $Prime(x)$ in post#17:
$(x \neq 0,1) \land \neg \, \exists k \, [(1<k<x) \land \exists n \, ( k \cdot n=x) ]$
Re-naming bound variables to $i$ and $j$ we get:
$(x \neq 0,1) \land \neg \, \exists i \, [(1<i<x) \land \exists j \, ( i \cdot j=x) ]$

Now it seems that we can re-write the same formula in an equivalent way as:
$(x \neq 0,1) \land \neg \, \exists i \, \exists j \, [(1<i<x) \land \, ( i \cdot j=x) ]$
Taking the negation inside the quantifiers we get:
$(x \neq 0,1) \land \, \forall i \, \forall j \, [\neg(1<i<x) \lor \, ( i \cdot j \neq x) ]$

======

Another alternative formula for $Prime(x)$ seems to be:
$(x \neq 0,1) \land \, \forall i \, \forall j \, [ (i<x \land j<x) \rightarrow (i \cdot j \neq x) ]$

 

[Agent Smith]

1. $s(x) = \text{aliquot sum of x} \wedge Px = \text{x is prime}$
2. $\forall x(Px \iff s(x) = 1)$