4
$\begingroup$

I was asked to show that if every subset of a poset has an infimum then every such subset has a supremum. I did my proof and now I realize that what I was calling "infimum" was actually "a smallest element in given subset" (i.e. minimal element), so I actually proved that if every subset has a minimal element it has a maximal element. But I don't see why we should require the original statement to be true.

I don't know how to draw things on here (seen a few questions with really pretty diagrams, 2nd question How do I draw graphs and things on this site?) Anyway my attempt at a counter-example to my original problem is four points in a square where the top two are not connected but are both connected to both of the bottom points and the bottom points are connected to each other but the top points are not connected to each other.

In particular, the two top points are a subset and either of the bottom points are an infimum. Well maybe this isn't a counterexample... I suppose the trick lies in understanding that the infimum is unique. Why must it be unique?

  • 1
    I don't think the example you give is a _poset_. (It doesn't appear to satisfy anti-symmetry.)2012-09-22
  • 0
    What exactly does "are connected to each other" mean? Perhaps it would be clearer if you specified the relation by the ordered pairs it contains.2012-09-22
  • 1
    @anon: In your example $\varnothing$ has no infimum. A partial order in which every subset has an infimum automatically has a maximum element.2012-09-22
  • 0
    Curse you, $\varnothing$.2012-09-22
  • 0
    ∅ always has a trivial infimum and supremum. Consider R, the infimum of ∅ is -Infinity, while the supremum of ∅ is +Infinity. "Connected to each other" means that there is a relation between them. For example, if the poset is the power set equipped with set inclusion then an edge is between sets that are proper subsets/supersets of one another.2012-09-22
  • 0
    Here is my proof that I originally did: "Proof:" Because every subset S of a poset P has an infimum (by assumption), there always exists p in P such that p≤ s for all s in S (by definition). But p ≤ S for all s in S implies we never have the case that x !≤ y and y !≤ x because in particular consider the subset {x,y}. Where x and y are "fingers" (i.e. vertices sticking "upward" with only a single edge... let them have a common meet x∧y, but a∨b= ∅ (does not exist). For example, consider a "crown" set with additional edges to make the meet existent. !≤ (not less than or equal to)2012-09-22
  • 0
    (http://mathworld.wolfram.com/CrownGraph.html)2012-09-22

1 Answers 1

7

Let $\langle P,\le\rangle$ be a poset in which every subset has an infimum, and let $A\subseteq P$ be arbitrary. Let $U=\{p\in P:a\le p\text{ for all }a\in A\}$, the set of upper bounds of $A$, and let $u=\inf U$. Clearly each $a\in A$ is a lower bound for $U$, so $a\le u$ for each $a\in A$, and therefore $u$ is actually the minimum element of $U$. In other words, $u$ is the smallest upper bound for $A$, which is precisely what is meant by saying that $u=\sup A$. Thus, every subset of $P$ has a supremum.

Note that the emptyset is not treated any differently from the non-empty sets: $u=\inf\varnothing$ if and only if (1) $u\le p$ for all $p\in\varnothing$, which is vacuously true of all $u\in P$, and (2) if $v\in P$ also has property (1), then $v\le u$. Since every $u\in P$ has property (1), property (2) says that $u$ is the maximum element of $P$, usually denoted by $\top$ or $1_P$. Similarly, if $\varnothing$ has a supremum, it must be the minimum element of $P$, usually denoted by $\bot$ or $0_P$.

  • 0
    Does this poset work? Graph vertices and edges V={1,2,3,4} E={{1,2},{1,4},{2,3},{3,4}} Draw them like a square and label the top left one as "1", bottom left as "2", top right as "3" and bottom right as "4".2012-09-22
  • 0
    @dustanalysis: To make that a partial order you’ll have to add the pairs $(1,1),(2,2),(3,3),(4,4),(1,3)$, and $(2,4)$. Then it’s a partial order $-$ in fact a linear order $-$ and every subset of $V$ has both an $\inf$ and a $\sup$.2012-09-22
  • 0
    Right?.... So I can kinda appreciate that we need (i,i) (because of reflectivity). But we must we have (1,3)? Can't we have that one element be neither greater nor lesser nor equal to another (i.e. uncomparable as Hungerford puts it).2012-09-22
  • 0
    @dustanalysis: Transitivity: once you have $(1,2)$ and $(2,3)$, transitivity requires that you have $(1,3)$. Yes, you can have incomparable elements; a simple example is $$\{(1,1),(2,2),(3,3),(4,4),(1,2),(1,3),(2,4),(3,4)\}\;.$$2012-09-22
  • 0
    Why is it not possible for $U$ to be empty? Is that assumption equivalent to Zorn's lemma?2012-09-22
  • 1
    @dustanalysis: It has nothing to do with Zorn’s lemma. $U$ can’t be empty because because $P$ has a maximum element, $\inf\varnothing$, and that maximum element is definitely in $U$.2012-09-22