User talk:Lord Farin/Backup/Definition:Join (Order Theory)

From ProofWiki
Jump to navigation Jump to search

Unique supremum

Is it necessary to remind the reader that the supremum is unique? If necessary it can be linked to from Supremum and Infimum are Unique but I think the page would be better uncluttered. --prime mover (talk) 21:17, 16 December 2012 (UTC)

I don't feel strongly about it. --Dfeuer (talk) 22:13, 16 December 2012 (UTC)

Relationship to Definition:Semilattice

Semilattice is currently defined only algebraically. We need to offer an order-theoretic definition of a semilattice, show that it's equivalent to the algebraic definition, and properly connect join semilattice and meet semilattice to semilattice. --Dfeuer (talk) 22:13, 16 December 2012 (UTC)

What are you waiting for? --prime mover (talk) 22:17, 16 December 2012 (UTC)

Some organization and related issues

The term join can be used in any ordered set to refer to the supremum of any set $\{a,b\}$ when such a supremum exists. On a set in which any two elements have a join, the set itself can be said to have a join operation, which has a nice relationship with an algebraic definition. The problem is that one definition is inherently broader than the other, and I'm not quite sure how to handle this. Certainly the narrower definition (join as a (total) binary operation) is the more important one by far, but I'm not sure how to make the distinction clear, separate the things that need separating, etc. --Dfeuer (talk) 18:06, 17 December 2012 (UTC)

If the join is just the supremum, why bother with that definition at all? If:
a) the join is defined only when the supremum of $\{a,b\}$ exists
b) the supremum of $\{a,b\}$ exists for all $\{a,b\}$ when the set they are in is a lattice
then the definition is tantamount to the same thing, innit.
What do your source works say? --prime mover (talk) 18:11, 17 December 2012 (UTC)

Having read what you just put ...

... it appears that definition 2 is a more general definition than definition 1. It's putting a name on a general commutative, associative, idempotent operation. This means that both $\cup$ and $\cap$ are joins. It means a meet is a join.

Sheesh. That looks pretty damn bogus to me. What are you using for a source work? --prime mover (talk) 18:15, 17 December 2012 (UTC)

Prime.mover, any commutative, associative, idempotent operation $\vee$ induces an order $a \preceq b \iff a \vee b = b$ in which $\sup \{a,b\} = a \vee b$ for any $a$ and $b$. They're entirely equivalent in that regard. The only reason to deal with what I called the broader notion is to capture situations where people use $a \vee b$ to mean the supremum of $\{a,b\}$, whether or not $a$ and $b$ are in a join semilattice. --Dfeuer (talk) 18:19, 17 December 2012 (UTC)
As for the "any meet is a join", yes, that's true, it can be considered a join, inducing the opposite order. --Dfeuer (talk) 18:20, 17 December 2012 (UTC)

I meant to put this in too.

I have been struggling with this in the past (when dealing with category theory, where duality also crops up naturally (in fact, join-meet duality probably is an instance of that)) and didn't manage to come up with a satisfactory solution. Ideally there would be an easy way to dualize a theorem or definition; however, any method I come up with is essentially no better than a properly linked pair of pages, something along the lines "The dual to this result is Blabla." If you have ideas on how to approach this without tedious duplication and hence copy-paste work, I'd love to hear them.


I say again, what are you using as a source work? --prime mover (talk) 19:20, 17 December 2012 (UTC)
Although I started out reading things on that other wiki, you'll see similar definitions in, say, [1]. In fact, just google "join semilattice".
The essential structure is a semilattice. Depending on whether you choose to call its operation a join or a meet determines whether you have a "join semilattice" or a "meet semilattice", and determines which of the two natural orderings you use. --Dfeuer (talk) 19:36, 17 December 2012 (UTC)

Definitive source: MacLane and Birkhoff

They write:

Definition: A set with a single binary operation which is idempotent, commutative, and associative is called a semilattice.

Lemma 1 has the following immediate corollary; a dual corollary for joins also holds.

