On Oct 9, 2008, at 6:59 AM, Rob Freeman wrote: Pat,
I am unable to distinguish your question "Why does this fact of
combinatory mathematics matter to a given system?" from my question
"whether all these possible sets are distinct in meaningful ways."
My question refers to a *system*, following your terminology. Your question does not mention any system. Your question uses the term "meaningful", whereas my question does not refer to meaning at all.
If you are unable to distinguish these, I am at a loss as to how to proceed with the conversation. You say for the case of "cardinality in logical interpretations", at
least, the question has been looked into, and the answer was that "the
number of possible relations over a universe is a much larger
cardinality than the universe ..., but this doesn't matter because the
logic isn't obliged to consider all of these relations, only enough to
provide denotations for all the relation-naming terms in the
language."
That argument strikes me as completely circular. Who says how many
relations are "enough to provide denotations for all the
relation-naming terms in the language"?
The semantics determines this. In the case of CL, for example, the semantics is based on the idea that the only relations that are required to exist are those that are actually named by relation names in the axioms. Now, you can of course object to this, but that would be an objection to the whole of CL, and you would then no doubt prefer a different logic. Other logics make different assumptions: the Henkin version of higher-order logic for example assumes that any relation which can be named by an lambda-_expression_ must exist: a much larger set, but still of at most of a countable cardinality. Classical higher-order logic assumes that all mathematically possible relations exist, which is uncountable when the base universe is infinite. Description logics (which deal directly with relational descriptions) typically satisfy the finite model property, so only assume a finite collection of relations. The number of relations we
need is exactly the question at issue.
Need FOR WHAT? Until you get down just a little detail here, questions like this are (literally) meaningless, as there is no fact of the matter. I mentioned CL only to to try to provide such a focus, but if you weren't talking about logics and semantics, please provide a different focus.
BTW, in resolutely practical terms, description logics are of wide utility in applied ontology work, so apparently a lot can be done with a very limited relational palette, so to speak. This is again the question when I ask "whether you can ignore sets and
work only with categories."
Again, until you clarify what you mean here (what kind of "working with" are you talking about? What is a category if it is not a set? Etc..) such discussions are just word-salad. Give us an example of 'working with' categories that aren't sets. The distinction at the end you "completely fail to follow" is yet
another a restatement of this question whether all these possible sets
"matter"/"are distinct in meaningful ways".
The passage I was referring to is this:
"It is really a question of complexity. For a given set of examples if there are fewer distinct sets than examples you will be able to label all the sets and get along fine with the labels. On the other hand if there are more distinct sets than elements you will have no alternative but to work directly with the sets."
This talks about (1) using labels rather than sets, and (2) being prevented from doing so by the large number, so (3) being forced to work directly with the sets. I have no idea what this is all about, or what kind of 'working with' you have in mind, or what you mean by labeling a set, or even why the conclusion follows. (Why can there not be more labels than elements?). But none of this seems to have anything at all to do with questions about which sets "matter".
Look. All distinct sets are distinct, obviously. The cardinality of the set of subsets of a given set is indeed much greater than the cardinality of the set itself. So far, this is all elementary set theory, and hardly worth discussing on this forum. Apparently, you see some "game-changing" deeper issue lurking here, to do with meaningfulness and 'systems' (and possibly labels?). You have not (yet) clarified what this deeper issue is. Simply repeating that power sets (= sets of distinctions, in effect) are awfully much bigger than their base sets, does not in itself provide the needed clarification.
Yes, these sets are all distinct. I don't know if they are distinct in "meaningful ways" because I don't know what you count as a 'meaningful way'.
Pat
-Rob On Wed, Oct 8, 2008 at 11:54 PM, Pat Hayes < phayes@xxxxxxx> wrote:
On Oct 7, 2008, at 11:59 PM, Rob Freeman wrote:
Pat,
Thanks for addressing my complexity point.
On Tue, Oct 7, 2008 at 11:26 PM, Pat Hayes <phayes@xxxxxxx> wrote:
On Oct 7, 2008, at 2:44 AM, Rob Freeman wrote:
My argument has been that for many systems there are more ways of
generalizing examples than there are examples. This is a game changing
assumption. Up to now it has always been assumed that there will be
fewer generalizations than examples (rules, classes, etc.) At worst
that you need to make one generalization per example (analogy.) If it
is possible to make more generalizations than examples, the game
changes completely. No one set of generalizations will suffice.
OK, that sounds really interesting. But Im having trouble understanding it.
Can you make the point more concrete, perhaps with an example/sketch? What
leads you to this conclusion, that there will be this overwhelming number of
generalizations in many systems? What kind of systems, and why will they
have the top-heavy quality?
It is easy to prove there could be more meaningful combinations of n
elements than n, for any system.
More combinations, of course. This is why for example classical higher-order
logic is undecidable, because its semantics requires that its
interpretations contain all relations in this mathematical sense (and when
the base set is infinite, this makes the set of relations much more
infinite.) But (1) you have to be more specific about what you mean by a
'system' in order to see what this means in practice; and (2) not all
combinations are 'meaningful'.
The maximum number is something like
the binomial coefficient {n choose k} = {n!}/{k!(n-k)!}. With
variations according whether the order of elements matters etc.
For sets its just 2|n
The only question is whether all these possible sets are distinct in
meaningful ways.
No, that is not the only question. A more important question is, so what?
Why does this fact of combinatory mathematics matter to a given system? Take
Common Logic, for example (which isn't a system, exactly, but never mind):
the number of possible relations over a universe is a much larger
cardinality than the universe (see above), but this doesn't matter because
the logic isn't obliged to consider all of these relations, only enough to
provide denotations for all the relation-naming terms in the language. So
this just isn't an issue in CL.
Let me turn the question around. How do we know they are not? Has
anyone ever looked into it?
Well, the question as posed isn't precise enough to look into. What kind of
system are you talking about? For the case of cardinality in logical
interpretations, the answer is certainly yes, in fact its been a major focus
of work in model theory for the past decade.
The only way to model that would be to base analysis on sets of examples.
There is an old idea (due I believe to Whitehead in the early 20th century)
that may be relevant here. If all you have are categories (generalizations,
classes,..), then you can define individuals to be maximal sets of
intersecting categories. Mathematically, they are ideals or ultrafilters
(same thing looked at upside-down.) Its a very elegant and powerful
technique: I've used for example to show that any notion of 'context' that
satisfies some basic assumptions can be reduced to sets of individual
context-points. It can be used to define time-point in terms of
time-interval, and other apparently impossible "backward" creations of
individual- or concrete- ish objects from clouds of vaguer ones.
Right, yes, basing categories on sets has a history. We can feel
comfortable thinking of categories in this way. Others have done it.
Using sets to represent categories is not a crazy proposal at all.
Um...no, its not. In fact, virtually all of modern mathematics is 'based on
sets'.
The
question is whether you can ignore sets and work only with categories.
? Why is that an interesting question or an interesting ambition? What do
you gain by ignoring sets?
It is really a question of complexity. For a given set of examples if
there are fewer distinct sets than examples you will be able to label
all the sets and get along fine with the labels. On the other hand if
there are more distinct sets than elements you will have no
alternative but to work directly with the sets.
I completely fail to follow you here. Of course there are not fewer sets
than examples, since there is a singleton set for each example.
Pat
------------------------------------------------------------ IHMC (850)434 8903 or (650)494 3973 40 South Alcaniz St. (850)202 4416 office Pensacola (850)202 4440 fax FL 32502 (850)291 0667 mobile
|