Algebra of sets

Template:Short description Template:About In mathematics, particularly in the study of set theory, the algebra of setsTemplate:Efn defines the properties and laws of sets, the set-theoretic operations of union, intersection, and complementation and the relations of set equality and set inclusion. It also provides systematic procedures for evaluating expressions and performing calculations involving these operations and relations.

Any set of sets closed under the set-theoretic operations forms a Boolean algebra with the join operator being union, the meet operator being intersection, the complement operator being set complement,Template:Sfnp the bottom being Template:Tmath and the top being the universe set under consideration.

Fundamentals

A set is a collection of many mathematical objects. Examples of such objects are numbers, symbols, points in space, lines, other geometric shapes, variables, functions, or even other sets.Template:Sfnp A set is usually denote a upper-case letter and curly braces, as in $A=\{1,2,3,4\}$ and $B=\{a,b,c,x,y,z\}$.

Union and intersection

Template:Main The algebra of sets studies the properties and laws of sets algebraically. Foundationally, there are two set-theoretic operations: union (Template:Tmath) and intersection (Template:Tmath). A union is a set-theoretic operation that collects all members of two or more sets into a single set. An intersection collects the common elements of two or more sets. For instance, let $A=\{1,2,3,5\}$ and $B=\{2,4,6\}$. Then $A\cup B=\{1,2,3,4,5,6\}$, $A\cap B=\{2\}$. Analogically, the algebra of sets can be interpreted as the algebra of numbers. Just as arithmetic addition and multiplication are associative and commutative, so are set union and intersection.Template:SfnpTemplate:Efn Similarly for the arithmetic relation "less than or equal" is reflexive, antisymmetric and transitive, so is the set relation of "subset".Template:Sfnp Several of these identities or "laws" are the following.Template:Sfnp

Commutative property

• Template:Tmath
• Template:Tmath

Associative property

• Template:Tmath
• Template:Tmath

Distributive property

• Template:Tmath
• Template:Tmath

The union and intersection of sets may be seen as analogous to the addition and multiplication of numbers. Like addition and multiplication, the operations of union and intersection are commutative and associative, and intersection distributes over union.Template:Sfnp However, unlike addition and multiplication, union also distributes over intersection.

Empty set, universe set, and the complement of a set

Template:Main article Two additional pairs of properties involve the special sets called the empty set Template:Tmath and the universe set Template:Tmath. These sets have no members, and the universe set has all possible members (in a particular context), respectively. A set where the members are not in a set $A$ is the complement; the operator denotes Template:Tmath or Template:Tmath (read as "A prime"). Equivalently, the complement of a set $A^{\complement }$ is a set that is included in a universe set Template:Tmath and not in $A$; i.e., Template:Tmath.Template:Sfnp

Identity

• Template:Tmath
• Template:Tmath

Complement

• Template:Tmath
• Template:Tmath

The identity expressions (together with the commutative expressions) say that, just like 0 and 1 for addition and multiplication,Template:Sfnp Template:Tmath and Template:Tmath are the identity elements for union and intersection, respectively.

Unlike addition and multiplication, union and intersection do not have inverse elements. However, the complement laws give the fundamental properties of the somewhat inverse-like unary operation of set complementation.

The preceding five pairs of formulae—the commutative, associative, distributive, identity, and complement formulae—encompass all of set algebra, in the sense that every valid proposition in the algebra of sets can be derived from them.

If the complement formulae are weakened to the rule Template:Tmath, then this is exactly the algebra of propositional linear logicTemplate:Clarify.

Principle of duality

Each of the identities stated above is one of a pair of identities such that each can be transformed into the other by interchanging Template:Tmath and Template:Tmath, while also interchanging Template:Tmath and Template:Tmath.

These are examples of an extremely important and powerful property of set algebra, namely, the principle of duality for sets, which asserts that for any true statement about sets, the dual statement obtained by interchanging unions and intersections, interchanging Template:Tmath and Template:Tmath and reversing inclusions is also true. A statement is said to be self-dual if it is equal to its own dual.

