Relations, Mappings, and Sets in Computer Science at VSB - Technical University

Department of Computer Science, Faculty of Electrical Engineering and Computer Science, VSB - Technical University of Ostrava Relations, mappings, countable and uncountable sets 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 12.06.2025 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. 12.06.2025 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 1stminus the 2ndone Relation adress of a person : { Jan Nov k, Praha 5, Bellu ova 1831 , Karel Hofmann, Praha 5, Bellu ova 1827 ,...,} 12.06.2025 4

Function (maping) n-ary function F on a set M is a special unique on the right- hand side (n+1)-ary relation F M ... M: 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. (n+1) x 12.06.2025 5

Function (maping) 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. 12.06.2025 6

Function (maping) 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 12.06.2025 7

Function (maping) 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) 12.06.2025 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. b [B(b) a (A(a) f(a)=b)]. A mapping f :A B is called an injection (one to one mapping A intoB), iff for all a A, b Asuch that a b it holds that f(a) f(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. 12.06.2025 9

Function (maping) Example: surjection injection {1 2 3 4 5} bijection {1 2 3 4 5} {2 3 4 } { 2 3 4 } If there is a bijection between the sets A, B, then we say that A and B have the same cardinality (number of elements). {1 2 3 4 5} {1 2 3 4 5} 12.06.2025 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. Hence0 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)! 12.06.2025 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 a) Proof: in two steps. Card(N) Card(R), because each natural number is rational: N R. Now we construct a mapping of N onto R (surjection N ontoR), 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 b) 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). 12 12.06.2025

Cardinality, countable 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 nthnumber inin the sequence i1i2i3 of decimals the number 1. We obtain a number which is not contained in the original sequence see the next slide: 12.06.2025 13

Cantors diagonal proof of uncountability of real numbers in the interval <0,1>. 1 i11 i21 i31 i41 i51 2 i12 i22 i32 i42 i52 3 i13 i23 i33 i43 i53 4 5 6 7 1 2 3 4 5 . A new number that is not contained in the table: 0,i11+1 i22+1 i33+1 i44+1 i55+1 i14 i24 i34 i44 i54 i15 i25 i35 i45 i55 i16 i26 i36 i46 i56 i17 i27 i37 i47 i57 12.06.2025 14