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
(Prove by showing LHS Í RHS)
x Î A
Þ(Use logic and set theory to prove)
x Î B
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.