"Given any Real number c, there exists a natural number n such that n >
c". If all naturals are reals, then this may be restated as "A neN E meN
| m>n". Sound a little Peanoesque to you?

Not at all. It is clearly Archimedean, preceding Peano by millennia.

Once they are ordered in whatever manner, they become sequences, trees,
or other structures, and it is only with such a recursive definition
that such an infinite structure can be created.

Why is a recursive definition required? Given any set S, the set of
all subsets of S can be (partially) ordered as follows: for subsets A,
B of S, define A <= B iff every member of A is a member of B. What is
recursive about that definition?

That structure doesn't look like a tree to you, which each node having
as children the elements of its power set? That's the picture that
appears to me.

Perhaps that works for you; although your "tree" has a maximal member
(every subset A of S satisfies A < S) and and a minimal member (the
empty sets satisfies {} < A for all subsets of A).
Most times, when people talk about trees, they mean a set having
either a maximal element or a minimal element; but not both.
To me, that "looks" more like a fish net or a giant diamond than a
tree.
At any rate, my question was: what is recursive about that definition?

May I restate the definition, for the purposes of this elucidation?

1. E S e P(S)
2. A X e P(S) A x e X E Y e P(S) | A y e X (x<>y -> y e Y)

Either I'm getting better at understanding the quirks of your
notation, or you are getting better at constructing readable sentences
in predicate caluclus (or both, or I'm delusional).

If I'm right, what you are trying to describe is sort of a dandelion
puff or fireworks explosion, with the set S as its center, and then
some branches and at the end of each branch another similar
"explosion"; and so on. (It's the "and so on" part that's going to be
contentious eventually ...)

But what your 1. and 2. don't take into account is that we can (and
"frequently" must have), given any two elelemnt x,y in S:

S
/ \
/ \

S-{x} S-{y}

\ /
\ /

S-{x,y}


So the "tree" criss-crosses like a chain link fence. This type of
partial order is usually called a lattice.

In order to get a "tree", we need to make sure that we don't do this
kind of criss-crossing; which is more than you've stated in 1. and 2.

It's easy to see how to do this is S is finite. It's harder to see how
to do this if S is not finite, without some sort of choice function.
And then we get to the whole axiom of choice implies well-ordering
thing.

Does this not recursively define a tree of subsets of P(S)?

It doesn't meet the usual notions of "recursive" that I know of; but I
think I see where you're trying to go - you're trying something
similiar to our previous discussion regarding how the axiom of choice
implies a well-order.

You may consider S to be the maximal element of P(S).

Yep.

Alternatively, S be the set of all subsets of the naturals (note that
S is not countable).

If A, B are in S, define A <= B if there is a

natural number m in B such that m is not in A, and for all n < m, n in
A and n in B. What is recursive about that definition?

The Archimedean principle, as far as I can tell.

In what way does the assertion:
For all positive real numbers r, there exists a natural number n such
that n*r > 1?
apply to definition above, which is about sets of naturals, and never
mentions real numbers at all?

"Given any Real number c, there exists a natural number n such that n >
c".

That's certainly equivalent. But how does that observation relate to
the ordering I gave? It is about sets of naturals, not reals. And how
is it recursive?

If all naturals are reals, then this may be restated as "A neN E meN
| m>n".

I would call that "the restriction of the principle to N".

Sound a little Peanoesque to you?

Not really. Peano helps understand the naturals; and usually one uses
the naturals (and a bunch of other stuff) to make the reals.

But the statement (btw I usually use ":" for "such that")

A neN E meN : m>n

doesn't imply that m is the /smallest/ m satisfying m > n. Yes, we
know from the properties of the naturals that there /is/ a smallest
such m which would then be the m that "comes right after" n (thus
satisfying your allusion to a successor); but that isn't always the
case.

I'll formalize "m is the smallest natural which is larger than the
natural n" by:

(m,n in N) and (m > n) and (for all s in N\{m}, if s > n, then s > m)

But if we switch to the rationals,

(m,n in Q) and (m > n) and (for all s in Q\{m}, if s > n, then s > m)

then there is no such m for any n in Q.

