I'm having problem with proving that a particular relation is Partial Order. Here is the task:
$ k, n \in \mathbb{N}_{+} $, $k\preceq n$ iff $$ \exists j \in \mathbb{N} (2j + 1) k | n $$
Prove that $\preceq$ is partial order.
That's what I did:
1) Reflexive
$ a \preceq a $
$ \exists j \in \mathbb{N} (2j + 1) a | a $
And that j is simply 0. So reflexivity is proved.
2) Antisymmetric
$ a \preceq b \wedge b \preceq a \Rightarrow a = b $
$ (2j_{1} + 1) a | b \wedge (2j_{2} + 1)b | a $
I guess that's only possible when a = b. But is that a correct proof for that part?
3) Transitivity
I define new variables $ p, q, f \in \mathbb{N} $. I will use them for my equations to show divisibility.
$ (2j_{1}+1)ap=b \wedge (2j_{2}+1)bq=c \Rightarrow (2j_{3}+1)af=c $
Now after some operations I can see that:
$ (2j_{3}+1)f= (2j_{2}+1)(2j_{1}+1)pq $
But... I think it leads to nowhere, because I didn't show that $ j_{3} $ belongs to N. It doesn't matter how hard I try, I always end up with something that doesn't work. I thought about multiplying odd numbers, divisibility etc. but unfortunately it didn't help. Could you please help me with that proof? I guess there is an easier way to do it. I will be very grateful.
2) $(2j_{1} + 1) a | b \wedge (2j_{2} + 1)b | a$. From the definition of $|$ we have that $b = m(2j_{1} + 1) a$. Substitute $b$ in the second equation and you have: $(2j_{2} + 1)m(2j_{1} + 1) a | a$. This tells us that a multiple of $a$ divides $a$, which can only happen if the multiple is itself $a$. So $(2j_{2} + 1)m(2j_{1} + 1)$ is equal to $1$ and since both numbers in the product are natural they are both equal to $1$. So we end up with $ a | b \wedge b | a$ which implies $a = b$.
3) $(2j_{1}+1)ap=b \wedge (2j_{2}+1)bq=c \Rightarrow (2j_{3}+1)af=c$. Simply substitute $b$ and you get $c = (2j_{2}+1)(2j_{1}+1)apq$. Now, set $f = pq$ and $(2j_{3}+1) = (2j_{2}+1)(2j_{1}+1)$ and you are done.