Simple theorems in the algebra of sets
Encyclopedia
The simple theorems in the algebra of sets are some of the elementary properties of the algebra
of union
(infix
∪), intersection
(infix
∩), and set complement (postfix
') of sets.
These properties assume the existence of at least two sets: a given universal set
, denoted U, and the empty set
, denoted {}. The algebra of sets describes the properties of all possible subset
s of U, called the power set of U and denoted P(U). P(U) is assumed closed
under union, intersection, and set complement. The algebra of sets is an interpretation
or model
of Boolean algebra, with union, intersection, set complement, U, and {} interpreting Boolean sum
, product
, complement, 1, and 0, respectively.
The properties below are stated without proof
, but can be derived from a small number of properties taken as axiom
s. A "*" follows the algebra of sets interpretation of Huntington's (1904) classic postulate set for Boolean algebra
. These properties can be visualized with Venn diagram
s. They also follow from the fact that P(U) is a Boolean lattice. The properties followed by "L" interpret the lattice
axioms.
Elementary discrete mathematics
courses sometimes leave students with the impression that the subject matter of set theory
is no more than these properties. For more about elementary set theory, see set, set theory
, algebra of sets
, and naive set theory
. For an introduction to set theory at a higher level, see also axiomatic set theory, cardinal number
, ordinal number
, Cantor–Bernstein–Schroeder theorem
, Cantor's diagonal argument
, Cantor's first uncountability proof
, Cantor's theorem
, well-ordering theorem
, axiom of choice, and Zorn's lemma
.
The properties below include a defined binary operation, relative complement, denoted by infix "\". The "relative complement of A in B," denoted B \A, is defined as (A ∪B′)′ and as A′ ∩B.
PROPOSITION 1. For any U and any subset A of U:
PROPOSITION 2. For any sets A, B, and C:
The distributive laws:
PROPOSITION 3. Some properties of ⊆:
Algebraic structure
In abstract algebra, an algebraic structure consists of one or more sets, called underlying sets or carriers or sorts, closed under one or more operations, satisfying some axioms. Abstract algebra is primarily the study of algebraic structures and their properties...
of union
Union (set theory)
In set theory, the union of a collection of sets is the set of all distinct elements in the collection. The union of a collection of sets S_1, S_2, S_3, \dots , S_n\,\! gives a set S_1 \cup S_2 \cup S_3 \cup \dots \cup S_n.- Definition :...
(infix
Infix
An infix is an affix inserted inside a word stem . It contrasts with adfix, a rare term for an affix attached to the end of a stem, such as a prefix or suffix.-Indonesian:...
∪), intersection
Intersection (set theory)
In mathematics, the intersection of two sets A and B is the set that contains all elements of A that also belong to B , but no other elements....
(infix
Infix
An infix is an affix inserted inside a word stem . It contrasts with adfix, a rare term for an affix attached to the end of a stem, such as a prefix or suffix.-Indonesian:...
∩), and set complement (postfix
Postfix
Postfix may refer to:* Suffix * Postfix notation, a way of writing algebraic and other expressions. Also known as reverse Polish notation* Postfix , a mail transfer agent program...
') of sets.
These properties assume the existence of at least two sets: a given universal set
Universal set
In set theory, a universal set is a set which contains all objects, including itself. In set theory as usually formulated, the conception of a set of all sets leads to a paradox...
, denoted U, and the empty set
Empty set
In mathematics, and more specifically set theory, the empty set is the unique set having no elements; its size or cardinality is zero. Some axiomatic set theories assure that the empty set exists by including an axiom of empty set; in other theories, its existence can be deduced...
, denoted {}. The algebra of sets describes the properties of all possible subset
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
s of U, called the power set of U and denoted P(U). P(U) is assumed closed
Closure
Closure may refer to:* Closure used to seal a bottle, jug, jar, can, or other container** Closure , a stopper* Closure , the process by which an organization ceases operations...
under union, intersection, and set complement. The algebra of sets is an interpretation
Interpretation (logic)
An interpretation is an assignment of meaning to the symbols of a formal language. Many formal languages used in mathematics, logic, and theoretical computer science are defined in solely syntactic terms, and as such do not have any meaning until they are given some interpretation...
or model
Model theory
In mathematics, model theory is the study of mathematical structures using tools from mathematical logic....
of Boolean algebra, with union, intersection, set complement, U, and {} interpreting Boolean sum
Logical disjunction
In logic and mathematics, a two-place logical connective or, is a logical disjunction, also known as inclusive disjunction or alternation, that results in true whenever one or more of its operands are true. E.g. in this context, "A or B" is true if A is true, or if B is true, or if both A and B are...
, product
Logical conjunction
In logic and mathematics, a two-place logical operator and, also known as logical conjunction, results in true if both of its operands are true, otherwise the value of false....
, complement, 1, and 0, respectively.
The properties below are stated without proof
Mathematical proof
In mathematics, a proof is a convincing demonstration that some mathematical statement is necessarily true. Proofs are obtained from deductive reasoning, rather than from inductive or empirical arguments. That is, a proof must demonstrate that a statement is true in all cases, without a single...
, but can be derived from a small number of properties taken as axiom
Axiom
In traditional logic, an axiom or postulate is a proposition that is not proven or demonstrated but considered either to be self-evident or to define and delimit the realm of analysis. In other words, an axiom is a logical statement that is assumed to be true...
s. A "*" follows the algebra of sets interpretation of Huntington's (1904) classic postulate set for Boolean algebra
Boolean algebra
In abstract algebra, a Boolean algebra or Boolean lattice is a complemented distributive lattice. This type of algebraic structure captures essential properties of both set operations and logic operations. A Boolean algebra can be seen as a generalization of a power set algebra or a field of sets...
. These properties can be visualized with Venn diagram
Venn diagram
Venn diagrams or set diagrams are diagrams that show all possible logical relations between a finite collection of sets . Venn diagrams were conceived around 1880 by John Venn...
s. They also follow from the fact that P(U) is a Boolean lattice. The properties followed by "L" interpret the lattice
Lattice (order)
In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
axioms.
Elementary discrete mathematics
Discrete mathematics
Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have the property of varying "smoothly", the objects studied in discrete mathematics – such as integers, graphs, and statements in logic – do not...
courses sometimes leave students with the impression that the subject matter of set theory
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
is no more than these properties. For more about elementary set theory, see set, set theory
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
, algebra of sets
Algebra of sets
The algebra of sets develops and describes the basic properties and laws of sets, the set-theoretic operations of union, intersection, and complementation and the relations of set equality and set inclusion...
, and naive set theory
Naive set theory
Naive set theory is one of several theories of sets used in the discussion of the foundations of mathematics. The informal content of this naive set theory supports both the aspects of mathematical sets familiar in discrete mathematics , and the everyday usage of set theory concepts in most...
. For an introduction to set theory at a higher level, see also axiomatic set theory, cardinal number
Cardinal number
In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality of sets. The cardinality of a finite set is a natural number – the number of elements in the set. The transfinite cardinal numbers describe the sizes of infinite...
, ordinal number
Ordinal number
In set theory, an ordinal number, or just ordinal, is the order type of a well-ordered set. They are usually identified with hereditarily transitive sets. Ordinals are an extension of the natural numbers different from integers and from cardinals...
, Cantor–Bernstein–Schroeder theorem
Cantor–Bernstein–Schroeder theorem
In set theory, the Cantor–Bernstein–Schroeder theorem, named after Georg Cantor, Felix Bernstein, and Ernst Schröder, states that, if there exist injective functions and between the sets A and B, then there exists a bijective function...
, Cantor's diagonal argument
Cantor's diagonal argument
Cantor's diagonal argument, also called the diagonalisation argument, the diagonal slash argument or the diagonal method, was published in 1891 by Georg Cantor as a mathematical proof that there are infinite sets which cannot be put into one-to-one correspondence with the infinite set of natural...
, Cantor's first uncountability proof
Cantor's first uncountability proof
Georg Cantor's first uncountability proof demonstrates that the set of all real numbers is uncountable. This proof differs from the more familiar proof that uses his diagonal argument...
, Cantor's theorem
Cantor's theorem
In elementary set theory, Cantor's theorem states that, for any set A, the set of all subsets of A has a strictly greater cardinality than A itself...
, well-ordering theorem
Well-ordering theorem
In mathematics, the well-ordering theorem states that every set can be well-ordered. A set X is well-ordered by a strict total order if every non-empty subset of X has a least element under the ordering. This is also known as Zermelo's theorem and is equivalent to the Axiom of Choice...
, axiom of choice, and Zorn's lemma
Zorn's lemma
Zorn's lemma, also known as the Kuratowski–Zorn lemma, is a proposition of set theory that states:Suppose a partially ordered set P has the property that every chain has an upper bound in P...
.
The properties below include a defined binary operation, relative complement, denoted by infix "\". The "relative complement of A in B," denoted B \A, is defined as (A ∪B′)′ and as A′ ∩B.
PROPOSITION 1. For any U and any subset A of U:
- {}′ = U;
- U′ = {};
- A \ {} = A;
- {} \ A = {};
- A ∩ {} = {};
- A ∪ {} = A; *
- A ∩ U = A; *
- A ∪ U = U;
- A′ ∪ A = U; *
- A′ ∩ A = {}; *
- A \ A = {};
- U \ A = A′;
- A \ U = {};
- A′′ = A;
- A ∩ A = A;
- A ∪ A = A.
PROPOSITION 2. For any sets A, B, and C:
- A ∩ B = B ∩ A; * L
- A ∪ B = B ∪ A; * L
- A ∪ (A ∩ B) = A; L
- A ∩ (A ∪ B) = A; L
- (A ∪ B) \ A = B \ A;
- A ∩ B = {} if and only ifIf and only ifIn logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
B \ A = B; - (A′ ∪ B)′ ∪ (A′ ∪ B′)′ = A;
- (A ∩ B) ∩ C = A ∩ (B ∩ C); L
- (A ∪ B) ∪ C = A ∪ (B ∪ C); L
- C \ (A ∩ B) = (C \ A) ∪ (C \ B);
- C \ (A ∪ B) = (C \ A) ∩ (C \ B);
- C \ (B \ A) = (C \ B) ∪(C ∩ A);
- (B \ A) ∩ C = (B ∩ C) \ A = B ∩ (C \ A);
- (B \ A) ∪ C = (B ∪ C) \ (A \ C).
The distributive laws:
- A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C); *
- A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C). *
PROPOSITION 3. Some properties of ⊆:
- A ⊆ B if and only ifIf and only ifIn logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
A ∩ B = A; - A ⊆ B if and only if A ∪ B = B;
- A ⊆ B if and only if A′ ∪ B;
- A ⊆ B if and only if B′ ⊆ A′;
- A ⊆ B if and only if A \ B = {};
- A ∩ B ⊆ A ⊆ A ∪ B.