retagged by
5,100 views
17 votes
17 votes

Consider the ordering relation $x\mid y \subseteq N \times N$ over natural numbers $N$ such that $x \mid y$ if there exists $z \in 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. $\mid$ is an equivalence relation.
  2. Every subset of $N$ has an upper bound under $|$.
  3. $\mid$ is a total order.
  4. $(N, \mid)$ is a complete lattice.
  5. $(N, \mid)$ is a lattice but not a complete lattice.
retagged by

5 Answers

Best answer
4 votes
4 votes

A. Taking an example, $\{4,2\}$ is not symmetric as  $4|2$ is not equal to $2|4.$ So, it cannot be an equivalence.

B. It is not necessary that every subset will have an upper bound.

C. For being total every element in the subset should be comparable have it is not total as well. We have counter example: $\{1,2,3,9,15\}.$ Here, $2\& 3$ are incomparable. $9\&15$ are also not comparable in this division relation.

D. Not every subset is a complete lattice. Counter example: $\{1,2,3,24,30\}$ Here, $2\&3$ have no LUB. 

So, E is the answer.

selected by
6 votes
6 votes

B and D both are the answers. (I think, Verification required.)

a.) | is an equivalance relation.  False

     3 | 6 but not the other way around. so not symmetric 

b.) Every subset of N has an upper bound under |.  True

     Every finite subset A does,  it is lcm(A) .
     Also even infinite subsets of $\mathbb{N}$ have least upper bound if we count 0 as natural number, (surprised !!) because everything divides zero.

Source: https://en.wikipedia.org/wiki/Complete_lattice. see examples.

c.) | is a total order. False

    3 and 5 are not comparable.

  Defination of total order: A poset  $(S, \preceq)$ is total order if $\forall{x,y \in S}$ either $x \preceq y$ or $y \preceq x$

d.) (N, |) is a complete lattice. True

    Option b explains the reason for upper bound. For finite subset we have gcd as lower bound, but for infinite subets we always have 1, if no other exists. :-)

e.) (N,∣) is a lattice but not a complete lattice. False.

    Now it's obvious, isnt' it. :-)

EDIT: I looked in an answer key. The answer as per the key is E. I guess they are not counting 0 as natural number. Which implies there is no upper bound for infinite subset, which makes both B and D false.

edited by
4 votes
4 votes
i think ans will be E)

as every subset  of this will not have LUB and GLB .
1 votes
1 votes

Reflexive?

a|a ? Yes.

Symmetric? a|b so b|a? No.

Not equivalence

Option A

Refer: https://gateoverflow.in/62381/go2017-maths-25

Every set of numbers have GCD as Lower Bound, and LCM as upper bound.

Trivial GCD is 1, and trivial LCM is 0.

So, just "upper bound" is asked and not LUB.

Option B seems correct

Existence of relatively prime numbers won't let | be a TOSET.

Option C

As stated above, any infinite subset will have trivial GCD 1 and trivial LCM 0.

But a finite subset like {1, 2, 3} is not a lattice because the pair 2, 3 lacks a join. Source(https://en.wikipedia.org/wiki/Lattice_(order)

So, Option D

A set is called lattice if every finite subset has a least upper bound and greatest lower bound.

The set {1, 2, 3, 12, 18, 36} partially ordered by divisibility is not a lattice. Every pair of elements has an upper bound and a lower bound, but the pair 2, 3 has three upper bounds, namely 12, 18, and 36, none of which is the least.

Source: https://en.wikipedia.org/wiki/Lattice_(order)

Option E

 

I've spent around 6 hours reading things related to this question, and have come to the following conclusion. The divisibility relation is a POSET (fact) and the divisibility POSET is:-
 

  • If the set is finite, check if it's a lattice or not.

    {1, 2, 3, 12, 18, 36} is a not lattice, but {1, 2, 3, 6} is.
     
  • If the set is infinite, 0 can be the Upper Bound and 1 can be the Lower Bound.

    So, check if 0 is available in the domain or not.

If you know more about this, please feel free to add a comment.

edited by
Answer: