Why is it possible to define a partition of integers as prime, composite and {1,-1,0} although divisibility is not an equivalence relationship?

50 Views Asked by At

It's a known theorem that if $\mathcal{R}$ is an equivalence relation defined on a set, let's say $A$, then $\mathcal R$-equivalence-classes define a partition of $A$. It is also known that the converse theorem is true too.

We define the divisibility relationship in $\mathbb{Z}$ and say that $a$ divides $b$, which is written as $ a|b $, iff $\exists k \in \mathbb{Z} : b = ak$, where $a,b \in \mathbb{Z}$ and $a\neq0$.

It is easy to prove that divisibility is not an equivalence relation in $\mathbb{Z}$. For example, $2|4$ but $4|2$ is false; this proves that | is not a equivalence relation.

Then how is it possible to define a partition based on divisibility as prime numbers, composite numbers and the subset $\{1,-1,0\}$ if divisibility is not an equivalence relation?

There are two possibilities:

  1. The relation that defines that partition is not divisibility, then, what is it?
  2. There's a hypothesis that I forgot.

Could you please help me?

2

There are 2 best solutions below

1
On

Possibility 1. is correct.

You don't need any specific operation to define equivalence class. You defined one just by telling explicitly what are it's equivalence classes. I'm also not sure how would divisibility help us define this partition even if we get forget that it's not symmetric. There are composite (whole?) numbers like 10, 12 which don't divide each other.

0
On

The relation $\mathcal R$ would be the following:

$a\,\mathcal R\,b$ if $a$ and $b$ are both in the same equivalence class (prime, composite, or neither).

That is a different relation from the relation $a\mid b$.