October 19, 2010 16:33  World Scientific Book - 9in x 6in  tst

Publishers’ page

October 19, 2010 16:33  World Scientific Book - 9in x 6in  tst

Publishers’ page

October 19, 2010 16:33  World Scientific Book - 9in x 6in  tst

Publishers’ page

October 19, 2010 16:33  World Scientific Book - 9in x 6in  tst

Publishers’ page

October 19, 2010 16:33  World Scientific Book - 9in x 6in  tst

Contents

Part I. Basic Set Theory 1

1. Sets, Functions, Relations . . . . . . . . . . . . . . . . . . . . 1 1.1. Sets and Functions . . . . . . . . . . . . . . . . . . . 1 1.2. Relations . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3. Ordering Relations . . . . . . . . . . . . . . . . . . . 10 1.4. Infinities . . . . . . . . . . . . . . . . . . . . . . . . . 12

I.1. Sets, Functions, Relations 1

Chapter 1 Sets, Functions, Relations

• Sets and Functions – Set building operations

– Some equational laws

• Relations and Sets with Structures – Properties of relations

– Ordering relations

• Infinities – Countability vs. uncountability

1: Sets and Functions

♢  a Background Story  ♢

A set is an arbitrary collection of arbitrary objects, called its members. One should take these two occurrences of “arbitrary” seriously. Firstly, sets may be finite, e.g., the set C of cars on the parking lot outside the building, or infinite, e.g. the set N of numbers greater than 5.

Secondly, any objects can be members of sets. We can talk about sets of cars, blood-cells, numbers, Roman emperors, etc. We can also talk about the set X whose elements are: my car, your mother and number 6. (Not that such a set necessarily is useful for any purpose, but it is possible to collect these various elements into one set.) In particular sets themselves can be members of other sets. I can, for instance, form the set whose elements are: my favorite pen, my four best friends and the set N. This set will have 6 elements, even though the set N itself is infinite.

A set with only one element is called a singleton, e.g., the set containing only planet Earth. There is one special and very important set – the empty set – which has no members. If it seems startling, you may think of the set of all square circles or all numbers x such that

2 Introduction to Logic

x < x. This set is mainly a mathematical convenience – defining a set by describing the properties of its members in an involved way, we may not know from the very begining what its members are. Eventually, we may find that no such objects exist, that is, that we defined an empty set. It also makes many formulations simpler since, without the assumption of its existence, one would often had to take special precautions for the case a set happened to contain no elements.

It may be legitimate to speak about a set even if we do not know exactly its members. The set of people born in 1964 may be hard to determine exactly but it is a well defined object because, at least in principle, we can determine membership of any object in this set. Similarly, we will say that the set R of red objects is well defined even if we certainly do not know all its members. But confronted with a new object, we can determine if it belongs to R or not (assuming, that we do not dispute the meaning of the word “red”.)

There are four basic means of specifying a set.

(1) If a set is finite and small, we may list all its elements, e.g., S = {1, 2, 3, 4} is a set with four elements.

(2) A set can be specified by determining a property which makes objects qualify as its elements. The set R of red objects is specified in this way. The set S can be described as ‘the set of natural numbers greater than 0 and less than 5’.

(3) A set may be obtained from other sets. For instance, given the set S and the set S′ = {3, 4, 5, 6} we can form a new set S′′ = {3, 4} which is the intersection of S and S′. Given the sets of odd {1, 3, 5, 7, 9...} and even numbers {0, 2, 4, 6, 8...} we can form a new set ℕ by taking their union.

(4) Finally, a set can be determined by describing the rules by which its elements may be generated. For instance, the set ℕ of natural numbers {0, 1, 2, 3, 4, ...} can be described as follows: 0 belongs to ℕ and if n belongs to ℕ, then also n + 1 belongs to ℕ and, finally, nothing else belongs to ℕ.

In this chapter we will use mainly the first three ways of describing sets. In particular, we will use various set building operations as in point 3. In the later chapters, we will constantly encouter sets described by the last method. One important point is that the properties of a set are entirely independent from the way the set is described. Whether we just say ‘the set of natural numbers’ or the set ℕ as de-

I.1. Sets, Functions, Relations 3

fined in point 2. or 4., we get the same set. Another thing is that studying and proving properties of a set may be easier when the set is described in one way rather than another.

♢  ♢

Definition 1.1 Given some sets S and T we write:

x ∈ S - x is a member (element) of S
S ⊆ T - S is a subset of T ..... . . . . . . . . . . for all x : if x ∈ S then x ∈ T
S ⊂ T - S ⊆ T and S ≠ T .... . . . . . . . . . . for all x : if x ∈ S then x ∈ T
and for some x : x ∈ T and x ∉ S

Set building operations :