In that sense, there is
no pure infinite set without some defining structure, so whatever
conclusions one thinks they have come to regarding infinite sets without
structure have no basis for comparison. Powerset(S) is 2^|S| sets, no
matter the size of S. That is a specific case of N=S^L, which applies to
symbolic strings and alphabets, as well as power sets where elements can
have S different levels of truth, not just 2. There are 3^log2(n) as
many ternary strings of length n as there are binary strings of length
n, be n finite or infinite. But, that involves a discussion of structure.

Anyway, my point is that the recursive nature of the definition of the
"set"

What recursive definition of what set?

Oh c'mon! N. ala Peano? (sigh) What kind of question is that?

Does TO seem to thing that N is the only set defineable recursively or
that "successor" is the only recursively defineable operations on sets?

Does Virgil forget what he cuts from the post? What do you think we were
discussing? I thought it was N specifically.

I thought it had something to do with the real line, and orderings.

Points and lines, anyway. And points on R in N.

On R, and yet in N? I don't understand what you mean.

On the real line R, in the subset of real points called N.

Or, whatever.

Indeed.

Order is defined by x<y ^ y<z -> x<z.

Transitivity is one of the properties of most of the orderings we're
talking about. But transitivity is not the only property that defines
such things as 'partial order', 'linear order', 'well order'.

It defines order, in general.

Only to TO. For everyone else, other properties are required.
For example, in addition to transitivity,
((x>y) and (y>x)) -> x = y
is a necessary property /every/ ordering.

Um, that one is blatantly self-contradictory. x>y -> not y>x, always.

I don't see how this follows only from your assertion "x < y and y < z
-> x < z". You stated:

Order is defined by x<y ^ y<z -> x<z.

Or do you mean that there is /more/ to the definition of an order "<"
than "x < y and y < z -> x < z"? If so, that was exactly Virgil's
point.

Actually I corrected this response to Virgil. I misspoke a little, but
he's still wrong. :)

suppose you meant:
((x>=y) and (y>=x)) -> x = y
or:
(~(x>y) and ~(y>x)) -> x = y

These two statements are not equivalent. In some situations, the first
can hold, while the second does not.

Please do elaborate.

See the example I posted below regarding subsets of {a,b,c}.

Yes, if neither x<y or y<x is true, that is, if no order can be
determined, then x=y for the purposes of that order.

Let's order the subsets of {a,b,c} by inclusion. Then: {a,b} <
{a,b,c}. {a,c} < {a,b,c}. {a} < {a,b}. {a} < {a,c}. But not ({a,b} <
{a,c}); and not ({a,c} < {a,b}). Does that mean that {a,b} = {a,c}
"for the purposes of that order"?

Where b<c, {a,b}<{a,c}.

Since "<" indicates subset inclusion, it is the case that not b < c.

If a, b and c are members of a set such that xeS ^ yeS -> x<y v y<x v
x=y, then either b<c v b<c v b=c.

Yes, if a set is totally ordered (i.e., the ordered pair (S, <)
defines a /total order/ on the /elements/ of S), then (trivially) it
can be totally ordered.

But I was talking about the ordered pair (P(S), <) where < is subset
inclusion; which defines a /partial/ order on the /subsets/ of S.

In that case there are distinct /subsets/ X, Y of S with not (X < Y or
Y < X). Which is to say that there are distinct /elements/ X, Y of
P(S) with not (X < Y or Y < X)

Where b=c, {a,b}={a,c}.

Since b and c are distinct elements of the set {a,b,c}, not b=c.

Then either b<c v c<b.

If not b<c and not c<b,
then b=c.

Since "<" indicates subset inclusion, it is the case that not c < b.
As noted earlier, also not b < c. And yet not b=c.
I should note that "<" is therefore a partial order, and not a total
order.

Well, in the standard vN model, each successor is proper superset.
Therefore, b is a proper subset of c, in that model. Is c successor to b?

But given some (vN) ordinal a, I was describing the ordering by
inclusion of the elements of P(a), not the ordering by inclusion of
the elements of a.

Suppose a = 7. Then the ordering implied by inclusion on the elements
of /a/ is indeed a total order: e.g., {0,1,2} < {0,1,2,3,4,5}.

But the ordering implied by inclusion on the /power set/ of 7 is not.
The set {0,1,2,7} is incomparable to the set {0,1,2,3}.

That defines '=' in
terms of '<'. It defines a point on the line, more or less, to get back
to the original question.

