search

metamath / set.mm

Metamath source file for logic and set theory
Other
254 stars 88 forks source link

Prove that equality of natural numbers is decidable #666

Closed jkingdon closed 4 years ago

jkingdon commented 5 years ago

This is in iset.mm.

The proof would be by induction (much like http://us2.metamath.org/ileuni/nn0suc.html ). It would be stated something like ( A e. om /\ B e. Om ) -> ( A = B \/ -. A = B ) (or the equivalent using DECID).

I have removed the good first issue label (although the trickiness is more in the math than in how the formalization works). Proving A e. om -> ( A = (/) \/ -. A = (/) by induction is easy (see nndc in #728 ), but going from there to A e. om -> ( A = B \/ -. A = B would seem to have different cases. From (/) up to before A we'd would hit the -. A = B half, and then one which hits the A = B half, and then -. A = B again. When stated like that, it sounds like the kind of case elimination which doesn't work in intuitionistic logic. There should be a way to fix this, although it might involve < or + or some other trick which requires some preliminary development.

jkingdon commented 4 years ago

This has been done for a while - http://us.metamath.org/ileuni/nndceq.html