When working a bit on another question (If $a \equiv b\pmod m$, then $\gcd(a, m) = \gcd(b, m)$), I discovered the following, which seems to be valid: $$ a = b \;\;\equiv\;\; \langle \forall d :: d \mid a \;\equiv\; d \mid b \rangle $$ (Note that all variables denote natural numbers.)

I have not seen this concept before, and tentatively call it division extensionality: two natural numbers are the same iff they have the same divisors. I did not succeed in proving this. How should I go about that proof (or is the above just not true)? And what is the usual name for this concept?

Also, very likely there is some more general concept of extensionality, which also covers set extensionality. Any pointers?

Finally, I found that (if the above is true) also the following holds: $$ a = b \pmod m \;\;\Rightarrow\;\; \langle \forall d : d \mid m : d \mid a \;\equiv\; d \mid b \rangle $$ The structure of this looks a lot like the first one. How does this fit in? Is there a concept of division extensionality modulo $m$?



1 Answer 1


To prove this analogue of the Axiom of Extensionality for divisibility, just note that if $a$ and $b$ have the same divisors then because every number divides itself we have $a \mid b$ and $b \mid a$, which can only happen if $a=b$. I don't know if this fact has a name.

I'm not sure that there is going to be a common generalization of this notion and the Axiom of Extensionality (besides the notion of an extensional relation, which it seems like you have already discovered.) After all, set membership is only extensional because we say it is—there are alternative set theories where Extensionality is false.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .