Message Boards Message Boards

0
|
8071 Views
|
18 Replies
|
10 Total Likes
View groups...
Share
Share this post:

Using Complement function?

Posted 8 years ago

Regarding the Complement function, I am trying to understand if I found an error or a misunderstanding of how the function is supposed to work.

Definition from MM documentation:

Complement[M,N1,N2,…]

gives the elements in the list M that are not in any of the lists N.

Here is an example:

Complement[{a, a, a, b, c}, {c,t}]

MM documentation says that the result should show those elements of the first set that are not in the second set. My read of this is that a, a, a, b are not in the second set. However, MM collapses the identical elements to a single element. In other words, MM seems to look at distinct elements.

So based on the documentation, I thought the result should be:

Complement[{a, a, a, b, c}, {c,t}] = {a,a,a,b}

but MM gives:

Complement[{a, a, a, b, c}, {c,t}] = {a,b}

Regardless of which is right or wrong, I'd like to suggest the following. If the function is kept as is, then the definition should be clarified to indicate that only distinct elements are considered. Written the way it is, it can easily be interpreted as ALL elements.

Thanks,

Jeff

POSTED BY: Jeffrey Lapides
18 Replies
Posted 8 years ago

See my point is the following: further up in this discussion Hans wrote: Complement works on sets. I learned long ago that a set is an assembly of well defined and well distinguished objects, so each object appears only once in a set. In the light of this definition {1,1} is not a set and therefore the reference for Subsets[] is not entirely correct.

Of course I agree that the way Subsets[] work is pretty useful, but its is not exactly what you would expect from the description.

POSTED BY: Michael Helmle

{1,1} is not a set

In strictly mathematical terms, the entity {1, 1} is a set, but {1, 1} = {1}. [Proof: Each element of {1, 1} is an element of {1}, and vice versa.]

But you are correct that Mathematica's Subsets function is not quite returning what one might expect. Of course the root of the problem is that you are feeding it as input something you really should not if you intend to be dealing with sets in the mathematical sense. You should be asking for Subsets[{1}, {2}] because the Mathematica list {1, 1, 1} does not properly model a set.

POSTED BY: Murray Eisenberg

I think it can be nicely summarized: if you give it a valid set, it will give you the valid subsets, if you given an invalid set, it will give you invalid subsets...

POSTED BY: Sander Huisman

Exactly.

And let's have a look what other "set-functions" do.

Take a set

set = {1, 1, 1, 3, 5}

which is NOT a set according to my remarks above. And so it turns out. The Intersection and the Union of a set with itself is the set. But

In[55]:= Intersection[set, set]

Out[55]= {1, 3, 5}

In[56]:= Union[set, set]

Out[56]= {1, 3, 5}

By the way, this is a convenient means to remove doubles

In[59]:= Union[set]

Out[59]= {1, 3, 5}
POSTED BY: Hans Dolhaine

Yes indeed, Intersection, Complement and Union force it to be mathematical sets, while Subsets is not so stringent.

Union removes doubles, but DeleteDuplicates does it a lot faster!

POSTED BY: Sander Huisman
Posted 8 years ago

In my opinion there a some inconsistencies left in the way Mathematica handles sets. Look for instance at Subsets: Taken from the reference: Subsets[list] gives a list of all possible subsets of list. So input can be a list (not necessarily a set), output will be a list holding sets. Now try this:

Subsets[{1, 1, 1}, {2}]

to receive

{{1, 1}, {1, 1}, {1, 1}}
POSTED BY: Michael Helmle

I think you could easily do DeleteDuplicates on it to eliminate 'doubles'. I.e. now the function is more useful, as you would not be able to do the opposite... Why Union/Complement/Intersection delete duplicates and sort the output? Just a design choice I think... tricky stuff indeed...

POSTED BY: Sander Huisman

Thanks again.

Jeff

POSTED BY: Jeffrey Lapides

OK, thanks. That's a simple resolution.

Jeff

POSTED BY: Jeffrey Lapides

Perhaps a little faster:

DeleteCases[eall,Alternatives@@Union[e1,e2,e3,...]]

...

POSTED BY: Sander Huisman

I think it is consistent if you read the guide page (guide/OperationsOnSets):

enter image description here

If you want to keep duplicates I suggest you use something like:

DeleteCases[eall,Alternatives@@Join[e1,e2,e3,...]]
POSTED BY: Sander Huisman

Are the elements of a list always to be rigorously considered to be elements of a set?

POSTED BY: Jeffrey Lapides

Sorry, but I don't understand that question!

From a strictly mathematical point of view, each object is a set (provided, of course, you stay away from objects that are "too big" to be considered sets and would fall within the category of "proper classes"). In particular, a "list" is modeled mathematically as an "ordered set", which more precisely can be defined as a function from an ordered index set to the set of elements that form the "entries" of the list.

In Mathematica, a list is such an ordered set, so that, for example, {a, a, a, b, c} is not the same thing as the list {a, b, c} — the latter being the result of Union[{a, a, a, b, c}].

Unfortunately, Mathematica does not directly provide a built-in kind of object that models sets. Perhaps the confusion is the use in Mathematica of the curly brace notation {...} notation for a list, whereas that same notation is conventionally used in mathematics to denote a set (which need have no order associated with its elements).

Just to make things worse, many mathematicians, and many mathematics books (including, alas, many if not most calculus books) use the curly brace notation for ordered sets, particularly when they are denoting sequences.

POSTED BY: Murray Eisenberg

Thanks for helping me understand where I went wrong.

Jeff

POSTED BY: Jeffrey Lapides

Elements of a set are not the same thing as entries in a list. The docs indicate that Complement treats the first argument, a list, as if it were a set and then deletes from that set those elements that belong to the second argument (or subsequent arguments). And that's what the result shows.

Of course it doesn't matter that the example you give has entries that are single-character strings. The same thing would result if, assuming no values had been assigned to a, b, c, or d, you evaluated instead Complement[{a, a, a, b, c}, {c, d}] to obtain result {a, b}.

If you really want to preserve the multiplicity of entries in the first argument, you may do so like this:

      DeleteCases[{a, a, a, b, c}, Alternatives[c, d]]
(* {a, a, a, b} *)
POSTED BY: Murray Eisenberg

Hi Jeff,

Complement works on sets. I learned long ago that a set is an assembly of well defined and well distinguished objects, so each object appears only once in a set.

Accordingly { a, a, a,..... } in this sense is not a valid set. But besides this, neither a nor b are contained in { c, d }.

Try

Complement[{a[1], a[2], a[3], b, c}, {c, t}]

If you really want to have your three a's, which destroys the nature of your result as a set and turns it to a list (or vector) , try

Complement[{a[1], a[2], a[3], b, c}, {c, t}] /. a[_] -> a
POSTED BY: Hans Dolhaine

But it is deleting elements. Here is the actual code and result:

Complement[{"a","a","a","b","c"},{"c","d"}] {a,b}

Jeff

POSTED BY: Jeffrey Lapides

The documentation for Complement seems perfectly clear (and consonant with the implementation): it says the result give the elements in the first argument that are not in the second (or additional) arguments. It does not say that it deletes elements from the first argument!

POSTED BY: Murray Eisenberg
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract