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.

This is Exercise III.2.8 of Bourbaki's Theory of Sets.

An ordered set $E$ is said to be ramified if, for each pair of elements $x,y$ of $E$ such that $x<y$, there exists $z>x$ such that $y$ and $z$ are not comparable. $E$ is said to be completely ramified if it is ramified and has no maximal elements.

(a) Let $E$ be an ordered set and let $a$ be an element of $E$. Let $\mathfrak{R}_a$ denote the set of ramified subsets of $E$ which have $a$ as least element. Show that $\mathfrak{R}_a$, ordered by inclusion, has a maximal element.

(b) If $E$ is branched, show that every maximal element of $\mathfrak{R}_a$ is completely ramified.

(An ordered set $E$ is said to be branched if for each $x\in E$ there exist $y,z$ in $E$ such that $x\leq y$, $x\leq z$ and the intervals $\left[y,\rightarrow\right[$ and $\left[z,\rightarrow\right[$ do not intersect.)

The proof of (a) is a straightforward application of Zorn's Lemma.

For (b), I would like to argue in the following way. Suppose $F$ is a maximal element of $\mathfrak{R}_a$ and $x$ is a maximal element of $F$. Then there is $y,z$ in $E$ such that $x\leq y$, $x\leq z$ and $\left[y,\rightarrow\right[\cap\left[z,\rightarrow\right[=\emptyset$. Then $F\cup\{y,z\}$ is ramified.

But I haven't been able to show that $F\cup\{y,z\}$ is ramified, and I'm not sure that it's true, since if $b\in F$ and $b<y$, I don't see a way to conclude that $b\leq x$ or $b<z$. On the other hand, there is no natural way of adding further elements to $F\cup\{y,z\}$ such that it becomes a ramified set.

  1. Any hints at the solution or general thoughts about the problem are greatly appreciated.

  2. Bourbaki seems to be the only mathematician to use the words "branched" and "ramified" for those properties. Are there other more common words, or are these properties without interest?

share|improve this question
1  
Silly comment: Bourbaki is not a single mathematician, but a group. –  Grumpy Parsnip Mar 7 '11 at 11:34
    
I don't know if the term ramified here can be applied to algebraic number theory where it means seemingly different thing. And I was a fan of Bourbaki in the past, and I am glad to find another fan here. –  awllower Mar 7 '11 at 12:00
    
i'm guessing they're just using 'ramified' to mean 'branched' –  maxymoo Mar 7 '11 at 13:02

2 Answers 2

up vote 1 down vote accepted

Here's a counterexample. Let $\{0,1\}^*$ denote the set of finite binary strings. Define E to be the set $$E=\{a\} \cup \{bw \mid w\in\{0,1\}^*\} \cup \{cw \mid w\in\{0,1\}^*\}$$ with $a\leq bw\leq cw$ for all $w$, and $cw\leq cw'$ if $w$ is a prefix of $w'$.

Let $E'=\{a\}\cup \{bw \mid w\in\{0,1\}^*\}$. I claim that $E$ is branched, and $E'$ is a maximal element of $\mathfrak{R}_a$, but $E'$ is not completely ramified.

Every element $x\in E$ satisfies $x\leq cw$ for some $w$, so $x\leq cw0,cw1$, but $\left[cw0,\rightarrow\right[$ and $\left[cw1,\rightarrow\right[$ do not intersect. Hence $E$ is branched. (This is pretty much 1, Exercise 24 (b).)

Let $E''$ be a proper superset of $E'$. There is a prefix-minimal $w$ such that $cw\in E''$. There is no $z>bw$ incomparable with $cw$, but $bw,cw\in E''$. So $E''$ is not ramified. Hence $E'$ is a maximal element of $\mathfrak{R}_a$.

Finally, $b01010$ (and every other element of the form $bw$) is maximal in $E'$. So $E'$ is not completely ramified.

share|improve this answer
    
Thanks a lot for your answer! –  Stefan Walter Dec 29 '12 at 22:54

I'm not sure if this counts as a rigourous proof, but what if you think of $F$ as a directed graph. Then $F' = F \cup \{y,z\}$ is formed from $F$ by adding $y$ and $z$ as vertices, and just two edges, one from $x$ to $y$ and one from $x$ to $z$. Now two elements satisfy $u<v$ if and only if there is a directed path from $u$ to $v$. Then it's clear that if $b<y$ then also $b\leqslant x$ since you can just take a directed path from $b$ to $y$ and remove the last arrow, and you get a directed path from $b$ to $x$; the same logic shows that $b<z$, and since $y$ and $z$ are by construction incomparible, this shows that $F'$ is a ramified set, contradicting the maximality of $F$.

share|improve this answer
    
Thank you. That's exactly the picture I have in my mind. But 1. what is the set of edges? And 2. even if we assume that this can somehow be made rigorous, suppose for example that $F$ has another maximal element $m$, then it could happen that $m<y$ and $m$ is not comparable to $z$. In our picture, this would mean that by adding $y$ and $z$, we automatically add an edge from $m$ to $y$, but not to $z$. –  Stefan Walter Mar 7 '11 at 14:35
    
hmm yes i see your point... –  maxymoo Mar 8 '11 at 4:31

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.