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.

On page 16, Lattice Theory: Foundation, George Grätze(2011),

1.19 Show that a join-semilattice $(L; \lor)$ has breadth at most $n$, for a positive integer n, iff for every nonempty finite subset $X$ of $L$, there exists a nonempty $Y \subseteq X$ with at most $n$ elements such that $$\bigvee X = \bigvee Y$$

I don't know in which way we shall establish this equivalence by appealing to the definition of breadth, which is

Let $n$ be a positive integer. We say that an order $P$ has breadth at most $n$ if for all elements $x_0, x_1, x_2,……x_n, y_0, y_1,……y_n$,in $P$, if $x_i \leq y_j$ for all $i \neq j$ in $\{0, 1, ……,n\}$, then there exists $ i \in\{0, 1, ……,n\}$,such that $x_i \leq y_i$. The breadth of $P$, in notation, breadth$(P)$, is the least positive integer $n$ such that $P$ has breadth at most $n$ if such an $n$ exists.

Observe that this definition of breadth is selfdual. For an equivalent denition for a join-semilattice (or for a lattice), see Exercise 1.19

Besides the aforementioned exercise, I have difficulty in visualizing this concept, breadth of an order. I don't know the meaning of selfdual, either.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

$\newcommand{\br}{\operatorname{breadth}}$Let’s start by assuming that for every non-empty finite $X\subseteq L$ there is a non-empty $Y\subseteq X$ such that $|Y|\le n$ and $\bigvee Y=\bigvee X$. We want to show that $\br(L)\le n$, so suppose that we have elements $x_0,\dots,x_n,y_0,\dots,y_n\in L$ such that $x_i\le y_j$ whenever $i,j\in\{0,\dots,n\}$ and $i\ne j$. We want to show that there is a $k\in\{0,\dots,n\}$ such that $x_k\le y_k$.

Let $X=\{x_0,\dots,x_n\}$; by hypothesis there is a non-empty $Z\subseteq X$ such that $|Z|\le n$ and $\bigvee Z=\bigvee X$. Since $|Z|\le n$, there is a $k\in\{0,\dots,n\}$ such that $x_k\notin Z$. For each $x_i\in Z$ we have $i\ne k$ and therefore $x_i\le y_k$, so $x_k\le\bigvee X=\bigvee Z\le y_k$, and we’re done: $x_k\le y_k$.

You can prove the other direction by induction on $|X|$. Assume that $\br(L)\le n$. It’s certainly true that if $|X|\le n$, then there is a non-empty $Y\subseteq X$ such that $|Y|\le n$ and $\bigvee Y=\bigvee X$: just take $Y=X$.

Now suppose that $|X|=n+1$, and let $X=\{x_0,\dots,x_n\}$. For $j\in\{0,\dots,n\}$ let $$y_j=\bigvee \left(X\setminus\{x_j\}\right)\;;$$ clearly this definition ensures that $x_i\le y_j$ whenever $i,j\in\{0,\dots,n\}$ and $i\ne j$. Since $\br(L)\le n$, there is a $k\in\{0,\dots,n\}$ such that $x_k\le y_k$ for some $k\in\{0,\dots,n\}$. Then $$x_k\le\bigvee\left(X\setminus\{x_k\}\right)\;,$$ so $$\bigvee X=\bigvee\left(X\setminus\{x_k\}\right)\;,$$ and we can take $Y=X\setminus\{x_k\}$.

Now suppose that $m>n+1$, and for each non-empty $X\subseteq L$ with $|X|<m$ there is a non-empty $Y\subseteq X$ such that $|Y|\le n$ and $\bigvee Y=\bigvee X$. Let $X$ be a subset of $L$ of cardinality $m$; we show that there is a non-empty $Y\subseteq X$ such that $|Y|\le n$ and $\bigvee Y=\bigvee X$. Fix $x\in X$, and let $X_0=X\setminus\{x\}$. By the induction hypothesis there is an $X_1\subseteq X_0$ such that $|X_1|\le n$ and $\bigvee X_1=\bigvee X_0$. Let $X_2=X_1\cup\{x\}$. Clearly $\bigvee X_2=\bigvee X$, so if $|X_2|\le n$, we’re done. Otherwise, $|X_2|=n+1$, and we just proved the result for that case. The theorem now follows by induction.


To say that the definition of breadth is selfdual is to say that replacing the definition by its dual does not change the concept. The definition of breadth:

An order $P$ has breadth at most $n$ if for all elements $x_0,\dots,x_n,y_n,\dots,y_n\in P$, if $x_i\le y_j$ for all $i,j\in\{0,\dots,n\}$ with $i\ne j$, then there is a $k\in\{0,\dots,n\}$ such that $x_k\le y_k$.

The dual definition:

An order $P$ has dual-breadth at most $n$ if for all elements $x_0,\dots,x_n,y_n,\dots,y_n\in P$, if $x_i\ge y_j$ for all $i,j\in\{0,\dots,n\}$ with $i\ne j$, then there is a $k\in\{0,\dots,n\}$ such that $x_k\ge y_k$.

If you interchange $x_i$ and $y_i$ for each $i\in\{0,\dots,n\}$, you transform each of these definitions into the other. Thus, they actually say the same thing and define the same concept: what I called dual-breadth is just breadth.

share|improve this answer
    
Thank you very much,sir!It's amazing (from my persepective) that the self-duality is far less obvious in the alternative defintion. –  Metta World Peace Jan 5 '13 at 10:49
    
@MettaWorldPeace: You’re welcome. (And I have to agree about it being less obvious in the form.) –  Brian M. Scott Jan 5 '13 at 15:01

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.