Transcript r - Florida Atlantic University

Signed-Bit Representations of Real
Numbers and the Constructive
Stone-Yosida Theorem
Robert S. Lubarsky
and Fred Richman
Florida Atlantic University
Def A Riesz space R is a lattice ordered vector
space.
Canonical example A (natural) collection of
functions from some domain into the reals
ℝ -- meet and join computed pointwise.
Representation Theorem (Stone, Yosida, …)
(classical) Every Riesz space is embeddable
into a function space.
(Extensions: Preserving certain structure;
domain a quotient of a function space, etc.)
Proof idea For R ⊆ ℝW, w  W induces ŵ : R →
ℝ via ŵ(f) = f(w).
So for a general Riesz space R, the desired
domain is a subset of Σ = Hom(R, ℝ). So
embed R into ℝΣ.
█
Proof idea For R ⊆ ℝW, w  W induces ŵ : R →
ℝ via ŵ(f) = f(w).
So for a general Riesz space R, the desired
domain is a subset of Σ = Hom(R, ℝ). So
embed R into ℝΣ.
█
Why does Σ have non-trivial elements?
Classically, the Axiom of Choice.
Constructively…
(Coquand-Spitters) (DC) If R is separable, and
every element is normable, and r  R is
(sufficiently) different from 0 then there is a
σ  Σ such that σ(r) ≠ 0.
(C-S) Is DC necessary? What choice principle
is involved?
(Coquand-Spitters) (DC) If R is separable, and
every element is normable, and r  R is
(sufficiently) different from 0 then there is a
σ  Σ such that σ(r) ≠ 0.
(C-S) Is DC necessary? What choice principle
is involved?
Example Let Ra be generated by the projections onto the real
and complex lines of the solutions to x2 = a. If you cannot
decide whether a = 0, then you cannot in general find the
roots.
Let 1  R be distinguished.
Def (r  R) r is normable if glb {q  ℚ | q > r}
(i.e. sup(r)) exists.
Def Pos(r) if sup(r) > 0.
Def r  (p, q) = (r – p) ⋀ (q – r)
Note For r a function, Pos( r  (p, q) ) iff
rng(r) ⋂ (p, q) is non-empty.
Hence r can be identified with those intervals
(p, q) such that Pos( r  (p, q) ) .
Dedekind real r is located:
if p<q, then p<r or q>r.
Dedekind real r is located:
if p<q, then p<r or q>r.
Signed-bit representation:
●
(-2, 2)
Dedekind real r is located:
if p<q, then p<r or q>r.
Signed-bit representation:
(-2, 1) ●
● (-1, 2)
●
(-2, 2)
Dedekind real r is located:
if p<q, then p<r or q>r.
Signed-bit representation:
(-2, 0) ●
●
(-1, 1)
(-2, 1) ●
●
(-2, 2)
● (0, 2)
● (-1, 2)
Dedekind real r is located:
if p<q, then p<r or q>r.
Signed-bit representation:
(-2, 0) ●
●
(-1, 1)
●
(-2, 2)
● (0, 2)
●
●
(-2, -1) (-3/2, -1/2)
(-2, 0) ●
●
(-1, 0)
●
(-1, 1)
●
(-2, 2)
● (0, 2)
●
●
(-2, -1) (-3/2, -1/2)
(-2, 0) ●
●
(-1, 0)
●
●
(-1/2, 1/2) (0, 1)
●
(-1, 1)
●
(-2, 2)
● (0, 2)
●
●
(-2, -1) (-3/2, -1/2)
(-2, 0) ●
●
(-1, 0)
●
●
(-1/2, 1/2) (0, 1)
●
(-1, 1)
●
(-2, 2)
(the pseudo-tree) T
●
●
(1/2, 3/2)
(1, 2)
● (0, 2)
●
●
(-2, -1) (-3/2, -1/2)
(-2, 0) ●
●
(-1, 0)
●
●
(-1/2, 1/2) (0, 1)
●
(-1, 1)
●
(-2, 2)
●
●
(1/2, 3/2)
(1, 2)
● (0, 2)
●
●
(-2, -1) (-3/2, -1/2)
(-2, 0) ●
●
(-1, 0)
●
●
(-1/2, 1/2) (0, 1)
●
(-1, 1)
●
(-2, 2)
●
●
(1/2, 3/2)
(1, 2)
● (0, 2)
Recall that r  R can be identified with
{ (p, q) | Pos(r  (p, q) ) }. That in turn is a
sub-tree Tr of T with the extendibility
property: no terminal nodes.
For r, s  R and intervals I, J,
(I, J) is in the signed-bit representation of R iff
Pos( r  I ⋀ s  J ).
The signed-bit representation TR of R is the
set of all such finite sequences of intervals,
indexed by members of R.
Theorem For every set TX of finite sequences
(indexed by X) of intervals from T with the
extendibility property, there is a canonical
Riesz space R ⊇ X such that TX is the signedbit representation of X.
Theorem For every set TX of finite sequences
(indexed by X) of intervals from T with the
extendibility property, there is a canonical
Riesz space R ⊇ X such that TX is the signedbit representation of X.
Definition An ideal Ir through Tr is a (nonempty) subset closed downwards and under
join and with no terminal element.
Definition An ideal through TR is an ideal Ir
through each Tr such that finite products
stay in TR: ΠrX Ir ⊆ TR (X finite).
Definition An ideal through TR is an ideal Ir
through each Tr such that finite products
stay in TR: ΠrX Ir ⊆ TR (X finite).
Theorem There is a canonical bijection
between ideals through TR and Σ. (Recall Σ is
Hom(R, ℝ).)
Definition An ideal through TR is an ideal Ir
through each Tr such that finite products
stay in TR: ΠrX Ir ⊆ TR (X finite).
Theorem There is a canonical bijection
between ideals through TR and Σ. (Recall Σ is
Hom(R, ℝ).)
(Note: This can be extended to account for
ideals through TX and homomorphisms of
the Riesz space generated by X.)
So the existence of homomorphisms from
Riesz spaces with dense subsets of size  is
equivalent to the existence of ideals through
subsets of -sized products of T with the
extendibility property. This is a Martin’s
Axiom-like property of set theory.
Let ℱ be the topological space of all ideals
through TX, where X has two elements. An
open set is given by finitely many pieces of
positive and negative information. Positive
information is a pair of intervals, i.e. a
member of T × T. Negative information is a
pair of such closed intervals.
Let ℱ be the topological space of all ideals
through TX, where X has two elements. An
open set is given by finitely many pieces of
positive and negative information. Positive
information is a pair of intervals, i.e. a
member of T × T. Negative information is a
pair of such closed intervals.
Claim The (full) topological model over ℱ is
the (canonical) generic model for a Riesz
space with two generators, and that space
has no homomorphisms to ℝ.