Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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
add comment

1 Answer

up vote 3 down vote accepted

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
share|improve this answer
    
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$? –  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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.