# Set Theory

Set theory is a branch of mathematical logic that studies sets, which informally are collections of objects

## Basic Operations

### Subset

A set is a subset of another set if all its elements are also member of the other set: .

A proper, or strict subset adds the additional requirement that the sets may not be equal: .

### Intersection

An intersection represents the elements that are members of both sets: .

• and are disjoint if

### Union

A union represents the elements that are members of at least one of the sets: .

### Difference

A difference represents the elements that are members of one set, but not of the other: .

### Symmetric Difference

A symmetric difference represents the elements that are member of any of the sets, but not of both: .

### Cardinality

The number of elements in the set is expressed as . For example, . There also exists the alternate notation .

### Complement

Given a set , the complement of is the set of all elements of not in . This is expressed as . Basically, if , . Also note that . As an example, if and , then .

## Empty Set

• No element is member of the empty set:
• The empty set is a subset of every set:
• Any universal quantification over the empty set is true: given proposition , is true

## Power Set

A power set is the set of all possible subsets of a set. Its defined like this: . Also denoted as . Note that the empty set is a member of all power sets: . Thus, the power set of the empty set is the set of the empty set: .

If a set has elements, then has elements.

### Properties

• The power set operation is distributive over but not over . but

### Finite Power Set

A set containing all the finite subsets of a set is denoted as . If is a finite set, then .

## Multi Set

The multi-set (or bag) is the generalization of the concept of a set, where multiple ocurrences of an element are permitted. For example, and (notice the square brackets) are equal sets, but are considered different multi-sets.

The multiplicity of an element is the number of times an element occurs in a multi-set. In the case of , has a multiplicity of 2, while has a multiplicity of 1.

The multi-set cardinality consists of the number of elements in the multi-set, including duplicate ocurrences.

Notice that a set is considered a multi-set, and for any non-empty set there are infinite multi-sets with different number of ocurrences for each of its elements.

A multi-set can be defined as a relation that maps the elements in the bag to positive integers denoting multiplicity.

For example, a multi-set of elements , , and , where multiplicity is 3, 1, and 2, respectively, can be denoted as . Elements that are not in the multi-set are left out, rather than mapped to a multiplicity of zero.

## Augmented Set

Given set , the augment set of is , which is the union of the given set and the undefined element: .

## Set Families

Set families are sets of other sets. They may be indexed, such that , where each is a set.

### Operations

• The expression represents the intersection of all the sets in the family :

It can be defined as follows: . Note that this operation is undefined if .

• The expression represents the union of all the sets in the family :

It can be defined as follows: .

### Properties

• Pairwise disjoint: A set family is pairwise disjoint if all its elements are disjoint:

### Partitions

is a partition of if:

• is pairwise disjoint

## Uniqueness Operator

This operation allows us to refer to a single unique element of a set that matches the given constraints. Notice that the result is undefined if the given constraints don’t result in one and only one element.

Given a finite set of different natural numbers , we can obtain the largest one as: . Similarly, given the set , there is only one element that wrote The Lord of the Rings. Such element is: .

We might also add a term part to map the resulting element. For example: .

## Comprehensions

A set comprehension is a handy mathematical notation to build sets based on arbitrarily complex expressions. The general form is , which defines the set of all elements of where holds.

We can add a term part to map the elements in the set. For example, given returns the address of person , is the set of addresses of all the male people.

If a set comprehension has no term part, like , then the type the elements in the result depends on the comprehension’s characteristic tuple. In this case, the set comprehension begins with , so the characteristic tuple is , which is of type .

Notice that the variables used in the characteristic tuple depend on the variables used inside the scope of the comprehension. If we have , then the characteristic tuple would be the pair .

## Binary Relations

Sets of tuples where the elements in the tuple have a logical relationship. Tuples may be expressed as , or as , known as maplet notation. Given , we say and are the source and target sets of . If and are of the same type, then the relation is homogeneous; if they are different, the relation is heterogeneous.

The powerset of a binary relation can be expressed with a double-headed arrow: .

### Cartesian Product

This operation can create binary relations from two sets consisting of all the possible tuple combinations: .

The cartesian product is distributive over and : and .

Also note the following equations with regards to and : and .

With regards to the empty set, a cartesian product of the empty set and any set is equal to the empty set: .

### Lifted Form

Given a relation , the lifted form of is denoted . This is simply the original relation plus the association of the undefined element with all the elements of the augmented target.

### Operations

Given , a relation from to :

• Domain: The domain represents the set of all the elements from the left side of the ordered pairs:

• Range: The range represents the set of all the elements from the right side of the ordered pairs:

• Inverse: The relation with the ordered pairs reversed: . This may also be expressed as

• Composition: Represents the combination of two relations where a certain elements from the ordered pairs are included in both relations. Given and , . Basically,

Note the following equation about inversing a composition: .

If a certain binary relation is homogeneous, then represents the result of composing with itself number of times. For example, .

## Homogeneous (Binary) Relations

A binary relation over and where is called an homogenous relation, or an endorelation over .

The identity binary relation on is denoted as .

### Properties

Homogenous relations may have one or more of the following properties:

• Reflexive: is reflexive on if . Or in terms of the identity relation:

• Irreflexive: is irreflexive on if

• Symmetric: is symmetric on if . Or in terms of inverses, if

• Antisymmetric: is antisymmetric on if

• Asymmetric: is asymmetric on if

Note that if is asymmetric, then its also antisymmetric.

• Transitive: is transitive on if . Or in terms of composition, if

### Equivalence Relations

Equivalence relations are binary relations that are also reflexive, symmetric, and transitive. They can be used to partition a set into equivalence classes. In this context, an ordered pair means that the pair of elements should be considered “equivalent.”

Consider . This equivalence relation tells us that , , , and . Therefore we have the following equivalence classes:

• , given that only is equivalent to
• , given that is equivalent to and to itself
• , given that is equivalent to and to itself

Given , we can obtain the equivalent class of as .

Notice an element is always in the set of its equivalent classes, since an element is always equal to itself: .

The set of all equivalence classes of all the elements of is called module ”, denoted . The resulting set family is always a partition of .

### Restrictions

A binary relation can be restricted on the domain, or on the range.

A restriction on the domain means that we only consider pairs where the left-side element is a member of a certain set. Given and , the domain restriction of by equals . This can be noted as .

Similarly, a restriction on the range means that we only consider pairs where the right-side element is a member of a certain set. Given and , the range restriction of by equals . This can be noted as .

We can use restrictions to exclude a list of pairs from a binary relation, which is called domain or range substraction (or anti-restriction). Following the above examples, we can exclude all pairs whose left-side element is in by doing , or we can exclude all pairs whose right-side element is in by doing . These restrictions can also be expressed as and , respectively.

### Relational Image

The relation image of a binary relation by a set is the range of the domain restriction of by : . In other words, the relation image would be the set of all the results of function where the argument is a subset of .

### Closures

The closure of a relation is the smallest relation containing that satisfies a certain propery. For example, if is an homogeneous relation, then represents the reflexive closure of . If , then we say is its own reflexive closure. Similarly, we can represent the symmetric closure of as

The transitive closure of an homogeneous relation is determined by composing the relation with itself enough times until the final relation stops growing. The union of all finite iterations of is formally defined as , which is the transitive closure of , the smallest transitive relation containing .

For example, consider . , , and . But at this point, , , and so on. Therefore, , which is the transitive closure of .

Finally, the reflexive transitive closure of an homogeneous relation is defined as .

Given a set, such as , and an operation, such as multiplication, we say that a set is closed under an operation if for all elements and from the set, the result of the operation (such as ), is already a member of the set.