8
$\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.

$\endgroup$
7
  • $\begingroup$ In your definition of ideal you should really get used to using english words. I looked up the definition on wikipedia and it is 100 times more clear than yours, just because you lack some brackets and commas that I think you explicitly didn't want to use. And your compact notation of $S$ really doesn't help ; you're speaking to human beings, use notation when it is pertinent only. $\endgroup$
    – Patrick Da Silva
    Feb 27, 2012 at 3:26
  • $\begingroup$ Actually, I added the first part since the OP forgot it. $\endgroup$
    – azarel
    Feb 27, 2012 at 3:36
  • $\begingroup$ @Patrick: Yes... Patrick, I just copied the definition from the book because I was scared to write the definition in a wrong way, that`s just the reason why I used the mathematical notation and not the human notation. Never wanted to make it purposely difficult to understand. Thanks however for your kindness in your message. $\endgroup$
    – Andry
    Feb 27, 2012 at 4:12
  • $\begingroup$ @azarel: please see changes $\endgroup$
    – Andry
    Feb 27, 2012 at 4:40
  • 1
    $\begingroup$ What your books call an ideal is in other contexts usually called just a lower set, an ideal then being a lower set that is also a directed set. The Wikipedia definition is for the more usual notion; in their terms you’re looking for lower sets, not ideals. $\endgroup$
    – Brian M. Scott
    Feb 27, 2012 at 5:42

3 Answers 3

Reset to default
7
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ But to build the set of all ideals, what should I do? The relation is the following: $I \subseteq S$ is Ideal if $t \ in I, s \leq t \implies s \in I$. The condition $s \leq t$ is not $s \subseteq t$. So I should not take necessarly all subsets in $t$, but should look in $S$ for all those $s$ being $\leq t$ and include those in set $I$? $\endgroup$
    – Andry
    Feb 27, 2012 at 5:08
  • $\begingroup$ I'll add a list for the ideals. $\endgroup$
    – azarel
    Feb 27, 2012 at 5:39
  • $\begingroup$ OK think I got it... quite long procedure... Thanks a lot azarel, I will read better and try to understand it fully. $\endgroup$
    – Andry
    Feb 27, 2012 at 6:04
6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Andry
    Feb 27, 2012 at 8:26
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Fizz
    Apr 22, 2015 at 17:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .