Transcript Document

Mathematical logic
Lesson 5
Relations, mappings,
countable and uncountable sets
2. 4. 2016
Relation, function
1
Relation
Relation between sets A, B is a subset of the
Cartesian product A  B.
Cartesian product A  B is a set of all ordered
pairs a, b, where aA, bB
(Binary) relation R2 on a set M is a subset of
M  M: R2  M  M
n-ary relation Rn on a set M: Rn  M ... M
n times
2. 4. 2016
Relation, function
2
Relation
Mind:
A couple a,b  b,a, but a set {a,b} = {b,a}
a, a  a, but {a,a} = {a}
n-tuples are ordered, particular elements of
tuples do not have to be unique (can be
repeated), unlike sets
Notation: a,b  R is written also in the prefix
R(a,b) or infix way a R b.
For instance 1  3.
2. 4. 2016
Relation, function
3
Relation - Example:
Binary relation on the set of natural numbers N: <
(strictly less than)
{0,1,0,2,0,3,…,1,2,1,3, 1,4, …,
2,3,2,4,…,3,4,…,5,7,…,115,119, .…}
Ternary relation on N: {0,0,0,1,0,1,1,1,0,…,
2,0,2, 2,1,1,2,2,0, …, 3,0,3, 3,1,2,
3,2,1,3,3,0,…,115,110,5, .…}
the set of triples of natural numbers such that the 3rd
number equals the 1st minus the 2nd one
Relation “adress of a person”: {Jan Novák, Praha 5,
Bellušova 1831, Marie Duží, Praha 5, Bellušova
1827,...,}
2. 4. 2016
Relation, function
4
Function (mapping)
n-ary function F on a set M is a special “unique on the
right-hand side” (n+1)-ary relation F  M ... M:
(n+1) x
a bc ([F(a,b)  F(a,c)]  b=c)
Partial F: to each n-tuple of elements a  M...M
there exists at most one element bM.
Notation F: M ... M  M,
instead of F(a,b) we write F(a)=b.
The set M ... M is called a domain of the function F,
the set M is called a range.
2. 4. 2016
Relation, function
5
Function (mapping)
Example: Relation on N
{1,1,1,2,1,2, 2,2 ,1, …, 4,2,2, …,
9,3,3, …, 27,9,3, .…}
Is a partial function dividing without a
remainder.
The relation minus on N (see the previous
slide) is a partial function on N: for instance
the couple 2,4 does not have an image in N.
In order that the function minus were total,
we’d have to extend the domain to integers.
2. 4. 2016
Relation, function
6
Function (mapping)
Functional symbols of FOL formulas are interpreted
only by total functions:
Total function F: A  B
To each element aA there is just one element bB
such that F(a)=b:
a b F(a)=b 
abc [(F(a)=b  F(a)=c)  b=c]
Sometimes we introduce a special quantifier !
With the meaning “there is just one”, written as:
a !b F(a)=b
2. 4. 2016
Relation, function
7
Function (mapping)
Examples:
Relation + {0,0,0, 1,0,1, 1,1,2, 0,1,1, …}
is a (total binary) function on N. To each pair of
numbers it assigns just one number, the sum of
the former.
Instead of 1,1,2  + we write 1+1=2.
The relation  is not a function:
x y z [(x  y)  (x  z)  (y  z)]
Relation {0,0, 1,1, 2,4, 3,9, 4,16, …}
is a function on N, namely the total function the
second power (x2)
2. 4. 2016
Relation, function
8
Surjection, injection, bijection

A mapping f : A  B is called a surjection
(mapping A onto B), iff to each element b  B
there is an element a  A such that f(a)=b.


A mapping f : A  B is called an injection (one to
one mapping A into B), iff for all aA, bA such
that a  b it holds that f(a)  f(b).


b [B(b)  a (A(a)  f(a)=b)].
a b [(A(b)  A(a)  (a  b))  (f(a)  f(b))].
A mapping f : A  B is called a bijection (one to
one mapping A onto B), iff f is a surjection and
injection.
2. 4. 2016
Relation, function
9
Function (mapping)

Example:
surjection
{1 2 3 4 5}
injection
{2 3 4 }
bijection
{1 2 3 4 5}
{234}
{1 2 3 4 5}
{1 2 3 4 5}
If there is a bijection between the sets A, B,
then we say that A and B have the same
cardinality (number of elements).
2. 4. 2016
Relation, function
10
Cardinality, countable sets
A set A that has the same cardinality as the
set N of natural numbers is called a
countable set.
 Example: the set S of even numbers is
