Exercise 6.27 (Scott 1981, PRG-19, ยง6) โ which subsystem relations hold #
EXERCISE 6.27. Which of the following relationships are true:
(๐ โ โฐ) โด (๐ ร โฐ);๐ โด ๐ ร โฐ;(๐ โ โฐ) โด (๐ + โฐ);๐ โด ๐ โ โฐ;(๐ โโฅ โฐ) โด (๐ โ โฐ);๐ โด ๐ โ โฐ?
Here โด is Scott's embeds-as-a-subdomain relation of Lemma 6.15
(Trianglelefteq): D โด E
means D โ
แดฐ D' for some D' โ E. We use the concrete {0,1}* constructions of
Exercises 6.19/6.21
(sumTok, prodTok, oplusTok, otimesTok) and the function spaces funSpace
/ strictFun.
Answer. The first five hold for all ๐, โฐ; the last fails in general.
| relation | verdict | name |
|---|---|---|
(๐ โ โฐ) โด (๐ ร โฐ) | true | otimes_trianglelefteq_prod (in fact |
otimesTok โ prodTok) | ||
๐ โด ๐ ร โฐ | true | fst_trianglelefteq_prod |
(๐ โ โฐ) โด (๐ + โฐ) | true | oplus_trianglelefteq_sum (in fact `oplusTok โ |
| sumTok`) | ||
๐ โด ๐ โ โฐ | true | inl_trianglelefteq_oplus |
(๐ โโฅ โฐ) โด (๐ โ โฐ) | true | strictFun_trianglelefteq_funSpace |
๐ โด ๐ โ โฐ | false in general | not_trianglelefteq_otimes_unit |
The smash product collapses the bottom: pairing anything with โฅ_โฐ is โฅ. So ๐
embeds in
๐ โ โฐ only when โฐ contributes a (finite) non-bottom point; for the trivial โฐ = ๐ we have
๐ โ ๐ โ
๐, refuting the universal claim.
All parts are choice-free (#print axioms โ {propext, Quot.sound}) except
(4)
(inl_trianglelefteq_oplus), whose oplus_mem_leftN decides the
genuinely-undecidable test
X = ฮโ over an arbitrary system and so depends on Classical.choice.
(1) (๐ โ โฐ) โ (๐ ร โฐ) โ the smash is literally a subsystem of the product #
The smash otimesTok has the same master {ฮ} โช 0ฮโ โช 1ฮโ = prodTokNbhd ฮโ ฮโ
and its proper
neighbourhoods prodTokNbhd X Y (with X โ ฮโ, Y โ ฮโ) are a sub-family of the
product's
neighbourhoods. The consistency clause is inherited because intersections stay off
the boundary.
Exercise 6.27 (1). (๐ โ โฐ) โด (๐ ร โฐ).
(2) ๐ โด ๐ ร โฐ โ first-factor projection pair #
๐ is not literally a subsystem of ๐ ร โฐ (the neighbourhoods have a different
shape), but it
embeds via the projection pair i(X) = (X, โฅ), j(W) = fst W. Concretely we send
X โ ๐ to the
product neighbourhood prodTokNbhd X ฮโ (pair X with all of โฐ); the
embedding/projection are the
two refinement relations against that neighbourhood, exactly as in Proposition
6.12.
The injection i : ๐ โ ๐ ร โฐ: X i W โ X โ ๐ โง W โ ๐รโฐ โง (X,ฮโ) โ W.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The projection j : ๐ ร โฐ โ ๐: W j X โ W โ ๐รโฐ โง X โ ๐ โง W โ (X,ฮโ).
Equations
- One or more equations did not get rendered due to their size.
Instances For
Exercise 6.27 (2). ๐ โด ๐ ร โฐ.
(3) (๐ โ โฐ) โ (๐ + โฐ) โ the coalesced sum is literally a subsystem of the #
sum
oplusTok drops the improper copies 0ฮโ, 1ฮโ of sumTok; what remains is a
sub-family, and
consistency is inherited (cross-tag intersections are empty, hence not
sumTok-neighbourhoods).
Exercise 6.27 (3). (๐ โ โฐ) โด (๐ + โฐ).
(4) ๐ โด ๐ โ โฐ โ left-injection projection pair #
Unlike the product, the coalesced sum identifies the two bottoms, so the
embedding of ๐ must
send โฅ_๐ = ฮโ to the shared bottom sumTokMaster and a proper X to its left
copy 0X. We
package this in leftN X (= 0X for proper X, = sumTokMaster for X = ฮโ).
Distinguishing the two cases is exactly the test X = ฮโ, which is undecidable
for an arbitrary
neighbourhood; consequently the single lemma oplus_mem_leftN โ and only it โ
uses Classical.em.
This is genuinely unavoidable at this level of generality (Scott's tokens are
concrete and decidable,
but we work over arbitrary NeighborhoodSystems), so inl_trianglelefteq_oplus
depends on
Classical.choice (called out in the axiom audit). Every other part of Exercise
6.27 is choice-free.
The left-copy generator: 0X for proper X, the shared bottom sumTokMaster
for X = ฮโ. The
set-builder {w โฃ w โ sumTokMaster โง X = ฮโ} keeps the definition choice-free.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The only classical step in Exercise 6.27: leftN X is an ๐ โ โฐ-neighbourhood. The proof
splits on the (undecidable for arbitrary X) test X = ฮโ.
The injection i : ๐ โ ๐ โ โฐ: X i W โ X โ ๐ โง W โ ๐โโฐ โง leftN X โ W.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The projection j : ๐ โ โฐ โ ๐: W j X โ W โ ๐โโฐ โง X โ ๐ โง W โ leftN X.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Exercise 6.27 (4). ๐ โด ๐ โ โฐ. (Uses Classical.choice via
oplus_mem_leftN.)
(5) (๐ โโฅ โฐ) โด (๐ โ โฐ) โ the strict maps embed in all maps #
A strict map is an approximable map, so ๐ โโฅ โฐ sits inside ๐ โ โฐ by
inclusion i, with the
strictification j (force f(โฅ) = โฅ) as its retraction. strictify f โ f
always, and on a strict
f strictification is the identity; this gives the projection-pair laws j โ i = id,
i โ j โ id. We work over arbitrary systems Vโ, Vโ (not just Str); the
construction is
choice-free. We realise i, j on principal inputs via ofMono of the
element-level inclusion /
strictification, then identify their element maps using the representations
funSpaceEquiv
(|๐โโฐ| โ ApproximableMap) and strictFunEquiv (|๐โโฅโฐ| โ StrictMap).
Strictification of a map (on relations): keep f but force the master
input to the master
output. The resulting map is strict, lies below f, and is the identity on strict
maps.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The strictification as an element of the strict function space's token type.
Equations
Instances For
The four inverse identities of the two representation equivalences (defeq unfoldings).
Element-level inclusion |๐ โโฅ โฐ| โ |๐ โ โฐ|.
Equations
Instances For
Element-level strictification |๐ โ โฐ| โ |๐ โโฅ โฐ|.
Equations
Instances For
The inclusion i : ๐ โโฅ โฐ โช ๐ โ โฐ.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The strictification retraction j : ๐ โ โฐ โ ๐ โโฅ โฐ.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Choice-free extensionality from agreement on principal inputs. Unlike
ext_of_toElementMap
(which splits on the undecidable Vโ.mem X), both sides of the relation carry
domain membership via
rel_dom, so no case analysis โ and hence no Classical.choice โ is needed.
Exercise 6.27 (5). (๐ โโฅ โฐ) โด (๐ โ โฐ) for all ๐, โฐ (choice-free).
(6) ๐ โด ๐ โ โฐ is false in general #
The smash product sends (x, โฅ) and (โฅ, y) to the single bottom, so if โฐ
contributes no proper
neighbourhood the whole product collapses to its bottom. Concretely, for the
one-point unit โฐ = ๐
the system ๐ โ ๐ has only its master as a neighbourhood, hence a one-point
element lattice; a
๐ with two distinct points therefore cannot embed. This refutes the universal
claim.
If a system's only neighbourhood is its master, its element lattice is a
single point (โฅ).
A concrete two-point domain over {0,1}*: neighbourhoods Set.univ (= โฅ)
and {[]}.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The one-point unit domain ๐ over {0,1}* (only neighbourhood {[]}).
Equations
Instances For
With the unit second factor, the smash twoPt โ ๐ collapses to its master.
Exercise 6.27 (6). ๐ โด ๐ โ โฐ does not hold for all ๐, โฐ: take ๐
two-point and
โฐ = ๐. Then ๐ โ ๐ has a one-point element lattice while ๐ has two, so no
isomorphism onto a
subsystem can exist.