Problem Set 4 — Sets and Quantifiers

Purpose

This problem set develops your ability to define sets and reason about quantified statements. The problem set thus addresses the following learning outcomes:

• Outcome 1.2, prove equivalence of statements involving logical quantifiers
• Outcome 2.1, Prove properties of and relationships between sets
• Outcome 5.1, Recognize claims amenable to proof using definitions and algebraic or other relationships pertinent to the subject of the claim, and construct the corresponding proofs
• Outcome 7, Write solutions to problems and proofs of theorems that meet rigorous standards based on content, organization and coherence, argument and support, and style and mechanics.

Background

This exercise is mainly based on sections 2.3 and 2.4 of our textbook. We discussed that material in classes between February 22 and March 3.

Activity

Answer the following questions. Any formal proofs should be typed according to the usual mathematical conventions, including typeface rules (e.g., italic variable names, emphasized labels for theorems and proofs, etc.)

Question 1

Part A

Use set builder notation to describe the set of all real numbers in the interval \([-2,2]\).

Part B

Letting \(X\) be the set from Part A, use set builder notation to describe the set of all real numbers that can be calculated by multiplying some member of \(X\) by \(2\).

Part C

Write a formal proof that \(X \subseteq Y\), where \(Y\) is the set defined in Part B.

Part D

If sets \(X\) and \(Y\) from Parts A and B were sets of integers instead of reals (i.e., the set of all integers in the interval \([-2,2]\) and the set of integers that could be calculated by multiplying those integers by 2), would it still be true that \(X \subseteq Y\)? Either give a formal proof that it is, or give an counterexample or similar demonstration that it isn’t.

Question 2

Classify each of the following as true or false, and justify each answer. Recall that for purposes of this course, the natural numbers are the integers strictly greater than 0.

1. All natural numbers greater than 9 are also greater than 10.
2. Some natural number greater than 9 is also greater than 10.
3. All natural numbers less than 1 are multiples of 10.
4. Some natural number less than 1 is a multiple of 10.

Question 3

Define the set \(\mathbb{Z}^-\) to be the set of negative integers, i.e., the integers less than \(0\).

Part A

Using the quantifier symbols \(\exists\) and \(\forall\) as needed, write a symbolic expression that means “if \(x\) is an element of \(\mathbb{Z}^-\), then there is no \(y\) in \(\mathbb{Z}^-\), such that \(xy\) is less than 0.”

Part B

Using the quantifier symbols \(\exists\) and \(\forall\) as needed, write a symbolic expression that means “if \(x\) and \(y\) are elements of \(\mathbb{Z}^-\), then \(xy\) is greater than or equal to 0.”

Part C

Show that the expressions you wrote in Parts A and B are equivalent. You do not need to write your answer as a formal proof.

Follow-Up

I will grade this exercise during one of your weekly individual meetings with me. That meeting should happen on or before the “Grade By” date above. During the meeting I will look at your solution, ask you any questions I have about it, answer questions you have, etc. Sign up for the meeting via Google calendar. Please have a written solution to the exercise ready to share with me during your meeting, as that will speed the process along.