Do J sets need to be ordered? Fraser believes not, and I will try to persuade
him otherwise following his note below.
Admission: My aim as an implementor of a J sets model is to have a model which
obeys most of the rules of mathematical set theory. I want things to be very
precisely specified. A different aim is not to worry "too much" about
mathematical set theory, instead aim for a consistent set of verbs with wide
applicability to arrays thought of as sets of their items.
Some mathematical rules are contained in my "Catechism for an Implementor"
begun
in a reply to Tracy in this thread on 2 August. In the present discussion we
are working on Question 1 for an implementor:
1. Question: What is a set?
Answer:
2. Question: What is an element of a set?
Answer:
Now please read Fraser's note and what follows.
Fraser Jackson wrote:
> I doubt if 'ordering' the elements of a set should be important. An
> 'ordered' set is a quite special class of set. I am not sure what order ;:
> 'apples oranges pears' should be in.
>
> My functions were written to avoid the need for ordering. It is however
> convenient to have a 'formal' or 'lexicographic' ordering for representing a
> set for some purposes. The function Set provided that but is not required
> anywhere else.
>
> For example the ordering of allsubsets given with Set is not a common
> ordering statisticians looking at the set of models of four factors would
> use.
Consider
]e1 =: allsubsets 'ab'
++-+-+--+
||b|a|ab|
++-+-+--+
]e2 =: '' ; (,'b') ; (,'a') ; 'ab'
++-+-+--+
||b|a|ab|
++-+-+--+
e1 isequalset e2
1
]e3 =: '' ; (,'b') ; (,'a') ; 'ba' NB. change order of 'ab'
++-+-+--+
||b|a|ba|
++-+-+--+
e1 isequalset e3
0
NB. But sets e1 and e3 have the same elements, so should be equal as sets.
NB. Same elements because
'ab' isequalset 'ba'
1
To avoid problems like this I recommend that every "set" in our model satisfy
(-: /:~) *. (-: ~.) -- that is, every "set" should be sorted and have no
duplicates. In order for this to be recursively true of sets some of whose
elements are sets, sets should be "sorted and nubbed" at creation time:
Redefining e1 and e3:
Set =: (/:~)@~. NB. sorted nub
]e1 =: Set allsubsets 'ab'
++-+--+-+
||a|ab|b|
++-+--+-+
]e3 =: Set ( '' ; (,'b') ; (,'a') ; Set 'ba' )
++-+--+-+
||a|ab|b|
++-+--+-+
e1 isequalset e3
1
e1 -: e3
1
A side benefit of this recommendation is that Match -: can be used for
isequalset.
You may wonder, why sort allsubsets 'ab' ? The reason is, this set could
become
an element of another set and cause the same difficulties 'ba' caused.
I would put a sort in verb allsets: any verb that creates a "set" should ensure
it is sorted and nubbed. With this addition, if allsets is given a "set" that
is recursively sorted and nubbed, it will produce a "set" that is recursively
sorted and nubbed. I call the new allsubsets "pwrset":
pwrset =: 3 : 0 NB. allsubsets with sort added
if. isemptyset y do. a:
else.
/:~ (#&y) &.> ( <"1 (#: i.2^#y))
end.
)
]e4 =: pwrset 'ab'
++-+--+-+
||a|ab|b|
++-+--+-+
e1 -: e4
1
Question 1: What is a set?
Answer: A set is an array that is sorted and nubbed.
Question 2: What is an element of a set?
Answer: If the set is open, an element is an item of the set. If the set is
boxed, an element is the open of an atom of the set.
(If an element is not sorted and nubbed, that element is not a set.)
Kip
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
