Simple theorems in the algebra of sets

Simple theorems in the algebra of sets

Elementary discrete mathematics courses sometimes leave students under an erroneous impression that the subject matter of set theory is the algebra of union, intersection, and complementation of sets. Those topics are treated below: they would typically be classified, as verification of properties of the Boolean algebra of subsets of a given universal set.

For an account of some elementary topics in set theory, see also set, naive set theory, axiomatic set theory, Cantor–Bernstein–Schroeder theorem, Cantor's diagonal argument, Cantor's first uncountability proof, Cantor's theorem, well-ordering theorem, axiom of choice, Zorn's lemma.

We list without proof several simple properties of the operations of union, intersection, and complementation of sets. These properties can be visualized with Venn diagrams.

PROPOSITION 1: For any sets "A", "B", and "C"::*"A" ∩ "A" = "A";:*"A" ∪ "A" = "A";:*"A" "A" = {};:*"A" ∩ "B" = "B" ∩ "A";:*"A" ∪ "B" = "B" ∪ "A";:*("A" ∩ "B") ∩ "C" = "A" ∩ ("B" ∩ "C");:*("A" ∪ "B") ∪ "C" = "A" ∪ ("B" ∪ "C");:*"C" ("A" ∩ "B") = ("C" "A") ∪ ("C" "B");:*"C" ("A" ∪ "B") = ("C" "A") ∩ ("C" "B");:*"C" ("B" "A") = ("A" ∩ "C") ∪ ("C" "B");:*("B" "A") ∩ "C" = ("B" ∩ "C") "A" = "B" ∩ ("C" "A");:*("B" "A") ∪ "C" = ("B" ∪ "C") ("A" "C");:*"A" ⊆ "B" if and only if "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" = "B";:*"A" ∩ "B" ⊆ "A" ⊆ "A "∪ "B";:*"A" ∩ {} = {};:*"A" ∪ {} = "A";:*{} "A" = {};:*"A" {} = "A".

PROPOSITION 2: For any universe U and subsets "A", "B", and "C" of U::*"A"′′ = "A";:*"B" "A" = "A"' ∩ "B";:*("B" "A")' = "A" ∪ "B"';:*"A" ⊆ "B" if and only if "B ⊆ "A;:*"A" ∩ U = "A";:*"A" ∪ U = U;:*U "A" = "A"′;:*"A" U = {}.

PROPOSITION 3: (distributive laws): For any sets "A", "B", and "C":::(a) "A" ∩ ("B" ∪ "C") = ("A" ∩ "B") ∪ ("A" ∩ "C");::(b) "A" ∪ ("B" ∩ "C") = ("A" ∪ "B") ∩ ("A" ∪ "C").

The above propositions show that the power set "P"(U) is a Boolean lattice.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • algebra — /al jeuh breuh/, n. 1. the branch of mathematics that deals with general statements of relations, utilizing letters and other symbols to represent specific sets of numbers, values, vectors, etc., in the description of such relations. 2. any of… …   Universalium

  • Algebra — This article is about the branch of mathematics. For other uses, see Algebra (disambiguation). Algebra is the branch of mathematics concerning the study of the rules of operations and relations, and the constructions and concepts arising from… …   Wikipedia

  • Boolean algebra — This article discusses the subject referred to as Boolean algebra. For the mathematical objects, see Boolean algebra (structure). Boolean algebra, as developed in 1854 by George Boole in his book An Investigation of the Laws of Thought,[1] is a… …   Wikipedia

  • Outline of logic — The following outline is provided as an overview of and topical guide to logic: Logic – formal science of using reason, considered a branch of both philosophy and mathematics. Logic investigates and classifies the structure of statements and… …   Wikipedia

  • Outline of discrete mathematics — The following outline is presented as an overview of and topical guide to discrete mathematics: Discrete mathematics – study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have… …   Wikipedia

  • Logic and the philosophy of mathematics in the nineteenth century — John Stillwell INTRODUCTION In its history of over two thousand years, mathematics has seldom been disturbed by philosophical disputes. Ever since Plato, who is said to have put the slogan ‘Let no one who is not a geometer enter here’ over the… …   History of philosophy

  • Boolean algebra (introduction) — Boolean algebra, developed in 1854 by George Boole in his book An Investigation of the Laws of Thought , is a variant of ordinary algebra as taught in high school. Boolean algebra differs from ordinary algebra in three ways: in the values that… …   Wikipedia

  • List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

  • List of mathematical logic topics — Clicking on related changes shows a list of most recent edits of articles to which this page links. This page links to itself in order that recent changes to this page will also be included in related changes. This is a list of mathematical logic …   Wikipedia

  • Universal algebra — (sometimes called general algebra) is the field of mathematics that studies algebraic structures themselves, not examples ( models ) of algebraic structures.For instance, rather than take particular groups as the object of study, in universal… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”