3
$\begingroup$

[Attention! This question requires some reading and it's answer probably is in form of a "soft-answer", i.e. it can't be translated into a hard mathematical proposition. (I hope I haven't scared away all readers with this.)]

Consider the following three examples:

1) [If this example seems too technical just skip it - it isn't that important for the idea I want to convey.] The set $T$ of all terms (of a functional structure) is the set $$T=\bigcap_{O\text{ closed under concatenation with function symbols}}_{O\supseteq X} O,$$where $X$ is the (countable) of all variables and "closed under concatenation with function symbol" means: If $f$ is some function symbol of arity $n$ and $x_1,\ldots,x_n\in X$, then $fx_1\ldots x_n\in T$. The above $T$ is the smallest set such that it contains the variables and is closed under concatenation with function symbols.

2) The smallest subgroup $G$ of a group $X$, containing a set $A\subseteq X$, is the set $$G:=\bigcap_{O\ \text{ is a subgroup of $X$}}_{O\supseteq A} O.$$

3) The smallest $\sigma$-algebra $\mathcal{A}$ on a set $X$ containing a set $A\subseteq X$ is the set $$\mathcal{A}:=\bigcap_{O\ \text{ is a $\sigma$-algebra on $X$}}_{O\supseteq A} O.$$

4) The set $$C:=\bigcap_{O\ \text{ is open in $X$}}_{O\supseteq A} O,$$ where $X$ is a metric space and $A\subseteq X$ is arbitrary.

Now here's the thing: The sets $T$, $G$, and $\mathcal{A}$, from examples 1),2) and 3) are also closed under the closing condition defining them, i.e. $T$ is also closed under concatenation with function symbols, $G$ is also a group and $\mathcal{A}$ is also a $\sigma$-algebra; for $G$ and $\mathcal{A}$ this is already implied by their name (the smallest subgroup, the smallest $\sigma$*-algebra*), which was the reason I also gave $T$ as an example, where it's name doesn't already imply it's closure under it's defining closure operations. But the set $C$ from example 4) need not be open, if for example $\mathbb{R}=X$ and $A=[0,1]$ (maybe there are nontrivial metric space, where it is open for nontrivial sets $A$, but I didn't want to waste time checking that). That is, $C$ isn't closed (no pun intended) under the closing condition I used to define it; or differently said: There isn't a smallest open set containing $A$.

Notice that the closure conditions in 1) and 2) have a more algebraic character, since we close under some algebraic operations, where the closure condition in 3) as a more "set-theoretical-topology"-type character, since we close under set-theoretic operations. Nonetheless in all cases the outcome is again "closed".

