Sets

SETS

What Is Set?

Set, is a basic concept of mathematics. The concept of a set is inseparable from a concept of an element. Sets have (or contain) elements, elements belong to sets. Roughly speaking, the terms set, collection, conglameration, class,assembly, group, pile, heap and such might have been interchangeable, except that some of them have acquired special meanings in mathematics.

The fact that element a belongs to set A is expressed as a ∈ A. If all elements of set A also belong to set B then A is called a subset of B: A ⊂ B. Every set is a subset of itself: A ⊂ A. As such, it is called an improper subset of itself. If it is important to distinguish between proper and improper subsets then in addition to B ⊂ A we sometimes use B ⊆ A. If the latter is used then B ⊂ A implies B ≠ A.

Algebraically, A ⊆ B is equivalent to either A = A∩B or B = A∪B.

The empty set - Ø - that has no elements is a subset of every set. This is because x ∈ Ø is false for any x and, therefore, the implication x ∈ Ø ⇒ x ∈ A is true for any set A.

There are various operations that defined over sets: intersection A∩B, union A∪B, symmetric difference A^B. It is common to restrict consideration only to the subsets of a particular "large" set, say X, in which case we also introduce a unary operation c - passing to a complement:

x ∈ Ac iff, x ∈ X and x ∉ A.

Complements satisfy de Morgan's Laws:

(A∩B)c = Ac∪Bc and (A∪B)c = Ac∩Bc.

Sets may be finite or infinite.

The set of all subsets of set A is denoted by 2A. This is because the number of the subsets of a finite set A with nelements is exactly 2n.

Addition of Sets

Sometimes in order to add one has to take the difference.Yes, that's true provided the difference is symmetric.

Several operations are customarily defined for general sets - union, intersection, difference:

1. Union: x∈A∪B iff either x∈A or x∈B
2. Intersection: x∈A∩B iff x∈A and x∈B
3. Difference: x∈A-B iff x∈A and x∉B

Adding elements of one set to another, only the union is intuitively suitable to be considered as the set addition. The empty set Ø plays the role of zero. Indeed, for every set A, A∪Ø = Ø∪A = A. The union is clearly associative. However, it's impossible to find a set (-A) such that A∪(-A) = Ø if A itself is not empty. This is because the union of two sets is a superset of each operand.

There is one additional set operation that is worth paying attention to:

4. Symmetric Difference: x∈A^B iff either x∈A or x∈B but x∉A∩B

There are several ways to define this operation:

1. A^B = (A∪B) - (A∩B)
2. A^B = (A - B)∪(B - A)

The latter is obviously suggestive of the name's origin. A nice feature of this operation is that, for any set A, A^A = Øso that in an algraic sense A = -A, and if symmetric difference satisfies the rest of the conditions, it may be legitimately called a "set addition". Clearly A^Ø = Ø^A = A. Also, the operation is commutative by definition. It's a good exercise to check that it's also associative.

Symmetric difference is reminiscent of the XOR operation defined for Boolean Algebras. So that the latter may be considered as addition defined for Boolean Algebras.