We will cover just enough set theory to use later.
Cardinalities are important for probability. We don’t have time to cover
probability sufficiently well, so we will not explore the sizes of sets deeply.
This is known as naïve set theory. We do not define absolutely
everything, nor do we push set theory’s logical limits. Much.
Goals:
Impart some of the language necessary for later chapters.
Practice reasoning in a formal setting.
One key aspect is what to do in extreme cases like empty sets.
To start, we require unambiguous definitions of terms and items. When a term or
item is unambiguously defined, it is called well-defined.
set
An unordered collection of unique elements.
Curly braces: \{A,B,C\}
is a set of three elements, A,
B,
and C.
Order does not matter: \{\text{cat},\text{dog}\}
is the same set as \{\text{dog},\text{cat}\}.
Repeated elements do not matter: \{1,1,1\}
is the same set as \{1\}.
Can be implicit: \{x\kern 1.66702pt |\kern 1.66702pt x\text{ is an integer},x > 0,x < 3\}
is the same set as \{1,2\}.
Read the implicit form as “the set of elements xsuch that x
is an integer, x > 0,
and x < 3”.
Or “the set of elements xwhere \mathop{\mathop{…}}”
Other symbols that sometimes stand for “such that”: :,
∋
(reversed )
Implicit (or set-builder) form can include formula or other bits left of
the bar. \{3x\kern 1.66702pt |\kern 1.66702pt x\text{ is a positive integer}\}
is the set \{3,6,9,\mathop{\mathop{…}}\}.
element
Any item in a set, even other sets. (Also entry, member, item,
etc.)
This is not ambiguous. If something is in a set, it is an item of that
set. It doesn’t matter if the item is a number or a grape.
\{A,\{B,C\}\}
is a set of two elements, A
and \{B,C\}.
None of the following are the same: \{A,\{B,C\}\},
\{A,B,C\},
\{\{A,B\},C\}.
empty set
Or null set. Denoted by ∅
rather than \{\}.
This is a set on its own.
\{∅\}
is the set of the empty set, which is not empty.
Think of sets as bags. An empty bag still is a bag, and if a bag
contains an empty bag, the outer bag is not empty.
Implicit definitions can hide empty sets.
For example, the set \{x\kern 1.66702pt |\kern 1.66702pt x\text{ is an odd integer divisible by }2\}
is ∅.
singleton
A set with only one element.
\{1\}
and \{∅\}
both are singletons (or sometimes singleton sets).
Of course, we’re using a representation of the days and not the days
themselves. That is how we reason about things; we model them and
represent them by symbols.
The days when homework is due:
\{\text{25th of August},\text{1st of September},\mathop{\mathop{…}}\}
We could list them all.
\{
every Monday after the 18th of August 2008 until after the 1st of
December \}
Or: \{x\kern 1.66702pt |\kern 1.66702pt x
is a Monday, x
is after the 18th of August, and x
is on or before the 1st of December \}
To English:
\{2,3,4\}:
The set containing two, three, and four.
\{x\kern 1.66702pt |\kern 1.66702pt x\text{ is an integer and }x > 0\}:
The positive integers, also called the counting numbers or the natural
numbers.
Often written as {J}^{+}.
The integers often are written as J
(because the “I” form can be difficult to read), rationals as ℚ
(for quotients), the reals as .
\{2x - 1\kern 1.66702pt |\kern 1.66702pt x {J}^{+}\}
The set whose members have the form 2x - 1
where x
is a positive integer.
Cannot list all the entries; this is an infinite set.
The expression x A
states that x is
an element of A.
If x\mathrel{∉}A, then
x is not an
element of A.
4 \{2,4,6\},
and 4\mathrel{∉}\{x\kern 1.66702pt |\kern 1.66702pt x\text{ is an odd integer }\}.
There is no x
such that x ∅,
so \{x\kern 1.66702pt |\kern 1.66702pt x ∅\}
is a long way of writing ∅.
subset
If all entries of set A
also are in set B,
A is a
subset of B.
superset
The reverse of subset. If all entries of set
B also are
in set A,
then A is a
superset of B.
proper subset
If all entries of set A
also are in set B, but
some entries of B
are not in A,
then A is a proper
subset of B.
\{2,3\}
is a proper subset of \{1,2,3,4\}.
equality
Set A
equals set B
when A is a
subset of B
and B is a
subset of A.
Order does not matter. \{1,2,3\} = \{3,2,1\}.
The symbols for these relations are subject to a little disagreement.
Many basic textbooks write the subset relation as ⊆,
so A ⊆ B
when A
is a subset of B.
The same textbooks reserve ⊂
for the proper subset. Supersets are ⊃.
This keeps a superficial similarity to the numerical relations ≤
and <.
In the former the compared quantities may be equal, while in the latter
they must be different.
Most mathematicians now use ⊂
for any subset. If a property requires a “proper subset”, it often is worth
noting specifically. And the only non-“proper subset” of a set is the set
itself.
Extra relations are given for emphasis, e.g. ⊊
or ⊊
for proper subsets and ⊆
or ⊆
to emphasize the possibility of equality.
Often a proper subset is written out: A ⊂ B
and A≠B.
I’ll never remember to stick with the textbook’s notation. Myuse of \mathbf{⊂}is for subsets and not proper subsets.
If A = B, then everymember of Ais amember of B, andevery member of Bis a member of A.
This is what we expect from equality, but we did not define set equality this way.
Follow the rules:
A = B
imples A ⊂ B
and B ⊂ A.
Because A ⊂ B,
every member of A
is a member of B.
Because B ⊂ A,
every member of B
is a member of A.
The empty set ∅is a subset of all sets. Unexpected! This is a case of carrying the formal logic to its
only consistent end.
For some set A,
∅⊂ A
if every member of ∅
is in A.
But ∅
has no members.
Thus all of ∅’s
members also are in A.
This is called a vacuous truth.
The alternatives would not be consistent, but proving that requires more machinery
that we need.
Which of these apply to set operations union and intersection? (Informally. Formally
we must rely on the properties of and and or.)
If C = A ∪ B, then
C = \{x\kern 1.66702pt |\kern 1.66702pt x A\text{ or }x B\}. Reversing the sets does not
matter, so C = A ∪ B = B ∪ A. The union is
commutative. Similary, if D = A ∪ (B ∪ C),
we can write D in an
implicit form and see that D = (A ∪ B) ∪ C
to see that the union is associative.
The same arguments show that set intersection is commutative and associative.
For the distributive property, which is similar to addition and which to multiplication? A
gut feeling is that unions add, so try it.
\eqalignno{
A ∩ (B ∪ C) & = \{x\kern 1.66702pt |\kern 1.66702pt x A\text{ and }x B ∪ C\} & &
\cr
& = \{x\kern 1.66702pt |\kern 1.66702pt x A\text{ and }(x B\text{ or }x C)\} & &
\cr
& = \{x\kern 1.66702pt |\kern 1.66702pt (x A\text{ and }x B)\text{ or }(x A\text{ and }x C)\} & &
\cr
& = (A ∩ B) ∪ (A ∩ C) & &
}
But with sets, both operations distribute:
\eqalignno{
A ∪ (B ∩ C) & = \{x\kern 1.66702pt |\kern 1.66702pt x A\text{ or }x B ∩ C\} & &
\cr
& = \{x\kern 1.66702pt |\kern 1.66702pt x A\text{ or }(x B\text{ and }x C)\} & &
\cr
& = \{x\kern 1.66702pt |\kern 1.66702pt (x A\text{ or }x B)\text{ and }(x A\text{ or }x C)\} & &
\cr
& = (A ∪ B) ∩ (A ∪ C) & &
}
The rules of set theory are intimately tied to logic. Logical operations dictate
how set operations behave. We will cover the properties of logic in the next
chapter.
A set of all ordered pairs whose entries are drawn from two
sets.
A × B = \{(x,y)\kern 1.66702pt |\kern 1.66702pt x A,y B\}.
Let A = \{{a}_{1},{a}_{2}\}
and B = \{{b}_{1},{b}_{2}\}.
Then A × B = \{({a}_{1},{b}_{1}),({a}_{1},{b}_{2}),({a}_{2},{b}_{1}),({a}_{2},{b}_{2})\}
and B × A = \{({b}_{1},{a}_{1}),({b}_{1},{a}_{2}),({b}_{2},{a}_{1}),({b}_{2},{a}_{2})\}. Because
({a}_{1},{b}_{1})≠({b}_{1},{a}_{1}) in
general, A × B≠B × A
in general.
)
(A)