7
$\begingroup$

Theoretic background

Lets just set some background to be sure what I am talking about

Posets

A Poset is defined to be a couple $(S,\leq)$ where a set $S$ and its elements $s \in S$ are connected together by binary relation $\leq$ satisfying the following properties for $s,t,u \in S$:

  • $s \leq s$
  • $s \leq t \wedge t \leq s \implies s=t$
  • $s \leq t \wedge t \leq u \implies s \leq u$

Lattices

A lattice is a poset where it is always possible, for every element of the set $S$: $\forall s \in S$, to find a meet and a join. Or equivalently a Greatest Lower Bound and a Least Upper Bound. Meet and Join MUST be UNIQUE for all elements of the set without ambiguity.

The problem

My problem is getting a Lattice from a Poset. This is always possible by means of the concept of Ideal.

Ideal

A debate on the definition of ideal is still ongoing here (in this community). Below I am reporting the two definitions, one in Wikipedia Wikipedia article on Ideals (poset) and the other one in some authoritative books (see below).

Definition of Ideal according to Wikipedia

Given poset $(S,\leq)$ we consider a $I \subseteq S$. It is an Ideal of $S$ if it has the following property:

$I \subseteq S,\forall x,y\in I\exists z\in I\ x\leq z\ \text{and}\ y\leq z \wedge x \leq y \in I \implies x \in I$

Definition of Ideal according to A. Bjorner, G. M. Ziegler (Matroid Applications edited by N. L. White - Cambridge University Press - First published 1992)

Citing from the book:

"Let $(E,\leq)$ be a finite partially ordered set and $F$ be the set of ideals of $E$ (a subset $A \subseteq E$ is an ideal if $x \leq y \in A$ implies $x \in A$)...".

Definition of Ideal according to Alexander Schrijver (3 volume encyclopedia "Combinatorial Optimization - Volume A" - Springer - 2002)

Citing from the book:

"Each partially ordered set $(S,\leq)$ gives a distributive lattice in the following way. Call a subset $I \subseteq S$ a lower ideal, or just an ideal, if $t \in I$ and $s \leq t$ implies that $s \in I$...".

Constructing the Lattice

To get a Lattice from a Poset $(S,\leq)$ one must consider the set of Ideals of $S$. My problem is understanding if I perform this process correctly. So please can you build the lattice from the poset characterized by the following elements where $\leq$ is the classic set containment relation?

$S = \{ \emptyset, \{1\}, \{2\}, \{3\}, \{4\}, \{1,2\}, \{3,4\}, \{1,2,3\}, \{2,3,4\}, \{1,2,3,4\} \}$

More compactly:

$S = \{ A, B, C, D, E, F, G, H, I, L \}$

Thankyou

What I thought about

I thought about some possible answers, but do not know if my interpretation is correct.

Which one am I referring to?

Considering the presence of some definitions of Ideal here, let me clear that I made the following assumptions basing on the definitions that I found in the books I read.

Is it the power set?