∅ - empty set ..... . . . . . . . . . . . . . . . . . . for any x : x ∉ ∅
S ∪ T - union of S and T .... . . . . . . . . . . . x ∈ S ∪ T iff x ∈ S or x ∈ T
S ∩ T - intersection of S and T .... . . . . . x ∈ S ∩ T iff x ∈ S and x ∈ T
S \ T - difference of S and T .... . . . . . . . x ∈ S \ T iff x ∈ S and x ∉ T
\overline{S} - complement of S; given a universe U of all elements \overline{S} = U \ S
S × T - Cartesian product of S and T .... x ∈ S × T iff x = ⟨s, t⟩ and
s ∈ S and t ∈ T
℘(S) - the power set of S .... . . . . . . . . . . x ∈ ℘(S) iff x ⊆ S

Also, {x ∈ S : Prop(x)} denotes the set of those x ∈ S which have the specified property Prop.

Remark. Sets may be members of other sets. For instance {∅} is the set with one element – which is the empty set ∅. In fact, {∅} = ℘(∅). It is different from the set ∅ which has no elements. {{a, b}, a} is a set with two elements: a and the set {a, b}. Also {a, {a}} has two different elements: a and {a}. In particular, the power set contains only sets as elements: ℘({a, {a, b}}) = {∅, {a}, {{a, b}}, {a, {a, b}}}.

In the definition of Cartesian product, we used the notation ⟨s, t⟩ to denote an ordered pair whose first element is s and second t. In set theory, all possible objects are modelled as sets. An ordered pair ⟨s, t⟩ is then represented as the set with two elements – both being sets – {{s}, {s, t}}. Why not {{s}, {t}} or, even simpler, {s, t}? Because elements of a set are not ordered. Thus {s, t} and {t, s} denote the same set. Also, {{s}, {t}} and {{t}, {s}} denote the same set (but different from the set {s, t}). In ordered pairs, on the other hand, the order does matter – ⟨s, t⟩ and ⟨t, s⟩ are different pairs. This ordering is captured by the representation {{s}, {s, t}}. We have here a set with two elements {A, B} where A = {s} and B = {s, t}. The relationship between these two elements tells us

4 Introduction to Logic

which is the first and which the second: A ⊂ B identifies the member of A as the first element of the pair, and then the element of B \ A as the second one. Thus ⟨s, t⟩ = {{s}, {s, t}} ≠ {{t}, {s, t}} = ⟨t, s⟩. □

The set operations ∪, ∩, and \ obey some well known laws:

1. Idempotency  2. Associativity
A ∪ A = A  (A ∪ B) ∪ C = A ∪ (B ∪ C)
A ∩ A = A  (A ∩ B) ∩ C = A ∩ (B ∩ C)
3. Commutativity  4. Distributivity
A ∪ B = B ∪ A  A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
A ∩ B = B ∩ A  A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
5. deMorgan  6. Complement
\overline{(A ∪ B)} = \overline{A} ∩ \overline{B}  A ∩ \overline{A} = ∅
\overline{(A ∩ B)} = \overline{A} ∪ \overline{B}  A \ B = A ∩ \overline{B}
7. Emptyset
∅ ∪ A = A  ∅ ∩ A = ∅
8. Consistency principles
a) A ⊆ B iff A ∪ B = B  b) A ⊆ B iff A ∩ B = A

Remark 1.2 [Venn’s diagrams] It is very common to represent sets and set relations by means of Venn’s diagrams – overlapping figures, typically, circles or rectangles. On the the left in the figure below, we have two sets A and B in some universe U. Their intersection A ∩ B is marked as the area belonging to both by both vertical and horisontal lines. If we take A to represent Armenians and B bachelors, the darkest region in the middle represents Armenian bachelors. The region covered by only vertical, but not horisontal, lines is the set difference A\B – Armenians who are not bachelors. The whole region covered by either vertical or horisontal lines represents all those who are either Armenian or are bachelors.

U A  B\overline{(A ∪ B)} = \overline{A} ∩ \overline{B}  ^{U A  B}

Now, the white region is the complement of the set A ∪ B (in the universe U)

– all those who are neither Armenians nor bachelors. The diagram to the right is essentially the same but was constructed in a different way. Here, the region

I.1. Sets, Functions, Relations 5

covered with vertical lines is the complement of A – all non-Armenians. The region covered with horisontal lines represents all non-bachelors. The region covered with both horisontal and vertical lines is the intersection of these two complements – all those who are neither Armenians nor bachelors. The two diagrams illustrate the first de Morgan law since the white area on the left, \overline{(A ∪ B)}, is exactly the same as the area covered with both horisontal and vertical lines on the right, \overline{A} ∩ \overline{B}. □

Venn’s diagrams may be handy tool to visualize simple set operations. However, the equalities above can be also seen as a (not yet quite, but almost) formal system allowing one to derive various other set equalities. The rule for performing such derivations is ‘substitution of equals for equals’, known also from elementary arithemtics. For instance, the fact that, for an arbitrary set A : A ⊆ A amounts to a single application of rule 8.a): A ⊆ A iff A ∪ A = A, where the last equality holds by 1. A bit longer derivation shows that (A ∪ B) ∪ C = (C ∪ A) ∪ B :

(A ∪ B) ∪ C =^{3} C ∪ (A ∪ B) =^{2} (C ∪ A) ∪ B.

In exercises we will encounter more elaborate examples.

