Results 1 to 2 of 2
Like Tree1Thanks
  • 1 Post By Deveno

Math Help - "x divides y" proof

  1. #1
    Member
    Joined
    Jan 2014
    From
    Arizona
    Posts
    103
    Thanks
    3

    "x divides y" proof

    Are these valid proofs? Specifically, is the way that I introduced the integer k the right way to do that? Thanks.

    Let R be the relation on Z given by xRy iff x divides y.

    Proof (Reflexive)
    Suppose x is in Z. Consider integer k = 1. Then, x = (1)x = kx, and x divides x.
    Thus, xRx and R is reflexive.

    Proof (Symmetric)
    Counterexample: Suppose (x, y) = (1, 10). Let k = 10. Then, y = 10 = (10)1 = kx, and xRy.
    But (y, x) = (10, 1) and y = 1 = (k)10 for k = 1/10. Thus, y does not divide x
    and (y, x) is not in R. So, R is not symmetric.

    Proof (Transitive)
    Suppose (x, y) and (y, z) are both in R. Then there exists integers k and n such that y = kx and z = ny.
    So, z = ny = n(kx) = (nk)x. Since the product of integers is again an integer, nk is an integer.
    Thus, x divides z and xRz. Therefore, R is transitive.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: "x divides y" proof

    Those are correct, but I would phrase your counter-example as a proof by contradiction, like so:

    Suppose 10 divides 1: then there is an integer k with 1 = 10k. Clearly, k = 0, or 1 do not work. So if k exists, we must have k > 1, in which case: 1 = 10k > 10 > 1, a contradiction.

    Why do it this way? Because we are only using properties of the INTEGERS, and not making reference to an "outside system" (the rational numbers) which we do not need. Also, in the rational numbers, 10 DOES divide 1, which muddies the waters, logically speaking.

    In other rings (essentially algebra systems in which we have addition, subtraction and multiplication, but perhaps not division) we may have no notion of what 1/k even "means", so it is a good idea to avoid using that way of thinking later on.

    Of course, to be able to use my argument, you must legally be allowed to use the ORDER properties of the integers, and I do not know if your course has gone into these yet.

    That is a small detail, however, and your proofs are correct, and your counter-example IS a valid one.
    Thanks from Convrgx
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: April 2nd 2012, 08:06 PM
  2. Replies: 1
    Last Post: September 16th 2011, 02:08 AM
  3. Replies: 2
    Last Post: June 4th 2011, 01:11 PM
  4. Replies: 2
    Last Post: April 24th 2011, 08:01 AM
  5. Replies: 1
    Last Post: October 25th 2010, 05:45 AM

Search Tags


/mathhelpforum @mathhelpforum