Re: Does the set of all sets exist?

-- Naturals N={1}* vs unNaturals 2^N={0,1}* (Peano/Cantor)

Subject:      Re: Does the set of all sets exist?
Author:       Nico Benschop 
Date:         6 Oct 99  -- news:sci.math

N.G. du Bois  on Tue, 05 Oct 1999 asked:
>
>Hi everyone, I have a question.
>
>Does the set of all sets exist?
>Let us assume R is the set of all sets. P(R) is the powerset of R.
>
>1. What is P(R)?
>    by definition contains all sets.
>    But when P(R) is a member of R, I immediately can
>    create a new powerset P'(R) which originally was NOT in R.  ..[*]
>    But then I must conclude that R is not the set of all sets.
>
>  b. Let us assume P(R) is not in R. Then I must conclude
>     that R is not the set of all sets.
>
>Does anyone have some idea's about this?
>Best regards, -- Nico du Bois.

Hi naamgenoot:

This kind of contradiction you are guaranteed to get if you stay
too 'abstract', or rather: too vague, in your concepts. There is
in fact no balance between the syntax and the semantics, meaning
(roughly;-) that the abstract concepts are not made 'hard' by
some definition of *how* to construct the elements in your
argumentation. Like: what is a SET, *how* do you construct a
POWERSET (under what conditions can you 'construct' such without
running into logical trouble as above?)

For instance, the concept of 'powerset' came into being (as far as
I know) due to Cantor's work on the cardinality of all subsets of
the set of integers (or rather, of all positive integers: the set
N of naturals), denoted 2^N because any finite image of it can be
constructed by (countable_length) strings over any alphabet of
two letters [with an arithmetic interpretation:
     n = \sum n_i.2^{-i} i=1-->inf,  ... with  n_i \in {0,1}
         being the "reals" between 0 and 1]

Now this 'exact' kind of description of a powerset should not be
'immediately' brought into the *much* larger context of the "set"
of all sets. Because you have ignored the charcter of the Naturals,
as Peano so nicely defined it: being a one_generator set, namely
as-it-were: N = 0{+1}* , starting with 0 produce all its successors
by "iteration" (or repetition: the star *, which is an intuitive
concept, difficult to define more precisely, with the naturals under
addition as a model -- equally 'vague' but it seems to work for most,
although: N is a one-sided infinity -- starting at 0 --
while the integers Z={-inf .. 0 .. +inf} are a two-sided infinity,
which *does* have effect on the number of generators you need
"upto iteration", namely N needs one {1}, and Z needs two {-1,+1} ;-)

