in Set Theory & Algebra retagged by
5,069 views
17 votes
17 votes

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.
in Set Theory & Algebra retagged by
5.1k views

4 Comments

It's nothing but ( Dn,| ) // Lattice under divisibility relation.

Partial order relation : Yes

Need not be complete lattice.

5
5
edited by

@Deepakk Poonia (Dee) 

Lattice as per que is for " Every subset" , but it has different definition in K.H Rosen.

Are they different and if yes , then which one to be considered ? 

0
0

@Mk Utkarsh 

will u help me in this ?

1. Every subset can have a common element which they divide. ( lcm) 

2. Every element have element that devides i.e "1"       ( gcd)

then why not complete order ? And i too dont understood the argument about inclusion and exclusion of "0" make difference, how ?

 

( or is it due to unboundedness ?)

0
0
Why do we  say that just because 0 is included
its a complete lattice . I agree every infinite subset will have a
a upper bound if 0 is included.But that doesnt mean that they will have lowest upper bound. Why isnt this possibility being proved when we say something is a complete lattice?
0
0

5 Answers

4 votes
4 votes
Best answer

A. Taking an example, $\{4,2\}$ is not symmetric as  $4|2$ is not equal to $2|4.$ So, it cannot be an equivalence.

B. It is not necessary that every subset will have an 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 division relation.

D. Not every subset is a complete lattice. Counter example: $\{1,2,3,24,30\}$ Here, $2\&3$ have no LUB. 

So, E is the answer.

selected by

4 Comments

But That (6) doesn’t  belongs to set
0
0

This might help

 

0
0
Can someone help me with the following doubts

So far I know only how to calculate LUB(join) and GLB(meet) of any two elements in the poset.

What is LUB and GLB of any finite subset of a poset ?

What is LUB and GLB of any infinite subset of a poset ?

What is upper bound and lower bound of any finite subset of a poset ?

What is upper bound and lower bound of any infinite finite subset of a poset ?

I’m totally messed with the concept of complete Lattice

Please someone help me out or even just provide me the resources with crisp explanation

Thank you in advance
0
0
6 votes
6 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.

edited by

1 comment

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 |".
0
0
4 votes
4 votes
i think ans will be E)

as every subset  of this will not have LUB and GLB .

4 Comments

@s.abhishek-Who Said 0 doesn't belong to N?

Please refer rosen
1
1
{0,1,2,....} is a whole numbers ...
0
0

@Arjun @Puja Mishra

option E is correct but why B is not correct.

Take subset {3,5,7,2} LUB for this is 2*3*5*7

is there any counter example for B

0
0
1 vote
1 vote

Reflexive?

a|a ? Yes.

Symmetric? a|b so b|a? No.

Not equivalence

Option A

Refer: https://gateoverflow.in/62381/go2017-maths-25

Every set of numbers have GCD as Lower Bound, and LCM as upper bound.

Trivial GCD is 1, and trivial LCM is 0.

So, just "upper bound" is asked and not LUB.

Option B seems correct

Existence of relatively prime numbers won't let | be a TOSET.

Option C

As stated above, any infinite subset will have trivial GCD 1 and trivial LCM 0.

But a finite subset like {1, 2, 3} is not a lattice because the pair 2, 3 lacks a join. Source(https://en.wikipedia.org/wiki/Lattice_(order)

So, Option D

A set is called lattice if every finite subset has a least upper bound and greatest lower bound.

The set {1, 2, 3, 12, 18, 36} partially ordered by divisibility is not a lattice. Every pair of elements has an upper bound and a lower bound, but the pair 2, 3 has three upper bounds, namely 12, 18, and 36, none of which is the least.

Source: https://en.wikipedia.org/wiki/Lattice_(order)

Option E

 

I've spent around 6 hours reading things related to this question, and have come to the following conclusion. The divisibility relation is a POSET (fact) and the divisibility POSET is:-
 

  • If the set is finite, check if it's a lattice or not.

    {1, 2, 3, 12, 18, 36} is a not lattice, but {1, 2, 3, 6} is.
     
  • If the set is infinite, 0 can be the Upper Bound and 1 can be the Lower Bound.

    So, check if 0 is available in the domain or not.

If you know more about this, please feel free to add a comment.

edited by

2 Comments

@JashanArora thanks for your answer. Your hard work will surely help others. Keep learning and share knowledge with others.
0
0

Reasons for Option D and E is completely incorrect. 

$\{N, |\}$ is not complete lattice because $0 \notin N$. 

The set {1, 2, 3, 12, 18, 36} partially ordered by divisibility is not a lattice. Every pair of elements has an upper bound and a lower bound, but the pair 2, 3 has three upper bounds, namely 12, 18, and 36, none of which is the least.

This is true when your set is $\{1, 2, 3, 12, 18, 36\}$. But, in this case, the set is $N$. And, for every finite subset of $N$, there exists a $lub$ and $glb$.

 If your subset is $\{1, 2, 3, 12, 18, 36\}$ then $lub = 36$ and $glb = 1$. If your subset is $\{2, 3\}$, then  $lub = 6$ and $glb = 1$ .

0
0
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