Talk:Lattice (order)

From Wikipedia, the free encyclopedia

Mathematics Portal

This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.

Mathematics rating:

B Class

High Priority

Field: Foundations, logic, and set theory

Please update this rating as the article progresses, or if the rating is inaccurate. Click to show/hide comments.
Please add to or update the comments to suggest improvements to the article.
Geometry guy 00:36, 23 June 2007 (UTC)

1 Map of lattices
2 Non-negative integers
3 Examples?
4 Top and bottom
5 Idempotent laws as a consequence ?
6 Dual lattices
7 Applications?
8 It is not lattice on picture
9 Acyclic?
10 Morphisms
11 Free lattice
12 Conditions for a poset to be a Lattice
13 Examples of posets which are not lattices
14 Partially ordered set or poset

[edit] Map of lattices

For the moment, I have added a "See also" link to my Map of lattices. It may be useful to have it figure more prominently in this article in the future.

I have transferred the discussion on the content of the map (as opposed to how to use it) to its talk page.

[edit] Non-negative integers

The list of examples of complete lattices contains this item:

The non-negative integers, ordered by divisibility. The supremum is given by the least common multiple and the infimum by the greatest common divisor.

What is the least common multiple of an infinite set of non-negative integers? How is this lattice then complete? It's not even bounded, is it? Am I missing something? Also, the issue of completeness aside, should that be positive integers?

Or have I just answered my own question? Zero could be considered the least common multiple of an infinite set, and a bound on the lattice. But then least here doesn't refer to the usual ordering of the integers, or zero, if considered a multiple of everything, would be the least common multiple of every set. Perhaps a little more explanation is in order Josh Cherry 23:26, 8 Jul 2004 (UTC)

Yes, that is basically correct: "least" and "greatest" refer to the given order of divisibility, not to the normal total order of integers. 0 is then the greatest element: it is divided by any number. 1 is least: it divides any number. Infinite sets have only 0 as an upper bound, while they may have numbers other than 1 as a lower bound (like 2 in the case of all even numbers). I will add some remarks... --Markus Krötzsch 14:57, 15 Jul 2004 (UTC)

Cool, thanks. I added a sentence to that section. Please verify that it's correct. Josh Cherry 22:15, 15 Jul 2004 (UTC)

Yep, that's true. --Markus Krötzsch 14:03, 20 Jul 2004 (UTC)

[edit] Examples?

I've moved the following "Examples" section to here for reasons stated below:

* For any set A, the collection of all finite subsets of A (including the empty set) can be ordered via subset inclusion to obtain a lattice.

* The natural numbers in their common order are a lattice.

* None of the above lattices is bounded. However, any complete lattice especially is a bounded lattice.

* The set of compact elements of an arithmetic (complete) lattice is a lattice with a least element.

Reasons for move:

The statement "None (neither?) of the above lattices is bounded." is not correct for the first example if A is finite. (I presume that the first example was meant to have A infinite?)
I don't understand the fourth example, what is an arithmetic (complete) lattice, is this defined somewhere? Why is complete in parenthesis? Is it meant to define arithmetic?
The placement of this section seems out of place to me. I think the examples of unbounded lattices should be closer to where bounded is mentioned. Same goes for the observation that every complete lattice is necessarily bounded.
Although I think this content should be included in the article, since I couldn't quite make out how to fix it, I've moved it here for someone else to have a look at. ;-)

Paul August 18:16, Sep 3, 2004 (UTC)

Agreed, some things here needed reconsideration. I put the list back into the article after the following fixes (refering to your comments):

True.
True: the article on arithmetic lattices needs to be written. It is a concept from domain theory, basically an algebraic lattice (i.e. a Scott domain that is a complete lattice) where the compact elements form a lattice. "Algebraic" and "arithmetic" is usually assumed to imply "complete" when applied to a lattice. Since this is not always the case, I added the term in parentheses.
Yes, I moved it upwards. The downside i, that some properties are only defined afterwards, but eventually all of these special lattices should have their own articles (including examples) anyway.
Well, a reasonable choice. However, I feel that there should be some prominent "examples" section in such an article (in the worst case just with a remark), in order to give newcomers a place to add some nice examples (Possible course of events: someone finds a reference to lattices without knowing the details, looks up the net, finds Wikipedia, and may want to contribute the example that caused her search in the first place -- I'm always optimistic ;-).

--Markus Krötzsch 20:45, 14 Oct 2004 (UTC)

Much better ;-). Paul August 21:13, Oct 14, 2004 (UTC)

[edit] Top and bottom

I'm surprised this article doesn't talk about top and bottom anywhere, although it does use the terms (with no defining link). Are these described elsewhere or this something that should be added? Deco 18:52, 16 December 2005 (UTC)

