8
$\begingroup$

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, 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, I don't see a way to conclude that $b\leq x$ or $b. 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?

  • 0
    @Robert: Thanks. Feel free to bring this up on meta again if you think it's necessary. It's usually a good idea to tackle old issues again (after carefully reading the arguments given last time, and explaining why the topic is now relevant again, of course). I think, however, that 8 months is not sufficiently old for this case, though, but it's borderline.2015-01-20

2 Answers 2

1

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.

  • 0
    Thanks a lot for your answer!2012-12-29
1

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 if and only if there is a directed path from $u$ to $v$. Then it's clear that if $b 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, and since $y$ and $z$ are by construction incomparible, this shows that F' is a ramified set, contradicting the maximality of $F$.

  • 0
    hmm yes i see your point...2011-03-08