0
$\begingroup$

Question

Consider the ordering relation $x\,\,|\, \,y \,⊆\, N\,×\,N\,$ over natural numbers $N$ such that $x \, | \,y\,\,$ iff there exists $z$ ∈ $N$ such that $x\,\, .\,\,z = y.$ A set is called lattice if every finite subset has a least upper bound and greatest lower bound. It is called a complete lattice if every subset has a least upper bound and greatest lower bound.

Then,

  1. $|$ is an equivalence relation.
  2. Every subset of $N$ has an upper bound under $|$
  3. $|$ is a total order.

  4. $\left(N, |\right)$ is a complete lattice

  5. $(N, |)$ is a lattice but not a complete lattice

My Attempt

1.$\,\,|\,\,$ cannot be an equivalence relation,because it will not be symmetric,example-: $(2,6)$ is while $(6,2)$ is not.

now

3..$\,\,|\,\,$ cannot be total order.As for total order ,every 2 elelment of the relation must be *comparable** .But it is not.Take example, $(3,9)$ and $(4,16)$ belongs to relation but $3$ and $4$ are not comprable.

i am sure about these 2 options ,I am also sure that it is a Lattice as every pair of element has a Greatest lower bound and a Least upper Bound.

As GLB(Greatest lower bound)=GCD of 2 elements

and LUB(Least upper Bound)=LCM of 2 elements.

both GCD and LCM will belong to $N\,X\,N$

But i am stuck at option $2,4,5$.Please help me out ! Thanks

$\endgroup$
6
  • $\begingroup$ Answering questions 2, 4, and 5 will depend on whether $0$ is a natural number or not $\endgroup$
    – amrsa
    Commented Apr 25, 2017 at 13:47
  • $\begingroup$ you arre correct ,but for the lower bound !Question is aking about upper Bound(option-2) $\endgroup$
    – laura
    Commented Apr 25, 2017 at 15:11
  • 2
    $\begingroup$ No, $0$, if you consider it to be a natural number, will be the top element: for every other natural $n$, we have $n \cdot 0 = 0$, whence $n | 0$. $\endgroup$
    – amrsa
    Commented Apr 25, 2017 at 17:00
  • $\begingroup$ yes , you are right !if it would be the whole number then option 2 would be right which makes option 4 also right !Isn't it? $\endgroup$
    – laura
    Commented Apr 25, 2017 at 17:14
  • $\begingroup$ Precisely! And then, of course, (5) would be wrong. $\endgroup$
    – amrsa
    Commented Apr 25, 2017 at 17:16

1 Answer 1

Reset to default
2
$\begingroup$

All you have to do is solve 2. Then with what you have, you should be done. For that, try to consider $N$ itself. It is a subset of $N$ (although not finite). Does it have an upper bound?

$\endgroup$
3
  • $\begingroup$ i missed that! thanks ! My reasoning for 1 and 3 is right ? $\endgroup$
    – laura
    Commented Apr 25, 2017 at 12:00
  • 1
    $\begingroup$ Yes. Also with the lattice, you are on the right track - although you should show that it suffices to prove the existence of bounds for sets of size two, i.e. you should explain how this can be generalized to any finite set. $\endgroup$
    – Dirk
    Commented Apr 25, 2017 at 12:05
  • $\begingroup$ Exercise. A subset has an upper bound iff it is finite. Every subset has a lower bound. $\endgroup$
    – William Elliot
    Commented Apr 26, 2017 at 7:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .