Talk:Join and meet

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated C-class, Mid-priority)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
C Class
Mid Priority
 Field:  Discrete mathematics

Changed redirect[edit]

I changed this from a redirect to Lattice (order) to an article. Cf. Talk:Join (mathematics) for further discussion. JoergenB 20:05, 21 September 2006 (UTC)

Some examples would greatly enhance this entry. Harry Metcalfe 12:39, 19 January 2007 (UTC)

Explain these names?[edit]

Could someone please explain how these common English words "join" and "meet" came to stand for "least upper bound" and "greatest lower bound"? On the face of it, they don't seem the slightest bit intuitive as names for these concepts. I have some hope that an explanation for this naming might aid in remembering what they refer to. Gwideman (talk) 00:12, 23 August 2012 (UTC)

Probably from the Boolean algebra: if the elements of your poset are sets, the join is the union (what you get when you join them together) and the meet is the intersection (where they meet). The notations (which are otherwise regrettable) reinforce this. I do not know off-hand of a reliable source for this. --JBL (talk) 00:53, 23 August 2012 (UTC)
Ah, that sounds plausible for some particular cases, as you point out. Thanks. Gwideman (talk) 09:23, 24 August 2012 (UTC)

Subsets[edit]

This article talks about sets when it should be talking about subsets. The concepts of suprema and infima only make sense when you are talking about subsets, otherwise you may as well be talking about maximal and minimal elements. (Of course, a subset of a set may be the set itself but that is a special case.) — Preceding unsigned comment added by Eptified (talkcontribs) 02:24, 22 June 2013 (UTC)

Nonsense. As usual, when you attempt to talk about mathematical concepts. — Arthur Rubin (talk) 07:19, 24 June 2013 (UTC)
Please comment on the content not the contributor. Spectral sequence (talk) 18:48, 5 July 2013 (UTC)

In the introduction it says: "The join/meet of a subset of a totally ordered set is simply its maximal/minimal element.", what's the point of that? supremum and infimum are stronger 192.76.172.10 (talk) 17:47, 16 May 2014 (UTC)

Idempotency vs reflexivity[edit]

It seems that the standard terminology for an operation with the property xx = x is idempotence [1]: in this context it is a consequence of the reflexivity of the partial order. Spectral sequence (talk) 18:48, 5 July 2013 (UTC)

I donated all my lattice theory textbooks in one of the few moves, so I can assert is that I have never seen xx = x referred to has reflexivity. As I noted on one of the talk pages, there is a difference between an element being idempotent (that is, a specific x satisfies x op x = x), and the idempotency of the operation op (that is, for x in the domain, x op x = x), but the same term is used for both. — Arthur Rubin (talk) 21:41, 5 July 2013 (UTC)
Spectral sequence and Arthur Rubin are correct. "Idempotent" is the proper way to describe combining x with x to obtain x. Notice that such a combination is an instance of a ternary relation. "Reflexive" is a possible property of binary relations, not ternary relations. JRSpriggs (talk) 05:57, 6 July 2013 (UTC)
Some reliable sources for the use of "idempotent" or "idempotency" in this context:
  • Rutherford, D.E. (1965). Introduction to lattice theory. Edinburgh-London: Oliver & Boyd. p. 6. Zbl 0127.24904. 
"xx = x, xx = x (idempotent laws)"
"xx = x (idempotency laws)"
Spectral sequence (talk) 11:01, 6 July 2013 (UTC)

Link back to ordered sets[edit]

The text says Partially ordered sets are categorized by the existence/non-existence of joins/meets for each pair of elements. Should this read charatcterised, and is it correct? The assertion appears to be that if a set has binary operations join and meet satisfying certain properties, then a partial order can be defined on it. What are those conditions, and what is the reference? Spectral sequence (talk) 11:23, 6 July 2013 (UTC)

