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.

i think ans will be E)

as every subset  of this will not have LUB and GLB .
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.

edited

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)