"A set is a collection of distinct objects". ( Wikipedia ) So is

{"John", "Mary", "Bob", "Alice" }

a set? Yes, would be the obvious answer but what if we are looking at people of a certain sex? Then

{"John"->M, "Mary"->F, "Bob"->M, "Alice"->F }

would imply that it is a collection and not a set. If we would be looking at strings of a certain length then

{"John"->4, "Mary"->4, "Bob"->3, "Alice"->5 }

would not be a set either. My point being that the following definition of a set would seem clearer.

"A set S is a tuple {C,~} where C is a collection of distinct objects and ~ is an equivalence relation on the objects of C ( by which the distinctiveness of the elements is determined ).

Considering that this is how Sets are implemented in some ( if not most ) programming languages, i.e. Java ( equals() ), Mathematica ( 'test' in functions like DeleteDuplicates ) I would expect to find definitions of Set in the literature with an explicit equivalence relation. I found none. Is this because such a definition would be wrong or in conflict with something?

Does the word 'distinct' in the definition of Set implies an equivalence relation between the objects of the collection? If so, then why isn't it made explicit?

  • $\begingroup$ The idea is that a collection is not a "list"; in the list : $\{ John, Mary, Bob, John \ldots \}$ the two occurrences of "$John$" are different, while in the set $\{ John, Mary, Bob, \ldots \}$ every objects "counts" only once. $\endgroup$ – Mauro ALLEGRANZA May 26 '16 at 9:12
  • $\begingroup$ No, the "distinct" refers explicitly to equality (which is usually given as a primitive notion). $\endgroup$ – Tobias Kildetoft May 26 '16 at 9:12

The word "distinct" here refers merely to the fact that there is no sense in which one element can be in the set "more than one time". (It doesn't express this idea very well in my opinion, but it is nevertheless what it is meant to express). A more precise -- but possibly less intuitive -- attempt at a definition would be

A set is something that everything either is or isn't an element of.

This is intended to capture the idea that fundamentally the only thing we can do with a set is to take something else and ask "is this an element of the set?", to which we will get a "yes" or "no" answer.

In particular we can't get the answer, "yes, and it's even an element twice".

We can't ask either, "between these two things that we know are elements, which of them comes first in the set?" Of course, if we want to, we can imagine an ordering of the element, but that ordering is something external to the set itself.


"A set S is a tuple {C,~} where C is a collection of distinct objects and ~ is an equivalence relation on the objects of C ( by which the distinctiveness of the elements is determined ).

Actually, a set is a tuple {C, ~} in the sense you described, where "~" is the equality. So, "distinct objects" means the objects are not equal.

Note that the equality is an equivalence relation.


{"John", "Mary", "Bob", "Alice" } is a set of four distinct strings.

{M, F, M, F} is a collection of genders, but not a set because the first object equals the third object and the second object equals the the fourth object. {M, F} is a set of two distinct elements, i.e. M and F.

{4, 4, 3, 5} is a collection of numbers, not a set because the first object equals the second object. {4, 3, 5} is a set of distinct elements.

Mathematically speaking, {"John"->M, "Mary"->F, "Bob"->M, "Alice"->F } is a mapping (function) from the set {"John", "Mary", "Bob", "Alice" } to the set {M, F}. It maps "John" to M, "Mary" to F, "Bob" to M and "Alice" to F.

{"John"->4, "Mary"->4, "Bob"->3, "Alice"->5 } is also a mapping from {"John", "Mary", "Bob", "Alice" } to {4, 3, 5}.

  • $\begingroup$ You might want to add that any binary relation that is reflexive, trasitive and symmetric is an equivalence relation, so the word "distinct" only implies inequality, but no inequivalence. $\endgroup$ – iBug Aug 30 '18 at 11:00

If you consider a tuple and a equivalence relation, well, then you ought to define them first: a tuple is a collection (?) of objects (?) and an equivalence relation is a subset (?) of the product (?) of the tuple with itself satisfying some axioms...

What you're quoting is an intuitive definition of "set", to grasp the idea that an element that belongs to a set cannot be considered more than once: whenever it seems that elements are equal, they can actually be distinguished in some other way. So you can identify John and Mary by the number of letters in their name, but they'll still be two different persons!


A set is defined as a distinct collection of objects. The relation between an object and a set has only two cases, belongs or does not belong. Any additional relation is outside a set's scope, such as "How many times does this object appear?".

All elements in a set are distinct, that's correct and it implies that "every two elements in a set are not equal". Equality and equivalence, however, are two slightly concepts. The definition of equivalence depends on the definition of an equivalence relationship, which is kinda "arbitrary", compared to the definition of equality. Any binary relationship $R$ that is reflexive, symmetric and transitive is considered "an equivalence relation", so there may be more than one definition of equivalence, depending on the relationship $R$.

So the question boils down to the difference between "equality" and "equivalence", which is answered above.

For programmatical implementations, one may define custom "equality operators" such that two objects can be considered "equal" in alternative ways. This does not contradict with "equivalence", because when you use a custom equality operator, you're treating the objects as the same one even when they're partially different. The different part, as a consequence, cannot be relied on if you use a custom equality with collections like Sets.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.