| 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 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 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 rationals {1, 2, 3, ... , 1/2, 1/3, ... , 2/3, 2/5, ...-2/5, -3/7, ... 5/2, -7/3, ...}.
Note that all rationals can be represented as
terminating decimals or as an infinite but repeating decimals.
e.g. 1/4=0.25 and 1/7=0.142857142857142857142857142857...
ℝ:
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...
[0,1]: The set of numbers in the closed line
interval from 0 to 1. The end points 0 and 1 are included.
(0,1): The set of numbers in the open interval from 0 to 1. The end points 0 and 1 are not 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
June 23, September 29, 2021
Copyright, John D. Norton