Chapter5 SET THEORY

5.1 Basic Definitions of Set Theory

The axiom of extension says that a set is completely determined by its elements; the order in which the elements are listed is irrevlevant, as is the fact that some elments may be listed more than once.

The def of set:

{a, b, c}  {a, b}

A = {x in S| p(x)}

Subsets

Proper Subset（真子集）

Venne Diagram to presents the relationship between sets

Set Equality

Operations on Sets

A certain situation all sets being considered might be sets of real numbers. In such a situation, the set of real numbers would be called a universal set (全集)or auniverse of discourse for the discussion.

The Empty Set

Partitions of Sets

Mutually disjoint（互不相交）

Power Sets （幂集）

Cartesian Products（笛卡尔乘积）

An Algorithm to Check Whether One Set Is a Subset of Another(Optional)

5.2 Properties of Sets

This section we discuss the basic set properties using element arguments.

Element argument  : it shows that one set to be a subset of another one by demonstrating that every element in the one set is also an element in  the other.

Set Identities

Proving Set Identities

The illustrated of the structured proof method.

The types of reasoning used above to derive the proof of the distributive law are called forward chaining and backward chaining. (In the study of artifical intelligence)

To proof the De Morgan's Law for Sets

Use the procedural versions of the definitions of complement, union, and intersection, and at  crucial points you use De Morgan's Laws of logic.

The Empty Set

A Proof for a Conditional Statement

5.3 Disproofs, Aglebraic Proofs, and Boolean Algebras

Disproving an Alleged Set Property

Recall that to show a universal statement is false ,it suffices to find one counter example.

Counter Example:

Let A = {1, 2} B = {1, 3} C = {1}

A - C = {2}    A - B = {2}   B - C = {3}

(A - B) V ( B - C ) = {2, 3}

Let x = 3.  X is in (A - B) V ( B - C ) = {2, 3}

but x is not in A - C = {2}

Problem-Solving Strategy

How to determine whether a given universal statement about sets is true or false?

the optimistic(乐观主义) and pessimistic（悲观主义）

The optimistic approach, plunge in and start trying to prove the statement, ask your self, "What do I need to show?" and "How do I show it?"

The pessitmistic approach, start by searching your mind for a set of conditions that must be fulfilled to construct a counterexample.

In either approach you may have clear sailing and be immediately successful or you may run into difficulty.

The trick is to be ready to switch to the other approach if the one you are trying does not look promising.

For some complicated problem, you may alternate several times between the two approaches before arriving at the correct answer.

The Number of Subsets of a set

proof by mathematical induction.

"Algebraic" Proofs of Set Identities

Boolean Algebras

Each property of about boolean algebra is a paired statements.

One can be interchanging all + and * ;and interchanging 1 and 0 to another. It is called the duality principle for a Boolean algebra.

Exercise 57. for all x, y, z in B if x + y = x + z and x.y = x.z then y = z.

y = (x + y) y  by absorption law and exercise 50.
  = (x + z) y  by  x + y = x + z
  = xy + zy    by distributive law
  = xz + yz    by xy = xz and substitution
  = z(x + y)   by distributive law
  = z(x + z)   by substitution for x + y = x + z
  = z          by absorption law

5.4 Russell's Paradox and the Halting Problem

Russell's paradox: Most sets are not elements of themselves. For instance, the set of all integers is not an integer and the set of all horses is not a horse. However, we can imagine the possibility of a set's being an element of itself. For Instance, the set of all abstract ideas might be considered an abstract idea. If we are allowed to use any description of a property as the defining property of a set, we can let S be the set of all sets that are not elements of themselves:

To avoid the Russell's paradox for the definition of the set, except for the power set whose existence is guaranteed by an axiom, whenever a set is defined using a predicate as a defining property, the stipulation must also be made that the set is a subset of a known set. This method  does not allow us to talk about "The set of all sets that are not elements of themselves." we can speak only of "The set of all sets that are subsets of some known set and that are not elements of themselves."

Considered the following definition:

The Halting problem

Is there an algorithm to check that an alternative algorithm is halts or loops forever?