GATE CSE
First time here? Checkout the FAQ!
x
+4 votes
317 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 (39.7k points) 256 1308 1941 | 317 views

3 Answers

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

as every subset  of this will not have LUB and GLB .
answered by Boss (9.8k points) 10 36 104
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 ?
Yes it is lattice. Not complete because 0 doesn't belong in N. So LUB do not exist for all.
+3 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.

answered by Active (1.6k points) 3 6 19
edited by
Every FINITE subset of N has an upper bound in N

Every INFINITE subset of N do not have an upper bound in N. As LUB(infinite set) is Zero(0) not belonging to N.

So if Opt .B would have been "Every finite subset of N has an upper bound under |". This would be true. Another interpretation can be "Every subset of N has an LCM of every pair though result of LCM can belong to N and not subset itself under |".
+2 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 by Loyal (2.7k points) 2 11 30
2 and 3 has lub as 6
@rio

question is about every subset  and the above mentioned subset is one of the possible  subset. so we have to find the lub  and glb  within  the set only. we can't take such an element '6' which is not even an element of the defined subset
hey  correct me if im wrong you want to say this question is a relation between  two subsets  which are related and where each element subset follow x*z=y  so how we are finding relation ?

{2,4}  is related to {2,4,8}  is true

but you mentioned

{2,3,9,15} how you got this subset

if not can you explain question ?
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23398 Points

  2. Bikram

    17078 Points

  3. Habibkhan

    8264 Points

  4. srestha

    6296 Points

  5. Debashish Deka

    5438 Points

  6. jothee

    4978 Points

  7. Sachin Mittal 1

    4772 Points

  8. joshi_nitish

    4348 Points

  9. sushmita

    3964 Points

  10. Rishi yadav

    3804 Points


Recent Badges

Notable Question KISHALAY DAS
Notable Question sh!va
Notable Question abhijeetbzu
Great Question jothee
Popular Question rahul sharma 5
Nice Question mohit kumar 5
Notable Question rishu_darkshadow
Nice Comment Pranay Datta 1
Copy Editor Shivansh Gupta
Nice Comment KULDEEP SINGH 2
27,324 questions
35,176 answers
84,107 comments
33,279 users