Mathematics desk
< September 20	<< Aug \| September \| Oct >>	September 22 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

September 21

Set-builder notation and primes

Would

P=\{1<p\in \mathbf {N} :\forall q\in \mathbf {N} \neq (p,1),[p/q]\notin \mathbf {N} \}

be legitimate notation for the set of primes? I'm wondering what the boundaries for set-builder notation are, especially with regard to the pre-colon component. Thanks. —Anonymous Dissident^Talk 13:27, 21 September 2009 (UTC)[reply]

The pre-colon part is fine, but the post-colon part has trouble. You could write,

P=\{1<p\in \mathbf {N} :\forall q\in \mathbf {N} \setminus \{1,p\}(p/q\notin \mathbf {N} )\}

but it would be more clear if you just rewrote the whole thing, for example,

\{p\in \mathbf {N} :\forall q\in \mathbf {N} (q{\mathbin {|}}p\to (q=1{\text{ or }}q=p))\}

.

— Carl (CBM · talk) 15:18, 21 September 2009 (UTC)[reply]

You only need to check for divisibility by numbers up to $[{\sqrt {p}}]$ , so why not try something along the lines of

P=\{p\in \mathbb {N} :\ \forall \ n\in \mathbb {N} ,\ 2\leq n\leq [{\sqrt {p}}],\ [p/n]\notin \mathbb {N} \}?

~~ Dr Dec (Talk) ~~ 15:37, 21 September 2009 (UTC)[reply]

The two commas make that hard to read; it would be easier if the second one was an arrow (→) of if you use the words if/then. — Carl (CBM · talk) 15:40, 21 September 2009 (UTC)[reply]

How should I read an arrow in set notation? ~~ Dr Dec (Talk) ~~ 15:49, 21 September 2009 (UTC)[reply]

As "implies", as in

P=\{p\in \mathbb {N} :\ \forall \ n\in \mathbb {N} (2\leq n\leq {\sqrt {p}}\to p/n\notin \mathbb {N} )\}

— Carl (CBM · talk) 15:52, 21 September 2009 (UTC)[reply]

Your first definition includes 1, and your second definition includes both 0 and 1. This does not agree with the generally accepted definition of primes. — Emil J. 16:43, 21 September 2009 (UTC)[reply]

So try

P=\{2\leq p\in \mathbb {N} :\ \forall \ n\in \mathbb {N} (2\leq n\leq {\sqrt {p}}\to p/n\notin \mathbb {N} )\}

~~ Dr Dec (Talk) ~~ 16:52, 21 September 2009 (UTC)[reply]

You're right; my first one did include 1, and both of our second ones included 0 and 1. That's a pretty common error when trying to write a formula that defines the primes. But at least the idea is clear. — Carl (CBM · talk) 17:47, 21 September 2009 (UTC)[reply]

Personally, I would go with:

\{p\in \mathbb {N} |p\,\mathrm {prime} \}

. Why go with a complicated solution when there is a simple one? --Tango (talk) 17:01, 21 September 2009 (UTC)[reply]

but yours contains an English word ;) --84.221.69.1 (talk) 17:08, 21 September 2009 (UTC)[reply]

English words are fine in set-builder notation, as we are discussing it here. In the context of formal set theory, we might restrict things to formulas in a particular formal language, but that's a different setting. — Carl (CBM · talk) 17:47, 21 September 2009 (UTC)[reply]

It is a common mistake among novice mathematicians to try and avoid using English. If the easiest way to express something is to write a paragraph of prose, then write a paragraph of prose. Using a single English word isn't a problem at all. --Tango (talk) 17:52, 21 September 2009 (UTC)[reply]

btw, it was an ironic comment --84.220.118.29 (talk) 07:51, 22 September 2009 (UTC) [reply]

I think the original spirit of Anonymous Dissident's post was more to do with whether the set is actually the same as the set of (positive) prime numbers. In other words, are the assumptions and conditions a reformulation of the definition of a prime number? ~~ Dr Dec (Talk) ~~ 18:06, 21 September 2009 (UTC)[reply]

The OP talks about the boundaries of set builder notation, so I think primes are just an example. I think the real answer is that any notation is acceptable as long as it is clear what it means (and it means what you want it to mean, of course). --Tango (talk) 18:23, 21 September 2009 (UTC)[reply]

