Skip to main content
Logo image

Elementary Foundations: An introduction to topics in discrete mathematics

Jeremy Sylvestre

Activities 9.8 Activities
A4US

Activity 9.1.

For each member of your group, consider the set of all math and computing science courses you have taken so far at university. What is the intersection of these sets for your group?

Activity 9.2.

Is it possible to have two sets \(A\) and \(B\) with \(A \union B = A \intersection B\text{?}\)

Activity 9.3. Cancellation is not always valid.

(a)

Demonstrate using an example that \((A \union B) \relcmplmnt B = A\) is not a valid simplification in set theory.

(b)

Demonstrate using an example that \(A \union B = A \union C \lgcimplies B = C\) is not a valid simplification in set theory.

Activity 9.4.

Fill in the blank with a concept from the reading.
Breaking the students in a class into groups is an example of .

Activity 9.5.

  1. Write a definition in Candidate-condition notation for the set of all points on the graph of the parabola \(f(x) = x^2\text{.}\)
  2. Write a definition in Form-parameter notation for the set of all numbers that are one less than a power of two.

Activity 9.6.

Recall that \(\matrixring_n(\R)\) is the set of all \(n \times n\) matrices. Let \(V\) be the subset of invertible \(n \times n\) matrices, and \(S\) the set of scalar \(n \times n\) matrices. Write \(\zerovec\) for the \(n \times n\) zero matrix.
Express each of the following statements using the symbols of set theory:
\begin{equation*} \in, \;\;\; \subseteq, \;\;\; \union, \;\;\; \intersection, \;\;\; \emptyset, \;\;\; \text{etc.} \end{equation*}

(a)

\(\zerovec\) is a scalar matrix.

(b)

\(\zerovec\) is scalar and singular.

(c)

\(\zerovec\) is the only scalar, singular matrix.

(d)

Every scalar matrix besides \(\zerovec\) is invertible.

(e)

Every matrix is either invertible or singular.

Activity 9.7.

Pick another group in the class and list the elements of the Cartesian product of your group with that other group. If that group happened to also choose your group for this task, would their answer be the same as yours?

Activity 9.8.

List the elements of the power set of your group. Make sure you have all the \(\{\ \}\)-pairs you need in all the right places.

Activity 9.9.

For alphabet \(\Sigma = \{\mathrm{a},\mathrm{b},\mathrm{c}\}\text{,}\) describe the elements of \(\words{\Sigma}\) and \(\words{(\words{\Sigma})}\text{:}\)
Elements of \(\words{\Sigma}\) are .
Elements of \(\words{(\words{\Sigma})}\) are .
Is the equality of sets \(\words{(\words{\Sigma})} = \words{\Sigma}\) true?

Activity 9.10.

The equality of sets
\begin{equation*} A \cartprod (B \relcmplmnt C) = (A \cartprod B) \relcmplmnt (A \cartprod C) \end{equation*}
is true in general.
Write a formal proof of this equality, using the Test for Set Equality.

Activity 9.11.

The equality of sets \((A \cartprod B) \union (C \cartprod D) = (A \union C) \cartprod (B \union D)\) is false in general.
  1. Write down definitions for example sets \(A,B,C,D\) that form a counterexample.
  2. Can you come up with some conditions on \(A,B,C,D\) that make this equality true?

Activity 9.12.

Write a formal proof of the equality
\begin{equation*} \powset{A \intersection B} = \powset{A} \intersection \powset{B} \end{equation*}
using the Test for Set Equality.
Keep Warning 9.7.3 in mind as you do this!

Activity 9.13.

Informally explain why the set equality \(\powset{A \union B} = \powset{A} \union \powset{B}\) is not true in general.
<Prev^TopNext>