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 don’t 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.