Discrete Mathematics Assignment for MATH1061, Semester 2, Uni Name

This document presents a complete solution to a discrete mathematics assignment (MATH1061). The solution includes proofs for set theory properties, specifically demonstrating the equality of A × (B ∩ C) and (A × B) ∩ (A × C). The assignment also analyzes a function f: Z × Z → Z, determining whether it is one-to-one and onto. Furthermore, the solution explores a bijection between a set of n-tuples and positive integers, utilizing prime factorization. The document concludes by examining a relation defined on real numbers, determining its reflexive, symmetric, and transitive properties. Finally, it investigates an equivalence relation based on modular arithmetic and provides a proof demonstrating its validity. The assignment covers key concepts in discrete mathematics, including set theory, functions, relations, and modular arithmetic, providing detailed explanations and justifications for each solution.

Running head: DISCRETE MATHS
Discrete Maths
Name of the Student:
Name of the University:

1DISCRETE MATHEMATICS
Table of Contents
Q1……………………………………………………………………………………………...2
Q2...............................................................................................................................................2
Q3...............................................................................................................................................2
Q4...............................................................................................................................................3
Q5...............................................................................................................................................3

2DISCRETE MATHEMATICS
Q1
To Prove, for all sets A, B and C: A × ( B ∩C ) =( A × B) ∩( A × C)
A × ( B ∩C ) = { ( x , y ) such that x ∈ A∧ y ∈ ( B ∩C ) }
∴ x ϵ A∧ yϵ B∧ yϵ C .
∴ xϵA∧ yϵB∧xϵA ∧ yϵC
¿ ( x , y ) ϵ ( A × B)∧ ( x , y ) ϵ (B ×C)
∴ ( x , y ) ϵ ( A × B)∩(B × C)
The reverse direction can be done similarly.
Q2.
f : Z × Z → Z where f ( ( x , y ) )=3 x +5 y for all ( x , y ) ∈ Z × Z
a)
No, the function is not one-one as f (0,0) = 0 and f (-5,3)=0.
b)
A function is onto if there exists a pre image foe every element in Z.
If z ∈ Z , then the equation 3 x +5 y=z is a Diophantine equation which has a solution only iff
g.c.d of (3,5) divides z. But g.c.d of (3,5) is 1 and hence will always be a multiple of any z
from Z. Hence there is always a solution to the equation and the function is onto.
Q3.
S is the set of all finite ordered n tuples of nonnegative integers where the last coordinate is
not 0.
To find a bijection from S to Z+.
A bijection from S to Z+ can be given by taking each n tuple and mapping it to the product of
ordered primes raised to the power of the elements in the n tuple.
Say, if s1 is an element of S and s1= (a1,a2, a3,…) then the map from S to Z will take s1 to
2a1
.3a2
. 5a3
…. .
Which is one one and onto.

3DISCRETE MATHEMATICS
Q4.
a r b iff ab−a−b< 0where a and b ∈R.
a)
Reflexive:
A relation is reflexive iff a R a holds.
For any x ∈ R , x∗x−x− x<0
x2−2 x<0
x ( x−2 )< 0
i.e the relation hold only for a fixed domain and not the whole R.
The relation is not reflexive.
b)
Let x, y be two real numbers.
The relation is symmetric iff x R y and y R x holds
i.e xy−x− y<o∧ yx− y−x <0.
Which is true. Thus, the relation is symmetric.
c)
Let x, y, z be three real numbers.
A relation is transitive iff x R y and y R z means x R z.
xy−x− y< 0∧ yz − y−z <0.
Both of the inequalities can be rewritten written as (x-1)(y-1)< 1 and (y-1)(z-1)< 1.
Multiplying both the inequalities:
(y-1)2(x-1)(z-1) < 1 ⟹ ( x−1 ) ( z −1 ) < 1
( y −1 ) 2
Which holds only when yϵ ( 0,2 ) .
The relation is not transitive.
Q5.
The relation τ on Z is defined as a τ b iff there exists x ∈ {1,4,16 } such that ax≡ b ( mod 63 ) .
To prove this is a equivalence relation.

4DISCRETE MATHEMATICS
The set x ∈ { 1,4,16 } forms a group under multiplication modulo 63.
1)
Checking for Reflexivity:
a τ a which is true as for x=1
a ×1 ≡ a(mod 63) holds.
2)
Checking for Symmetry
Let a τ b then there exists some xi ∈ { 1,4,16 } such that
a xi ≡ b . (mod 63)
Multiplying both sides of the congruence by the inverse of xi
a ≡ b x j (mod 63)
3)
Checking for transitivity:
Let a τ b and b τ c it needs to be checked if a τ c holds.
From the given information:
There exists some xi, xj ∈ {1,4,16 } such that:
a xi ≡ b and b x j ≡c .
i.e
a xi x j ≡ b x j ( mod 63 ) .
a xk ≡c ( mod 63 ) for some xk ∈ { 1,4,16 }
The relation is transitive.
As the relation satisfies the properties of being symmetric, transitive, and reflexive the
relation is an equivalence relation.
b) As congruent modulo 63 is already an equivalence relation. Any integer m can only be m
congruent n modulo 65 as x ∈ { 1,4,16 } will only take x=1 as the solution of the linear
congruence.

5DISCRETE MATHEMATICS
References:
Lyndon, R. C., & Schupp, P. E. (2015). Combinatorial group theory. Springer.
Halmos, P. R. (2017). Naive set theory. Courier Dover Publications.