Problem Set 8 - Equivalence Relations (1).ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Chen, Jameson, and Ron\n",
    "# CS 5002, Spring 2021\n",
    "# Problem Set 8 Problem 4\n",
    "\n",
    "# This block of code takes two inputs: a relation R\n",
    "# and a positive integer n.  The output is an n by n\n",
    "# matrix M, where the M[x][y] entry (namely the entry\n",
    "# in row x and column y) is equal to 1 if x and y are\n",
    "# \"related\".  Otherwise the output is 0.\n",
    "#\n",
    "# Don't forget that in Python the rows and columns\n",
    "# are numbered from 0 to n-1, instead of from 1 to n.\n",
    "\n",
    "def BuildMatrix(R, n):\n",
    "    M = [[0 for y in range(n)] for x in range(n)]\n",
    "    for x in range(n):\n",
    "        for y in range(n):\n",
    "            M[x][y]=R(x,y)\n",
    "    return M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "# You will define eight different relations, for each\n",
    "# of the 8 = 2x2x2 possible options for R: whether R is\n",
    "# reflexive, whether R is symmetric, and whether R is\n",
    "# transitive.  I have provided 2 of the 8 relations below.\n",
    "\n",
    "# Part A\n",
    "# R1 is reflexive, symmetric, transitive\n",
    "def R1(x, y):\n",
    "    if (x - y) % 2 == 0: return 1\n",
    "    else: return 0\n",
    "    \n",
    "# R2 is reflexive, symmetric, not transitive\n",
    "def R2(x, y):\n",
    "    if abs(x - y) <= 1: return 1\n",
    "    else: return 0\n",
    "    \n",
    "# R3 is reflexive, not symmetric, transitive\n",
    "def R3(x, y):\n",
    "    if x >= y: return 1\n",
    "    else: return 0\n",
    "\n",
    "# R4 is reflexive, not symmetric, not transitive\n",
    "#def R4(x, y):\n",
    "def R4(x, y):\n",
    "    if x == y or x == y + 1: return 1\n",
    "    else: return 0\n",
    "# R5 is not reflexive, symmetric, transitive\n",
    "def R5(x, y):\n",
    "    if x * y > 0: return 1\n",
    "    else: return 0\n",
    "\n",
    "# R6 is not reflexive, symmetric, not transitive\n",
    "def R6(x, y):\n",
    "    if abs(x - y) == 1: return 1\n",
    "    else: return 0\n",
    "\n",
    "# R7 is not reflexive, not symmetric, transitive\n",
    "def R7(x, y):\n",
    "    if x > y: return 1\n",
    "    else: return 0\n",
    "\n",
    "# R8 is not reflexive, not symmetric, not transitive\n",
    "def R8(x, y):\n",
    "    if x == y - 1: return 1\n",
    "    else: return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "[[1, 0, 1, 0, 1, 0, 1, 0, 1, 0],\n",
       " [0, 1, 0, 1, 0, 1, 0, 1, 0, 1],\n",
       " [1, 0, 1, 0, 1, 0, 1, 0, 1, 0],\n",
       " [0, 1, 0, 1, 0, 1, 0, 1, 0, 1],\n",
       " [1, 0, 1, 0, 1, 0, 1, 0, 1, 0],\n",
       " [0, 1, 0, 1, 0, 1, 0, 1, 0, 1],\n",
       " [1, 0, 1, 0, 1, 0, 1, 0, 1, 0],\n",
       " [0, 1, 0, 1, 0, 1, 0, 1, 0, 1],\n",
       " [1, 0, 1, 0, 1, 0, 1, 0, 1, 0],\n",
       " [0, 1, 0, 1, 0, 1, 0, 1, 0, 1]]"
      ]
     },
     "metadata": {},
     "execution_count": 24
    }
   ],
   "source": [
    "# Here is the matrix for the relation R1 with n=10.\n",
    "# R1 is reflexive, symmetric, transitive\n",
    "M1 = BuildMatrix(R1, 10)\n",
    "M1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "[[1, 1, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       " [1, 1, 1, 0, 0, 0, 0, 0, 0, 0],\n",
       " [0, 1, 1, 1, 0, 0, 0, 0, 0, 0],\n",
       " [0, 0, 1, 1, 1, 0, 0, 0, 0, 0],\n",
       " [0, 0, 0, 1, 1, 1, 0, 0, 0, 0],\n",
       " [0, 0, 0, 0, 1, 1, 1, 0, 0, 0],\n",
       " [0, 0, 0, 0, 0, 1, 1, 1, 0, 0],\n",
       " [0, 0, 0, 0, 0, 0, 1, 1, 1, 0],\n",
       " [0, 0, 0, 0, 0, 0, 0, 1, 1, 1],\n",
       " [0, 0, 0, 0, 0, 0, 0, 0, 1, 1]]"
      ]
     },
     "metadata": {},
     "execution_count": 25
    }
   ],
   "source": [
    "# Here is the matrix for the relation R2 with n=10.\n",
    "# R2 is reflexive, symmetric, not transitive\n",
    "M2 = BuildMatrix(R2, 10)\n",
    "M2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "[[1, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       " [1, 1, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       " [1, 1, 1, 0, 0, 0, 0, 0, 0, 0],\n",
       " [1, 1, 1, 1, 0, 0, 0, 0, 0, 0],\n",
       " [1, 1, 1, 1, 1, 0, 0, 0, 0, 0],\n",
       " [1, 1, 1, 1, 1, 1, 0, 0, 0, 0],\n",
       " [1, 1, 1, 1, 1, 1, 1, 0, 0, 0],\n",
       " [1, 1, 1, 1, 1, 1, 1, 1, 0, 0],\n",
       " [1, 1, 1, 1, 1, 1, 1, 1, 1, 0],\n",
       " [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]"
      ]
     },
     "metadata": {},
     "execution_count": 26
    }
   ],
   "source": [
    "# R3 is reflexive, not symmetric, transitive\n",
    "M3 = BuildMatrix(R3, 10)\n",
    "M3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    },
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "[[1, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       " [1, 1, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       " [0, 1, 1, 0, 0, 0, 0, 0, 0, 0],\n",
       " [0, 0, 1, 1, 0, 0, 0, 0, 0, 0],\n",
       " [0, 0, 0, 1, 1, 0, 0, 0, 0, 0],\n",
       " [0, 0, 0, 0, 1, 1, 0, 0, 0, 0],\n",
       " [0, 0, 0, 0, 0, 1, 1, 0, 0, 0],\n",
       " [0, 0, 0, 0, 0, 0, 1, 1, 0, 0],\n",
       " [0, 0, 0, 0, 0, 0, 0, 1, 1, 0],\n",
       " [0, 0, 0, 0, 0, 0, 0, 0, 1, 1]]"
      ]
     },
     "metadata": {},
     "execution_count": 27
    }
   ],
   "source": [
    "# R4 is reflexive, not symmetric, not transitive\n",
    "M4 = BuildMatrix(R4, 10)\n",
    "M4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    },
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       " [0, 1, 1, 1, 1, 1, 1, 1, 1, 1],\n",
       " [0, 1, 1, 1, 1, 1, 1, 1, 1, 1],\n",
       " [0, 1, 1, 1, 1, 1, 1, 1, 1, 1],\n",
       " [0, 1, 1, 1, 1, 1, 1, 1, 1, 1],\n",
       " [0, 1, 1, 1, 1, 1, 1, 1, 1, 1],\n",
       " [0, 1, 1, 1, 1, 1, 1, 1, 1, 1],\n",
       " [0, 1, 1, 1, 1, 1, 1, 1, 1, 1],\n",
       " [0, 1, 1, 1, 1, 1, 1, 1, 1, 1],\n",
       " [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]]"
      ]
     },
     "metadata": {},
     "execution_count": 28
    }
   ],
   "source": [
    "# R5 is not reflexive, symmetric, transitive\n",
    "M5 = BuildMatrix(R5, 10)\n",
    "M5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    },
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "[[0, 1, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       " [1, 0, 1, 0, 0, 0, 0, 0, 0, 0],\n",
       " [0, 1, 0, 1, 0, 0, 0, 0, 0, 0],\n",
       " [0, 0, 1, 0, 1, 0, 0, 0, 0, 0],\n",
       " [0, 0, 0, 1, 0, 1, 0, 0, 0, 0],\n",
       " [0, 0, 0, 0, 1, 0, 1, 0, 0, 0],\n",
       " [0, 0, 0, 0, 0, 1, 0, 1, 0, 0],\n",
       " [0, 0, 0, 0, 0, 0, 1, 0, 1, 0],\n",
       " [0, 0, 0, 0, 0, 0, 0, 1, 0, 1],\n",
       " [0, 0, 0, 0, 0, 0, 0, 0, 1, 0]]"
      ]
     },
     "metadata": {},
     "execution_count": 29
    }
   ],
   "source": [
    "# R6 is not reflexive, symmetric, not transitive\n",
    "M6 = BuildMatrix(R6, 10)\n",
    "M6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    },
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       " [1, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       " [1, 1, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       " [1, 1, 1, 0, 0, 0, 0, 0, 0, 0],\n",
       " [1, 1, 1, 1, 0, 0, 0, 0, 0, 0],\n",
       " [1, 1, 1, 1, 1, 0, 0, 0, 0, 0],\n",
       " [1, 1, 1, 1, 1, 1, 0, 0, 0, 0],\n",
       " [1, 1, 1, 1, 1, 1, 1, 0, 0, 0],\n",
       " [1, 1, 1, 1, 1, 1, 1, 1, 0, 0],\n",
       " [1, 1, 1, 1, 1, 1, 1, 1, 1, 0]]"
      ]
     },
     "metadata": {},
     "execution_count": 30
    }
   ],
   "source": [
    "# R7 is not reflexive, not symmetric, transitive\n",
    "M7 = BuildMatrix(R7, 10)\n",
    "M7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    },
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "[[0, 1, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       " [0, 0, 1, 0, 0, 0, 0, 0, 0, 0],\n",
       " [0, 0, 0, 1, 0, 0, 0, 0, 0, 0],\n",
       " [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],\n",
       " [0, 0, 0, 0, 0, 1, 0, 0, 0, 0],\n",
       " [0, 0, 0, 0, 0, 0, 1, 0, 0, 0],\n",
       " [0, 0, 0, 0, 0, 0, 0, 1, 0, 0],\n",
       " [0, 0, 0, 0, 0, 0, 0, 0, 1, 0],\n",
       " [0, 0, 0, 0, 0, 0, 0, 0, 0, 1],\n",
       " [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]"
      ]
     },
     "metadata": {},
     "execution_count": 31
    }
   ],
   "source": [
    "# R8 is not reflexive, not symmetric, not transitive\n",
    "M8 = BuildMatrix(R8, 10)\n",
    "M8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create three methods that determine whether your relation R is\n",
    "# reflexive, symmetric, and transitive.  If R is an equivalence\n",
    "# relation (i.e., it is reflexive, symmetric, and transitive),\n",
    "# then output the total number of equivalence classes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Part B\n",
    "# This is the function to test an x, y relation matrix for reflexivity:\n",
    "def reflexive(M):\n",
    "    reflexive = True  # Assume the function is reflexive\n",
    "    for x in range(len(M)):\n",
    "        if M[x][x] != 1:  # Test to see if x R x is true\n",
    "            reflexive = False  # If not, return False\n",
    "    return reflexive\n",
    "# This function works because it tests the relation matrix to ensure x relates to x,\n",
    "# which is the defenition of reflexivity.\n",
    "\n",
    "# This is the function to test an x, y relation matrix for symmetry:\n",
    "def symmetric(M):\n",
    "    symmetric = True  # Assume the function is symmetric\n",
    "    for x in range(len(M)):\n",
    "        for y in range(x, len(M)):  # Only runs for 1/2 the matrix to not double-test transposed values\n",
    "            if M[x][y] != M[y][x]:  # Checks if x R y implies y R x\n",
    "                symmetric = False  # If not, return False\n",
    "    return symmetric\n",
    "# This function works because it tests the relation matrix to ensure x R y is True and y R x is true,\n",
    "# which is the defenition of symmetry."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "# This is the function to test an x, y relation matrix for transitivity:\n",
    "def transitive(M, R):  # Requires the relation function in addition to the matrix\n",
    "    transitive = True\n",
    "    for x in range(len(M)):\n",
    "        for y in range(len(M)):\n",
    "            for z in range(len(M)):  # Tests additional value z\n",
    "                if R(x, y) == 1 and R(y, z) == 1 and R(x, z) != 1:  # Returns false if x R y, y R z doesn't imply x R z\n",
    "                    transitive = False\n",
    "    return transitive\n",
    "# This function works because it tests the relation to ensure that if x R y and y R z are true, x R z is also true,\n",
    "# which is the defenition of transitivity."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Part C\n",
    "def equivalence_classes(M, R):\n",
    "    if reflexive(M) and symmetric(M) and transitive(M, R):  # Tests to make sure the relation is an equivalence\n",
    "        ones = 0  # Counts the number of times a given x relates to a y\n",
    "        total = len(M) ** 2  # Total number of individual relations in matrix\n",
    "        for row in M:\n",
    "            for i in row:\n",
    "                if i == 1:\n",
    "                    ones += 1  # Counts 1s\n",
    "        if total % ones == 0:\n",
    "            classes = total // ones\n",
    "        # This conditional statement finds the average number of times an x in X relates to a y in Y. For example, with\n",
    "        # relation R1, a given x relates to half the given y (odds and evens), so there are 2 equivalence classes.\n",
    "        # Likewise, with a relation like x % 3 == y % 3, a given x will relate to 1/3 given y, etc.\n",
    "        else:\n",
    "            classes = total // ones + 1\n",
    "        # This conditional statement is a buffer in case there are relatively many equivalence classes for a small matrix.\n",
    "        # For example, the relation x % 7 == y % 7 will return a floating point average between 6 and 7 for a matrix size\n",
    "        # of 10x10, even though there are 7 equivalence classes. For this reason, it is best to always use a very large n.\n",
    "    else:\n",
    "        classes = False  # Returns False if the relation is not an equivalence\n",
    "    return classes\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "This relation is reflexive\nThis relation is symmetric\nThis relation is transitive\nThis relation is an equivalence relation and has 2 equivalence classes\n"
     ]
    }
   ],
   "source": [
    "# Now, we can write a driver function to test a relation and its matrix:\n",
    "# For R1:\n",
    "def main():\n",
    "    relation = R1\n",
    "    matrix = BuildMatrix(R1, 10)\n",
    "    if reflexive(matrix):\n",
    "        print('This relation is reflexive')\n",
    "    else:\n",
    "        print('This relation is not reflexive')\n",
    "    if symmetric(matrix):\n",
    "        print('This relation is symmetric')\n",
    "    else:\n",
    "        print('This relation is not symmetric')\n",
    "    if transitive(matrix, relation):\n",
    "        print('This relation is transitive')\n",
    "    else:\n",
    "        print('This relation is not transitive')\n",
    "    equivalence = equivalence_classes(matrix, relation)\n",
    "    if equivalence == False:\n",
    "        print('This relation is not an equivalence relation')\n",
    "    else:\n",
    "        print('This relation is an equivalence relation and has',\n",
    "            equivalence, 'equivalence classes')\n",
    "    \n",
    "main()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.1-final"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}