# Bourbaki exercise about “ramified” ordered sets

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?

-
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
@Robert: Please don't add the [bourbaki-exercises] anymore (and remove the ones you have added). See this meta thread for a discussion, meta.math.stackexchange.com/questions/13817/… – Asaf Karagila Jan 20 '15 at 19:24
@AsafKaragila IMO we should keep these tags, either forbid mention to reference in question, when the reference is an exercise of a book. Because, as you may have remark, even if "math.se was not well-suited for compiling a solutions manual" as written in your link, it does tend to become one. ;-) That's a fact. Anyway, as you are more authorative than me, I will remove them. – user10000100_u Jan 20 '15 at 19:29

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.

-
Thanks a lot for your answer! – Stefan 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$.

-
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 Mar 7 '11 at 14:35
hmm yes i see your point... – maxymoo Mar 8 '11 at 4:31