| HPS 0628 | Paradox | |
Back
to doc list
Back to Infinite Sets
Sets, Formally Speaking
John D. Norton
Department of History and Philosophy of Science
University of Pittsburgh
http://www.pitt.edu/~jdnorton
A set consists of elements a, b, c, ... enclosed in "curly brackets" { and }. (Elements are sometimes called "members.") That is, the set is {a, b, c, ...}. Why bother with the curly brackets? It enables us to distinguish something, say "a," from the singleton set "{a}" whose sole element is a.
We can specify a set merely by listing its elements. The set of planets is S = {Mercury, Venus, Earth, Mars, Jupiter, Saturn, Uranus, Neptune}. Other sets can also be members of sets. For example, the sets {a}, {a,b}, {a,b,c} can also form a set. It is {{a}, {a,b}, {a,b,c}}.
The null set, written as {} or ∅, is the set with no elements.
We may also specify a set as all those entitles x satisfying some condition F(x). The resulting is S = {x: F(x)}. This is the naive comprehension or existence axiom. It says that for any genuine condition or property F(x), this procedure does indeed define a set.
Self-test: Which of these are these sets
according to the naive axiom:
A = {x: x is an even number}
B = {x: x is equal to twice itself}
C = {x: x is NOT equal to itself}
D = {x: x is a sock}
E = {x: x is anything at all}
Answer
For practical purposes, this axiom works without problems almost everywhere. However, once we are on the trail of paradoxes, we shall see later that it leads to problems that require a drastic rethinking of just what a set can be.
All there is to a set are its
members. There is no notion of order or repetition.
• The order in which we write the elements does not matter. {a,b} = {b,a}.
• Repetition of the elements in what we write does not matter. {a} = {a,
a, a}
Self test: Which of these are the same set?
A = {a, b} B = {a, b, a, b} C = {{a}, b}
Answer
We can represent ordered pairs and fancier things by nestling structures. For example, take the ordered pair of a then b. It can be conventionally rendered in set theory as
<a, b> = { a, {a,b} }
Consider the set S = {a, b, c}.
The membership relation ∈ tells us which individuals are elements of a set. It is denoted by ∈. In this example, a ∈ S, b ∈ S, and c ∈ S. To say that d is not an element of S we write d ∉ S or ~(d ∈ S). The symbol ~ is read as "not" or "it is not the case that".
The subset relation tells
us which sets are included in a set. It is denoted by ⊆.
S' ⊆ S tells us that S' is a subset of S; that is, every element of S' is
also a member of S. For example, if S = {a, b, c}, then {a,b} ⊆ S, {a,c} ⊆
S and even S ⊆ S.
Self test: If S = {1} and T = {1,2}, which of
these are true:
A: S ⊆ T B: S ∈ T C: neither
Answer
The proper subset relation is a stricter version of the subset relation and is denoted by ⊂.
S' ⊂ S tells us that S' is a subset of S but that it is not the same as S. That is, there are some elements of S not in S'.
A useful convention that simplifies calculations is to say that {} is a subset of all sets. The basis is that the following is true for every set S: any element of {} is also a element of S! It is true since there are no elements in {}; it is what is sometimes called a "vacuous truth."
For example {}, {a}, {b} and {a,b} are subsets of
{a,b}:
{} ⊆ {a, b} {a} ⊆ {a, b} {b} ⊆ {a,
b} {a, b} ⊆ {a, b}
However, only {}, {a} and {b} are proper subsets of {a,b}.
{} ⊂ {a, b} {a} ⊂ {a,
b} {b} ⊂ {a, b}
Self test: For S = {1, 10, 100}, which are
subsets? Which are proper subsets?
A = {} B = {1} C = {1,10} D = {1, 10, 100} E = {1,
10, 100, 1000}
Answer
The power set P(S) of the set S is a set whose elements are exactly the subsets of S. If S = {a,b,c}, then its power set is P(S) = {{a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}, {}}.
Self test: Which of these are in the power
set of P(S) of
S = {1,2}?
A = 1 B = 2 C = {} D = {1}
E = {2} F = {1, 2} G = {1, 2, 3} H = {1, 1}
Answer
A function f from a set A to a
set B (written f:A→B) assigns to each element of A a unique element of B.
A is called the domain and B is the range. If a ∈ A, then f assigns to it
f(a) ∈ B. The uniqueness requirement is essential. If the relation assigns
more than one element of B to element some of A, then it is not a
function.
An example of a function from the set of positive and negative numbers to
the set of positive numbers is the square function. It assigns to each
number its square.
1→1
2→4
3→9
...
and also
-1→1
-2→4
-3→9
...
A function f:A→B is one-to-one if the uniqueness works
in the reverse direction. That is, at most one member of A is assigned to
each member of B.
The square function on integers (that include negative numbers) is not
one-one, since both 2 and -2 are assigned to 4.
Self test: Which of these is a function?
Which is a one-to-one function?
(x and y can be any real number)
A: y = x/3, so that ... -3→-1, 0→0, 3→1, 6→2, ...
B: y = smallest whole number larger that x, so that
... 0.5→1, 1.5→2, 0.1→1, 3.75→4, ...
C: y = 5 so that ... -1→5, 0→5, 1→5, 2→5, ...
D: y = square root(x), so that 0→0, 1→(1 or -1), 4→(2 or -2), ...
Answer
Fin: A finite set, such as {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
ℕ: The infinite set of natural numbers {1, 2, 3, 4, 5, ...}
ℤ: The infinite set of all integers {..., -2, -1, 0, 1, 2, ...}
ℚ: The infinite set of rational numbers {1, 2, 3, ... , 1/2, 1/3, ... , 2/3, 2/5, ...-2/5, -3/7, ... 5/2, -7/3, ...}. These are all numbers that can be expressed as a ratio of integers, excluding the case of division by zero.
Note that all rationals can be represented as
terminating decimals or as infinite but repeating decimals.
e.g. 1/4=0.25 and 1/7=0.142857142857142857142857142857...
This means that any rational number can always be described with a finite number of symbols. (The importance of this fact will be apparent later.)
ℝ:
The infinite set of real numbers. The reals include ℚ
as well as all numbers that can be represented by infinite and
non-repeating decimal expansions.
e.g. π=3.141592653589323846264338...
The numbers added that are represented by non-repeating decimal expansions are "irrational numbers," since they cannot be expressed as a ratio of integers. It will turn out that most real numbers are irrational numbers. It follows that that most real numbers cannot be described with a finite number of symbols. (The importance of this fact will be apparent later.)
[0,1]: "closed interval" The set of real numbers between 0 and 1. The end points 0 and 1 are included. It is often drawn on the number line as follows, where the filled in circles represent closure:
(0,1): "open interval" The set of real numbers between 0 and 1. The end points 0 and 1 are not included. It is often drawn on the number line as follows, where the unfilled circles represent openness:
(0,1]: "half open interval" The set of real numbers between 0 and 1. The end point at 1 only is included:
Self test: To which of ℕ, ℤ, ℚ, ℝ do the
following belong:
A: 27 B: -7 C: -7/5 D: 0.3333... E: π
= 3.14159...
Answer
Self test: Which of the following are true?
A: ℕ ⊂ ℤ ⊂ ℚ ⊂ ℝ
B: ℕ ⊆ ℤ ⊆ ℚ ⊆ ℝ
C: ℕ ∈ ℤ ∈ ℚ ∈ ℝ
Answer
Puzzle: How can an infinite repeating decimal be represented finitely? Here's how. Take the infinitely repeating decimal:
x = 0.012345679012345679012345679...
We can see the repetition more easily if we write it as:
x = 0.012345679 012345679 012345679 ...
Now some algebra:
Form 1,000,000,000x = 012345679 . 012345679 012345679 ...
1,000,000,000x - x = 999,999,999 x = 012345679
Solving for x, we have
x = 012345679/999999999 = 1/81
This demonstrates the familiar rule for converting any repeating decimal into a finitely expressible fraction.
Step 1. Take the repeating part, 012345679
Set 2. Divide it by as many 9's as there are digits: 012345679/999999999
We now have a finite expression for the rational number. Often it can be simplified by diving out common factors:
999999999 = 111111111 x 9 = 012345679 x 9 x 9 = 012345679 x 81
Therefore 012345679/999999999 = 012345679/(012345679 x 81) = 1/81
(Easy) Self test: Write the infinitely
repeating decimal 0.111111111... as a fraction.
Answer
(Harder) Self test: Write the infinitely
repeating decimal 0.384615 384615 384615 ... as a fraction.
Hint: Take out the common factors: 7, 11, 27 and 37.
Answer
June 23, September
29, 2021. February 18, 2023.
Copyright, John D. Norton