IDA - Department of Computer and Information Science

Assignments (2023)

• Chapter 1:

  Problem 1. Let A be the set of (straight) lines on a plane. Consider a relation R such that xRy when lines x and y both contain the point (0,0). Explain why R is not an equivalence relation.

  Problem 2. Consider binary relations defined over a set A. Define the following relation over binary relations R1 and R2: R1 =< R2 if there exists R such that R1 ∘ R = R2 where ∘ denotes composition of binary relations (see lecture notes). Verify whether =< is reflexive, irreflexive, symmetric, anti-symmetric, and transitive. Based on this, is it a pre-order, a (strict) partial order, or a (strict) total order?

  Problems 1.7, 1.8 from the lecture notes

  Deadline: 22/11.

• Chapter 2:

  Problem 1: Consider the poset of the first diagram of problem 2.1 from the lecture notes. Show that it is a lattice. Show that the lattice is not distributive. (Begin with naming the poset's elements.)

  Problem 2: Problem 2.2 from the lecture notes. It is sufficient to consider it for the case of A of 6 elements, or the case of A being infinite.

  Problem 3: Recall that the smallest clone (let us call it Min) on the Boolean domain only contains projection functions, i.e., functions returning a fixed argument. Hence, this is the minimal element in the lattice of sets of Boolean functions induced by using functional composition as closure operator. Say that a clone [F] is subminimal if (1) Min ⊂ [F] and (2) there is no [G] such that Min ⊂ [G] ⊂ [F], i.e., [F] covers Min. Describe (1) all Boolean subminimal clones generated by a single unary function f (i.e., it takes only one argument), and (2) give an example of a subminimal clone generated by a binary function which is distinct from the clones in task (1). An informal argument is sufficient.

  Deadline: 08/12.

• Chapter 3

  Problem 1: Prove that 2 * ω does not equal ω * 2.

  Problem 2: Determine whether each of the sentences below is true or false. If false - provide a counterexample. If true - explain why.

  * If X and Y are uncountable then |X| + |Y| is uncountable.

  * The intersection of any two uncountable sets is uncountable.

  Problem 3: We know that if X,Y are ordinals and X < Y then X is a subset of Y (and also is a member of Y). Is every subset of Y an ordinal?

Deadline: 08/12.
• Chapter 4

  PDF file here.

  Deadline: 20/12.
• Chapter 5

  PDF file here.

  Deadline: 20/12.

Rules of the game: You are supposed to try to solve all of the above exercises and provide correct solutions to most of them to pass the course. It is permitted to discuss the exercises with others, but you must solve each exercise individually. It is absolutely not allowed to copy or rephrase each others solutions, or to solve the exercises jointly .

Solutions handed in after the deadline will be dealt with a low priority, thus graded possibly rather late.