And you know that Cantors's work ignited (and still does ignite) a
lot of discussion. The problem *there* is that 2^N, which essentially
has the structure of a lattice (with two idempotent operations:
set intersection and union -- or: bitwise AND(&) and OR(V), is mapped
onto the real line_segment [0,1) which is *asking* for conceptual
trouble. Under (&),(V) the lattice 2^N has precisely N generators,
arithmetically: the countable set {2^-i} for i=1..inf, or: i \in N,
so of "infinite dimension" (because the operators are idempotent:
a&a=a, aVa=a for any subset a of N, so the concept of 'iteration' does
not exist in a lattice, such as 2^N, hence its enormous infinite
generator set N;-)

A  LINE is 1-dimensional (intuitive: iteration) while 2^N is
2-dimensional, the concept of "dimension" understood as the minimal
number of generators necessary for sequential generation of any
element of the set in question. So, for instance, any finite
(permutation) group G can be embedded (is a subgroup of) a group G_n
of ALL n! permutations of a finite set S of n elements -- with
dim(G_n)=2, so only 2 generators suffice to generate any 'full'
(symmetric) finite group of degree n
(viz: permutations of n states).

And for infinite sets there is even more NEED for a generative
definition, because how *otherwise* do we know what we're talking
about? (listing all elements would be impossible, now would'nt it?)

Then Peano's set N has dim(N)=1 -- the naturals have one generator
under addition (or: sequencing, if you prefer). And upto iteration:
2^N (all binary strings of countable length over alphabet 0,1) has
dim(2^N)=2, just as the set S of all strings over some alphabet
   A of k letters has dim(S_k)=k, of 'order' k^N.
For some low-by-the-ground & simple engineer's interpretation of
Cantor's diagonal argument, trying to interprete his work as much as
possible in a constructive way (just like Cantor's constructive
diagonal is: trying to reconcile 1-dim 'iteration' with 2-dim
lattice, which CANNOT be done, they are different data-types! ) see
  http://www.iae.nl/users/benschop/cantor.htm

Essentially, if you would want to go beyond Peano's N= 0{+1}*
and Cantor's 2^N = A* over A={0,1}  -- with or without arithmetic
interpretation as "reals" -- I think it is wise to introduce some
concept of "data-type" sothat one is NOT tricked into mapping a
(multi-dimensional) lattice onto some vague "dense linear" medium
as the "reals", where the concept of generator is ver te zoeken,
taking off in-a-tangent & escaping into infinities unrepresentable
(not even "upto iteration"...;-(

Ciao, Nico Benschop - http://www.iae.nl/users/benschop
                      http://www.iae.nl/users/benschop/finite.htm

Subject:  
 -- Naturals N={1}* vs unNaturals 2^N={0,1}* (Peano/Cantor)
Author:       Nico Benschop 
Date:         7 Oct 99 06:25:15 -0400 (EDT)

To elaborate, just a thought:
   comparing Peano's countable Naturals (set N: positive integers) with
   Cantor's uncountable powerset 2^N (Boolean lattice of all subsets of N)
it occurred to me that:
1. as model of "iteration" (*) in general, N has one generator:
        N(+) = {+1}* as an arithmetic model under addition.

2. as model of "combination" in general (set intersect & -- union V):
        2^N(&,V) = {0,1}* as boolean lattice of binary strings.

Rather then the different infinities they span, this view emphasizes
the way of representing and generating the objects involved, with as
distinguishing feature: the minimum number of generators ("dimension")
which essentially distinguishes N from 2^N (also finite sets |N|).

Let's call that "sequential dimension" (seqdim), or dim(S) in short -
in this context - of such set S of 'fundamental type'.

In other words: they are of different "data type", a concept familiar
in computer -science and -languages (re: object_oriented language).

For instance the folowing usual(sets of) math_objects are of distinct
data_type, with specific operations, well defined few number of
generators, and maximal orders related to the underlying sets:

dim(S)  type of S   operation   generators

 1  naturals N, addition (+):  N= {+1}*    (one_sided countable inf)
 2  integers Z, addition (+):  Z= {-1,+1}* (two_sided countable inf)
 2  permutations (n states) group G_n (sequencing): G_n = {a,b}*
     where a= n_cycle, b= (n-1)_cycle and one fixed state (finite)
 3  transformations (n states) semigrp T_n (seq): T_n = {a,b,c}*
     where {a,b}* =G_n,  c= (n-1)cycle and merge two states (finite)

The correponding closure orders are, relative to |N| = n :
 |Z|= 2n+1 (including 0),  |G|= n! and  |T| = n^n.

A slight problem is 2^N, of order 2^n, which has only idempotent
operations (non-iterative): set_intersection (&) and union (V),
over which operations the dimension of 2^N is |N|, for instance take
as generators the N binary strings with single '1' in place i (all i
\in N} and rest 0, with bitwise boolean AND cq OR as model for (&) and
(V).

But 2^N can be embedded into infinite group G_N, namely for instance
as fix-point subsets of permutations of N. Then each element of 2^N
can be coded, in the finite case over {a,b}* generating G_n. And in
the infinite case of all N! permutations group G_N = {a,b,c}* with
a= +1, b= -1,  c= [swap(0,1) rest fixed] as shown earlier in
         http://www.iae.nl/users/benschop/cantor.htm
Then 2^N < \subset G_N, with:  seqdim(2^N) = seqdim(G_N) = 3.

Would'nt much misunderstanding be avoided by this generative (seqdim)
viewpoint, emphasizing the operations and generators involved. That
is: rather stressing the _structure_ of sets in stead of only their
order (especially for infinite sets the generative view is imperative,
to define such sets in the first place!) --- Any comments?

Ciao, Nico Benschop - http://www.iae.nl/users/benschop/seqdim.htm

Re: -- Naturals N={1}* vs unNaturals 2^N={0,1}* (Peano/Cantor)
Author:  Nico Benschop 
Date:    1999/10/09
Forum:   sci.math

Fred W. Helenius wrote:
>
> Nico Benschop  wrote:
>
> >Fred W. Helenius wrote:
>
> >> I've pointed out before that, using conventional definitions, a
> >> finite number of generators produces only a countable number of
> >> elements. ..[%]
>
> >Re[%]: I never quite understood that a UC (uncountable) set like 2^N
> >       requires a UC set of generators. But I guess I understand what
> >       is meant: it's a matter of definition what "generator" means.
>
> That does seem to be the key; you want to include infinite products,
> even though they aren't defined in general.  For permutations of Z,
> what would the product of an infinite number of shifts to the right
> (your "+1") be?

I guess that would be w (omega)...
Just guessing: I'm clearly not an expert at infinities;-)

> Is the product of infinitely many "swaps" of 0 and 1
> equal to the identity or to "swap"?

It does not quite matter here: what matters is that all permutations
of Z can be expressed one way or another. For an minimal expression,
at least one could say that for group Z!={a,b,c}* with a= +1, b= -1,
c = swap(0,1) and rest fixed: then cc=e, and ab=ba=e (the neutral
group    element, that is: the "do nothing" or: "fix all states"
permutation).
   Then an irreducible representation would be of form (a* c b* c)*
   or (c a* c b*)*  or something like that: "c" playing the role of
   'separator' or 'comma' as it were. Then this looks already very
   similar to 2^N = {0,1}* with two generators - strings over a two-
   letter alphabet, such as 000110111001 <--> aaacbbcacbbbcaacb etc.
   Towards some kind of morphism between Z! and 2^Z.

> >In group theory, for instance, a cyclic group G = g* is meant to be
> >the collection (set) of all iterations of some generator g under
> >sequencing (sequential function composition), often noted as
> >{g, g^2, g^3, ...} in some "multiplicative" notation.
>
> As well as powers of its inverse, g^(-1), g^(-2), etc.
>
> >Also: N = {+1}* iss meant to have just one generator, namely '1'
> >under addition, or repetition if you like: the set of strings of
> >increasing lengths: {1, 11, 111, 1111, 11111, ... }  written as set N,
> >usually deonted as: {1, 2, 3, 4, 5, ... }
> >having just _one generator_ "1" under addition (resp union).
>
> Replace "union" with "concatenation" and that's fine.

Concatenation comes first: to produce each n-string of ones,
          union comes next, to form the SET of such strings.
>
> >Now Cantor's set 2^N of all subsets of N: here the elements of N are
> >represented for instance in binary code, as strings over {0,1} with
> >    the arithmetic interpretation of reals on interval [0,1) .
>
> >It was my understanding that this 2^N is a Boolean lattice under
> >union and intersection, which qua 0/1-strings can be represented
> >by "bitwise" OR and AND. For instance in the simple finite case
> >of 3-bit code: {0,1,2,3,4,5,6,7}={000,001,010,011,100,101,110,111}
> >   we have a 4-layer lattice, representing the 2^3 subsets involved:
>
> >              111
>
> >       110    101   011
>
> >       001    010   100  <--- N_3 set of generators under (V) union
>
> >              000
>
> >with the usual inclusion relation, like 010 < 110, and 010 < 011.
> >The set of "singletons" N_3 (strings with one '1', rest 0) is a
> >generating set under union,
>
> So far, so good...
>
> >which is understood as "upto repetition"
> >like: 111 can be reached upon repeated union of elements from N_3,
> >although indeed this requires two steps, such as
> >    111 = (001 V 010) V 100.
>
> >I guess that you mmean with "conventional definitions" that this
> >_upto repetition_ does not hold in the established Cantor theory.
> >In that case there's a misunderstanding on my part ;-(
>
> "upto repetition" means nothing to me

The meaning of it is that of the star (*) in for instance set S = A*,
which is the set of all strings over alphabet A (of a given finite
number of letters). Then S is specified by A, "upto iteration".
Or a function F(x) to compute the limit L with a converging algorithm,
limit L = F*(x_0) is defined by function F, "upto iteration" (of F).

> -- you never need to repeat
> a generator in a Boolean lattice.  And, AFAIK, Cantor doesn't
> address generators -- it's not a term I've seen in set theory.

That is precisely my point: powerset 2^N, or rather 2^Z, can be
seen as contained in infinite group Z! -- namely each subset of
Z is a fixpoint_set of some permutation of Z. The clue is the Z!
can be shown to be sequentially generated by only 3 generators
Z! = {a,b,c}* as defined above, and so each subset of Z has a
unique (?) irreducible code as string over generator alphabet
A={a,b,c} where c functions as "comma" between each a* and b*
(any a^i resp b^j repetitions) as shown above. I admit, a strange
construction, but it drags 2^N out of that counter-intuitive corner
of "reals on interval [0,1)" which form not quite a linear structure
(that our intuition connects with a number line, does'nt it?).

> >In other area's of math (like group thoery, and associative algebra
> >of strings cq function composition) the concept of "generator" _does_
> >by defiition mean: _upto iteration_ (or: upto repetition).
>
> It means that finite products of the generators (and, for groups,
> their inverses) are allowed.  Alternatively (and equivalently),
> one says that a set of elements generates the (semi)group G if
> G is the smallest (semi)group containing the generators.  That's
> what I mean by "conventional definitions".  They are from algebra.
>
> Why the restriction to finite products?  Because, in algebra, infinite
> products are not defined; we start with a product of two elements and
> use induction and associativity to define finite products.

Peano's set N of naturals is itself obtained by infinite "products"
namely repeating the generator 1 any number of times, in fact also
an infinite number of times, if I'm not mistaken.

> [By the way, what is that "cq" that appears in so many of your posts?
> I've found that substituting "that is" usually works, but what is it
> supposed to be?  A Latin abbreviation, perhaps?]
>
> >The whole concept of generator is otherwise rather empty... So in
> > _that_ interpretation: N as set of singletons (all strings with a
> >single 1, rest 0) _is_ a generator under union (bitwise OR) of 2^N,
> >hence the countable set N generates the uncountable set 2^N of all
> >binary strings of countable length. I hope you understand me now?
>
> This works fine for your finite example, but how can you generate
> a string with infinitely many ones?

No problem (;-) I just denote it by 1* -- and mind you: there is
precisely ONE such element: the 'top'-element of the corresponding
(infinite) Boolean lattice, with 0* as single bottom element.

> Since your product is "union",
> you know what you want an infinite product to mean, but it's still
> excluded by either definition of "generates".
>
> Using the "smallest containing semigroup" version of the definition,
> your generators are contained in the set of strings having a finite
> number of ones, and that set is closed under union, and so is a
> semigroup.  A countable one, of course.
>
> >Further comments, more about the essence of my proposal to shift
> >emphasis from cardinality of the closure towards cardinality of a
> >minimal generating set, please.
>
> It seems to me that you're trying to compare things that aren't
> comparable ("apples and oranges" is the English idiom).

That's precisely my objection against comparing cardinalities
of N and 2^N : they are of essentially different "data-type",
as the Cantor diagonal argument so clearly shows. Certainly one
should not even _try_ to map 2^N onto some "real-line" segment!
.... _That_ is comparing "apples with oranges": integers with lattices.

> Every set has a cardinality, but sets don't have generators; groups
> and semigroups do.  And the same set can, under different operations,
> be turned into structures with different numbers of generators.
> So the generators are giving you information about the operation,
> not just about the set.

Agreed: one can only talk of 'generator' if some operation is defined.
Now for SETs the only operations that (I assume) make sense
are set_intersection and set_union (apart from direct_product
constructions of course). And both are idempotent, which makes them not
very powerful as generators, I agree. Hence my 'gedanken experiment' to
embed 2^Z into Z! which latter has only 3 generators (under permutation
sequencing).

> For example, take the naturals, N.  Under addition, as you've noted,
> N needs only one generator.  But N under multiplication is also a
> perfectly good semigroup.  How many generators does it need?

All the primes, thus N(.) has an infinite set of generators under (.)

> Some sets don't have any natural operations on them, so it doesn't
> make much sense to speak of generators.  Consider the set of
> irrational real numbers:  What are its generators?
>
> Another issue is that cardinality is meant to formalize some aspects
> of the intuitive notion of size, and the number of generators has some
> properties that make it ill-suited for this.  In particular, a group
> with a finite set of generators (two is enough) can have a subgroup
> that has no finite set of generators; whereas the cardinality of a set
> is always greater than or equal to that of a subset.
>
> In some instances, the number of generators does behave well, and then
> it is used.  For instance, two important theorems in group theory say
> that free groups (or free abelian groups) are isomorphic if and only
> if they have the same number of generators.  In these two cases, the
> number of generators is called the rank of the group.  The dimension
> of a vector space is a similar example, although the vectors in a
> basis "generate" a vector space in a somewhat different sense than
> we've been using ("finite products" is meaningless, but "smallest
> containing subspace" still works).  And stretching the analogy still
> further, the number of generators of an ideal is important in
> algebraic number theory, and topologists care about the size of a
> basis of a space (or at a point).
>
> So the idea of "number of generators" is widely used, but doesn't
> have a place in set theory since sets, considered only as sets, don't
> have generators. -- Fred W. Helenius      

Agreed, on the other hand: as I have been trying to explain,
  this need not be the end of the story, via 2^Z < Z! ... ;-)
At least, this way of looking at powerset 2^N, or rather 2^Z = A* with
|A| = 2 in case of {0,1}* strings, or |A| = 3 in case of Z! = {a,b,c}*
one gets a better feeling of the essential distinction between N and 2^N,
since they are essentially distinct data-types (distinct object types).

BTW: "cq" is from the Latin "casu quo", meaning "as the case may be".

--
Ciao, Nico Benschop.             | AHA: One is Always Halfway Anyway
http://www.iae.nl/users/benschop | Institute of Advanced Engineering