Could you state what the definition of "<= totally orders the set S"
is again? There are three simply stated properties, IIRC.

Lookitup. Transitivity does not define "total order", but is that start
of order.

Of course. But when you stated as you did earlier:

Order is defined by x<y ^ y<z -> x<z.

then you were stating a falsehood; and you knew it was a falsehood.
Liar! Pants on fire!

Did I say "total" order? Maybe you snipped it....

Okay: if you said

A total order is defined by x<y ^ y<z -> x<z.

then you were stating a falsehood; and you knew it was a falsehood.
Liar! Pants on fire!

Also there are lots of transitive relations which are not orderings, at
least as usually understood. E.g., universal relations, which hold true
for all x and y in the relevant set.
So that TO's notion of an ordering does not necessarily order anything.

You're missing the point. All I said was that one starts with inequality
defining the line itself.

Is every set a line? Is the set of all triangles in the Euclidean
plane a line?

That's a bunch of lines.

Come, Mr. Tony mon, tally me triangles.
Daylight come, and me wan go home.
Isoceles, acute, obtuse, bunch!
Daylight come, and me wan go home.

Hey Mon, stay and have one more domn spliff, Mon.

If only.

You build geometry from points and lines, or from lines and points, if
you're Lester. :)

Then one defines equality. Defining equality
where there is no relative order doesn't make sense.

So, it makes no sense to say that the set of all finite subsets of the
naturals having a prime number of elements is equal to itself?
Cheers - Chas

Again, there is order to the elements themselves.

I'm confused.
Do you mean that the elements of the set of all (sets of subsets of N)
are ordered with respect to each other? If so, how?
Or do you mean that any given set of (subsets of N) is always, itself,
an ordered set? If so, how?
Or do you mean that any subset of the naturals is an ordered set? If
so, do you mean the usual order, or some other ordering?
In each of these cases, there of course are /many/ possible such
orders, not all of them isomorphic. Which one are you speaking of?
Cheers - Chas

Consider that all elements of N, x and y, are such that not(equal(x,y))
-> x<y v y<x.

Let's just say N is totally ordered by <.

Now, assign to each such natural a bit position, the first
most significant, and each successor less significant than the last.

Umm, I think you mean that the other way round; but sure, let's
associate each natural n in N with the sequence B_n defined by B_n(x)
= 0 if n <> x, and B_n(n) = 1.

Since we are either fully including each element in a member of P(N) or
fully excluding it, we have a dualistic function, such that we can
encode the inclusion using one of two symbols, for each neN.

Okay, so now for each subset X of N, we have the sequence B_n with
B_X(n) = 0 if n is not in X, and B_X(n) = 1 if n in X.

if We have
created a binary string, and if we consider all bits to be to the right
of the binary point, with the first being the first bit,

... but of course! ...

then we have
ordered the subsets of N according to the quantitative order of the
reals in [0,1].

Imposing the ordering of R as you propose is a /pre/-order (or a pre-
total-order) on the sequences you describe.

I think you would agree that the "sequence of bits":

0000111...

is not the /same/ sequence of bits as:

0001000...

Equivalently, the set X = {n : n > 3} and Y = {3} are not equal.

And yet, with the ordering you describe, (0000111... <= 0001000...)
and (0001000... <= 0000111...); which is to say X <= Y and Y <= X and
yet, not (X = Y).

So, there is order to P(N), such that SeP(N) ^ TeP(N) ^
s<>T -> S<T v T<S.

That's wrong with the ordering rule you describe; but it's easily
fixed. It's obvious where the problem is: trailing 1's and trailing
0's; so we can pretty starightforwardly add a rule which makes
0000111... < 0001000... and covers all similar cases.

So yes; we can define a total order on the elements of P(N) using the
ordering of N.

But I wasn't talking about ordering the /elements/ of P(N). I was
talking about ordering the /subsets/ of P(N); which is to say ordering
the /elements/ of P(P(N)). E.g., one element of P(P(N)) is the set X
of /all/ subsets of N having prime order; and another is the set Y of /
all/ subsets of N consisting of a finite number of primes. How should
I proceed to determine whether X <= Y or Y <= X in such a way that <=
is a total order on P(P(N))?

Cheers - Chas