Upper/Lower Bounds

  • Thread starter roam
  • Start date
  • #1
1,266
11

Homework Statement



Let S=P{2,3,4,6,7,8,14,28,42,98} and let p be the relation on S defined by a p b iff a|b. Then (S,p) is a poset.

(a) Find a subset of S which has no upper bound and no lower bound.
(b) Find the least upper bound for {3,7}
(c) Determine wether or not the subset {2,6,8} of S is totally ordered. Justify your answer.

Homework Equations



The Attempt at a Solution



(a) So, I drew a lattice diagram:

http://img514.imageshack.us/img514/8835/72872757.gif [Broken]

I think the set S'={7,3,8} qualifies as a subset of S which has no upper bound and no lower bound. Am I right?

(b) lub{3,7} = 7 ?

(c) I'm not sure how to answer this question. I think that a "total ordering" on a set means a partial order ~ on a set with the additional property that for any [tex]a,b \in S[/tex] we have a~b or b~a. Here in the subset {2,6,8} of S, 6 is devisible by 2, 6|2, also 8|2 but 6 isn't devisible by 8 or vice versa, so the set isn't totally ordered. Is this correct?
 
Last edited by a moderator:

Answers and Replies

  • #2
tiny-tim
Science Advisor
Homework Helper
25,832
251
Hi roam! :smile:
Let S=P{2,3,4,6,7,8,14,28,42,98} and let p be the relation on S defined by a p b iff a|b. Then (S,p) is a poset.

(a) Find a subset of S which has no upper bound and no lower bound.
(b) Find the least upper bound for {3,7}
(c) Determine wether or not the subset {2,6,8} of S is totally ordered. Justify your answer.

(a) … I think the set S'={7,3,8} qualifies as a subset of S which has no upper bound and no lower bound. Am I right?

(b) lub{3,7} = 7 ?

(c) I'm not sure how to answer this question. I think that a "total ordering" on a set means a partial order ~ on a set with the additional property that for any [tex]a,b \in S[/tex] we have a~b or b~a. Here in the subset {2,6,8} of S, 6 is devisible by 2, 6|2, also 8|2 but 6 isn't devisible by 8 or vice versa, so the set isn't totally ordered. Is this correct?

(a) yes :smile:
(b) nooo :redface:
(c) yes :smile:
 
  • #3
1,266
11
Hi roam! :smile:


(a) yes :smile:
(b) nooo :redface:
(c) yes :smile:


Hi Tiny tim!

I don't understand why my answer to part (b) is not correct, could you explain please? 3x7=21 which is not even in the bigger set, and the only (and hence smallest) upperbound is 7. :rolleyes:

Also for part (c), is my explanation correct/sufficient (because the question says you must justify the answer)?
 
  • #4
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
4,544
582
How can 7 be the least upper bound if 3 isn't less than 7? You say 21 isn't in S, and that's fine... what numbers in S could be the least upper bound?
 
  • #5
tiny-tim
Science Advisor
Homework Helper
25,832
251
Hi roam! :wink:
I don't understand why my answer to part (b) is not correct, could you explain please? 3x7=21 which is not even in the bigger set, and the only (and hence smallest) upperbound is 7. :rolleyes:

Office_Shredder :smile: is right … 3 does not divide 7 (ie, is not "less than" in the ordering), so how can 7 be the lub?
Also for part (c), is my explanation correct/sufficient (because the question says you must justify the answer)?

Yes … you've specifically said that "6 isn't divisible by 8 or vice versa", which itself shows that there is no total ordering … that's fine! :smile:
 
  • #6
1,266
11
The set has no upper/lower bound since there is no order on the set, 3 & 7 aren't devisible. So is it just the empty set i.e. lub{3,7}= {[tex]\emptyset[/tex]}? :redface:

Tiny tim, there's another question that I'm confused about: "Find all maximal and minimal elements of S."
It says "elements", plural. But there's only one max and one min:
maxP{2,3,4,6,7,8,14,28,42,98}=98
minP{2,3,4,6,7,8,14,28,42,98}=2
 
  • #7
tiny-tim
Science Advisor
Homework Helper
25,832
251
Hi roam! :smile:

(oh, and it's "divisible"! :wink:)
The set has no upper/lower bound since there is no order on the set, 3 & 7 aren't devisible. So is it just the empty set i.e. lub{3,7}= {[tex]\emptyset[/tex]}? :redface:

Forget division … just look at that very good picture you drew … go up from 3 and 7, and where do you get? :smile:

(btw, lub has to be an element

if there's no lub, you just say so, you don't say it's the empty set. :wink:)

Tiny tim, there's another question that I'm confused about: "Find all maximal and minimal elements of S."
It says "elements", plural. But there's only one max and one min:
maxP{2,3,4,6,7,8,14,28,42,98}=98
minP{2,3,4,6,7,8,14,28,42,98}=2

I haven't come across this terminology before :redface:, but I assume maximal means any element that doesn't have anything "higher" …

again, you can just read this off the picture. :smile:
 
  • #8
1,266
11
Thanks alot Tiny tim, I get it! :wink:

Forget division … just look at that very good picture you drew … go up from 3 and 7, and where do you get?

lub=42
 
  • #9
tiny-tim
Science Advisor
Homework Helper
25,832
251
:biggrin: Woohoo! :biggrin:
 

Related Threads on Upper/Lower Bounds

  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
0
Views
4K
  • Last Post
Replies
4
Views
819
  • Last Post
Replies
1
Views
4K
Replies
4
Views
1K
  • Last Post
Replies
1
Views
950
Replies
4
Views
802
Replies
0
Views
2K
Replies
2
Views
613
Replies
4
Views
6K
Top