Logical representation of prime numbers

lys04 said:

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?

lys04 said:

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?

lys04 said:

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 said:

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 said:

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

PeroK said:

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

lys04 said:

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?

lys04 said:

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

lys04 said:

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)?

PeroK said:

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.

lys04 said:

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 said:

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 said:

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