In addition to the set building operations from the above defintion, one often encounters also disjoint union of sets A and B, written A ⊎ B and defined as A ⊎ B = (A × {0}) ∪ (B × {1}). The idea is to use 0, resp. 1, as indices to distinguish the elements originating from A and from B. If A ∩ B = ∅, this would not be necessary, but otherwise the “disjointness” of this union requires that the common elements be duplicated. E.g., for A = {a, b, c} and B = {b, c, d}, we have A ∪ B = {a, b, c, d} while A ⊎ B = {⟨a, 0⟩, ⟨b, 0⟩, ⟨c, 0⟩, ⟨b, 1⟩, ⟨c, 1⟩, ⟨d, 1⟩}, which can be thought of as {a_{0}, b_{0}, c_{0}, b_{1}, c_{1}, d_{1}}.

Definition 1.3 Given two sets S and T, a function f from S to T, f : S → T, is a subset of S × T such that

• whenever ⟨s, t⟩ ∈ f and ⟨s, t′⟩ ∈ f, then t = t′, and

• for each s ∈ S there is some t ∈ T such that ⟨s, t⟩ ∈ f.

A subset of S × T that satisfies the first condition above but not necessarily the second, is called a partial function from S to T.

For a function f : S → T, the set S is called the source or domain of the function, and the set T its target or codomain.

The second point of this definition means that function is total – for each argument (element s ∈ S), the function has some value, i.e., an element

6 Introduction to Logic

t ∈ T such that ⟨s, t⟩ ∈ f. Sometimes this requirement is dropped and one speaks about partial functions which may have no value for some arguments but we will be for the most concerned with total functions.

Example 1.4 Let ℕ denote the set of natural numbers {0, 1, 2, 3, ...}. The mapping f : ℕ → ℕ defined by f(n) = 2n is a function. It is the set of all pairs f = {⟨n, 2n⟩ : n ∈ ℕ}. If we let M denote the set of all people, then the set of all pairs father = {⟨m, m′s father⟩ : m ∈ M} is a function assigning to each person his/her father. A mapping ‘children’, assigning to each person his/her children is not a function M → M for two reasons. For the first, a person may have no children, while saying “function” we mean a total function. For the second, a person may have more than one child. These problems may be overcome if we considered it instead as a function M → ℘(M) assigning to each person the set (possibly empty) of all his/her children. □

Notice that although intuitively we think of a function as a mapping assigning to each argument some value, the definition states that it is actually a set (a subset of S × T is a set.) The restrictions put on this set are exactly what makes it possible to think of this set as a mapping. Nevertheless, functions – being sets – can be elements of other sets. We may encounter situations involving sets of functions, e.g. the set T^{S} of all functions from set S to set T, which is just the set of all subsets of S × T, each satisfying the conditions of the definition 1.3.

Remark 1.5 [Notation] A function f associates with each element s ∈ S a unique element t ∈ T. We write this t as f(s) – the value of f at point s. When S is finite (and small) we may sometimes write a function as a set {⟨s_{1}, t_{1}⟩, ⟨s_{2}, t_{2}⟩, ..., ⟨s_{n}, t_{n}⟩} or else as {s_{1} ↦ t_{1}, s_{2} ↦ t_{2}, ..., s_{n} ↦ t_{n}}. If f is given then by f[s ↦ p] we denote the function f′ which is the same as f for all arguments x ≠ s : f′(x) = f(x), while f′(s) = p. □

Definition 1.6 A function f : S → T is injective iff whenever f(s) = f(s′) then s = s′; surjective iff for all t ∈ T there exists an s ∈ S such that f(s) = t; bijective, or a set-isomorphism, iff it is both injective and surjective.

I.1. Sets, Functions, Relations 7

Injectivity means that no two distinct elements from the source set are mapped to the same element in the target set; surjectivity that each element in the target is an image of some element from the source.

Example 1.7 The function father : M → M is injective – everybody has exactly one (biological) father, but it is not surjective – not everybody is a father of somebody. The following drawing gives some examples:

[figure: S; h; T; s_{1}; t_{1}; s_{2}; t_{2}; s_{3}; t_{3}; t_{4}; S; f; T; s_{1}; t_{1}; s_{2}; t_{2}; s_{3}; t_{3}; t_{4}; S; T; g; s_{1}; t_{1}; s_{2}; t_{2}; s_{3}; t_{3}; t_{4}]

[figure: S; b; T; s_{1}; t_{1}; s_{2}; t_{2}; s_{3}; t_{3}; S; T; b′; s_{1}; t_{1}; s_{2}; t_{2}; s_{3}; t_{3}]

Here h is neither injective nor surjective, f is injective but not surjective, g : T → S is surjective but not injective. b and b′ are both injective and surjective, i.e, bijective. □

Soon we will see the particular importance of bijections. There may exist several different set-isomorphisms between two sets S and T. If there is at least one set-isomorphism, we say that the two sets are isomorphic and write S ⇌ T. The following lemma gives another criterion for a function to be a bijection.

Lemma 1.8 f : S → T is a set-isomorphism if and only if there is an inverse function f^{−1} : T → S, such that for all s ∈ S : f^{−1}(f(s)) = s and for all t ∈ T : f(f^{−1}(t)) = t.

