Homework 1

Sets

1. Given sets A and B, show that $A \cap B$ is the largest common subset of A and B, in the sense that it contains every such common subset.
   Note: Typically for statements involving largest or smallest, a proof by contradiction works quite well.

2. Given sets A and B, prove if $A \cap X = B \cap X$ and $A \cup X = B \cup X$ for some set X, then A = B
   Hint: $A = A \cap (A \cup X)$

Functions

1. Given functions $f:A \rightarrow B$ and $g:B \rightarrow C$, prove that if $g \circ f$ is one-to-one (injective), then f is one-to-one.
   Note: The function g need not be injective nor surjective.
2. Consider a circle C, a straight line tangent to it L, and a point P located anywhere in the plane of the circle except on L. Define the mapping $f:C \rightarrow L$ by a point $c_1 \in C$ is mapped to a point $l_1 \in L$ if and only if they are collinear with P, i.e. a straight line passes through c₁,l₁ and P. Consider this mapping for each of the following locations of P and answer the following questions: Is f a function and if so, is it injective, surjective, and/or bijective?
   1. P may lie anywhere on the opposite side of the line from C.
   2. P lies on the same side of the line as the circle but outside the circle.
   3. P is inside the circle
   4. P lies on the circle but not diametrically opposite the point of tangency.
   5. P lies on the circle diametrically opposite the point of tangency.

Equivalences

1. Let f be a function mapping set A into set B. Define the relation ρ on A by
   $x \rho y \leftrightarrow f(x) = f(y)$.
   Show that ρ is an equivalence relation on A and define the corresponding equivalence classes.
   Note: ρ is called the kernel equivalence of f.

Numbers

1. Find the gcd(198,241) and express it as a linear combination of 198 and 241.

Binary Operations

1. On$\mathbb{Z}^+$, define a * b = c where c is the largest integer less than the product of a and b. Determine if * is a binary operation and if not, why it fails.
2. Suppose that * is an associative binary operation on a set S. Let $H = \{a \in S | a*x = x*a \text{ for all } x \in S\}$. Show that H is closed under *.