[SOLVED] Disprove Relation - Can somebody check my work

• April 11th 2009, 09:33 PM
spearfish
[SOLVED] Disprove Relation - Can somebody check my work
Disprove R on Q is either reflexive, symmetric, or transitive. x, y are elements in Q. xRy iff x = yk -1 for some integer k.
In order for to disprove this relation, I think I should show that it is

• NOT reflexive
• NOT symmetric
• NOT transitive

REFLEXIVE:
Suppose xRx.
x = xk -1.
1 = k - 1/x
1 + 1/x = k
k = (1+x)/x, since k is rational, R is not reflexive.

SYMMETRIC:
Suppose xRy.
x = yk-1.
Suppose yRx.
y = xm-1.
Plugging in for x, and solving for y
y = (yk-1)m-1
y = y(km - m) - 1
1 = (km-m) - 1/y
(km-m) = (y + 1)/y, once again, (km-m) is rational, so R is not symmetric.

TRANSITIVE:
Suppose xRy.
x = yk-1.
Suppose yRz
y = zn-1
Plugging in for y and solving for x
x = (zn-1)k - 1
x = z(nk - k) - 1
x/z = (nk - k) -1/z
x/z + 1/z = (nk - k)
(x+1)/z = (nk - k), so again, (nk - k) is rational, so R is not transitive

This is the only way that I could come up to disprove the relation. Please correct me if I am wrong on any work and show how I can correct with an explanation. Much thanks.
• April 11th 2009, 10:26 PM
Jhevon
Quote:

Originally Posted by spearfish
Disprove R on Q is either reflexive, symmetric, or transitive. x, y are elements in Q. xRy iff x = yk -1 for some integer k.
In order for to disprove this relation, I think I should show that it is

• NOT reflexive
• NOT symmetric
• NOT transitive

REFLEXIVE:
Suppose xRx.
x = xk -1.
1 = k - 1/x
1 + 1/x = k
k = (1+x)/x, since k is rational, R is not reflexive.

k is a NON-INTEGER rational is what you want to say. also, consider the case where x = 0. it is trivial, but if you are dividing by x, you must consider it.

Quote:

SYMMETRIC:
Suppose xRy.
x = yk-1.
Suppose yRx.
y = xm-1.
Plugging in for x, and solving for y
y = (yk-1)m-1
y = y(km - m) - 1
1 = (km-m) - 1/y
(km-m) = (y + 1)/y, once again, (km-m) is rational, so R is not symmetric.
again, say k is a non-integer rational, clearly. and consider the case y = 0.

Quote:

TRANSITIVE:
Suppose xRy.
x = yk-1.
Suppose yRz
y = zn-1
Plugging in for y and solving for x
x = (zn-1)k - 1
x = z(nk - k) - 1
x/z = (nk - k) -1/z
x/z + 1/z = (nk - k)
(x+1)/z = (nk - k), so again, (nk - k) is rational, so R is not transitive

This is the only way that I could come up to disprove the relation. Please correct me if I am wrong on any work and show how I can correct with an explanation. Much thanks.
now this one is a little shaky. how do we know that (x + 1)/z is not an integer? can z = x + 1? and of course, consider the case z = 0 since you divide by it
• April 11th 2009, 10:33 PM
spearfish
Awsome, I 'll get to work on that transitive part.
• April 12th 2009, 11:55 AM
Hello spearfish
Quote:

Originally Posted by spearfish
Disprove R on Q is either reflexive, symmetric, or transitive. x, y are elements in Q. xRy iff x = yk -1 for some integer k.

All you really need to do here is to find a single counter-example in each case.

$R$ is reflexive $\Rightarrow\forall x, \, xRx$. But when $x = 2$

$2 = 2k-1 \Rightarrow k = \tfrac32$

$\Rightarrow R$ is not reflexive.

$R$ is symmetric $\Rightarrow (\forall x,y,\,xRy \Rightarrow yRx)$

Now $x=5, y = 2 \Rightarrow k = 3$

So $5R2$. But $x = 2, y = 5 \Rightarrow k = \tfrac35$

$\Rightarrow R$ is not symmetric.

And $R$ is transitive $\Rightarrow (\forall x, y, z, \,xRy \wedge yRz \Rightarrow xRz)$

But $7R4 \,(k=2) \wedge 4R5 \,(k=1)$. But $7 = 5k-1 \Rightarrow k = \tfrac85$

So $R$ is not transitive.

Incidentally, the algebra goes a bit wrong here:
Quote:

x = (zn-1)k - 1
x = z(nk - k) - 1