Proof. We have to show two implications:

only if) If f is iso, we can define f^{−1} simply as the set of pairs f^{−1} =^{def} {⟨t, s⟩ : t = f(s)}.

8 Introduction to Logic

if) If f(s) = f(s′) then s = f^{−1}(f(s)) = f^{−1}(f(s′)) = s′, i.e., f is injective. Then, for any t ∈ T we have an s = f^{−1}(t) for which f(s) = f(f^{−1}(t)) = t, i.e., f is surjective. QED (1.8)

In the example 1.7 both b and b′ were bijective. In fact, they acted as mutual inverses satisfying the conditions of the above lemma: for each s ∈ S; b′(b(s)) = s and for each t ∈ T : b(b′(t)) = t.

Definition 1.9 For any set U and A ⊆ U, the characteristic function of A (relatively to U), denoted f_{A}, is the function

{⟨x, 1⟩ | x ∈ A} ∪ {⟨x, 0⟩ | x ∈ A′}.

Hence f_{A}(x) = 1 iff x ∈ A. Note that f_{A} is a function from U to {1, 0}, where {1, 0} is a(ny) set with exactly two elements.

Let f : ℘(U) → 2^{U} denote the function sending each subset A of U to its characteristic function f_{A} (the notation 2^{U} stands for the set of all functions from U to a two-element set, e.g., to {1, 0}).

It is clear that if A ≠ B then f_{A} ≠ f_{B}. The first inequality means that there is an x such that either x ∈ A \ B or x ∈ B \ A. In either case we will have that f_{A}(x) ≠ f_{B}(x). Thus f is injective.

On the other hand, every function f ∈ 2^{U} is the characteristic function of some subset of U, namely, of the set A_{f} = {x ∈ U : f(x) = 1}. That is, f is surjective. Together, these two facts mean that we have a setisomorphism f : ℘(U) ⇌ 2^{U}.

2: Relations

Definition 1.10 A binary relation R between sets S and T is a subset R ⊆ S × T. A binary relation on a set S is a subset of S × S, and an n-ary relation on S is a subset of S_{1} × S_{2} × ... × S_{n}, where each S_{i} = S.

Comment. The definition 1.10 makes any subset of S × T a relation. The definition 1.3 of function, on the other hand, required this set to satisfy some additional properties. Thus, it is clear, that a function is a special case of relation, namely, a relation which relates each element of S with exactly one element of T. Binary relations are sets of ordered pairs, i.e., ⟨s, t⟩ ≠ ⟨t, s⟩ – if s ∈ S and t ∈ T, then the former belongs to S × T and the latter to T × S, which are different sets. For sets, there is no ordering and thus {s, t} = {t, s}. It is common to write the fact that s and t stand in a relation R, ⟨s, t⟩ ∈ R, as sRt or as R(s, t).

I.1. Sets, Functions, Relations 9

In general, relations may have arbitrary arities, for instance a subset R ⊆ S × T × U is a ternary relation, etc. As a particular case, a unary relation on S is simply a subset R ⊆ S. In the following we are speaking only about binary relations (unless explicitly stated otherwise). □

Example 1.11 Functions, so to speak, map elements of one set onto the elements of another set (possibly the same). Relations relate some elements of one set with some elements of another. Recall the problem from example 1.4 with treating children as a function M → M. This problem is overcome by treating children as a binary relation on the set M of all people. Thus children(p, c) holds if an only if c is a child of p. Explicitly, this relation is children = {⟨p, c⟩ : p, c ∈ M and c is a child of p}. □

Definition 1.12 Given two relations R ⊆ S × T and P ⊆ T × U, their composition is the relation R ; P ⊆ S ×U, defined as the set of pairs {⟨s, u⟩ ∈ S × U : there is a t ∈ T with R(s, t) and P (t, u)}.

As functions are special cases of relations, we may also form the composition g ; f of functions g : S → T and f : T → U. It is easy to see that g ; f will be a function from S to U. Note that (g ; f)(s) is equal to f(g(s)).

Definition 1.13 A relation R ⊆ S × S is :

connected iff for all pairs of distinct s, t ∈ S : R(s, t) or R(t, s)
reflexive iff for all s ∈ S : R(s, s)
irreflexive iff for no s ∈ S : R(s, s)
transitive iff when R(s_{1}, s_{2}) and R(s_{2}, s_{3}) then R(s_{1}, s_{3})
symmetric iff when R(s, t)  then R(t, s)
asymmetric iff when R(s, t)  then not R(t, s)
antisymmetric iff when R(s, t) and R(t, s)  then s = t
equivalence iff it is reflexive, transitive and symmetric.

Numerous connections hold between these properties: every irreflexive, transitive relation is also asymmetric, and every asymmetric relation is also antisymmetric. Note also that just one relation is both connected, symmetric and reflexive, namely the universal relation S × S itself.

The most common (and smallest) example of equivalence is the identity relation id_{S} = {⟨s, s⟩ : s ∈ S}. The relation ⇌ – existence of a setisomorphism – is also an equivalence relation on any set (collection) of sets. An equivalence relation ∼ on a set S allows us to partition S into disjoint

