Question

Show that the relation R on N is given by aRb iff \( b = 2^ka \) for some integer \( k \ge 0 \) is a partial ordering

Answer 1

reflexive, anti symmetric and transitive? is that the definition?

Answer 2

yaaaaa

Answer 3

so i guess we have to check them one by one right?

Answer 4

reflexive means \(aRa\) which is true because \(a=2^0a\)

Answer 5

i.e. there exists \(k\geq 0\) such that \(a=2^ka\) namely \(k=0\)

Answer 6

yaaaaaaa i see that

Answer 7

anti symmetric: if \(aRb\) and \(,bRa\implies a=b\) so now we translate out of the \(R\) notation and we need to show what?
if there exists a \(k\geq 0\) such that \(b=2^ka\) and also a \(j\geq 0\) such that \(a=2^kb\) then \(a=b\)

Answer 8

this is fairly obvious when you write down what it really means yes?
we have \(b=2^ka=2^jb\) which tells you that \(b=2^jb\) implying \(j=0\) and so \(b=2^0a=a\)

Answer 9

yaaaaaaa

Answer 10

this leaves transitive, and i bet you can do it for yourself
what is the idea?
get it out of the abstract \(aRb\) notation and write what it really means

Answer 11

a small mistake ! :) \[b=2^jb \Rightarrow b=0 or j=0\]

Answer 12

\(aRb\)means there exists \(k\geq 0\) such that \(b=2^ka\) and
\(bRc\) means there exist \(j\geq 0\) such that \(c=2^kb\)
then you need to show that \(aRc\) i.e that there exists \(l\geq 0\) such that \(c=2^la\) and you get it by the law of exponents

Answer 13

@neemo
i think maybe not a small mistake since the relation is on \(\mathbb{N}\)

Answer 14

however there is definitely a typo in the last part that i wrote

Answer 15

but the idea is clear i hope
go from abstract R to specific meaning of R and it drops right out.

Answer 16

yuppppp Thanks satellite :DDDD

Answer 17

yw

Answer 18

\[a=2^kb \text{ and }b=2^ja \text{ then }b=(2^j)(2^kb)\]
\[b=2^{k+j}b \Rightarrow b(2^{k+j}-1)=0\]
then b=0 or 2^{k+j}=1===>b=0 or i+j=0===>b=0 or( i=0 and j=0)
if b=0 then a=2^kb====>a=0 then a=b
else k=0 then a=2^0b=b
@satellite73 it's a mistake since \[0 \in \mathbb{N}\]

Answer 19

well you are free to include 0 in the natural numbers so long as i am free to exclude them
apparently it is sometimes debated, but it is not an interesting debate
http://en.wikipedia.org/wiki/Natural_number

Answer 20

*exclude IT

Answer 21

\[\mathbb{N}=0,1,2,3............\]
\[\mathbb{N}^{*}=1,2,3,......\]
in case you want to exclude it ..just use the right symbol :) :)
and you're right It's not an interesting debate