0
$\begingroup$

Prove that a countable inductive poset is directed complete.

This question is from Notes on Set Theory 2nd edition by Yannis Moskovakis. Here, an inductive poset is a poset such that every chain in the poset has a least upper bound.

I am not sure what I can do here. Let $P$ be a countable, inductive partially ordered set, and let $S$ be a directed set. If $S$ is a chain, then it has a least upper bound so we are done. However $S$ need not be a chain.

As the chapter that has this problem has the following theorem, I may be able to use this but I am not sure how to:

Theorem: every monotone mapping $\pi: P \to P$ on an inductive poset to itself has exactly one strongly least fixed point $x^*$ characterized by two properties $$\pi(x^*)=x^*,$$ $$\forall y\in P[\pi(y) \leq y \Rightarrow x^* \leq y]$$

Actually, the theorem on the chapter requires $\pi$ to be countably countinuous, but such condition is later in the book proven to be superflous.

I may be able to use the "least property" of a function $\pi$ satisfying the conditions stated in the theorem, but I am not sure how I can define such a $\pi$.

$\endgroup$
1
$\begingroup$

Suppose that $A$ is an infinite Dedekind-finite set which can be linearly ordered, e.g. a set of real numbers such as in Cohen's first model.

Now consider the partial order $P=[A]^{<\omega}$ of finite subsets of $A$, ordered by inclusion. I claim that this is an inductive partial order. And to see why note that if we have a chain of finite subsets, then it has to be countable, since every finite set in the chain must have a unique cardinality which is a natural number; but since $A$ is linearly ordered that means that we can enumerate all the finite sets in the chain uniformly and so the union of the chain is countable. Finally by the fact that $A$ is Dedekind-finite that means that the chain had to be finite to begin with.

But at the same time, the partial order is not directed-complete, since the whole partial order is directed and there is no supremum to the partial order itself.


The key point here, which is how we avoid using choice, is that your assumption includes countability, which lets you use recursion as needed by fixing the enumeration of your partial order and using it to choose elements as needed.

The main point here is that if $X$ is a countable directed set, then $X$ has a cofinal chain. And to see why, note that we can construct this chain recursively: write $X=\{x_n\mid n<\omega\}$ and define $C_0=\{x_0\}$ and $C_{n+1}$ as $C_n\cup\{x_k\}$ where $k$ is the least index of an element which is larger than all the elements of $C_n\cup\{x_n\}$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks. I was wondering if you could give hints or solution to the same quesion if we assume the axiom of countable choice? Unfortunately I don't think this book is very clear on the kind of axioms that it allows rraders to assume. $\endgroup$ – Account Private Dec 12 '19 at 12:16
  • $\begingroup$ I assumed that, since the chapter on the axiom of choice comes later in the book than the chapter of this problem, we cannot assume the axiom of choice. $\endgroup$ – Account Private Dec 12 '19 at 12:24
  • $\begingroup$ The general case is somehow similar. If $X$ is a well-orderable inductive directed set, then $X$ has a cofinal chain. You start by recursion, and at limit steps utilise the inductive property. (This prevents a situation like finite subsets of some uncountable set, which is a directed set without cofinal chains.) $\endgroup$ – Asaf Karagila Dec 12 '19 at 13:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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