Some additional laws for unions and intersections

For any subsets Template:Tmath and Template:Tmath of a universe set Template:Tmath, the following identities hold:

idempotent laws

• Template:TmathTemplate:R
• Template:TmathTemplate:R

domination laws

• Template:Tmath
• Template:Tmath

absorption laws

• Template:TmathTemplate:R
• Template:TmathTemplate:R

Intersection can be expressed in terms of set difference:

Template:Tmath

Some additional laws for complements

Let Template:Tmath and Template:Tmath be subsets of a universe Template:Tmath, then:

de Morgan's laws

• Template:Tmath
• Template:Tmath

double complement or involution law

• Template:Tmath

complement laws for the universe set and the empty set

• Template:Tmath
• Template:Tmath

Notice that the double complement law is self-dual. The following is also self-dual, saying that the complement of a set is the only set that satisfies the complement laws. In other words, complementation is characterized by the complement laws: Let Template:Tmath and Template:Tmath be subsets of a universe Template:Tmath,

uniqueness of complements

• If Template:Tmath, and Template:Tmath, then Template:Tmath

Algebra of inclusion

The algebra of sets include the inclusion of sets. That is, the binary relation of one set being a subset of another, which is a partial order. If Template:Tmath, Template:Tmath and Template:Tmath are sets then the following hold:

reflexivity

• Template:Tmath

antisymmetry

• Template:Tmath and Template:Tmath if and only if Template:Tmath

transitivity

• If Template:Tmath and Template:Tmath, then Template:Tmath

For any set Template:Tmath, the power set of Template:Tmath, ordered by inclusion, is a bounded lattice, and hence together with the distributive and complement laws above, shows that it is a Boolean algebra. That is, if Template:Tmath, Template:Tmath and Template:Tmath are subsets of a set Template:Tmath then the following hold:

existence of a least element and a greatest element

• Template:Tmath

existence of joins

• Template:Tmath

• If Template:Tmath and Template:Tmath, then Template:Tmath

existence of meets

• Template:Tmath
• If Template:Tmath and Template:Tmath, then Template:Tmath

The inclusion set Template:Tmath is equivalent to various other statements involving unions, intersections, and complements. That is, for any two sets Template:Tmath and Template:Tmath, the following are equivalent:

• Template:Tmath
• Template:Tmath
• Template:Tmath
• Template:Tmath
• Template:Tmath

This shows that the relation of set inclusion can be characterized by either of the operations of set union or set intersection, meaning that the notion of set inclusion is axiomatically superfluous.

Algebra of relative complements

The following proposition lists several identities concerning relative complements and set-theoretic differences.

PROPOSITION 9: For any universe Template:Tmath and subsets Template:Tmath, Template:Tmath and Template:Tmath of Template:Tmath, the following identities hold:

• Template:Tmath
• Template:Tmath
• Template:Tmath
• Template:Tmath
• Template:Tmath
• Template:Tmath
• Template:Tmath
• Template:Tmath
• Template:Tmath
• Template:Tmath
• Template:Tmath
• Template:Tmath
• Template:Tmath

See also

• σ-algebra is an algebra of sets, completed to include countably infinite operations.
• Axiomatic set theory
• Template:Slink
• Field of sets
• List of set identities and relations
• Naive set theory
• Set (mathematics)
• Topological space — a subset of Template:Tmath, the power set of Template:Tmath, closed with respect to arbitrary union, finite intersection, and containing Template:Tmath and Template:Tmath.

Notes

Works cited

• Template:Cite book
• Template:Cite book
• Stoll, Robert R.; Set Theory and Logic, Mineola, N.Y.: Dover Publications (1979) Template:ISBN. "The Algebra of Sets", pp 16—23.
• Template:Cite book

External links

• Operations on Sets at ProvenMath