countable. The bijection f of S into N is
defined, e.g., by f(n) = 2n.
Hence 0  0, 1  2, 2  4, 3  6, 4  8, …
One of the paradoxes of Cantor’s set theory:
S  N (a proper subset) and yet the number of
elements of the two sets is equal:
Card(S) = Card(N)!

2. 4. 2016
Relation, function
11
Cardinality, countable sets
The set of rational numbers R is also
countable.
1/1 1/2 1/3 1/4 1/5 1/6 …
Proof: in two steps.
a) Card(N)  Card(R),
because each natural number is
rational: N  R.
b) Now we construct a mapping of N
onto R (surjection N onto R), by
which we prove that
Card(R)  Card(N):
1
2 3 4 5 6…
1/1 2/1 1/2 3/1 2/2 1/3 …
But, in the table there are repeating
rationals, hence the mapping is not
one-to-one. However, no rational
number is omitted, therefore it is a
mapping of N onto R (surjection).

2/1 2/2 2/3 2/4 2/5 2/6 …
3/1 3/2 3/3 3/4 3/5 3/6 …
4/1 4/2 4/3 4/4 4/5 4/6 …
5/1 5/2 5/3 5/4 5/5 5/6 …
6/1 6/2 6/3 6/4 6/5 6/6 …
…
…
…
…
…
…
…
Card(N) = Card(R).
2. 4. 2016
Relation, function
12
Cardinality, uncountable sets





There are, however, uncountable sets: the least of them is the set
of real numbers R
Even in the interval 0,1 there are more real numbers than the
number of all natural numbers. However, in this interval there is the
same number of reals than the number of all the reals R!
Cantor’s diagonal proof: If there were countably many real numbers
in the interval 0,1, the numbers could be ordered into a sequence:
the first one (1.), the second (2.), the third (3.),…, and each of these
numbers would be of a form 0,i1i2i3…, where i1i2i3… is the decimal
part of the number.
Rational numbers have a finite decimal part, irrational numbers have
an infinite decimal part.
Let us add to each nth number in in the sequence i1i2i3… of decimals
the number 1. We obtain a number which is not contained in the
original sequence – see the next slide:
2. 4. 2016
Relation, function
13
Cantor’s diagonal proof of uncountability of real
numbers in the interval 0,1.
1
2
i12
i22
i32
i42
i52
3
i13
i23
i33
i43
i53
4
i14
i24
i34
i44
i54
5
i15
i25
i35
i45
i55
6
i16
i26
i36
i46
i56
7
i17
i27
i37
i47
i57
1
i11
2
i21
3
i31
4
i41
5
i51
….
A new number that is not contained in the table:
0,i11+1 i22+1 i33+1 i44+1 i55+1 …
2. 4. 2016
Relation, function
14
Propositional Logic again

Summary of the most important notions
and methods.
2. 4. 2016
Relation, function
15
Table of the truth functions
A
1
1
0
0
B
1
0
1
0
A
0
0
1
1
AB
1
1
1
0
AB
1
0
0
0
AB AB
1
1
0
0
1
0
1
1
Be careful with implication, p  q. It is false only in one case: p = 1, q = 0.
It is something like a promise:
“If you behave well you will get a Christmas gift” (p  q).
“I have been a good boy but there is no Christmas gift”. (p  q)
Has the promise been fulfilled?
If he were not a good boy (p = 0), then the promise would not obligate to anything.
2. 4. 2016
Propositional Logic - summary
16
Summary

Typical tasks:






Check whether an argument is valid
What is entailed by a given set of assumptions?
Add the missing assumptions so that the argument is valid
Is a given formula tautology, contradiction, satisfiable?
Find the models of a formula, find a model of a set of formulas
Up to now we know the following methods:

Truth-table method
Equivalent transformations
An indirect semantic proof
The resolution method

Semantic tableau



2. 4. 2016
Propositional Logic
17
Example. The proof of a tautology
|= [(p  q)  (p  r)]  (q  r)
A
Table:
p
q
r
(p  q)
(p  r)
A
(q  r)
A  (q  r)
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
0
1
0
1
0
1
1
1
0
0
0
1
0
0
1
0
1
1
1
1
1
1
1
0
1
0
1
0
0
1
1
0
0
1
1
1
1
1
1
0
0
0
1
0
0
0
1
Indirect proof of the tautology
|= [(p  q)  (p  r)]  (q  r)
The formula A is a tautology, iff the negated formula A is a
contradiction:
|= A
iff
A |=
 Let us assume that the negated formula can be true.
 Negation of implication: (A  B)  (A  B)
 (p  q)  (p  r)  q  r
