[Set Theory] Proving Linear Order on a Subset of a Partially Ordered Set

  • #1

Homework Statement



Let L be a partially ordered set. Every countable chain in L has an upper bound. Let S be a countable subset of L such that for arbitrary a,b in S there exists a c in S such that a (less-than-or-equal) c and b (less-than-or-equal) c. Prove S has an upper bound in L.


Homework Equations



Definition of linear, partial orders.

The Attempt at a Solution



I assume the goal is to prove that S is linearly ordered and thus a chain, having an upper bound in L by the problem text. S is clearly a partial order because it is a subset of L. After listing the properties of a partial order, I have no idea how to continue. Any help would be greatly appreciated! Thanks!
 

Answers and Replies

  • #2
22,089
3,296
S is not a chain in general. So you won't be able to prove that. But try selecting a few elements in S which DO form a chain. This chain will have an upper bound. And if you selected the elements correctly, then the upper bound of the chain, will be an upper bound of S...
 
  • #3
Okay, I assume that a,b, and c are the elements to which you are referring. Obviously a and b are comparable with c but I am having trouble showing that it then follows that a is comparable with b. I know it can't be this easy, but I don't completely understand why c is not already an upper bound because it is defined to be greater than or equal to all elements of S. Since S is a subset of L, c must also be an element of L, giving S an upper bound in L. What is wrong with this line of thinking?
 
  • #4
22,089
3,296
Okay, I assume that a,b, and c are the elements to which you are referring. Obviously a and b are comparable with c but I am having trouble showing that it then follows that a is comparable with b.

No, a, b and c aren't the elements which I had in mind. The chain is somewhat harder to construct... In fact, nothing guarantees you that a and b are comparable. In fact, it isn't even true!!

I know it can't be this easy, but I don't completely understand why c is not already an upper bound because it is defined to be greater than or equal to all elements of S. Since S is a subset of L, c must also be an element of L, giving S an upper bound in L. What is wrong with this line of thinking?

I don't see why it is greater or equal to all elements of S? I only see why it is greater or equal than a and b. But it certeinaly isn't an upper bound of S!!

It may help you to think of some explicit examples!!
 

Related Threads on [Set Theory] Proving Linear Order on a Subset of a Partially Ordered Set

  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
7
Views
2K
Replies
9
Views
4K
Replies
1
Views
1K
  • Last Post
Replies
6
Views
2K
Replies
2
Views
1K
  • Last Post
Replies
1
Views
926
Replies
3
Views
3K
  • Last Post
Replies
7
Views
2K
Top