Loading [MathJax]/jax/output/HTML-CSS/jax.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

1.1: Sets and Operations on Sets. Quantifiers

( \newcommand{\kernel}{\mathrm{null}\,}\)

Sets and Operations on Sets

A set is a collection of objects of any specified kind. Sets are usually denoted by capitals. The objects belonging to a set are called its elements or members. We write xA if x is a member of A, and xA if it is not.

A={a,b,c,...} means that A consists of the elements a,b,c,.... In particular, A={a,b} consists of a and b; A={p} consists of p alone. The empty or void set, , has no elements. Equality (=) means logical identity.

If all members of A are also in B, we call A a subset of B (and B is a superset of A), and write AB or BA. It is an axiom that the sets A and B are equal (A=B) if they have the same members, i.e.,

ABandBA.

If, however, AB but BA (i.e., B has some elements not in A), we call A a proper subset of B and write AB or BA. “” is called the inclusion relation.

Set equality is not affected by the order in which elements appear. Thus a,b=b,a. Not so for ordered pairs (a,b). For such pairs,

(a,b)=(x,y)iffa=xandb=y,

but not if a=y and b=x. Similarly, for ordered n-tuples,

(a1,a2,...,an)=(x1,x2,...,xn)iffak=xk,k=1,2,...,n.

We write x|P(x) for "the set of all x satisfying the condition P(x)." Similarly, (x,y)|P(x,y) is the set of all ordered pairs for which P(x,y) holds; xA|P(x) is the set of those x in A for which P(x) is true.

For any sets A and B, we define their union AB, intersection AB, difference A=B, and Cartesian product (or cross product) A×B, as follows:

AB is the set of all members of A and B taken together:

{x|xAorxB}.

AB is the set of all common elements of A and B:

{xA|xB}.

AB consists of those xA that are not in B:

{xA|xB}.

A×B is the set of all ordered pairs (x,y), with xA and yB:

{(x,y) xA,yB}.

Similarly, A1×A2×...×An is the set of all ordered n-tuples (x1,...,xn) such that xkAk,k=1,2,...,n. We write An for A×A×...×A (n factors).

A and B are said to be disjoint iff AB = (no common elements). Otherwise, we say that A meets B (AB). Usually all sets involved are subsets of a "master set" S, called the space. Then we write X for SX, and call X the complement of X ( in S). Various other notations are likewise in use.

Example 1.1.1

Let A={1,2,3},B={2,4}. Then

AB={1,2,3,4},AB{2},AB={1,3},

A×B={(1,2),(1,4),(2,2),(2,4),(3,2),(3,4)}.

If N is the set of all naturals (positive integers), we could also write

A={xN|x<4}.

Theorem 1.1.1
  1. AA=A;AA=A;
  2. AB=BA,AB=BA;
  3. (AB)C=A(BC);(AB)C=A(BC);
  4. (AB)C=(AC)(BC);
  5. (AB)C=(AC)(BC).
Proof

The proof of (d) is sketched out in Problem 1. The rest is left to the reader.

Because of (c), we may omit brackets in ABC and ABC; similarly for four or more sets. More generally, we may consider whole families of sets, i.e., collections of many (possibly infinitely many) sets. If M is such a family, we define its union, M, to be the set of all elements x, each belonging to at least one set of the family. The intersection of M, denoted M, consists of those x that belong to all sets of the family simultaneously. Instead, we also write

{X|XM}and{X|XM},respectively.

Often we can number the sets of a given family:

A1,A2,...,An,...