Corollary: Let $P$ be any poset in which any two elements have a meet. Then $P$ is a semilattice with respect to the binary operation $\wedge$.

Such semilattices are called meet-semilattices. Conversely:

Lemma 5. If $S$ is a semilattice under the binary operation $\square$, the definition

$x \le y \iff x \square y = x$

makes $S$ a poset in which $x \square y = \operatorname{g.l.b.} \left\{{x,y}\right\}$.

My advice: first you get straight in your own understanding exactly what this area of mathematics is trying to communicate. You've gathered all sorts of random stuff from all over the internet, along with some work from an early book on the topic, and fairly clearly there's redundancy and contradictions and the same thing said different ways. Before you can put something coherent on this website you need to structure it consistently. Do that first and then when you yourself are not confused you'll know what it is you want to paste up.
As for me, I know nothing about this area (apart from the concept of sup and inf in the context of lattices, and its concretisation in the context of set theory, and the isomorphism between a general ordering on a set and a general subset of the power set of that set. Beyond that I haven't gone (more because in the books I have access to its not entered into in detail).--prime mover (talk) 21:20, 17 December 2012 (UTC)
These aspects aren't really complicated, and aside from what I've read in Kelley (who defines an ordering as a transitive relation with no further restrictions) things seem to be reasonably consistent. The point is that there are two ways to characterize a lattice or semilattice: either by specifying the joins and/or meets (which must satisfy certain axioms) or by specifying the ordering, which must satisfy other (simpler) ones. Given either characterization you can produce the other. It's true that my understanding of the significance is shallower than I would like (particularly on the algebraic side of it) but I think I have a clear understanding of what these structures are. --Dfeuer (talk) 22:23, 17 December 2012 (UTC)
Don't know, I'm afraid. As I say, haven't studied it. All I can say is: familiarise yourself with the rest of this site (or sufficient for you to know how this sort of thing is currently treated) and do the same sort of thing. --prime mover (talk) 22:35, 17 December 2012 (UTC)

Partial reply

There's a lot of potential for ending up with a lot of duplication between Definition:Join of Subgroups, Definition:Meet, Definition:Semilattice, Definition:Join Semilattice, and Definition:Meet Semilattice, and perhaps Definition:Lattice. I'd like to minimize this to the extent possible. Do you have any suggestions? --Dfeuer (talk) 18:06, 17 December 2012 (UTC)

I have been struggling with this in the past (when dealing with category theory, where duality also crops up naturally (in fact, join-meet duality probably is an instance of that)) and didn't manage to come up with a satisfactory solution. Ideally there would be an easy way to dualize a theorem or definition; however, any method I come up with is essentially no better than a properly linked pair of pages, something along the lines "The dual to this result is Blabla." If you have ideas on how to approach this without tedious duplication and hence copy-paste work, I'd love to hear them.
I'd also like to hear/see it when you have ideas to integrate the duality references smoothly and prominently on a page (I feel that a mere link in the Also see section is insufficient). --Lord_Farin (talk) 19:47, 19 December 2012 (UTC)
As for the algebraic/order-theoretic interplay, I'll start creating stuff in my sandbox that ought to replace the current mess at some point. See User:Lord_Farin/Sandbox, under "Reworking of Meet/Join theory". --Lord_Farin (talk) 19:45, 19 December 2012 (UTC)
It's an interesting problem. I don't know anything to speak of about category theory, but yes, I've heard that duality is important there. One approach, which is rather invasive, would be to do things like create templates instead of pages for some of these things. So you might have a page reading just ((footheoremtemplate | join | meet | supremum | \sup | \ge)) and
((footheoremtemplate | meet | join | infimum | \inf | \le)), but I don't know if the wiki software can even handle substitutions within math, and in any case this approach is rather awkward. We could just choose one of each dual per theorem to have proofs, and let the other one just say it's a dual of so-and-so as proof, I suppose. --Dfeuer (talk) 23:32, 19 December 2012 (UTC)