Skip to content
Tutorials Center
My learning

Topics

Lesson 37 of 37 ยท Projects and Practice

Practice: Sets, Relations and Logic Problems

Work through graded practice problems on sets, relations, functions, cardinality, orders and formal logic, each with a worked answer and a Python check.

You learn logic by doing it. This lesson collects problems from every chapter you have just finished, from warm-ups to challenges. For each, try on paper first, then run the Python check. A solution you derived and then confirmed by brute force is worth more than one you only read. Every check below also shows a habit worth keeping: test small cases before you trust a general claim.

Part 1: sets

Problem 1. In a class of 60 students, 35 study French, 28 study German and 12 study both. How many study neither?

By inclusion-exclusion, |F โˆช G| = 35 + 28 โˆ’ 12 = 51, so 9 study neither. See sets and operations.

Problem 2. Prove or refute: A \ (B โˆช C) = (A \ B) โˆฉ (A \ C). Then test A \ (B โˆฉ C) = (A \ B) โˆฉ (A \ C).

The first is De Morgan in disguise and holds; the second is false (it should be a union).

Python Check problems 1 and 2

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Part 2: relations and functions

Problem 3. How many relations on a 4-element set are reflexive? Symmetric? Reflexive and symmetric?

A relation is a subset of 16 pairs. Reflexive fixes the 4 diagonal pairs and leaves 12 free: 2ยนยฒ = 4096. Symmetric needs a choice for each of the 4 diagonal pairs and each of the 6 unordered off-diagonal pairs: 2ยนโฐ = 1024. Both: only the 6 unordered pairs are free: 2โถ = 64.

Problem 4. How many surjections are there from a 4-element set onto a 3-element set?

Use 3! ยท S(4, 3) = 6 ยท 6 = 36 where S is the Stirling number of the second kind (see equivalence relations). Or inclusion-exclusion: 3โด โˆ’ 3ยท2โด + 3ยท1โด = 81 โˆ’ 48 + 3 = 36.

Python Check problems 3 and 4 by enumeration

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Problem 5. Let f: โ„ค โ†’ โ„ค, f(n) = 2n. Is f injective? Surjective? And g: โ„ค โ†’ โ„ค, g(n) = n + 7?

f is injective but not surjective (odd numbers are missed). g is a bijection, with inverse n โˆ’ 7. Compare with the function classification lesson.

Part 3: cardinality and orders

Problem 6. Show the set of all finite subsets of โ„• is countable.

Map a finite subset S to the number ฮฃ 2หข for s โˆˆ S (its binary representation). This is an injection into โ„•, and every natural number arises, so it is a bijection. See countable sets.

Problem 7. How many linear extensions does the divisibility poset on {1, 2, 3, 4, 6, 12} have?

The element 1 comes first and 12 last. The middle elements 2, 3, 4, 6 must satisfy 2 < 4, 2 < 6 and 3 < 6. There are 5 such orderings; the code below confirms it.

Python Check problems 6 and 7

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Part 4: logic and proof

Problem 8. Is ((p โ†’ q) โ†’ p) โ†’ p a tautology? (This is Peirce's law, valid classically but not provable in intuitionistic logic.)

Test the one falsifying case: for the whole formula to be false, (p โ†’ q) โ†’ p must be true and p false; but p false makes p โ†’ q true, so (p โ†’ q) โ†’ p is false. No countermodel, so it is a tautology.

Problem 9. Write the negation of โˆ€x โˆƒy (y > x โˆง y is prime) and decide whether the original is true over โ„•.

Negation: โˆƒx โˆ€y (y > x โ†’ y is not prime). The original says there are infinitely many primes, which is true (Euclid). The negation says there is a largest prime, which is false.

Problem 10. Use resolution to show {p โ†’ q, q โ†’ r, p} โŠจ r.

Clauses: {ยฌp, q}, {ยฌq, r}, , and the negated goal {ยฌr}. Resolve with {ยฌp, q} to get ; with {ยฌq, r} get ; with {ยฌr} get {}.

Python Check problems 8 to 10

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Part 5: challenges

  1. Show that every nonempty set has as many subsets of even size as of odd size. (Hint: pair S with S ฮ” {a} for a fixed element a, as a bijection.)
  2. Prove that if A ร— B is countable and B is nonempty, then A is countable.
  3. Write a program that, given a finite relation, outputs its reflexive-symmetric-transitive closure (the smallest equivalence relation containing it) and the number of classes. Compare with union-find.
  4. Show that a lattice in which every element has a complement and the distributive law holds is a Boolean algebra, and give three examples.
  5. Construct, using diagonalization, a function โ„• โ†’ โ„• that grows faster than every function in a given list fโ‚€, fโ‚, fโ‚‚, โ€ฆ. (Hint: g(n) = max(fโ‚€(n), โ€ฆ, fโ‚™(n)) + 1.)
Python Challenge 1 and challenge 5, checked on small cases

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

When stuck on a proof, test the statement on the smallest nontrivial case with code, then look at what the small cases have in common. Patterns found this way often become the induction hypothesis or the bijection you need.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In a group of 40 people, 25 like tea, 20 like coffee and 8 like both. How many like neither?

    |T โˆช C| = 25 + 20 โˆ’ 8 = 37, so 40 โˆ’ 37 = 3 like neither.
  2. 2. How many functions map a 2-element set onto a 2-element set bijectively?

    There are 2! = 2 bijections between two-element sets.
  3. 3. Which is a tautology?

    Peirce's law is true in every valuation. The others fail for some assignment.
  4. 4. The set of finite subsets of โ„• is

    Encoding a finite subset by its binary number gives a bijection with โ„•.
  5. 5. The best first step when a general claim looks plausible but unproven is to

    Small cases quickly reveal counterexamples or the pattern behind a proof.

Summary

  • Inclusion-exclusion, De Morgan and bijections solve most counting and set problems.
  • Counting relations and functions reduces to counting free choices; check small cases by brute force.
  • Countability proofs build explicit encodings; diagonalization builds objects that escape a list.
  • Resolution, truth tables and countermodel search are interchangeable tools for small logical questions.

Next: back to the Mathematical Logic and Set Theory track page