Looking at the definition of ideal it seems that I must take all subsets of $S$ and, for every subset, in order to make it an ideal, I must take all subsets of $I$. So I will get the set of all Ideals. But this would be a power set of $S$ and I don`t think this is the set of all ideals of $S$.

Is it right what I am telling?

In Ideal definition "$I \subseteq S$ Ideal if $t \in I$ and $s \leq t$ implies that $s \in I$", $s$ is to be considered as elements in $S$?

If I consider a subset of $S$, I consider for example $t \in S$, $t = H = \{ 1,2,3 \}$. The condition tells me that I must consider all subsets in $H$? I guess not. It says that I should look for $s \leq t$. But, using the $\leq$ operator kinda implies that $s$ is an element in $S$ right? So, in my case, considering such $t$, I have to consider in my ideal also $\{1,2\}, \{1\}, \{2\}, \emptyset$.

Is this ok?

Addition

This question was edited changing the ideal definition with the one reported in Wikipedia. Lately I changed this question again reporting all definitions and their corresponding sources.

The point is that a different concept of Ideal is being formulated by the Wikipedia article while in some authoritative books other definitions (simpler) are considered. Changes in this question are made in order to discuss also about this other than the many purpose of the question (the problem I asked about).

A new question

The definition in Wikipedia adds a condition that I cannot see in most authoritative texts about combinatorial optimization. Please, explain me the equivalence with relations I provided, I cannot understand.

  • 0
    I see, $b$ut it`s ki$n$da strange. I admit that these books are quite old, some of them preceding 1990... maybe conventions about ideals changed in time... thanks Brian, I`ll investigate more about this.2012-02-27

3 Answers 3

5

Not all subsets of $S$ are ideals. For example $\{\{1\},\{2\}\}$ is not an ideal since is not downward closed. On the other hand, there ideals different from the power set of $S$ as $\{\emptyset, \{1\}\}$.

Let us list all the ideals by the cardinality $n$ of its biggest element. (1) If $n=0$ then the ideal is $\{\emptyset\}$ (2) If $n=1$ then we have $\{\emptyset, \{a\}\},\ \{\emptyset, \{a\}, \{b\}\},\ \{\emptyset, \{a\},\{b\},\{c\}\}$ and $\{\emptyset, \{a\},\{b\},\{c\},\{d\}\}$, where $a,b,c,d\in\{1,2,3,4\}$ (3) If $n=2$ then we get $\{\emptyset, \{a,b\},\{a\},\{b\}\}$ where $a\in\{1,3\},\ b\in\{2,4\}$ and $\{\emptyset, \{1,2\}, \{2,3\}, \{1\}, \{2\},\{3\},\{4\}\}$. It should be clear how to proceed from there.

  • 0
    OK think$I$got it... quite long procedure... Thanks a lot azarel, I will read better and try to understand it fully.2012-02-27
5

Since your poset is small, it might help you to draw its Hasse diagram:

                           L                             / \                          /   \                           /     \                          H       I                          |       |                          F       G                         / \     / \                        B   C   D   E                         \  |   |  /                          \ |   | /                           \ \ / /                            \| |/                            A 

A lower set (or in your terms an ideal) is a set with the property that if one of these elements is in it, every element below that one is also in it. Thus, you immediately get an ideal for each of the nine elements:

$\begin{array}{}A&\mapsto&\{A\}\\B&\mapsto&\{B,A\}\\C&\mapsto&\{C,A\}\\D&\mapsto&\{D,A\}\\E&\mapsto&\{E,A\}\\F&\mapsto&\{F,B,C,A\}\\G&\mapsto&\{G,D,E,A\}\\H&\mapsto&\{H,F,B,C,A\}\\I&\mapsto&\{I,G,D,E,A\}\\ L&\mapsto&\{L,H,I,F,G,B,C,D,E,A\} \end{array}\tag{1}$

However, these aren’t the only lower sets of the poset. For example, $\{B,C,A\}$ is a lower set: it contains everthing that is below any of its members. Two more lower sets not in the list $(1)$ are $\{A,B,C,D\}$ and $\{A,B,C,D,E,G\}$. You should be able to find quite a few more.

  • 0
    Thankyou very much for your answer Brian, it helped me but azarel`s one was a little more explicit for the construction of the set using an inductive cardinal oriented approach.2012-02-27
1

Regarding the partially unsolved matter concerning Ideals, I think I got an answer.

Important references

In order to better explain it, I will refer to the following authoritative books:

  • (R1) "Lattice Theory" by Garrett Birkhoff - American Mathematical Society - 1984

  • (R2) "Matroid Applications" from Encyclopedia of Mathematics and its Applications by N. L. White - G. Rota - 1992 (first published)

  • (R3) "Combinatorial optimization, Polyhedra and Efficiency, Volume A on Paths, Flows and matchings" by Alexander Schrijver - Springer - 2002

Differences

Results from R2 and R3 are those reported in the question.

Birkhoff formulation

Birkhoff in R1 page 25 (Chapter II, Paragraph 3: "Morphisms and ideals") actually focuses on the definition of ideal as follows (citation):

An Ideal is a nonvoid subset $J$ of a lattice (or join-semilattice) $L$ with the properties

(2) $a \in J, x \in L, x \leq a$ imply $x \in J$

(3) $a \in J, b \in J$ imply $a \vee b \in J$

Birkhoff is one of the most important figures in this theory.

Where is the difference?

Wikipedia actually is providing a formulation equivalent to the one provided by Birkhoff with one possible mistake, Birkoff defined Ideals from Lattices in order to get another Lattice. Birkhoff starts from a Lattice while the other authors refer to Posets. In this way the article in Wikipedia is incorrect because it is hypothizing a Poset and is using conditions evaluated by Birkhoff for Lattices.

We have, so, without caring so much about names (what matters is the concept), two types of ideals in literature:

  • Poset Ideals able to let one pass from a Poset to a Lattice.

  • Lattice Ideals able to let one pass from a Lattice to another lattice

Hope this helps.

  • 0
    The notion of _ideal of a poset_ and _ideal of a lattice_ differ in a widely read book (and thus influential in applied math circles): Davey and Priestley. Specifically, for a poset, the only requirement for an (order) ideal (=down-set) is that it be "closed under going down" (p. 20). On the other hand, for a lattice, an ideal is a down-set that is also closed under joins (p. 44). The latter coincides with the def from Birkhoff. So you must be careful when you talk of ideals of a lattice if you consider it only as a poset.2015-04-22