## You are here

Homeirredundant

## Primary tabs

# irredundant

Definition. Let $L$ be a lattice. A finite join

$a_{1}\vee a_{2}\vee\cdots\vee a_{n}$ |

of elements in $L$ is said to be *irredundant* if one can not delete an element from from the join without resulting in a smaller join. In other words,

$\bigvee\{a_{j}\mid j\neq i\}<a_{1}\vee a_{2}\vee\cdots\vee a_{n}$ |

for all $i=1,\ldots,n$.

If the join is not irredundant, it is *redundant*

*Irredundant meets* are dually defined.

Remark. The definitions above can be extended to the case where the join (or meet) is taken over an infinite number of elements, provided that the join (or meet) exists.

Example. In the lattice of all subsets (ordered by inclusion) of $\mathbb{Z}$, the set of all integers, the join

$\mathbb{Z}=\bigvee\{p\mathbb{Z}\mid p\mbox{ is prime}\}$ |

is irredudant. Another irredundant join representation of $\mathbb{Z}$ is just the join of all atoms, the singletons consisting of the individual elements of $\mathbb{Z}$. However,

$\mathbb{Z}=\bigvee\{n\mathbb{Z}\mid n\mbox{ is any positive integer}\}$ |

is redundant, since $n\mathbb{Z}$ can be removed whenever $n$ is a composite number. The join of all doubletons is also redundant, for $\{a,b\}\leq\{a,c\}\vee\{c,b\}$, for any $c\notin\{a,b\}$.

Definition. An element in a lattice is *join irredundant* if it can not be written as a redundant join of elements. Dually, an element is *meet irredundant* if each of its representation as a meet of elements is irredundant.

Example. In the two lattice diagrams (Hasse diagram) below,

$\xymatrix{&1\ar@{-}[ld]\ar@{-}[rd]\ar@{-}[d]\\ a\ar@{-}[rd]&b\ar@{-}[d]&c\ar@{-}[ld]\\ &0}\xymatrix{&1\ar@{-}[ld]\ar@{-}[rd]\\ a\ar@{-}[rd]&&b\ar@{-}[ld]\\ &0}$ |

The $1$ on the left diagram is not join irredundant, since $1=a\vee b\vee c=a\vee b$. On the other hand, the $1$ on the right is join irredundant. Similarly, the $0$ on the right is not meet irredundant, while the corresponding one on the right is.

## Mathematics Subject Classification

06B05*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections