# How to deal with Ideals generation from a Poset of sets including the empty set?

This question is strictly connected with this one: Getting a Distributive-Lattice from Poset or, equivalently, a Greedoid from a Poset. I started this question a week ago and I am still struggling on Ideals and their generation.

## Definition of Ideal

Not to bother everyone reading an entire question to get just a definition, here is the definition of Ideal I will use in this question.

Given poset $(S,\leq)$, given $X \subseteq S$ a subset of $S$, then it is an Ideal if $y \leq x \in X \implies y \in X$.

Using natural language the definition is as follows: considering a poset $(S,\leq)$ and a subset of it $X \subseteq S$, then subset $X$ is an Ideal only if the lower set of every element of $X$ is also in $X$. Having lowerset $Y$ of $X$ defined as the set of all elements in $S$ for which $y \in Y,y \leq x \in X$.

# The situation

Consider to have a poset $(S,\leq)$ where the set $S$ consists of many sets and relation $\leq$ is the set containment relation $\subseteq$. The particularity of the poset is that, among elements $s \in S$, we have also $s_0=\{\}=\emptyset$.

## An example we will consider from now on

It is always better, in these cases, to consider an example. So, lets consider:

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

# The problem

I want to get the set of all ideals in the poset. Accordingly to the definition of Ideal that enables one to pass from a poset to a lattice (N. L. White, A. Bjorner, G. M. Ziegler and A. Schijver). However, the thing is that I do not know how to deal with the empty set $\emptyset$ in the poset.

# Questions

So, following I am going to proceed in some ways, could you tell me whether they aerew correct or not? Thankyou

## The procedure to build the set of all ideals

In order to build set of all ideals, I must consider all possible ideals that I can extract from the poset. Considering the definition of Ideal (the one I was talking about before), I must consider the poserset of $S$, $2^S$, and for every subset get its Ideal using the definition.

It means that I expect a Lattice $(I_S,\subseteq)$ ($I_S$ is the set of all ideals in $S$) with number of elements $|I_S|=|2^S|=2^{|S|}=2^7$.

Is this procedure correct?

## Dealing with $\emptyset$

When getting the set of all ideals, in the powerset of $S$ I will also find the null set $\{\} = \emptyset$. Among all subsets of my poset I will also find those subsets consisting in only one element, among these I also have $\{\{\}\} = \{\emptyset\}$.

So in my set of all ideals, one ideal is $\{\} = \emptyset$ and another ideal is $\{\{\}\} = \{\emptyset\}$. They will both be in the set of ideals. Is this correct?

I build a lattice from a poset, the lattice will be $(I_S,\subseteq)$ where $I_S$ is the set of all ideals of $S$. As I said before, the emptyset and the set containing the emptyset will be in $I_S$. If I were to draw the Hasse Diagram I would have an edge connecting $\{\} = \emptyset$ and $\{\{\}\} = \{\emptyset\}$ meaning that $\{\} = \emptyset$ is covered by $\{\{\}\} = \{\emptyset\}$. Is this right?

Thankyou

-
What definition of ideal are you using? – Patrick Feb 29 '12 at 4:28
In the link to the question.... there you will find the definition. OK, I will write the definition also here... wait a min, sorry – Andry Feb 29 '12 at 4:33
@Patrick: The definition that Andry is using is of what I’d call a lower set or simply a downward closed set. – Brian M. Scott Feb 29 '12 at 4:36
Yes, thanks Patrick. Ah Patrick could you please tell me what you think about the two definitions I found of Ideal? In the linked question there is also a community wiki I started about this little debate of before, remember? What do you think about the two definitions? – Andry Feb 29 '12 at 4:43

Yes, you need to treat $\varnothing$, the empty ideal, as a member of $I_S$, and yes, it’s different from $\{\varnothing\}$. I see the following ideals in your poset:

• Ideals with no members: $\varnothing$

• Ideals with one member: $\{\varnothing\}$

• Ideals with two members: $\{\varnothing,\{1\}\};\{\varnothing,\{2\}\};\{\varnothing,\{3\}\}$

• Ideals with three members: $$\Big\{\varnothing,\{1\},\{2\}\Big\};\Big\{\varnothing,\{1\},\{3\}\Big\};\Big\{\varnothing,\{2\},\{3\}\Big\}$$

• Ideals with four members: \begin{align*}&\Big\{\varnothing,\{1\},\{2\},\{3\}\Big\};\\ &\Big\{\varnothing,\{1\},\{2\},\{1,2\}\Big\};\Big\{\varnothing,\{2\},\{3\},\{2,3\}\Big\}\end{align*}

• Ideals with five members: $$\Big\{\varnothing,\{1\},\{2\},\{3\},\{1,2\}\Big\};\Big\{\varnothing,\{1\},\{2\},\{3\},\{2,3\}\Big\}$$

• Ideals with six members: $$\Big\{\varnothing,\{1\},\{2\},\{3\},\{1,2\},\{2,3\}\Big\}$$

• Ideals with seven members: $S$

(You should double-check, however, as I did this fairly quickly and might have missed something.)

Added: If I’ve made no mistakes, here’s the Hasse diagram of the lattice; the number by a vertex is the number of elements in the ideal represented by that vertex.

                                      o 7
|
o 6
/ \
/   \
5 o     o 5
/|\   /|\
/ | \ / | \
4 o  |  o4 |  o 4
|  | / \ |  |
|  |/   \|  |
|  /     \  |
| /|     |\ |
|/  \   /  \|
3 o    \ /    o 3
|\    o3   /|
| \  / \  / |
|  \/   \/  |
|  /\   /\  |
| /  \ /  \ |
|/    o2   \|
2 o     |     o 2
\    |    /
\   |   /
\  |  /
\ | /
o 1
|
o 0

-
OK, wait a moment Brian, sorry for disturbing again, but actually I cannot understand how you are building the lattice. Shouldnt I consider all possible subsets in $S$? – Andry Feb 29 '12 at 5:54
Ah, ok some of ideals are equal... is it correct??? – Andry Feb 29 '12 at 6:11
@Andry: Only some of the subsets of $S$ are ideals, and it’s only those subsets that you want to consider. For instance, $\{\{1\}\}$ is a subset of $S$, but it’s not an ideal of $S$, so you don’t care about it. – Brian M. Scott Feb 29 '12 at 6:28
In your example, subset $\{\{1\}\}$ when considered generates as ideal element $\{\emptyset,\{1\}\}$ right? So ideals for all subsets in poset are not distinct, some of them are the same and for this reason I do not have $2^{|S|}$ ideals but a less number of them. – Andry Feb 29 '12 at 6:34
@Andry: Okay, if you’re considering each subset of $S$ and looking at the ideal generated by it, that’s fine. And you’re right: two different subsets can generate exactly the same ideal. – Brian M. Scott Feb 29 '12 at 6:38