Those are not technical terms. I guess someone used those terms to try to be friendlier to laymen. The definition of bounded lattice can be found later down the article: a bounded lattice is a lattice with a least and greatest element. The words "top" and "bottom" are more or less meaningless. Maybe they make sense when you have the Hasse diagram of the lattice in front of you, vertically aligned. -lethe ^talk 19:12, 16 December 2005 (UTC)

Well, I've encounter them a lot in classes and such. They seem to be conventional names for the least and greatest element of a bounded lattice, in the same way that p is a conventional name for a positive prime integer. I think they're frequently used enough to justify mentioning, at least in passing. Deco 20:37, 16 December 2005 (UTC)

I've never heard that before in my life, though surely there are a lot of things I've never heard of. But can you tell me a textbook that uses that terminology, if you know one off-hand? I'd like to see it for myself. -lethe ^talk 21:08, 16 December 2005 (UTC)

Davey and Priestley, Introduction to Lattices and Order (ISBN 0521784514) uses top and bottom. As far as I now they are in fact technical terms, at least in domain theory and its applications to denotational semantics. — Tobias Bergemann 22:48, 16 December 2005 (UTC)

Also see greatest element. — Tobias Bergemann 22:58, 16 December 2005 (UTC)

Ah, that's why they're familiar to me. I encountered them in programming language semantics. I also encountered them studying compiler optimizations like sparse conditional constant propagation. Seems CS people like them. Deco 23:29, 16 December 2005 (UTC)

My readings so far in quantum physics and statistical mechanics and set theory and such has led me to seriously wonder whether how much of quantum physics actually knows of mathematics. When I saw top and bottom I jumped right in to find out whether, as one would maybe expect, the quark model people knew full well what top and bottom were when they labelled the top quark and the bottom quark.

