Problem Set 11—Sets and Functions

Purpose

This problem set reinforces your ability to reason about Cartesian products of sets, indexed families of sets, and basic concepts related to functions.

Background

Our textbook discusses Cartesian products in section 5.4, indexed families of sets in section 5.5, and basic function concepts in sections 6.1 and 6.2. We discussed Cartesian products in class on March 29, and indexed families on March 31. We will begin discussing functions on April 3.

Activity

Solve the following problems. Formal proofs should be word-processed (i.e., not hand-written) and should follow the guidelines in Sundstrom’s text.

Problem 1

Let A = {-1,0,1} and B = {a,b}. Find the Cartesian product A × B.

Problem 2

Exercise 8 from section 5.4 of our textbook (prove that A×B = B×A if and only if A = B).

Problem 3

Exercise 4b in section 5.5 of our textbook (prove that the complement of the union of all sets in an indexed family is the intersection of the complements of the sets; see the textbook for a more formal and precise description of the problem).

Problem 4

Exercises 8a, b, c, e, and f in section 6.1 of our textbook (construct various functions between certain finite sets or explain why it isn’t possible to construct the requested functions; see the textbook for details of each question). You do not need to give formal proofs for any of your answers.

Problem 5 (Proofs Not Quite Out Of Context)

(Thanks to Prof. Aaron Heap for this question.)

Define addition of ordered pairs of numbers to be pairwise addition, i.e., (a,b) + (c,d) =  (a+c,b+d). For example, (1,2) + (3,5) = (4,7).

Definition. A function f : ℤ → ℤ×ℤ is called a homomorphism if f(x+y) = f(x) + f(y) for all x, y ∈ ℤ.

Is the function g : ℤ → ℤ×ℤ defined by g(x) = (x,2x) a homomorphism? Prove your answer or provide a counterexample to justify it.

Follow-Up

I will grade this exercise in a face-to-face meeting with you. During this meeting I will look at your solution, ask you any questions I have about it, answer questions you have, etc. Please bring a written solution to the exercise to your meeting, as that will speed the process along.

Sign up for a meeting via Google calendar. Please make the meeting 15 minutes long, and schedule it to finish before the end of the “Grade By” date above.