Homework 1
MATH 301/601 (Spring 2025)
Test #1 is on Tuesday, February 18
 

Instructions. Read the Homework Guide to make sure you understand how to successfully complete the assignment. Click here for a pdf version of the homework.

*Exercise 1.

1. Give an example of a function $\mathbb{N}\to \mathbb{N}$ that is injective but not surjective.

2. Give an example of a function $\mathbb{N}\to \mathbb{N}$ that is surjective but not injective.

3. Give an example of a bijection from $\mathbb{N}\to \mathbb{Z}$.

Exercise 2.

Let $f:A\to B$ and $g:B\to C$. Prove the following statements.

1. If $f$ and $g$ are both injective, then $g\circ f$ is injective.

2. If $g\circ f$ is surjective, then $g$ is surjective.

3. If $g\circ f$ is injective and $f$ is onto, then $g$ is injective.

Exercise 3.

Let $f:X\to Y$ be a function, let $A_1,A_2\subset X$, and let $B_1,B_2\subset Y$.

1. Prove that $f(A_1\cup A_2)=f(A_1)\cup f(A_2)$.

2. Prove that $f(A_1\cap A_2)\subset f(A_1)\cap f(A_2)$, and then give an example where $f(A_1\cap A_2)\ne f(A_1)\cap f(A_2)$.

3. Prove that $f^{-1}(B_1\cup B_2)=f^{-1}(B_1)\cup f^{-1}(B_2)$, where $f^{-1}(B)=\{x\in X:f(x)\in B\}$.

4. Prove that $f^{-1}(B_1\cap B_2)=f^{-1}(B_2)\cap f^{-1}(B_2)$.

*Exercise 4.

Let $S\subset \mathbb{N}$ such that $1\in S$ and $n+1\in S$ whenever $n\in S$. Prove that $S=\mathbb{N}$. (Hint: Use the well-ordering principle.)

**Exercise 5.

Define the ordering on $\mathbb{N}\times \mathbb{N}$ by if or $a=c$ and (this is called the lexicographical ordering). Prove that is well ordered, that is, show that given a nonempty subset $S$ of $\mathbb{N}\times \mathbb{N}$ there exists $s\in S$ such that for all $s^{\prime }\in S\setminus \{s\}$.
Aside: as a set with no additional structure, $\mathbb{N}\times \mathbb{N}$ is equivalent to $\mathbb{N}$, as there is a bijection between them (can you find it?); however, as ordered sets, these sets are not equivalent (meaning, there is no order-preserving bijection between them), as bounded sets need not be finite in the lexicographical ordering. Various notions of equivalence are very important in mathematics.

Exercise 6.

Let $a,b,c,m,n\in \mathbb{Z}$. Prove that if $a\mid b$ and $a\mid c$, then $a\mid (mb+nc)$.

Exercise 7.

Let $a,b\in \mathbb{Z}$. Prove that if $a\mid b$ and $b\mid a$, then either $a=b$ or $a=-b$.

*Exercise 8.

Let $n\in \mathbb{N}$. Prove that the remainder obtained from dividing $n^2$ by 4 is either 0 or 1.

Exercise 9.

Use the Euclidean algorithm to compute the following greatest common divisors:

1. $\gcd (42,55)$

2. $\gcd (14,30)$

3. $\gcd (234,165)$

4. $\gcd (1739,9923)$

*Exercise 10.

Let $a,b\in \mathbb{Z}\setminus \{0\}$. Prove that if there exists $s,t\in \mathbb{Z}$ such that $as+bt=1$, then $\gcd (a,b)=1$.