How to submit:

  • Submit before actual tutorial time for it to be graded. There are 2 ways to do this:
    1. There is a submission box on Canvas for you to submit your document. Either .docx, .pdf, or a picture of your written solutions are acceptable as long as we can read your attempts.
    2. Submit your written attempts in-person during our tutorial.
  • Official due date for submission : 04-Mar-2025, 23:59 or during tutorial itself.

Collaboration Policy:

  • You may discuss high-level ideas with your classmates or friends. You should list your collaborators if you do so.
  • Do not share your solutions.
  • ChatGPT (and other LLMs) are not allowed.
  • Your submission must be of your own write-up.

Late Policy:

  • < 1 week after submission deadline: 50% penalty
  • < 2 weeks after submission deadline: 75% penalty
  • No submissions after 2 weeks.

Overview

This tutorial gives practice questions to be discussed during the relevant tutorial in person. This particular tutorial sheet corresponds to Unit 2 and Unit 3. It is recommended to either watch the lectures or read the notes for each respective parts before attempting the tutorial sheet.

  1. Questions 1 through 4 are related to set theory.
  2. Questions 5 through 8 are related to relations.

After week 5’s content, you should be able to attempt questions 1 through 4. After week 6’s content, you should be able to attempt questions 5 through 8.

Questions 2, 4, 5, 7 are graded for participation.

That said, we encourage you to try all the questions, this way when you come for tutorial we can best make use of your time since you can either verify your solutions, or understand the discussions when our tutors go through the solutions.


Question 1

Let , and .

Find and .

Solutions:

. Observe that has elements.

, so:

Observe that has elements.


Question 2 [Graded for Participation]

Consider the sets and , .

Find the following sets:

Note: Some of these can be written using Set Roster Notation, these are the ones where you can list them out one by one. For the rest, you can write them using set builder notation.

Solutions:

First, we write out in set-roster notation: .

Next, set is simply all the positive natural numbers that are greater than a multiple of .

Then, we have the following sets:


Question 3

Convert the following from set builder notation to set roster notation:

  1. .

Hint for : It might be helpful to first think about what it’s trying to do. That might speed things up for you.

Solutions:

  1. , i.e., the set of prime numbers between and

Question 4 [Graded for Participation]

Prove the set equality .

Prove the set equality .

Hint: Based on logical equivalences shows a method that is helpful.

Solutions:

The first problem is equivalent to the following:

Using a truth table, we see that this equivalence is true:

Hence, .

The second problem is equivalent to the following:

Using a truth table, we see that this equivalence is also true:

Hence, .

For those who are interested in reading more rigorous proofs:


Question 5 [Graded for Participation]

Let be the following relation:

Compute . Compute .

It might be helpful to refer to Operations on Relations.

Solution:

Solution


Question 6

Let be the following set: . Let .

Sub-part 1

Is the following statement true?

is reflexive.

If it is true, prove it. Otherwise, prove the negation of the statement. It might be helpful to refer to Reflexivity.

Solutions:

True.

Proof: is reflexive

  1. Let be arbitrarily chosen.
  2. [Conjunction on line 1]
  3. [Definition of cartesian product]
  4. [Definition of ]
  5. [Universal generalisation on lines 1, 4]
  6. is reflexive. [Definition of reflexivity]

Sub-part 2

Is the following statement true?

is symmetric.

If it is true, prove it. Otherwise, prove the negation of the statement. It might be helpful to refer to Symmetry.

Solutions:

True.

Proof: is symmetric

  1. Let and be arbitrarily chosen.
  2. Suppose that .
  3. [Conjunction on line 1]
  4. [Definition of cartesian product, from line 2.1]
  5. [Definition of ]
  6. [Implication introduction on lines 2, 2.3]
  7. [Universal generalisation on lines 1, 3]
  8. is symmetric. [Definition of symmetry]

Sub-part 3

Is the following statement true?

is anti-symmetric.

If it is true, prove it. Otherwise, prove the negation of the statement. It might be helpful to refer to Anti-Symmetry.

Solutions:

False.

Proof: is not antisymmetric

Lets start by taking the negation of the statement for antisymmetry. If we are be able to prove that the negation is true we can prove the the original statement is false. [Negating universal quantifiers] [Logically equivalent] [Logically equivalent]

  1. .
  2. [Definition of cartesian product, from line 1]
  3. [Definition of R]
  4. [Definition of cartesian product, from line 1]
  5. [Definition of R]
  6. [Conjunction on lines 4 and 6]
  7. [By basic algebra]
  8. [Conjunction on lines 7 and 8]
  9. Therefore, [Existential generalization]
  10. Since the negation of antisymmetry is true for , therefore is not antisymmetric [Definition of antisymmetry]

Sub-part 4

Is the following statement true?

is transitive.

If it is true, prove it. Otherwise, prove the negation of the statement. It might be helpful to refer to Transitivity.

Solutions:

True.

Proof: is transitive

  1. Let , and be arbitrarily chosen.
  2. Suppose that .
  3. Since , . [Definition of cartesian product, from line 1]
  4. [Definition of ]
  5. [Implication introduction on lines 2, 2.2]
  6. [Universal generalisation on lines 1, 3]
  7. is transitive. [Definition of transitive]

Question 7 [Graded for Participation]

Is the following statement true?

Let be any set. Let .

If is symmetric, then is reflexive.

If it is, prove it. If it is not, give examples of and such that the is symmetric, but is not reflexive.

Solutions:

Solution

False.

Consider the set . Then . Let . Then .

Since , we need for to be symmetric, which is true.

However, is not reflexive, since but .


Question 8

Is the following statement true?

Let be any set. Let .

If is both reflexive and anti-symmetric, then is not symmetric.

If it is, prove it. If it is not, give examples of , and such that the is both reflexive and anti-symmetric, but is not symmetric.

Correction:

If it is, prove it. If it is not, give examples of and such that the is both reflexive and anti-symmetric, but is also symmetric.

Solutions:

Solution

False.

Consider . Then . Let .

Clearly, is reflexive, since both and are in .

Next, is also anti-symmetric. Let’s examine the elements of .

  1. For , we have , and .
  2. Similarly, for , we have , and .

Hence, is anti-symmetric.

It is easy to check that is symmetric as well.