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

Thread: "x divides y" proof

  1. #1
    Jan 2014

    "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

    Mar 2011

    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: Apr 2nd 2012, 07:06 PM
  2. Replies: 1
    Last Post: Sep 16th 2011, 01:08 AM
  3. Replies: 2
    Last Post: Jun 4th 2011, 12:11 PM
  4. Replies: 2
    Last Post: Apr 24th 2011, 07:01 AM
  5. Replies: 1
    Last Post: Oct 25th 2010, 04:45 AM

Search Tags

/mathhelpforum @mathhelpforum