2
$\begingroup$

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, let`s 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?

What about Hasse Diagram?

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

  • 0
    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?2012-02-29

1 Answers 1

3

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 
  • 0
    @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.2012-02-29