GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
251 views

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.
asked in Set Theory & Algebra by Veteran (32.9k points)   | 251 views

3 Answers

+2 votes
Best answer
i think ans will be E)

as every subset  of this will not have LUB and GLB .
answered by Boss (9.7k points)  
selected by
Yes, it is a lattice , but how Complete ?

what is Least upper bound if  Subset is {x | x>=50}

I think for this Subset there is not LUB i.e. LUB exists for every finite subset but not any Infinite subset..
yeah you are right , i guess . for every subset LUB and GLB is not possible .
What does it mean by X.Z=Y?
Here prime numbers are not related to each other..how it will be a lattice?

@Vaishali Jhalani

Though they are not related they have least upper bound. It's their least common multiple. And a poset is lattice if every pair has the least upper bound.

any counter example for not complete lattice ?
+1 vote

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.

answered by Active (1.4k points)  
edited by
0 votes

a> {4,2} its not symmetric as  4/2 is not equal to 2/4. so it cant be equivalance.

b> it its not necessary that every subset will have 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 divison Relation.

d> not every subset is complete lattice . counter example : 

{1,2,3,24,30}  here 2&3 have no LUB. 

so E is the answer .

 

answered ago by Active (1.3k points)  
Answer:

Related questions



Top Users Aug 2017
  1. Bikram

    4902 Points

  2. ABKUNDAN

    4704 Points

  3. akash.dinkar12

    3480 Points

  4. rahul sharma 5

    3158 Points

  5. manu00x

    3012 Points

  6. makhdoom ghaya

    2480 Points

  7. just_bhavana

    2388 Points

  8. stblue

    2138 Points

  9. Tesla!

    2060 Points

  10. joshi_nitish

    1758 Points


25,014 questions
32,141 answers
74,824 comments
30,185 users