If it is true that top and bottom as in quarks does not relate to top and bottom as in lattices why do I have haunting vague hand-waving recollections of having recently read a lot of quantum physics that hand-waved in the direction of lattice and/or gauge theories? (Note: I am on lattice right now, have to get to guage soon, so dunno if gauge even had anything to do with lattice.

Basically what is bothering me is a haunting suspicion that cardinality and catastrophe and 'phase transitions' and such, that call for mysterious new 'bosons' mediated by coloured mediators and such, and mysteriously conjure mass into and out of existence, might be related. Markovianism is in the brew too: if each cardinality pretty much amounts to a markovian 'past events horizon' up to which all previous history is pretty much 'moot', a lattice might be precisely what the quark people are squeezing in between the bottom catastrophe (the cardinality below) and the top catastrophe (the cardinality above) of the tiny space in which they are waving their hands and invoking 'Quantum Mechanics' (maybe in one cardinality regime?) and 'Quantum Chromodynamics' (maybe in another cardinality regime) about?

Maybe I am just seeing too many coincidences? But cardinality also seems to potentially be referrable to orders of logic, and certainly the logic of quantum physics expositions that I have been reading does seem to involve different orders of logic. Cardinality might not be the right word, I am trying to refer to aleph null and upwards, the infinities that are whole orders above each other. Are quantum folk making lattices that bottom out at one of those infinity levels and top out at the next, something like that? Thus using the terms top and bottom from lattice theory?

If top and bottom do truly have nothing to do with quarks do please elucidate that fact.

Knotwork 05:25, 24 August 2006 (UTC)

I think it's even worse. As far as I know (I could be wrong, though), the lattice theories in physics have nothing at all to do with lattice (order), but are somehow related to lattice (group). Which is something entirely different. --Hans Adler (talk) 10:52, 18 April 2008 (UTC)

[edit] Idempotent laws as a consequence ?

This article states that the idempotent laws follow from the associative, commutative and absorption laws of a lattice. I think they don't. If anyone can construct a brief proof, please send it, otherwise the article should be corrected. Nidus 14:21, 17 February 2006 (UTC)

Nidus is quite right. The idempotent law is not a consequence of the others. Consider the counter example where $a \wedge b$ is the union of $a, b$ plus a single element $x$ and $a \vee b$ is the interesection of $a, b$ minus a single element $x$ . Verify that the associative, commutative and absorption laws hold but the idempotent doesn't. The article should be corrected! —The preceding unsigned comment was added by 130.130.37.6 (talk • contribs) 00:50, 23 March 2006 (UTC1)

A short proof of the idempotent laws: The first absorption law gives us $a = a \wedge (a \vee b)$ . Replacing $b$ with $a \wedge c$ we get $a = a \wedge (a \vee (a \wedge c))$ . Since $a \vee (a \wedge c) = a$ by the second absorption law we get $a = a \wedge a$ . The proof of the other idempotent law is dual to this one.

The absorption laws do not hold for the operation given in your counter example:

$S \wedge (S \vee T) = S \wedge (S \cup T \cup \{ x \}) = (S \cap (S \cup T \cup \{ x \}) - \{x\} = S - \{x\}$

So the absorption law does not hold if $x \in S$ . —Tobias Bergemann 13:40, 23 March 2006 (UTC)

I miss the argument why

b

can always be written as $a \wedge c$ .

In general there is no such and thus the article should be corrected.

Actually if we require distributivity the idempotent law can be prooven:

$a = a \vee (a \wedge a) = (a \vee a) \wedge (a \vee a)$

$a = a \wedge (a \vee a) = (a \wedge a) \vee (a \wedge a) = (a \vee (a \wedge a)) \wedge (a \vee (a \wedge a)) = ((a \vee a)) \wedge (a \vee a)) \wedge ((a \vee a) \wedge (a \vee a)) = a \wedge a$

—The preceding unsigned comment was added by 85.124.7.101 (talk)

You wrote: "I miss the argument why $b$ can always be written as $a \wedge c$ ." You don't need this, all you need is that $a = a \wedge (a \vee (a \wedge c))$ for every

a

and

c

, and this is true because $a = a \wedge (a \vee b)$ holds for every

a

and

b

and therefore specifically holds if $b=a \wedge c$ . —Tobias Bergemann 07:34, 2 May 2007 (UTC)

[edit] Dual lattices

If no one objects within a couple of days, I'll add a section on dual lattices (reversing the partial order, or, equivalently, substituting meet by join and vice versa). This duality is pretty obvious to any lattice theoretician, of course, but not necessarily so for the readers. It is interesting in itself, and I'd like to refer to it in order to clarify why e.g. meet-semilattices and join-semilattices coincide as abstract algebraic structures. I also found no other article dealing with this particular duality.

(Actually, it might be possible to outline connections to other kinds of duality. E.g., recall that if $(L,+,\cap)$ is the (modular) lattice of all subspaces of a finite-dimensional vector space V over a field k, then the dual lattice may be canonically identified with the lattice of subspaces to the dual vector space $V * =$ Hom $(V, k)$ , by letting W ∈L correspond to $\{ f \in V^* : f(W)=0 \}$ . However, I suspect that this would lead too far for the Lattice (order) article.) JoergenB 18:42, 21 September 2006 (UTC)

[edit] Applications?

Quoting: "Distributivity is too strong a condition for certain applications" Such as??? What is ment by applications? -kaz

[edit] It is not lattice on picture

Partially ordered set, shown on picture, is not a lattice! For example, elements 1234 and 12/2/4 have no infimum. Dims 05:20, 16 January 2007 (UTC)

Are you sure? If you mean 1234 and 12/3/4 then their infimum is 12/3/4 and their supremum is 1234 as 1234 > 12/3/4. --- Richard CHS^Talk 22:49, 18 January 2007 (UTC)

[edit] Acyclic?

Is a lattice necessarily acyclic? If so, that is a key fact that would be helpful to mention explicitly. Based on reading the definitions of supremum and infimum, I would assume that a lattice is acyclic, but not being well versed in this area of mathematics I would have to spend much more time reading and thinking it through to convince myself with certainty, so it would be nice to simply hear it from an expert. Of course, implicit here is the fact that I'm thinking of a lattice as a kind of graph, which I hope is a reasonable way to think about it, and one which I also think would be helpful to mention. Thanks. -- DBooth 21:40, 22 January 2007 (UTC)

It's easiest to see that they're acyclic by the requirement of partial-orders that a≤b and b≤a imply a=b. Combined with transitivity of the ordering relation, this means that a cycle of two or more distinct elements is impossible. -- Sswords 05:24, 26 January 2007 (UTC)

[edit] Morphisms

The article defines morphisms like this:

Given two lattices (L, $\vee$ , $\wedge$ ) and (M, $\cup$ , $\cap$ ), a homomorphism of lattices is a function f : L → M such that

f(x $\vee$ y) = f(x) $\cup$ f(y), and

f(x $\wedge$ y) = f(x) $\cap$ f(y).

Thus f is a homomorphism of the two underlying semilattices. If the lattices are bounded, then f should preserve the bounds so that:

f(0) = 0, and

f(1) = 1.

Is preservation of bounds part of the definition of morphism, or is it supposed to follow from the other two requirements? Wouldn't, say, f : {0,1} → {0,1} with f(x) = 1 be a counterexample?

Sswords 18:54, 25 January 2007 (UTC)

The preservation of bounds does not follow from the preservation of ordinary (i.e., binary) join and meet, as your counterexample shows. Actually, the more structure you add to your concept, the fewer of the functions will respect all of them. Thus, properly you should distinguish between "morphisms in the category of lattices", "morphisms in the category of bounded lattices", and "morphisms in the category of complete lattices", where you have joins and meets defined only for non-empty finite families of lattice elements, for all finite families, or for all families of any cardinality, respectively. (Technically, in this case the category with more structure is a subcategory of the one with less structure, but not an full subcategory. However, that is just a fancy way to sum up what we already said.)

You may also consider the lattice categories as non-full subcategories of the category of posets. Indeed, demanding only that meet be preserved, or only join, or only the partial order, yields different sets of morphisms between the same two lattices. I do not think that all this should be explained in the article, though. JoergenB 08:29, 25 February 2007 (UTC)

The primary examples of what JoergenB is talking about are frames and locales, which are cats both having the same object, but having different morphisms. linas 14:20, 8 June 2007 (UTC)

[edit] Free lattice

I'm thinking of moving the section called "free lattice" to its own article; would there be objections to that? linas 16:40, 6 April 2007 (UTC)

I'm gonna do it, unless someone says no...linas 04:34, 19 April 2007 (UTC)

Done. See Free lattice. linas 14:18, 8 June 2007 (UTC)

[edit] Conditions for a poset to be a Lattice

I'm not a mathematician at all, but I'm dealing with a physical model that can be viewed as a poset - yet I'm not certain at all if it is a lattice.
The graph structures produced are always most disordered and complex, and it's not easy to grasp if inf{} and sup{} do exist always.
I was wondering if some rule of thumb exists, to judge the lattic-ity of a poset.
E.g. if a poset is 1) connected and 2) does not exhibit a "butterfly" pattern (fig.2.1(ii) in "Introduction to Lattices and Order") is it a lattice?

