Assignment #1: Prerequisite Review: Logic, Integers, Sets, and Relations (back to full lecture notes)

In this assignment you will define Python functions that represent various constructs. For this assignment, you will submit a single Python source file a1.py.

Your file may not import any modules or employ any external library functions associated with integers and sets (unless the problem statement explicitly permits this). Solutions to each of the programming problem parts below should fit on one or two lines. You will be graded on the correctness, concision, and mathematical legibility of your code. The different problems and problem parts rely on each other; carefully consider whether you can use functions you define in one part within subsequent parts.

    1. Define a Python function divides() that takes two positive integer arguments and returns True only if the first argument divides the second argument.
    2. Define a Python function prime() that takes a single argument and returns True only if the argument is a prime positive integer. You may use the range(), len(), and divides() functions.
  1. In this problem, you will implement a small algorithm that can generate arbitrarily many prime numbers. This algorithm is very inefficient; its purpose is to serve as a programmatic argument that there are infinitely many distinct prime numbers.
    1. Implement a Python function factors that takes a single positive integer argument and returns the set of factors of that number.
    2. Implement a Python function primeFactors that takes a single positive integer argument and returns the set of prime factors of that number.
    3. Implement a Python function anotherPrime that takes a set of prime numbers and returns a new prime that is distinct from all the others in the list. To accomplish this, compute the product p of all the prime numbers in the set, then return a prime factor that belongs to the set of factors of p+1.
    4. Implement a Python function generatePrimes that takes a single input n and returns a set of n distinct prime numbers. Hint: use recursion and another function you have already implemented.
    1. Define a Python function implies() that takes two arguments and correctly implements the logical operator implies.
  2. To receive credit for each part below, your solutions must employ forall, exists, and/or list comprehensions. Solutions that are more than one or two lines in length will receive no credit.

    1. Define a Python function product(X,Y) that takes two sets as arguments and returns the set product of the sets.

    2. Define a Python function relation(R,X,Y) that takes three arguments and returns True only if the first argument R is a relation between the second and third arguments X and Y.

    3. Define a Python function function(R,X,Y) that takes three arguments and returns True only if the first argument R is a function from X to Y.

    4. Define a Python function injection(R,X,Y) that takes three arguments and returns True only if the first argument R is an injection from X to Y.

    5. Define a Python function surjection(R,X,Y) that takes three arguments and returns True only if the first argument R is a surjection from X to Y.

    6. Define a Python function bijection(R,X,Y) that takes three arguments and returns True only if the first argument R is a bijection from X to Y.

    7. Define a Python function transitive(R,X) that takes two arguments and returns True only if the first argument R is a transitive relation on X.

    8. Define a Python function lte(R) that takes one argument and returns True only if the relation R is a subset of the relation represented by the relational operator <=.