GATE CSE
First time here? Checkout the FAQ!
x
0 votes
207 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 (29.5k points)   | 207 views

2 Answers

+1 vote
Best answer
i think ans will be E)

as every subset  of this will not have LUB and GLB .
answered by Boss (9.5k 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.

+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 Junior (975 points)  
edited by
Answer:

Related questions



Top Users May 2017
  1. akash.dinkar12

    3152 Points

  2. pawan kumarln

    1630 Points

  3. sh!va

    1590 Points

  4. Arjun

    1350 Points

  5. Devshree Dubey

    1246 Points

  6. Angkit

    1044 Points

  7. Debashish Deka

    1022 Points

  8. Bikram

    972 Points

  9. LeenSharma

    820 Points

  10. Prashant.

    692 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 May 22 - 28
  1. pawan kumarln

    256 Points

  2. Ahwan

    232 Points

  3. jjayantamahata

    114 Points

  4. joshi_nitish

    114 Points

  5. Arnab Bhadra

    94 Points


22,731 questions
29,061 answers
65,094 comments
27,625 users