More generally, we may denote all sets of a family M by some letter (say, X) with indices i attached to it (the indices may, but need not, be numbers). The family M then is denoted by {Xi} or {Xi|iI, where i is a variable index ranging over a suitable set I of indices ("index notation"). In this case, the union and intersection of M are denoted by such symbols as

{Xi|iI}=iXi=Xi=iIXi;

{Xi|iI}=iXi=Xi=iIXi;

If the indices are integers, we may write

mn=1Xn,n=1Xn,mn=kXn,etc.

Theorem 1.1.1: De Morgan's Duality Laws

For any sets S and Ai (iI), the following are true:

(i)SiAi=i(SA);(ii)SiAi=i(SAi).

(If S is the entire space, we may write Ai for SAi, Ai for SAi, etc.

Before proving these laws, we introduce some useful notation.

Logical Quantifiers

From logic we borrow the following abbreviations.

"(xA)..." means "For each member x of A, it is true that . . ."

"(xA)..." means "There is at least one x in A such that . . ."

"(!xA)..." means "There is a unique x in A such that . . ."

The symbols "(xA)" and "(xA)" are called the universal and existential quantifiers, respectively. If confusion is ruled out, we simply write "(x)," "(x)," and "(!x)" instead. For example, if we agree that m, and n denote naturals, then

"(n)(m)m>n"

means "For each natural n, there is a natural m such that m>n." We give some more examples.

Let M={Ai|iI} be an indexed set family. By definition, xAi means that x is in at least one of the sets Ai; in symbols,

(iI)xAi.

Thus we note that

xiIAiiff[(iI)xAi].

Similarly,

xiAiiff[(iI)xAi].

Also note that xAi iff x is in none of the Ai, i.e.,

(i)xAi.

Similarly, xAi iff x fails to be in some Ai. i.e.,

(i)xAi.(Why?)

We now use these remarks to prove Theorem 2(i). We have to show that SAi has the same elements as (SAi), i.e., that xSAi iff x(SAi). But, by our definitions, we have

xSAi[xS,xAi](i)[xS,xAi](i)xSAix(SAi),

as required.

One proves part (ii) of Theorem 2 quite similarly. (Exercise!)

We shall now dwell on quantifiers more closely. Sometimes a formula P(x) holds not for all xA, but only for those with an additional property Q(x).

This will be written as

(xA|Q(x))P(x),

where the vertical stroke stands for "such that." For example, if N is again the naturals, then the formula

(xN|x>3)x4

means "for each xN such that x4." In other words, for naturals, x>3x4 (the arrow stands for "implies"). Thus (1) can also be written as

(xN)x>3x4.

In mathematics, we often have to form the negation of a formula that starts with one or several quantifiers. It is noteworthy, then, that each universal quantifier is replaced by an existential one (and vice versa), followed by the negation of the subsequent part of the formula. For example, in calculus, a real number p is called the limit of a sequence x1,x2,...,xn,... iff the following is true:

For every real ϵ>0, there is a natural k (depending on ϵ) such that, for all natural n>k, we have |xnp|<ϵ|.

If we agree that lower case letters (possibly with subscripts) denote real numbers, and that n, k denote naturals (n,kN), this sentence can be written as

(ϵ>0)(k)(n>k)|xnp|<ϵ.

Here the expressions "(ϵ>0)" and "(n>k)" stand for "(ϵ|ϵ>0)" and "(n|n>k)," respectively (such self-explanatory abbreviations will also be used in other similar cases).

Now, since (2) states that "for all ϵ>0" something (i.e., the rest of (2)) is true, the negation of (2) starts with "there is an ϵ>0" (for which the rest of the formula fails). Thus we start with "(ϵ>0)," and form the negation of what follows, i.e., of

(k)(n>k)|xnp|<ϵ.

This negation, in turn, starts with "(k)," etc. Step by step, we finally arrive at

(ϵ>0)(k)(n>k)|xnp|ϵ.

Note that here the choice of n>k may depend on k. To stress it, we often write nk for n. Thus the negation of (2) finally emerges as

(ϵ>0)(k)(nk>k)|xnkp|ϵ.

The order in which the quantifiers follow each other is essential. For example, the formula

(nN)(mN)m>n

("each nN is exceeded by some mN") is true, but

(mN)(nN)m>n

is false. However, two consecutive universal quantifiers (or two consecutive existential ones) may be interchanged. We briefly write

"(x,yA)" for "(xA)(yA),"

and

"(x,yA)" for "(xA)(yA)," etc.

does not imply the existence of an x for which P(x) is true. It is only meant to imply that there is no x in A for which P(x) fails.

The latter is true even if A=; we then say that "(xA)P(x)" is vacuously true. For examplek the formula B, i.e.,

(x)xB

is always true (vacuously).


This page titled 1.1: Sets and Operations on Sets. Quantifiers is shared under a CC BY 3.0 license and was authored, remixed, and/or curated by Elias Zakon (The Trilla Group (support by Saylor Foundation)) via source content that was edited to the style and standards of the LibreTexts platform.

Support Center

How can we help?