Re: Uncountable sets in CZF?

From: David McAnally (D.McAnally_at_i'm_a_gnu.uq.net.au)
Date: 09/01/04 

Date: 1 Sep 2004 04:15:16 GMT

raf@tiki-lounge.com (Ross A. Finlayson) writes:

<snip>

>By "plain set theory" I meant theory where the only primary objects
>were sets as opposed to a theory where numbers are primary objects.

ZF and ZFC are therefore what you call "plain set theories". In ZF and
ZFC, numbers are defined AS SETS. I wonder where you got the erroneous
idea that numbers were primary objects in ZF and ZFC???

A natural number is defined to be either the empty set or a successor
ordinal whose elements are all either empty or successor ordinals, a
set n is a natural number if

n is empty or [n is a successor ordinal and for all m in n (m is empty
or m is a successor ordinal)].

Equivalently, a natural number is an element of the smallest limit
ordinal. The smallest limit ordinal omega is a model of Peano's Axioms
with 0 being given by the empty set and the successor function being
given by S(x) = x u {x}, where for sets A and B, A u B denotes the union
of A and B. Addition on N (the set of natural numbers, i.e. omega) is
defined by recursion by

        m + 0 = m,

        m + S(n) = S(m + n).

Multiplication on N is defined by recursion by

        m.0 = 0,

        m.S(n) = m.n + m.

Define the relation == on N x N by (a,b) == (c,d) iff a + d = b + c,
then == is an equivalence relation on N x N. Define Z = (N x N)/==,
and define an integer to be an element of Z, i.e. an integer is an
equivalence class in N x N, and therefore a subset of N x N. Addition
is defined on Z by

        [(a,b)] + [(c,d)] = [(a + c,b + d)].

Multiplication is defined on Z by

        [(a,b)].[(c,d)] = [(a.c + b.d,a.d + b.c)].

Both addition and multiplication on Z are well-defined. N is embedded
in Z by mapping m to [(m,0)].

Define the relation == on Z x (Z-{0}), where 0 in Z is identified with 0
in N by the embedding, by (a,b) == (c,d) iff a.d = b.c, then == is an
equivalence relation on Z x (Z-{0}). Define Q = (Z x (Z-{0}))/==, and
define a rational number to be an element of Q, i.e. a rational number is
an equivalence class in Z x (Z-{0}), and therefore a subset of Z x (Z-{0}).
Addition on Q is defined by

        [(a,b)] + [(c,d)] = [(a.d + b.c,b.d)].

Multiplication on Q is defined by

        [(a,b)].[(c,d)] = [(a.c,b.d)].

Both addition and multiplication on Q are well-defined. Z is embedded in
Q by mapping x to [(x,1)], where 1 in Z is identified with 1 in N by the
embedding of N in Z.

So, we have definitions of natural numbers, integers and rational numbers
completely in terms of sets.

There are two possible definitions of real numbers.

A sequence in Q is defined as a function x : N -> Q. A Cauchy sequence
in Q is a sequence x in Q such that for all rational d > 0, there exists
k in N such that if m and n are natural numbers such that m > k and n > k,
then |x(m) - x(n)| < d, i.e.

        for all d in Q (d > 0 => exists k in N for all m in N for all n in N
        [(m > k and n > k) => |x(m) - x(n)| < d]).

Define the relation == on Cauchy sequences in Q by x == y if for all
rational d > 0, there exists k in N such that for all natural numbers
n > k, |x(n) - y(n)| < d, i.e.

        for all d in Q (d > 0 => exists k in N for all n in N (n > k =>
        |x(n) - y(n)| < d)).

Let CauchyQ be the set of Cauchy sequences in Q, then == is an equivalence
on CauchyQ. Define R = CauchyQ/==, and define a real number to be an
element of R, so that a real number is a set of Cauchy sequences in Q.
Define addition and multiplication on CauchyQ by

        (x + y)(n) = x(n) + y(n) for all n in N,

        (x.y)(n) = x(n).y(n) for all n in N.

Define addition and multiplication on R by

        [x] + [y] = [x + y],

        [x].[y] = [x.y].

Addition and multiplication are well-defined on R. For r in Q, define
the sequence x_r in Q by x_r(n) = r for all n in N, then x_r is a Cauchy
sequence in Q. Q is embedded in R by mapping r to [x_r] for all r in Q.

An alternative definition of real number is the Dedekind definition: a
real number is a set x of rational numbers such that

        (1) x is not empty,

        (2) x is not equal to Q,

        (3) if r is an element of x and s is a rational number such that
            s < r, then s is an element of x,

        (4) if r is an element of x, then there exists a rational number
            s such that r < s and s is an element of x.

So a real number x is a nonempty proper subset of Q such that

        for all r in x for all s in Q (s < r => s in x),

        for all r in x exists s in Q (r < s and s in x).

Let R be the set of all real numbers.

Addition is defined on R by

        x + y = {r + s : r in x, s in y}.

then x + y is an element of R.

0 in R is defined equal to {r in Q : r < 0}.

Order is defined on R by x <= y (x is less than or equal to y) iff x is
a subset of y, so that x < y iff x is a proper subset of y.

For x in R, -x is defined by

        -x = {r in Q : exists s in Q (r < -s and s not in x)},

then -x is an element of R.

Multiplication on R is defined by

        x.y = 0 if x = 0 or y = 0,

        x.y = {r in Q : r <= 0} u {r.s : r in x, s in y, r > 0, s > 0}

                if x > 0, y > 0,

        x.y = -(x.(-y)) if x > 0, y < 0,

        x.y = -((-x).y) if x < 0, y > 0,

        x.y = (-x).(-y) if x < 0, y < 0,

then x.y is an element of R.

Q is embedded in R by mapping r to {s in Q : s < r}.

So a natural number is an ordinal, an integer is an equivalence class of
ordered pairs of natural numbers, a rational number is an equivalence
class of ordered pairs of integers, and real number is an equivalence
class of Cauchy sequences of rational numbers (Cauchy definition) or a
set of rational numbers (Dedekind definition).

C can be defined by C = R x R. Addition on C is given by

        (a,b) + (c,d) = (a + c,b + d).

Multiplication on C is given by

        (a,b).(c,d) = (a.c - b.d,a.d + b.c).

R is embedded in C by mapping x to (x,0). The elements of C are called
the complex numbers. There are other definitions of complex numbers
(the most satisfying probably being C = R[x]/(x^2 + 1)).

>So you have that in the generic extension that there are more elements
>in R,

There *may* be more elements in R. It depends on the extension.

>but no more elements in N. R is the complete set of real
>numbers in V, but you have that R in V is a proper subset of R in the
>extension V[G]. Then you claim there is a bijection between N^V[G]
>and R^[V].

In V[G], for an *appropriate* extension. Never a bijection in V.

>N^V[G] has no more elements that N^V, yet you have it
>bijectively mapping to R^V,

In V[G].

>which you claim has less elements than
>R^V[G] as a proper subset or R^V. Conversely, R^V is the complete set
>of real numbers, each real number is defined in R^V, and N^V[G] is not
>different than N^V in that for each n E N^V there exists n E N^V[G]
>and vice versa.

>N^V and N^V[G] are the same set in that they differ in no elements,
>they are each no different than N, yet you have that N^V[G]
>bijectively maps to R^V but not to R^V[G], and claim that R^V[G] is a
>proper superset of R^V.

R^V would be a proper subset of R^{V[G]}, not vice versa.

>Please name or describe a real element of
>R^V[G] not in R^V, that is R, the set of all real numbers.

Let the set F of forcing conditions be the set of all functions p whose
domain is a finite subset of N and whose range is a subset of {0,1}, i.e.
F = {p : p is a function, dom(p) is a finite subset of N, range(p) is a
subset of {0,1}}. Define q <= p (q is stronger than p) if q extends p,
i.e. p is a subset of q, i.e. dom(p) is a subset of dom(q) and p(n) = q(n)
for all n in dom(p). It follows that p and q are compatible iff
p(n) = q(n) for all n in the intersection of dom(p) and dom(q).

Let G be a generic set in F (G is not necessarily an element of V).

Let n be an element of N, and let D = {p in F : n in dom(p)}. If q is
a forcing condition, and n is an element of dom(q), then q is stronger
than q and q is an element of D.

If q is a forcing condition and n is not an element of dom(q), let
r = q u {(n,0)}, then r is a function, dom(r) is a finite subset of N
and range(r) is a subset of {0,1}, and so r is a forcing condition,
r is stronger than q, and n is an element of dom(r), and so r is an
element of D.

It follows that for all forcing conditions q, there exists a forcing
condition r stronger than q such that r is an element of D. So D is
dense. Since G is a generic set, then G intersects D. Let p be a common
element of G and D, then n is an element of dom(p), and so n is an element
of dom(UG) (where, for a set A, UA is the union of A).

Since n is an arbitrary element of N, then dom(UG) = N.

Since range(p) is a subset of {0,1} for all p in G, then range(UG) is a
subset of {0,1}.

Suppose UG is not a function, then there exists n in N such that (n,0) and
(n,1) are both elements of UG. It follows that there exist p in G and
q in G such that p(n) = 0 and q(n) = 1. Since n is an element of the
intersection of dom(p) and dom(q), and p(n) and q(n) are not equal, then
p and q are incompatible, contradicting the genericity of G. Since the
assumption that UG is not a function leads to a contradiction, then UG is
a function UG : N -> {0,1} in V[G].

Let A = {n in N : (UG)(n) = 1}, then A is a subset of N in V[G].

Let B be a subset of N in V, and define D = {p in F : exists n in dom(p)
((n in B and p(n) = 0) or (n not in B and p(n) = 1))}. If q is a forcing
condition and q is an element of D, then q is stronger than q and q is an
element of D.

Suppose q is a forcing condition and q is not an element of D, then
for all n in dom(q) ((n in B and q(n) = 1) or (n not in B and q(n) = 0)).
Since dom(q) is finite, then N-dom(q) is nonempty. Let m be an element
of N-dom(q), and define r = q u {(m,0)} if m is an element of B, and
r = q u {(m,1)} if m is not an element of B. Then r is a function,
dom(r) is a finite subset of N, and range(r) is a subset of {0,1},
so that r is a forcing condition, r is stronger than q, and ((m in B and
r(m) = 0) or (m not in B and r(m) = 1)). It follows that r is an element
of D.

So D is a dense set. Since G is generic, then G intersects D, and so
there exist p in G and n in dom(p) such that ((n in B and p(n) = 0) or
(n not in B and p(n) = 1)). If n is an element of B, then p(n) = 0, so
(UG)(n) = 0, so n is not an element of A. If n is not an element of B,
then p(n) = 1, so (UG)(n) = 1, so n is an element of B. It follows that
n is an element of either A or B, but not both, and so A and B are not
equal. That is, for any subset B of N in V, there is a natural number n
such that n is an element of the symmetric difference of A and B, and so
A and B are not equal. It follows that A is not a subset of N in V, i.e.
A is an element of V[G], but not an element of V.

Let x = \sum_{n in N} 2^{-(UG)(n)}, then x is a real number in [0,2] in
V[G], but x is not an element of V, i.e. x is a new real number.

>That's why I interpreted what you said as affirming the existence of a
>bijection between N and R, because N^V[G] has no element not in N and
>bijectively maps to R, the set of all real numbers.

Only if you do not take enough care to precisely specify your meaning.

>EF is basically n/oo defined for n E N.

That is not a proper definition of EF. Define oo. If oo is meant to be
infinity, then your definition is no definition at all.

>There is much discussion of
>it on sci.math.

>The average value of all hypercomplex numbers is zero.

Define "hypercomplex number" if you don't mean quaternion, and explain
what you mean by "average value" in this context.

>I try to not use models in theory,

Then how do you know what you are calling a set and what you are not
calling a set? The model is the collection of all sets.

>because I think a theory should be
>just a theory,

If you have "just a theory", then you don't have any concrete examples of
your objects.

>and to not use classes in set theory, because a set
>theory should have only sets.

Which ZF and ZFC do.

>Applying a metatheory or extended model or denying that anything is a
>set in set theory only leads to obfuscation and not a real addressing
>of the resolution of basically set existence issues within the set
>theory itself.

You need axioms to specify what you are calling a set. What are your
axioms?

The rest is cut out until Ross supplies convincing evidence that he knows
what he is talking about.

David

-----