1
1
10 10
q = 0, r = 0, hence p  0, p  0
0 0
0
0
therefore: p = 0, p = 0, i.e.
1
p=1
contradiction
 The negated formula does not have a model, it is a contradiction.
Hence the formula A is a tautology.
2. 4. 2016
Propositional Logic
19
The proof by equivalent transformations
We need the laws:

(A  B)  (A  B)  ((A  B))

(A  B)  (A  B)
de Morgan

(A  B)  (A  B)
de Morgan

(A  B)  (A  B)
negation of implication

(A  (B  C))  ((A  B)  (A  C))
distributive law

(A  (B  C))  ((A  B)  (A  C))
distributive law

1A 1

1A A

0A 0

0A A
2. 4. 2016
1  tautology,
e.g. (p  p)
0  contradiction
e.g. (p  p)
propositional logic
20
The proof by equivalent transformations
|= [(p  q)  (p  r)]  (q  r)
[(p  q)  (p  r)]  (q  r) 
[(p  q)  (p  r)]  (q  r) 
 (p  q)  (p  r)  q  r 
 [p  (p  r)  q  r]  [q  (p  r)  q  r] 

(p  p  q  r)  (p  r  q  r)  (q  p  q  r)  (q  r  q  r)
 1  1  1  1  1 – tautology
 Note:
We obtained a conjunctive normal form (CNF)
2. 4. 2016
Relation, function
21
Proof of a tautology – resolution method
|= [(p  q)  (p  r)]  (q  r)

Negated formula is transformed into a clausal form
(CNF), the indirect proof:
(p  q)  (p  r)  q  r  (p  q)  (p  r)  q  r
1.
2.
3.
4.
5.
6.
7.
p  q
pr
q
r
q  r resolution 1, 2
r
resolution 3, 5
resolution 4, 6 – contradiction
2. 4. 2016
propositional logic
22
Proof by a semantic tableau
|= [(p  q)  (p  r)]  (q  r)
Direct proof: we construct the CNF
(‘’: branching, ‘’: comma – closed branches: ‘p  p’)
(p  q)  (p  r)  q  r
p, (p  r), q, r
q, (p  r), q, r
+
p, p, q, r
+
2. 4. 2016
p, r, q, r
+
propositional logic
23
Indirect proof by a semantic tableau
|= [(p  q)  (p  r)]  (q  r)
Indirect proof: by the DNF of the negated formula
(‘’: branching, ‘’: comma, - closed branches 0: ‘p  p’)
[(p  q)  (p  r)]  q  r
p, (p  r), q, r
q, (p  r), q, r
+
p, p, q, r
+
2. 4. 2016
p, r, q, r
+
propositional logic
24
Proof of an argument
|= [(p  q)  (p  r)]  (q  r)
[(p  q)  (p  r)] |= (q  r)
(p  q), (p  r) |= (q  r)
iff
iff
p: The program goes right
q: The system is in order
r: It is necessary to call for a system engineer
If the program goes right, the system is in order.
If the program malfunctions, it is necessary to call for a
system engineer
---------------------------------------------------------------------------If the system is not in order, it is necessary to call for a
system engineer.
2. 4. 2016
propositional logic
25
Proof of an argument
(p  q), (p  r) |= (q  r)
Indirect proof:
{(p  q), (p  r), (q  r)}
– it cannot be a satisfiable set
1. p  q
2. p  r
3. q
4. r
5. q  r
resolution 1, 2
6. r
resolution 3, 5
7.
resolution 4, 6, contradiction
26
Proof of an argument
(p  q), (p  r) |= (q  r)
Direct proof: What is entailed by the assumptions?
The resolution rule is truth preserving:
p  q, p  r |-- q  r
1
1
1
In any valuation v it holds that if the assumptions are true, the
resolvent is true as well
Proof:
a) p = 1  p = 0  q = 1  (q  r) = 1
b) p = 0  r = 1  (q  r) = 1
1.
p  q
2.
pr
3.
qr
resolution 1, 2 – consequence:
(q  r)  (q  r)
QED
2. 4. 2016
propositional logic
27