10 Introduction to Logic

equivalence classes [s] = {s′ ∈ S : s′ ∼ s}.

Given a relation R ⊆ S × S, we can form its closure with respect to one or more of these properties. For example, the reflexive closure of R, written \underline{R}, is the relation R ∪id_{S}. (It may very well happen that R already is reflexive, R = \underline{R}, but then we do have that \underline{R} = \underline{\underline{R}}.) The transitive closure of R, written R^{+}, can be thought of as the infinite union R ∪ (R ; R) ∪ (R ; R ; R) ∪ (R ; R ; R ; R) ∪ (R ; R ; R ; R ; R) ∪ … and can be defined as the least relation R^{+} such that R^{+} = R ∪ (R^{+} ; R).

3: Ordering Relations

Of particular importance are the ordering relations which we will use extensively in chapter ?? and later. Often we assume an implicit set S and talk only about relation R. However, it is important to realize that when we are talking about a relation R, we are actually considering a set with structure, namely a pair ⟨S, R⟩.

Definition 1.14 ⟨S, R⟩ is a quasiorder (or preorder), QO, iff R is

transitive : R(x, y) ∧ R(y, z) → R(x, z)
reflexive : R(x, x)

⟨S, R⟩ is a weak partial order, wPO, iff R is

a quasiorder : R(x, y) ∧ R(y, z) → R(x, z)
: R(x, x)
antisymmetric : R(x, y) ∧ R(y, x) → x = y

⟨S, R⟩ is a strict partial order, sPO, iff R is

transitive : R(x, y) ∧ R(y, z) → R(x, z)
irreflexive : ¬R(x, x)

A total order, TO, is a PO which is connected : x ≠ y → R(x, y) ∨ R(y, x)

Notation. Obviously, given a wPO, we can trivially construct its strict version (by making it irreflexive) and vice versa. We will therefore often say “partial order” or PO without specifying which one we have in mind.

Instead of writing R(x, y) for a PO, we will use the infix notation x ≤ y for a wPO, and x < y for the corresponding sP O. In other words, x ≤ y means x < y or x = y, and x < y means x ≤ y and x ≠ y. □

A QO allows loops, for instance the situations like R(a_{1}, a_{2}), R(a_{2}, a_{3}), R(a_{3}, a_{1}) for distinct a_{1}, a_{2}, a_{3}. PO forbids such situations: by applications of transitivity we have

I.1. Sets, Functions, Relations 11

• R(a_{2}, a_{1}) as well as R(a_{1}, a_{2}), which for wPO’s imply a_{1} = a_{2}.

• R(a_{1}, a_{1}), which is impossible for sPO’s.

Example 1.15 Consider the set of all people and their age.

(1) The relation ‘x is older than y’ is an sPO on the set of all people : it is transitive, irreflexive (nobody is older than himself) and asymmetric: if ‘x is older than y’ then ‘y is not older than x’.

(2) The relation ‘x is not younger than y’ is a QO. It is not a wPO since it is not antisymmetric. (There are different people of the same age.)

The weak version of the relation in 1. is the relation ‘x is older than y or x, y is the same person’, which is clearly different from the relation in 2. The relation in 1. is not a TO – of two different persons there may be none who is older than the other. □

Example 1.16 Given a set of symbols, for instance Σ = {a, b, c}, the set Σ^{∗} contains all finite strings over Σ, e.g., a, aa, abba, aaabbababab, .... There are various natural ways of ordering Σ^{∗}. Let s, p ∈ Σ^{∗}

(1) Define s ≺_{Q} p iff length(s) < length(p). This gives an sPO. The weak relation s ⪯_{Q} p iff length(s) ≤ length(p) will be a QO but not a wPO since now any subset containing strings of equal length will form a loop.

(2) Define s ≺_{P} p iff s is a prefix of p. (Prefix is an initial segment.) We now obtain a wPO because any string is its own prefix and if both s is a prefix of p and p is a prefix of s the two must be the same string. This is not, however, a TO : neither of the strings a and bc is a prefix of the other.

(3) Suppose that the set Σ is totally ordered, for instance, let Σ be the Latin alphabet with the standard ordering a ≺ b ≺ c ≺ d.... We may then define the lexicographic TO on Σ^{∗} as follows: s ≺_{L} p iff either s is a prefix of p or else the two have a longest common prefix u (possibly empty) such that s = uv, t = uw and head(v) ≺ head(w), where head is the first symbol of the argument string. This defines the usual ordering used, for instance, in dictionaries.

□

Homomorphisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . [optional] The following notions will not be used extensively, but it is often important to realize that the functions between ordered sets should consider not only the

12 Introduction to Logic

elements of the sets but also the relation between these elements.

Definition 1.17 Given two orderings (of any kind) P = ⟨S_{1}, R_{1}⟩ and Q = ⟨S_{2}, R_{2}⟩, a homomorphism h : P → Q is an order preserving function, i.e., a function h : S_{1} → S_{2} such that R_{1}(x, y) implies R_{2}(h(x), h(y)). An order-isomorphism is a set-isomorphism h : S_{1} ⇌ S_{2} such that both h and h^{−1} are homomorphisms. Thus, an order-isomorphism is a set-isomorphism which, in addition, preserves the structure of the isomorphic relations. One often encounters two ordered sets which are set-isomorphic but not order-isomorphic.