See Semilattice:
Join and meet are associative, commutative, idempotent binary operations, and any such operation induces a partial order (and the respective inverse order) such that the result of the operation for any two elements is the least upper bound (or greatest lower bound) of the elements with respect to this partial order.
And in Semilattice#Connection between both definitions:
An order theoretic meet-semilattice S, ≤〉 gives rise to a binary operation ∧ such that S, ∧〉 is an algebraic meet-semilattice. Conversely, the meet-semilattice S, ∧〉 gives rise to a binary relation ≤ that partially orders S in the following way: for all elements x and y in S, x y if and only if x = x y.
The relation ≤ introduced in this way defines a partial ordering from which the binary operation ∧ may be recovered. Conversely, the order induced by the algebraically defined semilattice S, ∧〉 coincides with that induced by ≤.
See e.g. Vickers, Steven (1989). Topology via Logic. Cambridge University Press. ISBN 0-521-36062-5. Tobias Bergemann (talk) 13:32, 6 July 2013 (UTC)
(Replying to self.) Stupid me, Join and meet#Universal algebra approach and Join and meet#Equivalence of approaches already say this. I was confused by having both pages open side by side. —Tobias Bergemann (talk) 14:33, 6 July 2013 (UTC)
And the citation for all of this? I'll say right now that it does not appear to be in Vickers (1989). Spectral sequence (talk) 15:49, 6 July 2013 (UTC)
You are right, I was confused by the presentation in chapters 3.3 and 3.4 in Vickers' book. On page 16 there is the sentence "The significance of this proposition is that if we define ∧ or ∨ independently, as algebraic operators, then it tells us how we have to define ≤ to have any hope of recovering ∧ or ∨ as actual meets or joins." But it never is made explicit. Sorry.
There is however Theorem 2.10 on page 40 in Davey, B. A.; Priestley, H. A. (2002). Introduction to Lattices and Order (second ed.). Cambridge University Press. ISBN 0-521-78451-4. 
Tobias Bergemann (talk) 17:07, 6 July 2013 (UTC)
Indeed, but absorbency is one of the conditions in D&P (L4/L4∂) and not mentioned here. Spectral sequence (talk) 17:17, 6 July 2013 (UTC)
You are right. While the absorption laws are not used to prove 2.10(ii) and 2.10(iii), this isn't stated explicitly. So, off-hand, I don't have a citation for these claims. —Tobias Bergemann (talk) 17:48, 6 July 2013 (UTC)
Part of the problem is that the statement in such broad generality is not true. For example, consider a three element set {x,y,z} and define a meet operation ∘ by x∘x=x, y∘y=y, z∘z=z and x∘y=y∘x=x, y∘z=z∘y=y. This is commutative, associative and idempotent but does not define an order: defining uvu∘v=u implies that xy and yz but does not imply that xz. The best that one can say is that ≤ is a pre-order. I expect, but have not worked out the details, that the transitive closure of ≤ is an order ≪ and the meet operation ∧ associated with ≪ is the smallest meet semilattice containing the original operation °. So in terms of partial binary operations ordered by refinement and preorders again ordered by refinement there would be a Galois connection in which the closed sets were the semilattices and the orders. However I have no reference for any of that. Spectral sequence (talk) 09:22, 7 July 2013 (UTC)
I'm not sure I understand your example. For the operation you defined to be associative, commutative and idempotent you need xz=zx=x (because of x∘(yz)=xy=x and (xy)∘z=xz), and so you get xz because xz = x.
And the statement in such broad generality most certainly is true:
  • You get reflexivity of ≤ (xx for all x) from the idempotency of ∘ (xx=x for all x).
  • You get antisymmetry of ≤ (xy and yx together imply x=y) from the commutativity of ∘:
    • xyxy=x (by definition of ≤)
    • yxyx=y (by definition of ≤)
    • xy=yx (commutativity of ∘)
  • You get transitivity of ≤ (xy and yz together imply xz) from the associativity of ∘:
    • xyxy=x (by definition of ≤)
    • yzyz=y (by definition of ≤)
    • x∘(yz) = xy = x
    • (xy)∘z = xz
    • x∘(yz) = (xy)∘z (associativity of ∘)
    • Therefore x = xz, and so xz.
  • To show that xy is a lower bound of {x,y} we have to show both xyx and xyy, i.e. we have to show both (xy)∘x = xy and (xy)∘y = xy. The first is true because (xy)∘x = (yx)∘x (commutativity of ∘) = y∘(xx) (associativity of ∘) = yx (idempotency of ∘) = xy (commutativity of ∘). The second is true because (xy)∘y = x∘(yy) (associativity of ∘) = xy (idempotency of ∘).
  • To show that xy is a/the greatest lower bound of {x,y} we have to show that zx and zy together imply zxy:
    • zxzx=z (by definition of ≤)
    • zyzy=z (by definition of ≤)
    • zxy is true iff z∘(xy) = z, by definition of ≤. Now, z∘(xy) = (zx)∘y (associativity of ∘) = zy = z
Or perhaps I am even more confused than usual?
Tobias Bergemann (talk) 11:24, 7 July 2013 (UTC)
I think there's confusion over what associativity means for partial operations. I'm taking it to mean that if both sides exist then they are equal: you're taking it to mean that if one side exists so does the other and they are equal. Spectral sequence (talk) 11:55, 7 July 2013 (UTC)