Discrete Mathematics Assignment 4 Solutions: MATH1061/7861

This document presents a complete solution to a discrete mathematics assignment. The assignment covers several key concepts, including proving the cardinality of intervals using bijections and the Schroder-Bernstein theorem, demonstrating group isomorphism between (Q × Q, +) and (Q[√2], +), and constructing Cayley tables for a given group. The solution provides detailed justifications for each step, including the definition and verification of mappings, and the application of relevant theorems. Furthermore, the solution includes a discussion on whether (Z9, +, .) forms a field. The assignment also addresses combinatorial problems, such as finding the number of possible codes with specific constraints on digits, including odd and even numbers and digit repetitions. The solution provides a step-by-step breakdown of each case.

Discrete mathematics 1
DISCTETE MATHEMATICS
By Name
Course
Instructor
Institution
Location
Date

Discrete mathematics 2
QUESTION 1
PART A
[0, ∞] and [ 0,1]
Define f: [ 0,1] [1, ∞]
By f(x) = ½
0<x ≤ 1 then 1
x ≥ 1
Therefore f does map [0,1] to [1, ∞]
Also f-1 (x) = 1
x since x≥ then
0< 1
x ≤ 1 so f-1 maps [1, ∞] to [0,1]
Moreover
F(f-1 (x))= f( 1
x )=
1
1
x
= x
F-1 (f (x))= f-1 ( 1
x )=
1
1
x
= x
Thus f is bijection
Define g : [1, ∞] to [0,∞] by

Discrete mathematics 3
g(x) =x-1
If x≥ 1 then x-1 ≥ 0
Therefore g does map [1,∞ ¿ to [0,∞ ¿
Moreover g ( g-1 (x)) = g(x+1)= x +1-1 =x
g-1 (g(x)) = g-1(x-1)=x-1+1=x
g is bijection
Hence coordinates | [0,1]| = |[1, ∞]| = |[0, ∞ ¿∨¿
PART B
Schr¨oderBernstein theorem
f: S T is injective
g: T S is injective
Then |S| = |T|
[0,∞] and [0,1]
f: [0,∞] and [0,1]
f: [0,1] [0,∞]
f (0) = 2 , f(x) , f(x) =x ∀ x ∈ [ 0,1]
f is injective
g: [0, ∞] [0,1]

Discrete mathematics 4
g(x) = ⌊ x
2+1 if x {1,2,3 , … . }⌋ and ⌊ x +1
2+1 if x ∈{1,2,3 , … . }⌋
Clearly g is injective
Hence by Schr¨oderBernstein theorem
| [0,1]| = |[0, ∞ ¿∨¿
QUESTION 2
Define a mapping Q: Q×Q Q √ 2
∅ (a.b) a+b √2
Step 1 ∅ is homomorphum
Justification : ∅ [ (a.b) + (c.d)] = ∅ (a+c.b+d)
= (a+c) + (b+d) √2
= (a+b √ 2 ¿+ (c+d √ 2 ¿
= ∅ (a.b) + ∅ (c.d)
Thus ∅ is hormorphism.
Step 2 ∅ is one-one
Let ∅ (a.b) = ∅ (c.d) √ 2
= a+b √ 2 ¿= c+d √ 2 ¿
= (a-c)+(b-d) √2 ¿ =0

Discrete mathematics 5
a-c=0 and (b-d)=0
a=c and b=d
Therefore ( a.b)= (c.d)
Thus ∅ is one-one
Step 3
∅ is onto justification
Let a+b √2 ∈ Q ( √ 2
a.b ∈ Q×Q
Moreover ∅ (a.b) = a+b √2
Thus a.b √ 2 preimage .
From step q,3,3 is group homomorphism one-one onto . Hence an isomorphism
Therefore ( Q×Q.+) and (Q √ 2 , + ) are isomorphic
QUESTION 3
(Z9, +) = { 0,1,2,3,4,5,6,7,8 }
+ 0 1 2 3 4 5 6 7 8
0 0 1 2 3 4 5 6 7 8
1 1 2 3 4 5 6 7 8 0
2 2 3 4 5 6 7 8 0 1

Discrete mathematics 6
3 3 4 5 6 7 8 0 1 2
4 4 5 6 7 8 0 1 2 3
5 5 6 7 8 0 1 2 3 4
6 6 7 8 0 1 2 3 4 5
7 7 8 0 1 2 3 4 5 6
8 8 0 1 2 3 4 5 6 7
Va = { 1,2,4,5,7,8 } is a group ( therefore 3,6,0 do not have multiplicative inverse
(Z9) = { 0,1,2,3,4,5,6,7,8} do not form group still we write carley table
 0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6 7 8
2 0 2 4 6 8 1 3 5 7
3 0 3 6 0 3 6 0 3 6
4 0 4 8 3 7 2 6 1 5
5 0 5 1 6 2 7 3 8 4
6 0 6 3 0 6 3 0 6 3
7 0 7 0 1 1 8 6 4 2
8 0 8 7 6 5 4 3 2 1

Discrete mathematics 7
A formal proof is not required because in field ever entry has multiplicative inverse but in Z9
3,6 do not have multiplicative inverse so ( Z9 , + . ) is not field
QUESTION 4
Part A
The codes contain six different digits . Number of ways to choose a 6 digit pin is
9 × 9×8×7×6×5 = 136080
We have digits from 0 to 9. Since first digit convert start from 0 we have to choose from
remaining 9 digits
Part B
The codes containing only odd numbers but digits are allowed to be repeated
Number of ways to choose a six digit pin is
5×5×5×5×5×5 = 15625 ways
Since digits can be repeated and code contain only odd numbers we have to choose from
1,3,5,7,9
Part C
The code contains at least one odd number and at least one even number and digit are allowed to
be repeated
Number of ways to choose a 6 digit pin is
5×5×10×10×10×10×10 = 250000 ways
Part D

Discrete mathematics 8
The codes containing exactly three odd numbers and three even numbers.
Number of ways to choose a six digit pin is
5×4×3×5×4×3 = 3600 ways
Part E
6 different digits
Case 1 : Only one odd and 5 even numbers
Case 2 : three odd and three even numbers
For first place = 5
For second place= 5
For third place = 4
For fourth place= 4
For fifth place = 3
For sixth place = 3
= ( 5×4×3)2 = 3600
Multiply by 2 , because number can start from odd = 2×(5×4×3)2
Case 3 : 2 odd
The total number of ways when 2 is odd together are
5P2 ×2×3×4×5
Hence the total = 5P5 5P1 + (5P3 )2 + 5.5 (5P2)

Discrete mathematics 9
Bibliography
Levasseur, K. M., 2011. Exploring Abstract Algebra With Mathematica. 3rd ed. Chicago: Springer Science
& Business Media.
Plemmons, R. J., 2011. Cayley tables for all semigroups of order. 2nd ed. Hull: Department of
mathematics.