6
$\begingroup$

Let a poset with distinguished elements be a triple $F = (P,\leq, X)$ where $(P,\leq)$ is a poset and $X\subseteq P$. Call the $X$ the distinguished elements.

Say that $F$ is isomorphic to $G$ iff there is an order isomorphism that takes the distinguished elements of $F$ to the distinguished elements of $G$. Finally, if $F=(P,\leq, X)$, and $x\in P$ write $F\uparrow x$ for $(P_x, \leq_x, X_x)$ where $P_x=\{y\in P\mid x\leq y\}$, $X_x=\{y\in X\mid x\leq y\}$ and $\leq_x$ is $\leq$ restricted to $P_x$.

Is it possible to find a non-empty poset with distinguished elements, $F=(P,\leq, X)$, satisfying both of the following conditions:

  • For every $Y\subseteq P$, $(P,\leq, Y)$ is isomorphic to $(P,\leq, X)\uparrow x$ for some $x\in P$.
  • For every $x\in P$, $(P, \leq, X)\uparrow x$ is isomorphic to $(P,\leq, Y)$ for some $Y\subseteq P$.

Note: one might have thought this would be impossible for cardinality reasons, but the straightforward that this isn't possible isn't quite sound.

$\endgroup$
  • $\begingroup$ For the second one use Y = $X_x.$ $\endgroup$ – William Elliot Jan 28 '18 at 4:08
  • $\begingroup$ Do you have an application in mind? $\endgroup$ – Keith Kearnes Feb 16 '18 at 17:39
  • $\begingroup$ I'm looking for intensional models of higher-order logic (over a given signature) in which the claim $\Box A$ is true iff $\forall x1..xn A[x1/c1...xn/cn]$ is true, where c1...cn are the constants appearing in A, ad $\Box A$ can be defined as $A=\top$. If the signature contains just a single constant of type t, and the question has a positive answer, then there are models satisfying thi constraint. $\endgroup$ – Andrew Bacon Feb 16 '18 at 17:47
1
$\begingroup$

Here is a partially-constructed diagonalization argument. I believe that no such $P$ can exist, and I have a sketch of the proof, below. There's more to do (the proof doesn't work! it's a sketch we may turn into a workable proof), but I figured it might be useful for others to build upon, and I'll update if I think of more to add.


To review,

We are searching for a partially-ordered set $\langle P, \leq\rangle$ and a set $X\subseteq P$ such that:

  1. For every $Y\subseteq P$, there exist an element $x\in P$ and order isomorphism $f_x : (P\uparrow x)\rightarrow P$ such that the image of the set $(X\uparrow x)$ is the set $Y$.
  2. For every $x\in P$, there exist a set $Y\subseteq P$ and order isomorphism $g_Y : (P\uparrow x)\rightarrow P$ such that the image of the set $(X\uparrow x)$ is the set $Y$.

In what follows, suppose $\langle P, \leq, X\rangle$ satisfies the two conditions. Our aim is to produce a contradiction. We start with some observations.

  • P must not be empty. If $P$ is empty, then $P$ fails to satisfy the first condition when $Y=\varnothing$, because there does not exist any element $x\in \varnothing$.
  • X must not be empty. Since P is nonempty, pick a nonempty subset $Y\subseteq P$. If X is empty, then every up-set of X is empty, thus there is no function such that the image of empty $(X\uparrow x)$ is nonempty $Y$, and so P fails the first condition.
  • X must not be all of P. To pass the first condition with $Y=\varnothing$, there must be an isomorphism sending some up-set $(X\uparrow x)$ to $Y=\varnothing$. Hence there must be an up-set of X which is empty. Whenever x belongs to X, the up-set $(X\uparrow x)$ is nonempty; hence there must be an $x$ that does not belong to X. Hence X must not be all of P.
  • P and X must be infinite. If we satisfy the first condition with $Y=P$, there's a bijection $(P\uparrow x)\rightarrow P$ which maps $(X\uparrow x)$ onto $Y=P$. It's easy to show that $(X\uparrow x)$ and $(P\uparrow x)$ are therefore equal as sets. But then, as sets, we have $$P\cong (P\uparrow x) \cong (X\uparrow x) \subseteq X \subsetneqq P.$$ Because P is bijective with a proper subset $(X\uparrow x)\subsetneqq P$, it follows that P is infinite.
    Because P is infinite and bijective with a subset of X, X is likewise infinite.
  • P has a bottom (initial) element. Indeed, P is nonempty so we can pick $x\in P$, and if P satisfies the second condition, then $(P\uparrow x)$ is order-isomorphic to $P$. But since $x\in P$, $(P\uparrow x)$ has a bottom element (namely $x$ itself), and so $P$ must have a bottom element.
  • Every element of P has at least one successor. P has a bottom element, which certainly has a successor because P is infinite. Furthermore, by the second condition, every up-set $(P\uparrow x)$ is order-isomorphic to P; that isomorphism sends the bottom element of P to $x$. By order isomorphism, every point in P has at least one successor.

Now we have the tools to construct a diagonalization argument. Having fixed a set $X\subseteq P$ in advance, we attempt to construct a set $Y$ for which $\langle P, \leq, X\rangle$ fails the first condition.

  • In this proof sketch, suppose we satisfy the two given conditions. Fix a particular family $\{h_x : x\in X\}$ of order isomorphisms $h_x : P\rightarrow (P\uparrow x)$.
  • Define the set $Y$ by: $$Y\equiv \{x \in P : h_x(x) \notin X\}$$
  • To satisfy the first condition, we must be able to find a point $z$ and an order-isomorphism $h_z:P\rightarrow (P\uparrow z)$ such that the image of $Y$ is the set $(X\uparrow z)$.
  • Notice what this diagonal construction does: for each $x\in X$, $h_x(P)$ is the up-set $(P\uparrow x)$. We ensure that there's a mismatch between $h_x(Y)$ and the set $(X\uparrow x)$ by ensuring that there's at least one point (namely $x$) which $h_x$ sends outside of $(X\uparrow x)$. Hence $h_x(Y) \neq (X\uparrow x)$. Because we built in failure for each $h_x$, there is no $h_x$ in our fixed set for which $h_x(Y) = (X\uparrow x)$.
  • This argument, while a good start, actually involved some sleight of hand: even if we cause these isomorphisms $h_x$ to fail, there may be many other isomorphisms for a single $x$ which send $(P\uparrow x)\rightarrow P$ and which we haven't ensured will fail. We've only blocked one isomorphism per $x$.

I'm not sure yet, but I think it might be possible to ammend this proof to make it work. The idea is to consider instead of individual points, clusters of points related to one another through order isomorphism.

  • For each point $x\in P$, let $F_x$ be the set of all order isomorphisms $P\rightarrow (P\uparrow x)$. Let $S_x$ be the images of $x$ through all of these isomorphisms: $$S_x \equiv \{f(x) : f \in F_x\} \subseteq (P\uparrow x)$$
$\endgroup$
  • $\begingroup$ Thanks! I'll have a think about your proof strategy. $\endgroup$ – Andrew Bacon Jan 30 '18 at 19:07

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.