Antisymmetric proof in x | y relation.

1k Views Asked by At

I need to prove that the relation $$ xRy \iff x|y$$ is an ordering relation. In order to do that, i know that i have to prove that the relation is : Reflexive, Antisymmetric and Transitive.

To prove the antisymmetry i was doing this:

I know that the relation is antisymmetric if $$ \forall x,y \in A : xRy,yRx \to x=y $$

So i have been showing it to be true this way:

$$ x|y \iff \exists k\in N, kx = y$$

then:

$$ x =_{yRx} k_1 y =_{xRy} k_1k_2 x =_{k1,k2\in N} k_3x = y $$

But now I am realising that that proof is incorrect, or at least i think so because if in my hypothesis i am saying that $$ k_2x = y $$ then i can't say that $$ k_3x = y$$ unless $$ k_1 = k_3 $$ which would require that $$ k_2 = 1 $$

Am i correct? How should i prove it?

I also have to show that $$xRy \iff y = x^r ,r \in N $$ is an order relation

1

There are 1 best solutions below

2
On

You are on the right track in that we need to prove $k_2=1$ in order to complete your proof.

You got the following equation: $$x=k_1k_2x$$ Divide both sides by $x$: $$1=k_1k_2$$ Thus, we have $k_2 \mid 1$. This means $k_2=\pm 1$. However, by the definition of $R$, we have $k_2 \in \Bbb{N}$ and thus $k_2=1$.


For the second thing, let's say $x R y \implies x=y^{r_1}$ and $y R x \implies y=x^{r_2}$. Thus, we get: $$x=x^{r_1r_2}$$ Now, if you can prove $1=r_1r_2$ from this equation, then you can prove that $r_2=1$ and thus $y=x^{r_2}=x^1=x$, which is similar to the proof above.

(The exception to the above is $x=1$, which must be dealt with as a separate case.)