My question is: How do generally (abstractly) "closing conditions" $\mathscr{C}$ have to look like such that the set $$ S:=\bigcap_{O\ \text{ is closed under $\mathscr{C}$}}_{O\supseteq A} O$$ is itself closed in $X$ under $\mathscr{C}$, where $A\subseteq X$ is an arbitrary set ? Differently said: How do generally (abstractly) "closing conditions" have to look like such that there is a smallest set being closed under these conditions, containing some arbitrary fixed set.

  • 0
    Yikes, when I first read this question, I thought I'd need to flag it for migration to the [meta.math.se](http://meta.math.stackexchange.com/) forum!2012-11-04
  • 0
    haha :) Maybe I should have said "criterion" instead of "condition" to make it sound more like mathematics-talk, but I think I'll leave it at "condition" for now.2012-11-04
  • 1
    Let $\mathscr{C}(X)$ be the family of subsets of $X$ that are closed under $\mathscr{C}$. What you need is simply that $\mathscr{C}(X)$ be closed under arbitrary intersections; I really doubt that one can say much more than that.2012-11-04
  • 0
    @BrianM.Scott Well, requiring that is a bit tautological I think, since I asked how $\mathscr{C}$ must be such that it is closed under intersection: If the answer is, that $\mathscr{C}X$ is closed under arbitrary intersection, that doesn't tell me anything about $\mathscr{C}$. What I'm looking is somewhat similar to the HSP theorem (also called Birkhoff's theorem) from model theory that tells me under which circumstances an algebraic structure (like a group) is *solely* defined by equations its element have to obey: Said circumstances being, that the algebraic structure has to be [...]2012-11-04
  • 0
    I know that it doesn’t tell you anything about $\mathscr{C}$; my point is that I don’t think that you **can** say much more than that in general.2012-11-04
  • 0
    [...] closed under 3 "operations" (which for brevity I'm not going to list here) abbreviated with "H", "S" and "P". The other direction also holds, i.e. if an algebraic structure is closed under H,S, and P, it is defined by a set of equations. Now what the algebraic structures are in the HSP theorem, is here my set $S$ and the analogue to "be defined by equations" is "be closed under $\mathscr{C}$" and what I'm looking for is the analogue for "closed und H,S and P" whic would tell me what my $\mathscr{C}$ would have to be.2012-11-04
  • 0
    Indeed, I'm also not sure, if there exists such an analogue in this case, but if model theorists found one for varieties, why shouldn't one exists (already) for this case, which is similar ?2012-11-04
  • 0
    What you're looking for *might be* in the topic of inductive definitions in Moschovakis' book **Elementary Induction on Abstract Structures**. Also, try googling "inductive definition" (or "inductive definability") along with the words/phrases "closure" and "transitive closure".2012-11-11
  • 0
    @DaveL.Renfro I browsed through the book (and looked through the internet) - it seems to be to difficult for me, to understand it yet, since it requires a lot of background. I'm wondering if someone could maybe explain to me the relevant sections of these books/what is to be found on the internet in a more elementary way ?2012-11-17
  • 0
    If your theory has any existential axioms then it becomes much harder for the intersection of submodels to still be a submodel. If your axioms are all of the form "for all [...] there exists _unique_ [...] such that [...]" (more precisely, if you have a "cartesian" theory in the sense of Johnstone, [_Sketches of an elephant_, Part D]) then the intersection of submodels should still be a submodel.2012-11-18

2 Answers 2

0

We are given a set $A$ and a predicate $\Phi$ and take the intersection over the class of all sets $O$ with $A\subseteq O\land \Phi(O)$. One may read from the structure of that predicate $\Phi$ wether or not this is a good closure condition.

For example:

  • transitive closure of relations: $\Phi(O)\equiv \forall x,y\in O\colon\phi(x,y)\to f(x,y)\in O$ where $\phi(\langle x_1,x_2\rangle,\langle y_1,y_2\rangle)\equiv x_2=y_1$ and $f(\langle x_1,x_2\rangle,\langle y_1,y_2\rangle)=\langle x_1,y_2\rangle$.
  • generated subgroup: $\Phi(O)\equiv \forall x,y\in O\colon\phi(x,y)\to f(x,y)\in O$ with $\phi(x,y)\equiv x\in X\land y\in X$ and $f(x,y)=xy^{-1}$.
  • topological closure: $\Phi(O)\equiv \forall S\subset O, x\in O\colon\phi(x,S)\to f(x,S)\in O$ with $\phi(x,S)\equiv S\subseteq X\land x\text{ is a limit point of }S$ and $f(x,S)=x$.

and so on. In general there may occur elements of $O$, subsets of $O$ and many other higher structures (elations, functions, ...). In all these cases we obtain closure of the condition under arbitrary intersection: If for all $O_i$ we have that e.g. $\phi(x,S)$ implies $f(x,S)\in O$ then for $O=\bigcap O_i$ we have that $\phi(x,S)$ for $x\in O, S\subset O$ implies the same for all $O_i$, hence $f(x,S)$ in all $O_i$, hence in $O$.

  • 0
    But what fails (in the structure of the predicate) in the case of arbitrary intersection of open sets (as in example 4) of my question) ?2012-11-19
  • 0
    There is an existential quantifier in the ways2012-11-19
  • 0
    Could you please be a little more explicit ? I can't see where this quantifier has to be, since one defines a set $O\subseteq X$ to be open, if it is in some a priori defined topology on $X$; and in the definition of topology we don't use an existential quantifier, as far as I can see...2012-11-19
  • 0
    I think the main difference is: If you simply take the topology $T$ on $X$ as given data, then $\Phi(O)$ has simply the form $\Phi(O)\equiv O\in T$, whereas all my examples use only $\in O$, not $O\in$.2012-11-19
  • 0
    But where is then the existential quantifier ? (And could you please also answer my comment below the answer of the other question I had a bounty on: http://math.stackexchange.com/questions/222855/finding-a-logical-expression-under-some-constrains-s-t-it-is-equivalent-to-an)2012-11-20
  • 0
    @temo: I'm not completely sure, but $\exists$ and $O\in$ can be severe obstacles, though I'm not sure how to formalize that. My gut feeling about the mishap with "open" is: If $T$ is *any* subset of $2^X$, we can consider $x\in O\rightarrow \exists U\in T\colon x\in U\subseteq O$, which happens to coincide with "open" if $T$ is a topology (or a basis of one)2012-11-20
0

Suppose that $X$ is a set, $\mathcal{A}$ is a distinguished family of subsets of $A$, and $f \colon \mathcal{A} \rightarrow \mathbf{Pow}\,X$. Here $\mathbf{Pow}\,X$ is the power set of $X$. Now define a class of functions indexed by the ordinals. In all cases the domain of the function is $\mathbf{Pow}\,X$. \begin{align} g_{0} : A &\mapsto A \\ g_{\alpha + 1} \colon A &\mapsto g_{\alpha}(A) \cup (\cup \{ f (B) \colon B \subseteq g_{\alpha}(A) \} )\\ g_{\alpha} \colon A &\mapsto \cup \{ g_{\beta}(A) \colon \beta < \alpha \} \text{ if $\alpha$ is a limit ordinal.} \end{align} There is an ordinal $\alpha^*$ satisfying for all $A \subseteq X$ and all $\alpha \geq \alpha^*$ we have $g_{\alpha}(A) = g_{\alpha^*}(A)$. The function $g_{\alpha^*}$ is a closure operator. For all $A,B \subseteq X$ we have $$A \subseteq g_{\alpha^*}(A) = g_{\alpha^*}(g_{\alpha^*}(A))$$ and, if $A \subseteq B$ we have $$g_{\alpha^*}(A) \subseteq g_{\alpha^*}(B).$$

You may wish to check out my answer to this question and this question.

  • 0
    I'm afraid that was a little bit too high for me, since I know almost nothing about ordinals. I also couldn' figure out, how the $g_{\alpha^*}$ is related to my closure condition. Is it, that my closure conditions $\mathscr{C}$ are "good" if there existsan ordinal $\alpha^*$ such that $g_{\alpha^*}$ becomes a closure operator ? If that is so, what does that tell me about $\mathscr{C}$ ?2012-11-19
  • 0
    Suppose you have a set $A$ and you wish to find the closure of $A$. In general the closure of $A$ is bigger than $A$. To be concrete suppose that $X$ is a group and the closure of a set $A \subseteq X$ is the smallest subgroup that contains $A$. The smallest subgroup is $\{ e \} $, the trivial subgroup so we might want $f(\varnothing) = \{ e \} $. Since subgroups are closed under products of elements and taking inverses we might want to say $f(A) = \{ ab \colon a, b \in A \} \cup \{ a^{-1} \colon a \in A \} $...2012-11-20
  • 0
    ...All that ordinal stuff is just a fancy way of saying: Keep on adding stuff until you are no longer adding anything new.2012-11-20