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.