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.




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,


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.