Actually, thinking about it, isn't the usual set notation of the form

\{{\mbox{a general member of some collection of objects}}:{\mbox{some conditions imposed on that set}}\}?\,

In that case, the condition 1 < p should go after the colon. ~~ Dr Dec (Talk) ~~ 19:03, 21 September 2009 (UTC)[reply]

Given all of the above comments, how does

P=\{p\in \mathbf {N} \setminus \{1\}:\forall q\in \mathbf {N} \setminus \{1,p\},[p/q]\notin \mathbf {N} \}

work? To Tango: those below you are correct – I realise that it would be much simpler just to use your form, but I wanted to know if my denotation was feasible. Thanks to all of you for your feedback. —Anonymous Dissident^Talk 05:59, 22 September 2009 (UTC)[reply]

Almost there. I have two concerns. One, the notation

[p/q]

is sometimes used to mean the floor function -- especially right after dividing two integers (if you're a computer scientist, anyhow) -- so its use is liable for confusion. The simple solution is to just drop the brackets, like Carl did. The second concern is a bit more nebulous: some mathematicians use "natural numbers" to mean "nonnegative integers" rather than "positive integers", and taking the former interpretation causes confusion when you consider the case q = 0; if q = 0 then is

p/q

an integer or not? Ideally, whatever definition you write will work equally well for either definition of "natural numbers". The direct solution is to explicitly specify that q is positive before doing the division. Eric. 71.139.177.245 (talk) 06:45, 22 September 2009 (UTC)[reply]

Point one: I suppose we could use parentheses instead. It's not a big issue how ever you turn it. Point two: I believe the definition of

0\in \mathbb {N}

is most used by computer scientists, whereas number theorists use

0\notin \mathbb {N}

. Either definition is acceptable, but I think the latter would be assumed in set theory. Do correct me if I'm mistaken. —Anonymous Dissident^Talk 10:57, 22 September 2009 (UTC)[reply]

It's not safe to assume a particular definition for natural numbers. The standard constructions of natural numbers in set theory include 0; I was raised by number theorists to exclude 0; and others will all have their own particular preference. I usually write

\mathbb {Z}

and explicitly specify "positive" or "nonnegative" as desired, but that can feel cumbersome if you're using lots of symbols like you are here. Eric. 67.169.125.37 (talk) 04:00, 24 September 2009 (UTC)[reply]

The problem with Tango's solution is not that it contains an English word, it is that it is circular. Taemyr (talk) 06:48, 22 September 2009 (UTC)[reply]

Not necessarily. It defines the set of primes from the definition of an individual prime. So it's more like kicking the can down the road. Rckrone (talk) 07:31, 22 September 2009 (UTC)[reply]

If you want an actual formalized expression, you have to precisely specify the syntax you're looking for. Otherwise you may as well be a bit less formal. It's also a bit weird that you're using integer division. Normally I'd describe a prime as a natural number p so that there are no naturals a,b so that a*b=p and a>1 and b>1. 70.90.174.101 (talk) 07:17, 22 September 2009 (UTC)[reply]

But that's equivalent to AD's division condition. ~~ Dr Dec (Talk) ~~ 11:29, 22 September 2009 (UTC)[reply]

I didn't mention this earlier, because it seemed off topic. The issue with division is that it is not in the signature of the set of natural numbers (in, say, Peano arithmetic). So, to the extent that we want the thing inside the set builder notation to resemble a formula from formal logic, we want to avoid using the division symbol. Put another way: there is a type difference between natural numbers and the image of the natural numbers inside the reals. — Carl (CBM · talk) 12:28, 22 September 2009 (UTC)[reply]

Do you mean to say that defining the set in terms of division is strictly less valid than in terms of multiplication because one may divide some two numbers in N to produce a result not in N, but may not multiply any two numbers in N to produce a result not in N? —Anonymous Dissident^Talk 12:37, 22 September 2009 (UTC)[reply]

Yes, I think that is what CBM means. To put it more succinctly, when working in N p/q is only defined if p is a multiple of q. A definition of the set of primes that avoids using division might be:

P=\{p\in \mathbf {N} \setminus \{1\}:\nexists q,r\in \mathbf {N} \setminus \{1\}:qr=p\}

Gandalf61 (talk) 12:56, 22 September 2009 (UTC)[reply]

Basically, yes. I am saying that there is no division symbol "/" in the language of rings, and so if we want to define the prime numbers with a formula (with quantifiers) in the language of rings, we will need to avoid the division symbol. One can obviously use the division symbol in general, it just results in a definition that is not in the language of rings. One reason you might care to show primality is definable in the language of rings is to know that primality is preserved under ring isomorphisms. — Carl (CBM · talk) 13:56, 22 September 2009 (UTC)[reply]

You could just replace division with divisibility. Then it's pretty much equivalent since q|p implies there's r with qr = p. Rckrone (talk) 17:35, 22 September 2009 (UTC)[reply]

Yes, you're right. This is exactly the reason why "divisible" is defined in terms of multiplication, rather than division. — Carl (CBM · talk) 19:11, 22 September 2009 (UTC)[reply]

An unexpectedly elaborate full formalisation of the primes

(ec) It really depends on how much of arithmetic you want to assume. You basically work your way down from the top concepts until you are satisfied or you have reached the fundamental logical notions and the things defined in your axioms, defining each new predicate or notation as you go. So it works like this, assuming that 0 is the smallest natural (and not 1):

The "set of primes" P is the set of p in N such that p is prime : $\textstyle P=\{p\in \mathbb {N} :{\mbox{Prime}}(p)\}$
p is prime iff it is greater than one and every number n that divides p (notated here as n | p) is either p or 1 : $\textstyle {\mbox{Prime}}(p)\Leftrightarrow (p>1\land (\forall n)(n|p\Rightarrow (n=1\vee n=p))$
a is greater than b iff there exists a nonzero number c that can be added to b to produce a : $\textstyle a>b\Leftrightarrow (\exists c)(c\neq 0\land a=b+c)$
One is the successor of zero : $\textstyle 1=S0$
a divides b iff there exists some number c that can be multiplied by b to produce a : $\textstyle a|b\Leftrightarrow (\exists c)(a=b\times c)$
a times b is defined recursively: a times zero is zero, and a times the successor of b is a plus (a times b) : $\textstyle (a\times 0=0)\land (a\times Sb=(a\times b)+a)$
a plus b is also defined recursively: a plus zero is a, and a plus the successor of b is the successor of (a plus b) : $\textstyle (a+0=a)\land (a+Sb=S(a+b)$

Putting it all together (but allowing the multiplication and addition to be defined separately, since unlike a predicate, functions are quite tricky to replace in formulas), we produce a complete, self-contained definition of the set of primes:

P=\left\{p\in \mathbb {N} :(\exists a){\Big (}a\neq 0\land p=a+S0{\Big )}\land (\forall a){\Big (}(\exists b)\left(p=a\times b\right)\Rightarrow \left(a=S0\vee a=p\right){\Big )}\right\}

which we can parse, somewhat awkwardly, as follows: P is the set of numbers satisfying both these conditions:

There exists some number a such that a does not equal zero and p equals a plus the successor of zero, and
For any number a, if some number b exists such that p equals a times b, then either a equals the successor of zero or a equals p

This is a fairly 'general' approach, that we could actually tighten up a little with some clever ideas (e.g. instead of defining > for the sake of p > 1, just say $\textstyle (\exists q)(p=SSq)$ ), but it demonstrates how to formalise things into Peano arithmetic and formal logic. Note that our final definition (apart from multiplication and addition, which we can define as above) uses no concepts that are not explicitly defined in the axioms. Note that, in theory, we actually build these ideas from the ground up (rather than, as we did, starting from the result and working backwards), but prime numbers were discovered well before arithmetic was formalised so we already know the interesting destinations we want our formalised mathematics system to work towards. In theory, there is no difference between "in practice" and "in theory", but in practice there is :) Maelin (Talk | Contribs) 13:31, 22 September 2009 (UTC)[reply]

Yes but in theory, there should be no difference between practice and theory even in practice; on the other hand in practice no theory is currently able to justify a complete equivalence of practice and theory. --84.220.118.29 (talk) 22:09, 22 September 2009 (UTC) [reply]