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

  • 1
    What definition of ideal are you using?2012-02-29
  • 0
    In the link to the question.... there you will find the definition. OK, I will write the definition also here... wait a min, sorry2012-02-29
  • 0
    @Patrick: The definition that Andry is using is of what I’d call a *lower set* or simply a *downward closed* set.2012-02-29
  • 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
    OK, wait a moment Brian, sorry for disturbing again, but actually I cannot understand how you are building the lattice. Shouldn`t I consider all possible subsets in $S$?2012-02-29
  • 0
    Ah, ok some of ideals are equal... is it correct???2012-02-29
  • 0
    @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.2012-02-29
  • 0
    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.2012-02-29
  • 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