Example 1.18 Given two 4-element sets A and B, consider two sPO’s A = ⟨A, ≺_{A}⟩ and B = ⟨B, ≺_{B}⟩ as shown below: Any injective f : A → B is also a bijection, i.e., A ⇌ B. However, a homomorphism h : A → B must also satisfy the additional condition, e.g., a_{1} ≺_{A} a_{2} requires that also h(a_{1}) ≺_{B} h(a_{2}). Thus, for instance, f from the table is not a homomorphism A → B while h_{1} and h_{2} are.

Now, although the underlying sets A and B are isomorphic, there is no orderisomorphism between A = ⟨A, ≺_{A}⟩ and B = ⟨B, ≺_{B}⟩ because there is no homomorphism from the latter to the former. B is connected, i.e., a total order while A is not – any homomorphism would have to preserve the relation ≺_{B} between arbitrary two elements of B, but in A there is no relation ≺_{A} between a_{2} and a_{3}.

□

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .[end optional]

4: Infinities

♢  a Background Story  ♢

Imagine a primitive shepherd who possesses no idea of number or counting – when releasing his sheep from the cottage in the morning he wants to find the means of figuring out if, when he collects them in the evening, all are back or, perhaps, some are missing.

He can, and most probably did, proceed as follows. Find a stick and let the sheep leave one by one. Each time a sheep passes through the gate, make a mark – something like / – on the stick. When all the sheep have left, there will be as many marks on the stick as there were sheep. On their return, do the same: let them go through the gate one by one. For each sheep, erase one mark – e.g., set a \making one /into ×. When all the sheep are inside, check if there are any

I.1. Sets, Functions, Relations 13

/-marks left. If no, i.e., there are only ×on the stick, then everything is ok – as many sheep returned home as had left in the morning. If yes, then some sheep are missing.

Notice, that the shepherd still does not know “how many” sheep he has – he still does not have the idea of a number. But, perhaps a bit paradoxically, he has the idea of two equal numbers! This idea is captured by the correspondance, in fact, several functions: the first is a morning-function m which for each sheep from the set S_{M} of all sheep, assigns a new /on the stick – all the marks obtained in the morning form a set M. The other, evening-function e, assigns to each returning sheep (from the set of returning sheep S_{E}) another mark \. Superimposing the evening marks \onto the morning marks /, i.e., forming ×-marks, amounts to comparing the number of elements in the sets M and E by means of a function c assigning to each returning sheep marked by \, a morning sheep /.

S_{M} m ↔ M c ↔ E e ↔ S_{E}
[figure: →; /; ×; \; ←]
[figure: →; /; ×; \; ←]
[figure: →; /; ×; \; ←]
…

In fact, this simple procedure may be considered as a basis of counting – comparing the number of elements in various sets. In order to ensure that the two sets, like S_{M} and M, have equal number of elements, we have to insist on some properties of the involved function m. Each sheep must be given a mark (m must be total) and for two distinct sheep we have to make two distinct marks (m must be injective). The third required property – that of surjectivity – follows automatically in the above procedure, since the target set M is formed only along as we mark the sheep. In short, the shepherd knows that there are as many sheep as the morning marks on the stick because he has a bijective function between the respective sets. For the same reason, he knows that the sets of returning sheep and evening marks have the same number of elements and, finally, establishing a bijection between the sets M and E, he rests satisfied. (Violating a bit the profiles of the involved functions, we may say that the composite function e ; c ; m : S_{E} → E → M → S_{M} turns out to be bijective.)

14 Introduction to Logic

You can now easily imagine what is going on when the shepherd discovers that some sheep are missing in the evening. He is left with some /-marks which cannot be converted into ×-marks. The function c : E → M is injective but not surjective. This means that the set E has strictly fewer elements than the set M.

These ideas do not express immediately the concept of a number as we are used to it. (They can be used to do that.) But they do express our intuition about one number being equal to, smaller or greater than another number. What is, perhaps, most surprising is that they work equally well when the involved sets are infinite, thus allowing us to compare “the number of elements” in various infinite sets.

♢  ♢

In this section, we consider only sets and set functions, in particular, setisomorphisms.

Definition 1.19 Two sets S and T have equal cardinality iff they are setisomorphic S ⇌ T. The cardinality of a set S, |S|, is the equivalence class [S] = {T : T ⇌ S}.

This is not an entirely precise definition of cardinality which, as a matter of fact, is the number associated with such an equivalence class. The point is that it denotes the intuitive idea of the number of elements in the set – all set-isomorphic sets have the same number of elements.

Definition 1.20 |S| ≤ |T | iff there exists an injective function f : S → T.

It can be shown that this definition is consistent, i.e., that if |S_{1}| = |S_{2}| and |T_{1}| = |T_{2}| then there exists an injective function f_{1} : S_{1} → T_{1} iff there exists an injective function f_{2} : S_{2} → T_{2}. A set S has cardinality stricly less than a set T, |S| < |T |, iff there exists an injective function f : S → T but there exists no such surjective function.

