SECTION 3.2 Set Properties and Definitions

SECTION 3.
2 Set Properties and Definitions

Set Properties
Set Definitions
Set Equality
The Empty Set
Set Partitions and Power Sets
Boolean Algebras
Set Properties
Given sets A, B, and C, and a universal set U, the following properties hold:
A B=B A Commutative property
A B=B A
A (B C) = (A B) C Associative property
A (B C) = (A B) C)
A (B C) = (A B) (A C) Distributive properties
A (B C) = (A B) (A C)
A=A =A Identity properties
U A=A U=A
A Ac = U Union and Intersection with Complement
A Ac =
A U=U Union and Intersection with U
A U= A
(Ac)c = A Double Complement Law
A A=A Idempotent Laws
A A=A
A (A B) = A Absorption properties
A (A B) = A
A-B=A Bc Alternate Set Difference Representation
A A B Inclusion in Union
B A B
A B A Inclusion in Intersection
A B B
if A B, and B C, then A C Transitive Property of Subsets
Set Definitions
Given a universal set U, let A and B be subsets of U, and x and y be elements of U. Then,
• x A B x A or x B
• x A B x A and x B
• x A-B x A and x B
• x Ac x A
• (x, y) A x B (the cross product) x A and y B
Set Equality
Given sets X and Y, the two sets are equal (X = Y) iff every element of X is in Y, and every
element of Y is in X.
Drawing from the earlier definition of subsets, set equality can be represented symbolically as
follows:
X=Y X Y and Y X.
The Empty Set
Earlier, we touched on the concept of an "empty set", a set with no elements. Just as it is
possible and even necessary to use '0' in mathematics, or to speak of 'nothing' or 'nobody' in
daily conversation, so is the concept of an empty set necessary to set theory.
The following theorem and corollary deal with properties of the empty set.
Theorem: The Empty Set is a subset of every other set.
Let A be any set, and let be the set with no elements. Then A.
Proof (by contradiction):
Suppose that there exists a set A, and a set with no elements, , and further suppose
that A. By our earlier definition of 'not a subset of ', this means there must be
an element of that is not an element of A. This is a contradiction, since has no
elements. Therefore, the theorem is true.
Corollary: There is only one empty set. (The empty set is unique.)
Proof:
Let 1 and 2 be sets with no elements. Then, by the above theorem, 1 is a subset
of 2 , and 2 is a subset of 1 . So, by the earlier definition of set equality, 1 and
2 are equal.
Set Partitions and Power Sets
Disjoint Sets
Two sets which have no elements in common are called disjoint, defined symbolically as
follows:
A and B are disjoint A B=
Mutually Disjoint Sets

Let A = {1, 2, 3, 4, 5, 6, 7, 8, 9}. Suppose that A is
divided into the following:
A1 = {1, 2, 3},
A2 = {4, 5, 6}, and
A3 = {7, 8, 9}.
The collection of these subsets, {A1, A2, A3}, is a partition of set A, and A is a union of
mutually disjoint subsets. The sets A1, A2, A3, . . ., An are said to be mutually disjoint iff, for
all i, j = 1, 2, 3, ..., n,
Ai Aj = whenever i j.
Power Sets
Let X = {a, b, c}. The power set of X, denoted P(X), is the set consisting of all subsets of X.
For this example, P(X) = { , {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}.
Power sets have the following 2 properties:
For all sets X and Y, if X Y, then P(X) P(Y).
If a set X has n elements, then P(X) has 2n elements.
Boolean Algebras
Boolean algebra is a particular algebraic method used to determine the truth or falsity of
statements. It uses 2 operators, generally denoted as + (addition) and x (multiplication), and
given a set S with elements a and b, both a + b and a x b are in S. The operations performed
by and upon statement forms, and the set theory operations performed by and
are specialized forms of Boolean algebras. The similarities can be seen in the following table.
Boolean Statement Set English
Algebra Algebra Theory Equivalent
+ "or"
x "and"
0 F "false"
1 T "true"
a' ~a ac "not a"
Likewise, similarities can be seen in the properties of statement algebra, set theory properties
and Boolean algebra. Given a set S, with elements a, b and c, the following axioms are true:
1. Commutative property: a+b=b+a
axb=bxa
2. Associative property: (a + b) + c = a + (b + c)
(a x b) x c = a x (b x c)
3. Distributive property: a + (b x c) = (a + b) x (a + c)
a x (b + c) = (a x b) + (a x c)
4. Identity properties: a+0=a
ax1=a
5. Complementation properties: a + a' = 1
a x a' = 0
Go to next section review.

Go to Class Agenda.

SECTION 3.2 Set Properties and Definitions

Uploaded by

Copyright:

Available Formats

SECTION 3.2 Set Properties and Definitions

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

SECTION 3.2 Set Properties and Definitions

Uploaded by

Copyright:

Available Formats

SECTION 3.

2 Set Properties and Definitions

The Empty Set

Set Partitions and Power Sets

A B=B A Commutative property

A A=A Idempotent Laws

if A B, and B C, then A C Transitive Property of Subsets

• (x, y) A x B (the cross product) x A and y B

The Empty Set

Theorem: The Empty Set is a subset of every other set.

Proof (by contradiction):

Set Partitions and Power Sets

A and B are disjoint A B=

Mutually Disjoint Sets

A2 = {4, 5, 6}, and

Power sets have the following 2 properties:

For all sets X and Y, if X Y, then P(X) P(Y).

If a set X has n elements, then P(X) has 2n elements.

1. Commutative property: a+b=b+a

Go to next section review.

You might also like