Results 1 to 8 of 8
Like Tree1Thanks
  • 1 Post By emakarov

Math Help - smallest element

  1. #1
    Newbie
    Joined
    Sep 2012
    From
    Moonn
    Posts
    23

    smallest element

    Let u,v ∈ \ {0} define A as A={a∈ N\{0} : u|a and v|a}

    I want to prove two things
    1) I want to show that A has a smallest element and call this b
    2) Show that for every a∈ A follows b|a

    1) I know that a fundamental follow of the axiom of induction is that every not empty subset of N contains a smallest element.
    I need to show that A is a not empty subset. ( I don't know how to do this because I have no questions or explanation in my math book )
    Last edited by Burcin; September 30th 2012 at 07:45 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Sep 2012
    From
    Moonn
    Posts
    23

    Re: smallest element

    1) I need to show that A is a not empty set
    there exist an a so that a=|u*v| so A is not empty so A has a smallest element b

    Did I tell it correct ?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785

    Re: smallest element

    Quote Originally Posted by Burcin View Post
    1) I need to show that A is a not empty set
    there exist an a so that a=|u*v| so A is not empty so A has a smallest element b

    Did I tell it correct ?
    Yes. To be more precise, the claim is not that |u * v| exists, but that it is in A. And to be very detailed, you could explain why |u * v| is in A, i.e., why it does not equal 0 and is divisible by u and v.

    To prove 2), consider the remainder r when some arbitrary a is divided by b. Note that 0 <= r < b by the definition of remainder (at least when a >= 0). Show that r is divisible by u and v.
    Thanks from Burcin
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Sep 2012
    From
    Moonn
    Posts
    23

    Re: smallest element

    1) I need to prove that A is not empty
    prove: a=|v*u| and u ≠ 0 and v ≠ 0 so for very a∈ A there is a number dividable for u and v, so the set A isn't empty and has a smallest element

    2) a=q*b +r so r=a-(q*b) r∈A because q*b∈A and a∈A
    this isn't right because r<b and b is not the smallest element

    So we have a contradiction because we said in 1) that b was the smallest element
    Last edited by Burcin; September 30th 2012 at 09:21 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785

    Re: smallest element

    Quote Originally Posted by Burcin View Post
    1) I need to prove that A is not empty
    prove: a=|v*u| and u ≠ 0 and v ≠ 0 so for very a∈ A there is a number dividable for u and v, so the set A isn't empty and has a smallest element
    No. To prove that a set {y ∈ Y : P(y)} is not empty you need to exhibit an element x of the set. Further, to prove that x ∈ {y ∈ Y : P(y)}, you need to show that x ∈ Y and P(x). You constructed a potential element a = |v * u|, but you have not shown that a ∈ {a ∈ N \ {0} : u | a and v | a} because you have not shown, or even claimed, that a ∈ N \ {0} or that u | a and v | a. In showing this, you need to talk about this concrete a = |v * u| and not about every a ∈ A.

    Quote Originally Posted by Burcin View Post
    2) a=q*b +r so r=a-(q*b) r∈A because q*b∈A and a∈A
    this isn't right because r<b and b is not the smallest element
    This is the right direction, but your reasoning omits more details than is appropriate for a claim of this complexity. You need to explain why q * b ∈ A and why the difference of two elements of A is again in A.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Sep 2012
    From
    Moonn
    Posts
    23

    Re: smallest element

    2) a=q*b+r 0<=r<|b| if r=0 then q=a/b you can also right b|a

    Prove; if a is not divisible by b then
    r=a-(q*b)
    r∈A because a∈A and q*b∈A so r<b Contradiction!
    We stated that b was the smallest element of the set A not r So r=0 so q=a/b
    So for every a∈ A is divisible by b
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Sep 2012
    From
    Moonn
    Posts
    23

    Re: smallest element

    Oke I am going to have a look at it
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,925
    Thanks
    1764
    Awards
    1

    Re: smallest element

    Quote Originally Posted by Burcin View Post
    Let u,v ∈ \ {0} define A as A={a∈ N\{0} : u|a and v|a}
    I want to prove two things
    1) I want to show that A has a smallest element and call this b
    2) Show that for every a∈ A follows b|a
    Here are some different considerations.
    Let c=\text{LCM}(|u|,|v|). Is c\in A~?

    If a\in A~\&~a<c is there a contradiction there?

    If a\in A~\&~c\not| a then a=kc+r where 0<r<c.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Smallest Element proof
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: January 16th 2012, 02:06 AM
  2. Orbits of an element and the Stabilizer of the element
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: December 24th 2011, 06:41 AM
  3. Replies: 13
    Last Post: May 12th 2011, 05:32 AM
  4. Replies: 3
    Last Post: March 23rd 2010, 08:05 PM
  5. Replies: 2
    Last Post: March 26th 2009, 07:58 PM

Search Tags


/mathhelpforum @mathhelpforum