references:
G. Bertotti, P. Bortolotti, A. Magni, V. Basso Topological and energetic aspects of the random-field Ising model J.App.Phys.101(2007)09D508
P.Bortolotti, A.Magni, V.Basso, G.Bertotti Dynamical-system theory approach to the study of metastable states in the random field Ising model J.Magn.Magn.Mat. 310(2007)1543-1545

thanks for any hint, 193.204.114.65 10:07, 7 August 2007 (UTC) Alessandro Magni

[edit] Examples of posets which are not lattices

I want examples of (infinite) partially ordered sets which are not lattices and even not semilattices.

porton (talk) 18:10, 28 November 2007 (UTC)

The purpose of this page is to discuss improvements to the article. This question belongs on Wikipedia:Reference desk/Mathematics instead. Michael Slone (talk) 20:26, 28 November 2007 (UTC)

Or there is an other type of lattice.This lattice is where your are doing mutiplication. You are going to set up the problem like a window and then after that you will cut each little square. After that you will put the number(s) on top of the square and then the other number(s) will go on the side and you will start the problem.when you are doing multiplication you will times the numbers and add all of them together and you will get you'r factor. —Preceding unsigned comment added by 69.239.138.181 (talk) 01:22, 14 February 2008 (UTC)

That's Lattice multiplication and it has very little to do with the theory of partially ordered sets. —David Eppstein (talk) 01:25, 14 February 2008 (UTC)

[edit] Partially ordered set or poset

"In mathematics, a lattice is a partially ordered set (or poset)": Ambiguous? I am guessing that it means "In mathematics, a lattice is a partially ordered set (a poset)" but I have not the expert knowledge of the topic necessary to be certain that is in fact what it means, rather than what it well might, taken as English, mean, to wit that it is EITHER a partially ordered set (see explanatory link if not sure what that means) OR a poset (oops no clickability of this term so no idea what the heck does it mean).

My immediate impulse as a Wikipedia Proofreader was to edit it to change 'or' to 'a' in order to make it less susceptible to being interpreted the wrong way, aka IMO to make it 'less ambiguous' aka 'more clear'. But what if the author already did this soul-searching, determined with mathematical rigour that 'a' would be incorrect, that 'or' is correct, yet somehow managed to neglect to make 'poset' an active hyperlink? I guess the reader should first search for themselves to discover whether there is or is not an entry in the Wikipedia explaining what a poset is? Maybe I should do that search and if such a page exists make 'poset' an active link?

I dunno, would using 'a' instead of 'or' be such an awful thing that all this extra work is preferable to using the term 'a' instead of the term 'or' ???

Knotwork (talk) 09:20, 18 April 2008 (UTC)

Fixed. I have also moved your comment down and added a title. It's better to use the little "+" at the top of the talk page to start a new topic. --Hans Adler (talk) 10:46, 18 April 2008 (UTC)