Counter definition of prime number?

  • (2 Pages)
  • +
  • 1
  • 2

22 Replies - 1902 Views - Last Post: 24 June 2013 - 01:12 PM

#1 deprosun  Icon User is offline

  • D.I.C Regular

Reputation: 0
  • View blog
  • Posts: 289
  • Joined: 16-November 10

Counter definition of prime number?

Posted 24 June 2013 - 09:49 AM

This is actual definition of Prime number according to my book:
P(x) ↔ ((x>1) Λ (∀y: D(y,x) → (y=1 ∨ y=x)))

This is my interpretation, is it correct?
P(x) ↔ ((x>1) Λ (∃y: D(y,x) → ((y=1) ∧ (y=x))))
Is This A Good Question/Topic? 0
  • +

Replies To: Counter definition of prime number?

#2 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7294
  • View blog
  • Posts: 12,138
  • Joined: 19-March 11

Re: Counter definition of prime number?

Posted 24 June 2013 - 09:53 AM

This looks like a correct application of de Morgan's law. However, I think there may be a flaw in the implication side.

Let me put it in English and you can see what you think:

X is prime iff x is positive and (if there exists no y which divides x evenly then y is not 1 and y is not x)

This post has been edited by jon.kiparsky: 24 June 2013 - 09:57 AM

Was This Post Helpful? 1
  • +
  • -

#3 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10186
  • View blog
  • Posts: 37,613
  • Joined: 27-December 08

Re: Counter definition of prime number?

Posted 24 June 2013 - 09:54 AM

No. The contrapositive would be valid. So if y != 1 and y != x, then y does not divide x.

You are only inverting the necessary condition, not the sufficient condition, which is only half of the inverse and still incorrect.

Edit- Can you write out your definition in plain English? The mathematical representation of your definition is bulky and hard to work with. I'd be interested in hearing your thoughts more plainly.

Quote

This is my interpretation, is it correct?
P(x) ↔ ((x>1) Λ (¬∃y: D(y,x) → (¬(y=1) ∧ ¬(y=x))))


Edit again- I would agree with how Jon read this. I'm just not a fan of it because you're mixing up the necessary and sufficient conditions.

Quote

X is prime iff x is positive and (if there exists no y which divides x evenly then y is not 1 and y is not x)

Was This Post Helpful? 0
  • +
  • -

#4 deprosun  Icon User is offline

  • D.I.C Regular

Reputation: 0
  • View blog
  • Posts: 289
  • Joined: 16-November 10

Re: Counter definition of prime number?

Posted 24 June 2013 - 10:21 AM

So..
P(x) ↔ ((x>1) Λ (¬∃y: D(y,x) → (¬(y=1) ∧ ¬(y=x))))

According to me it says, x is a prime number iff x is greater than 1 and there does NOT exists a number such that if it divides x then the number does not equal x and 1.

This post has been edited by deprosun: 24 June 2013 - 10:26 AM

Was This Post Helpful? 0
  • +
  • -

#5 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10186
  • View blog
  • Posts: 37,613
  • Joined: 27-December 08

Re: Counter definition of prime number?

Posted 24 June 2013 - 10:51 AM

Your sufficient condition will never be true though.

Quote

If there does not exist a y that divides x


Clearly, let y = 1 or y = x. Thus, your implication does not hold.

Again, order of implication matters. If p -> q is a valid implication, then ~q -> ~p is a valid implication as well.

When negating a logical statement, if you have a universal quantifier "for all x, p(x)", the negation is "there exists an x such that ~p(x)." Similarly, an existential quantifier is negated by a universal quantifier. So "if there exists an x such that p(x)," the negation is "for all x, ~p(x)."
Was This Post Helpful? 1
  • +
  • -

#6 deprosun  Icon User is offline

  • D.I.C Regular

Reputation: 0
  • View blog
  • Posts: 289
  • Joined: 16-November 10

Re: Counter definition of prime number?

