Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

First, a barrage of definitions.

Define that a relation on a set $X$ is a subset of $X^2$. If $f$ is a symmetric relation on $X$, define that $f$ is connected if and only if there do not exist disjoint and exhaustive $A, B \subseteq X$ and non-empty relations $\alpha,\beta$ on $A$ and $B$ respectively such that $f = \alpha \cup \beta$.

Given a collection of sets $\mathcal{J}$, define the that overlap relation is the set $$\mathcal{J}^{\mathrm{ov}} = \{(A,B)|A,B \in \mathcal{J}, A \cap B \neq \emptyset\}.$$

Finally, define that a connectivity space is a pair $(X,\mathcal{K})$ with $\mathcal{K} \subseteq \mathcal{P}(X)$ such that

  1. $\emptyset \in \mathcal{K}$

  2. For all non-empty $\mathcal{J} \subseteq \mathcal{K}$ such that $\bigcap \mathcal{J} \neq \emptyset,$ it holds that $\bigcup \mathcal{J} \in \mathcal{K}$.

(Note: It is typical to call the elements of $\mathcal{K}$ "connected sets." Also, I presume that the set of all connected relations on a set $X$ forms a connectivity space; however, this is tangential to the issue.)

Question: Suppose we replaced condition 2 in the definition of a connectivity space with the following.

2.* For all non-empty $\mathcal{J} \subseteq \mathcal{K}$ such that $\mathcal{J}^{\mathrm{ov}}$ is connected, it holds that $\bigcup \mathcal{J} \in \mathcal{K}$.

Is the resulting definition equivalent to the original?

share|improve this question
    
Every relation satisfies your definition of "connected" -- just take $A = \emptyset$, $B = X$. And the definition feels like it's describing something disconnected. Furthermore, you don't use the definition in the rest of your question. Are you sure you've transcribed everything correctly? –  Amit Kumar Gupta Feb 26 '13 at 6:19
    
Thanks, thats probably why i was finding the question so hard! Can you look over my "fixed" definition and let me know if it works? –  goblin Feb 26 '13 at 6:23
    
Sorry, I edited my comment since I thought you weren't using the definition of connected relation, but now I see you use it in reference to $\mathcal{J}^{ov}$. Unfortunately I can no longer edit my comment. –  Amit Kumar Gupta Feb 26 '13 at 6:26
    
Its no big deal. Anyway, i feel bad that i screwed up the question... –  goblin Feb 26 '13 at 6:29

1 Answer 1

up vote 1 down vote accepted

First we show $(2^\ast) \rightarrow (2)$:

Assume $(2^\ast)$, and let $\mathcal{J} \subset \mathcal{K}$ be arbitrary, but such that $\bigcap \mathcal{J} \neq \emptyset$. We can conclude $\bigcup \mathcal{J} \in \mathcal{K}$ if we can show that $\mathcal{J}^{ov}$ is connected. We're assuming that $\bigcup \mathcal{J} \neq \emptyset$, so $\mathcal{J}^{ov} = \mathcal{J}^2$, i.e. the "full" relation on $\mathcal{J}$. It's not hard to see that this relation is connected; let's extract this as a:

Lemma: if $S \neq \emptyset$ is a set, then $S^2$ is connected.
Proof: Suppose not, and let $A, B, \alpha, \beta$ witness this. $A, B$ are non-empty, so let's pick elements from them, say $a, b$. Clearly $(a,b) \in S^2$, but it's impossible for $(a,b) \in \alpha \cup \beta$ since $\alpha \subset A^2$, $\beta \subset B^2$, and $A, B$ are disjoint from one another.

Now $(2) \rightarrow (2^\ast)$:

Let $\mathcal{J}$ be such that $\mathcal{J}^{ov}$ is connected. We'll apply Zorn's Lemma to see that $\bigcup \mathcal{J}\in\mathcal{K}$. Let $$\mathbb{P} = \left\{ \mathcal{I}\subset\mathcal{J}\ |\ \bigcup \mathcal{I}\in\mathcal{K}\right\}$$

And partially order $\mathbb{P}$ by inclusion. $\mathcal{P}$ is not empty: for any $J \in \mathcal{J}$, $\mathcal{I} = \{J\}$ witnesses the non-emptiness. Every chain in $\mathbb{P}$ has an upper bound in $\mathbb{P}$: this follows from your observation about nested collections of connected sets, which follows immediately from $(2)$. Thus by Zorn's Lemma $\mathbb{P}$ has a maximal element. Let's pick one and call it $\mathcal{I}$. I claim that $\mathcal{I} = \mathcal{J}$ (and so $\bigcup\mathcal{J}\in\mathcal{K}$, as desired).

Suppose not. Case 1: there is some $J\in\mathcal{J}\setminus\mathcal{I}$ such that $J\cap\bigcup\mathcal{I}\neq\emptyset$. If that were the case, then by $(2)$, $\{J\}\cup\bigcup\mathcal{I}\in\mathcal{K}$, but then $\{J\}\cup\mathcal{I}\in\mathbb{P}$, contradicting the maximality of $\mathcal{I}$. Case 2: Every $J\in\mathcal{J}\setminus\mathcal{I}$ is disjoint from $\bigcup\mathcal{I}$. This also yields a contradiction, for $A=\mathcal{I}$, $B=\mathcal{J}\setminus\mathcal{I}$ witness that $J^{ov}$ is disconnected.

share|improve this answer
    
Are you sure its false? Consider three pairwise overlapping sets whose mutual inersection is empty. According to both definitions, their union is an element of $\mathcal{K}$. Its immediate from 2*, but slightly non-trivial from 2. –  goblin Feb 26 '13 at 7:00
    
Good point. The counterexample I had in mind is wrong; but it made me think of a better one. If you have collection $\mathcal{J}\subset\mathcal{K}$ of $n$ sets, each intersecting the next so they form a "chain", then $(2^\ast)$ forces their union to belong to $\mathcal{K}$ too. Does $(2)$ force the same fact? As you suggest, yes, but non-trivially. First apply $(2)$ to get that the union of the first two of the sets is in $\mathcal{K}$. Apply $(2)$ again to get that the union of the first three is in. Continuing you get $\bigcup\mathcal{J}\in\mathcal{K}$. Now what if $\mathcal{J}$ is infinite? –  Amit Kumar Gupta Feb 26 '13 at 7:24
    
Good point. Perhaps adding closure with respect to unions of nested collections would fix the problem... –  goblin Feb 26 '13 at 7:41
    
As in, the union of a nested collection of connected sets is a connected set. –  goblin Feb 26 '13 at 7:43
1  
Yup, you got it. And so $\alpha = A^{ov}$, $\beta = B^{ov}$. –  Amit Kumar Gupta Feb 26 '13 at 10:50

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.