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.

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.

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
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 |".

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 ?