Example 1.21 |∅| = 0, |{∅}| = 1, |{{∅}}| = 1, |{∅, {∅}}| = 2. |{a, b, c}| = |{•, #, +}| = |{0, 1, 2}| = 3. For finite sets, all operations from Definition 1.1 yield sets with possibly

I.1. Sets, Functions, Relations 15

different cardinality:

\begin{aligned}1. & |\{a, b\} ∪ \{a, c, d\}| = & |\{a, b, c, d\}| & |S ∪ T | & ≥ & |S| \\ 2. & |\{a, b\} ∩ \{a, c, d\}| = & |\{a\}| & |S ∩ T | & ≤ & |S| \\ 3. & |\{a, b\} \ \{a, c, d\}| = & |\{b\}| & |S \ T | & ≤ & |S| \\ 4. & |\{a, b\} × \{a, d\}| = & |\{⟨a, a⟩, ⟨a, d⟩, ⟨b, a⟩⟨b, d⟩\}| & |S × T | & = & |S| ∗ |T | \\ 5. & |℘(\{a, b\})| = & |\{∅, \{a\}, \{b\}, \{a, b\}\}| & |℘(S)| & > & |S| \end{aligned}

□

From certain assumptions (“axioms”) about sets it can be proven that the relation ≤ on cardinalities has the properties of a weak TO, i.e., it is reflexive (obvious), transitive (fairly obvious), antisymmetric (not so obvious) and total (less obvious).

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . [optional] As an example of how intricate reasoning may be needed to establish such “not quite but almost obvious” facts, we show that ≤ is antisymmetric.

Theorem 1.22 [Schröder-Bernstein] For arbitrary sets X, Y, if there are injections i : X → Y and j : Y → X, then there is a bijection f : X → Y (i.e., if |X| ≤ |Y | and |Y | ≤ |X| then |X| = |Y |).

Proof. If the injection i : X → Y is surjective, i.e., i(X) = Y, then i is a bijection and we are done. Otherwise, we have Y_{0} = Y \ i(X) ≠ Ø and we apply j and i repeatively as follows

\begin{matrix}Y_{0} = Y \ i(X) & X_{0} = j(Y_{0}) \\ Y_{n+1} = i(X_{n}) & X_{n+1} = j(Y_{n+1}) \\ Y^{∗} = ⋃_{n=0}^{ω}Y_{n} & X^{∗} = ⋃_{n=0}^{ω}X_{n} \end{matrix}

[figure: i.e.,; Y_{0}; j; Y_{1}; j; Y_{2}; j; j; … Y^{∗}; X; i; X_{0}; i; X_{1}; i; X_{2}; i; … X^{∗}]

So we can divide both sets into disjoint components as in the diagram below.

[figure: Y =; j; Y^{∗}; j; ∪; (Y \ Y^{∗}); X =; i; X^{∗}; ∪; (X \ X^{∗}); i]

We show that the respective restrictions of j and i are bijections. First, j : Y^{∗} → X^{∗} is a bijection (it is injective, and the following equation shows

16 Introduction to Logic

that it is surjective):

j(Y^{∗}) = j( ⋃_{n=0}^{ω} Y_{n}) = ⋃_{n=0}^{ω} j(Y_{n}) = ⋃_{n=0}^{ω} X_{n} = X^{∗}

By lemma 1.8, j^{−} : X^{∗} → Y^{∗}, defined by j^{−}(x) = y : j(y) = x is a bijection too. Furthermore:

i(X^{∗}) = i( ⋃_{n=0}^{ω} X_{n}) = ⋃_{n=0}^{ω} i(X_{n}) = ⋃_{n=0}^{ω} Y_{n+1} = ⋃_{n=1}^{ω} Y_{n} = Y^{∗} \ Y_{0}. (1.23)

Now, the first of the following equalities holds since i is injective, the second by (1.23) and since i(X) = Y \ Y_{0} (definition of Y_{0}), and the last since Y_{0} ⊆ Y^{∗}:

i(X \ X^{∗}) = i(X) \ i(X^{∗}) = (Y \ Y_{0}) \ (Y^{∗} \ Y_{0}) = Y \ Y^{∗},

i.e., i : (X \ X^{∗}) → (Y \ Y^{∗}) is a bijection. We obtain a bijection f : X → Y defind by

f(x) = \{ \begin{matrix}i(x) & if x ∈ X \ X^{∗} \\ j^{−}(x) & if x ∈ X^{∗} \end{matrix}

QED (1.22)

A more abstract proof. The construction of the sets X^{∗} and Y^{∗} in the above proof can be subsumed under a more abstract formulation implied by the Claims 1. and 2. below. In particular, Claim 1. has a very general form.

Claim 1. For any set X, if h : ℘(X) → ℘(X) is monotonic, i.e. such that, whenever A ⊆ B ⊆ X then h(A) ⊆ h(B); then there is a set T ⊆ X : h(T) = T.

We show that T = ⋃{A ⊆ X : A ⊆ h(A)}.

a) T ⊆ h(T) : for for each t ∈ T there is an A : t ∈ A ⊆ T and A ⊆ h(A). But then A ⊆ T implies h(A) ⊆ h(T), and so t ∈ h(T).

b) h(T) ⊆ T : from a) T ⊆ h(T), so h(T) ⊆ h(h(T)) which means that h(T) ⊆ T by definition of T.