Posted 24 June 2013 - 11:34 AM

I think i am thinking too much
Was This Post Helpful? 0
  • +
  • -

#7 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10186
  • View blog
  • Posts: 37,613
  • Joined: 27-December 08

Re: Counter definition of prime number?

Posted 24 June 2013 - 11:38 AM

Just another note as well. Make sure you specify your domain of discourse in your definitions. I'm assuming you're talking about the integers. You get some interesting results when you look at complex numbers and primality. In fact, analytic number theory is a pretty well-defined field. :)
Was This Post Helpful? 1
  • +
  • -

#8 deprosun  Icon User is offline

  • D.I.C Regular

Reputation: 0
  • View blog
  • Posts: 289
  • Joined: 16-November 10

Re: Counter definition of prime number?

Posted 24 June 2013 - 11:39 AM

I am working with naturals here as of now
Was This Post Helpful? 0
  • +
  • -

#9 deprosun  Icon User is offline

  • D.I.C Regular

Reputation: 0
  • View blog
  • Posts: 289
  • Joined: 16-November 10

Re: Counter definition of prime number?

Posted 24 June 2013 - 12:35 PM

I have one more,
The statement says: A prime number like 7 is relatively prime to any natural number except one of its own multiple.
On a side note: Relatively Prime is when GCD(x,y)=1.

I wanted to translate the bolded statement into predicates as following:
P(x) defines that x is prime
GCD(P(x),y) == 1 → (∀y: D(x,y))

Correct?
Was This Post Helpful? 0
  • +
  • -

#10 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10186
  • View blog
  • Posts: 37,613
  • Joined: 27-December 08

Re: Counter definition of prime number?

Posted 24 June 2013 - 12:41 PM

It's not a universal statement though. And the quantifier should be on the sufficient condition, not the necessary condition. When talking about coprimality, you are talking about two distinct integers (both existential). The only number that is relatively prime to all the naturals is 1.
Was This Post Helpful? 1
  • +
  • -

#11 deprosun  Icon User is offline

  • D.I.C Regular

Reputation: 0
  • View blog
  • Posts: 289
  • Joined: 16-November 10

Re: Counter definition of prime number?

Posted 24 June 2013 - 12:43 PM

oohh!! umm getting there..
So you're saying my statement is incorrect? How many points will i get out of 10? :P/>
Was This Post Helpful? 0
  • +
  • -

#12 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10186
  • View blog
  • Posts: 37,613
  • Joined: 27-December 08

Re: Counter definition of prime number?

Posted 24 June 2013 - 12:47 PM

Probably not a lot. You seem to be able to articulate the definitions, but you need work on the flow of logic, as well as necessary vs. sufficient conditions. :)
Was This Post Helpful? 0
  • +
  • -

#13 deprosun  Icon User is offline

  • D.I.C Regular

Reputation: 0
  • View blog
  • Posts: 289
  • Joined: 16-November 10

Re: Counter definition of prime number?

Posted 24 June 2013 - 12:48 PM

I think that what I need to learn here then before i go further. Any online documents you suggest?
Was This Post Helpful? 0
  • +
  • -

#14 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10186
  • View blog
  • Posts: 37,613
  • Joined: 27-December 08

Re: Counter definition of prime number?

Posted 24 June 2013 - 12:50 PM

What class are you in? What textbooks are you using? Those can be good resources sometimes.

Jimmy Arnold's book is used for the proofs class at my school. Martin Day has a textbook as well, though I prefer Arnold's. Both are free.

http://www.math.vt.e...k/3034Chap1.pdf
Was This Post Helpful? 0
  • +
  • -

#15 deprosun  Icon User is offline

  • D.I.C Regular

Reputation: 0
  • View blog
  • Posts: 289
  • Joined: 16-November 10

Re: Counter definition of prime number?

Posted 24 June 2013 - 12:54 PM

That look clean! I had Kenneth H. Rosen last semester. Now I am using my current professor's own published book
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2