Math Notes Set Membership

 

The standard method of proving that set A is a subset of set B is to assign a variable x as a member of set A, then prove that x is also a member of set B. Thus

 

Theorem: A B

(Prove by showing LHS RHS)

x A

(Use logic and set theory to prove)

x B

End of Proof

 

The subset proof is logical enough, but the proof of the cross-product theorem,

 

S T = T S S = T = S = T,

creates a problem. An equivalent form,

S T = T S (S T ) S = T,

suggests a proof that starts with nonempty sets S and T. The next step is to assign an element x as a member of set S, and that is the problem. In the subset example, an element x is assigne as a member of set A without requiring that set A be nonempty, but in the cross-product example, a nonempty set S is necessary for the proof. What is the distinction that makes on membership assignment require a nonempty set while the other membership assignment can be made without regard to the set properties?

 

The definition of subset is the universal quantification

 

("x|x A : x B);

 

for all elements, membership in set A implies membership in set B. Thus, the membership assignment in the subset proof assigns a quantifying variable x as a member of set A. The range of the universal quantification may be empty. The existence of elements in set A is not needed, and the membership assignment is hypothetical. That is, if an element is in set A it must be in set B.

 

The variable in the cross-product example, in contrast, requires that the set S be nonempty.

 

Most mathematics texts make a distinction between set membership to a nonempty set and set membership to prove a subset theorem, but the distinction is not always well stated, so subset proofs dont always make clear that universal quantification is a necessary part of the proof. Set theorems on this web site convert the theorem expression to a universal quantification form to make the distinction that some set memberships are abstractions as in the subset theorem, and other set memberships are real as in the cross-product theorem.

 

References:

 

Fejer, Peter and Simovici, Dan A., 1991, Mathematical Foundations of Computer Science, New York, NY: Springer-Verlag

 

Ganong, Rick 1999, Course notes and comments from M1090 and M2090 math and logic courses, http://www.math.yorku.ca/Who/Faculty/Ganong

 

Gries, David and Schneider, Fred B., 1993, A Logical Approach to Discrete Math, New York, NY: Springer-Verlag

 

Hu Sze-Tsen, 1963, Elements of Modern Algebra, San Francisco: Holden-Day, Inc.