While playing around with least-fixed-point constructions on a powerset lattice, I've found this property to be useful. Let's say that $F : \mathcal{P(U)} \to \mathcal{P(U)}$, and that $A \subseteq F(A)$ for all $A \in \mathcal{P(U)}$. What's the name of this property $A \subseteq F(A)$? I've read that $F$ is sometimes called "monotone" or "isotone," but I can't Google for those terms without running into the wrong definitions (i.e. what most call monotone: $A \subseteq B \implies F(A) \subseteq F(B)$).
What's the name of this function property?
1 Answers
A map $F\colon\mathcal{P}(X)\to\mathcal{P}(X)$ is said to be increasing if $A\subseteq F(A)$ for all $A\in\mathcal{P}(X)$.
The map is said to be isotone if $A\subseteq B$ implies $F(A)\subseteq F(B)$.
E.g., see Lemma 5.3.1 and Definition 5.3.2 in George Bergman's An Invitation to General Algebra and Universal Constructions. (Link is to the PDF of Chapter 5; the definitions are on page 16 of that document, which corresponds to page 140 of the book; other parts of the book can be accessed through the links in this page.)
(Other common properties are decreasing, if $F(A)\subseteq A$ for all $A$; and idempotent, if $F(F(A)) = F(A)$ for all $A$. A map $F$ is a closure operator if it is increasing, isotone, and idempotent; and it is an interior operator if it is decreasing, isotone, and idempotent.)
-
0I think there should be a word added on the Knaster-Tarski theorem, don't you? :-) – 2011-05-08
-
0Thanks for the quick answer! I guess I'm expecting too much of English, because most hits for "increasing" take it to mean what you called "isotone". Also, I've just discovered that what you called "increasing" is also called "extensive," but most hits for "extensive" are talking about extensionality. Geez. – 2011-05-08
-
1@Neil: Google tends to be useless if you try to google a mathematical term that is a single common word without any context. Google "interior", and good luck finding a link that gives you the interior of a set in topology! On the other hand, googling "interior" *and* "topology" gives it to you in the top link. "Increasing", "isotone", and "extensive" are overloaded words, but there you are. – 2011-05-08
-
0@Asaf: I'm not sure I understand... – 2011-05-08
-
0@Asaf: I'm totally down with Mr. Knaster and Mr. Tarski. But I'm after a more constructive fixed point - one that's built "from below" by transfinite recursion instead of "from above" by an intersection. Most of what I find on fixed-point theory uses continuity (supremum/join/union-preserving) to do it, but I don't think I have continuity. – 2011-05-08
-
0@Neil: The construction from above and from below are described in the Wikipedia page of the **Knaster-Tarski theorem** (Arturo, you might want to check it out). You don't need to use transfinite recursion. You can take all the sets which have a certain property, their union will be the the maximal fixed point of $F$. – 2011-05-08
-
0@Asaf: I saw the page; I just don't understand what you mean by "a word added on the Knaster-Tarski theorem"; if you mean adding something to the page, what? "Order-preserving" is a perfectly good term, probably better than "isotone" (which likely has some historical reason for being...) – 2011-05-08
-
0@Arturo: It seems very clear to me that the OP had some aim towards their theorem, one way or another. By the comment he made above I believe I was correct as well. I thought that reminding this theorem fits into the answer (as well as it would also fit into the question, coming to think about it). – 2011-05-08
-
0@Asaf:
Oh, I see. Well, you've added the word, so that's that. (-: – 2011-05-08