Claim 2. Given injections i, j define ^{∗} : ℘(X) → ℘(X) by A^{∗} = X \ j(Y \ i(A)). If A ⊆ B ⊆ X then A^{∗} ⊆ B^{∗}. Follows trivially from injectivity of i and j. A ⊆ B, so i(A) ⊆ i(B), so Y \ i(A) ⊇ Y \i(B), so j(Y \i(A)) ⊇ j(Y \i(B)), and hence X \j(Y \i(A)) ⊆ X \j(Y \i(B)).

3. Claims 1 and 2 imply that there is a T ⊆ X such that T = T^{∗}, i.e., T =

X \ j(Y \ i(T)). Then f : X → Y defined by f(x) = \{ \begin{matrix}i(x) & if x ∈ T \\ j^{−1}(x) & if x ∉ T \end{matrix} is a

bijection. We have X = j(Y \ i(T)) ∪ T and Y = (Y \ i(T)) ∪ i(T), and obviously

I.1. Sets, Functions, Relations 17

j^{−1} is a bijection between j(Y \ i(T)) and Y \ i(T), while i is a bijection between T and i(T). □

We now see. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . [end optional]

Cardinality of each finite set is a natural number. The apparently empty Definition 1.19 becomes more significant when we look at the infinite sets.

Definition 1.24 A set S is infinite iff there exists a proper subset T ⊂ S such that S ⇌ T.

Example 1.25 Denote the cardinality of the set of natural numbers by |ℕ| =^{def} ℵ_{0}. (Sometimes it is also written ω, although axiomatic set theory distinguishes between the cardinal number ℵ_{0} and the ordinal number ω. Ordinal number is a more fine-grained notion than cardinal number, but we shall not worry about this.) We have, for instance, that |ℕ| = |ℕ \ {0}|, as shown below to the left. In fact, the cardinality of ℕ is the same as the cardinality of the even natural numbers! It is easy to see that the pair of functions f(n) = 2n and f^{−1}(2n) = n as shown to the righ:

\begin{aligned}\{ & 0 & 1 & 2 & 3 & ... \\ & ↕ & ↕ & ↕ & ↕ & ... \\ \{ & 1 & 2 & 3 & 4 & ... \end{aligned}  \begin{aligned}& \{ & 0 & 1 & 2 & 3 & 4 & 5 & ... \\ f ↓ & & ↕ & ↕ & ↕ & ↕ & ↕ & ↕ & ↑ f^{−1} \\ & \{ & 0 & 2 & 4 & 6 & 8 & 10 & ... \end{aligned}

In general, when |S| = |T | = ℵ_{0} and |P | = n < ℵ_{0}, we have

\begin{matrix}|S ∪ T | = & ℵ_{0} \\ |S \ P | = & ℵ_{0} \\ |S × T | = & ℵ_{0} \end{matrix}

The following drawing illustrates a possible set-isomorphisms ℕ ⇌ ℕ × ℕ:

[figure: 03; 13; 23; 33; 43; 02; 12; 22; 32; 42; 01; 11; 21; 31; 41; 00; 10; 20; 30; 40; 50]

□

A set-isomorphism S ⇌ ℕ amounts to an enumeration of the elements of S. Thus, if |S| ≤ ℵ_{0} we say that S is enumerable or countable; in case of

18 Introduction to Logic

equality, we say that it is countably infinite. Now, the question “are there any uncountable sets?” was answered by the founder of modern set theory, Georg Cantor

Theorem 1.26 For any set A : |A| < |℘(A)|.

Proof. The construction applied here shows that the contrary assumption – A ⇌ ℘(A) – leads to a contradiction. Obviously,

|A| ≤ |℘(A)|

since the inclusion defined by f(a) = {a} is an injective function f : A → ℘(A). So, assume the equality |A| = |℘(A)|, i.e., a corresponding F : A → ℘(A) which is both injective and surjective. Define the subset of A by B =^{def} {a ∈ A : a ∉ F (a)}. Since B ⊆ A, so B ∈ ℘(A) and, since F is surjective, there is a b ∈ A such that F (b) = B. Is b in B or not? Each of the two possible answers yields a contradiction:

(1) b ∈ F (b) means b ∈ {a ∈ A : a ∉ F (a)}, which means b ∉ F (b)

(2) b ∉ F (b) means b ∉ {a ∈ A : a ∉ F (a)}, which means b ∈ F (b).

QED (1.26)

Corollary 1.27 There is no greatest cardinal number. In particular, ℵ_{0} = |ℕ| < |℘(ℕ)| < |℘(℘(ℕ))| < ... Theorem 1.26 proves that there exist uncountable sets, but are they of any interest? Another theorem of Cantor shows that such sets have been around in mathematics for quite a while.