Some of our users here admit to having some difficulties reading or writing more formal and technical mathematical writings and proofs. Here are two practice problems for translating back and forth between intuition and formality.

Part of the challenge is researching and understanding the terms used, so I won't answer any questions asked about that.


Consider the following theorem:

Let \(\phi\) be a computable surjective function \(\mathbb{N} \mapsto \mathbf{P}^{(1)}\), where \(\mathbf{P}^{(1)}\) is the set of all unary partial computable functions. Given a set \(A \subseteq \mathbf{P}^{(1)}\), let \(D_A\) be the decision problem of determining whether \(\phi(k) \in A\) given a natural number \(k\). \(D_A\) is decidable iff \(A = \emptyset\) or \(A = \mathbf{P}^{(1)}\).

Explain what this means in plain English. (Bonus problem: find the name of the theorem. Don't try this until after you've done the former.)

corrections thanks to LittlePeng9


State Lagrange's theorem in formal logic (no English!). Your definition has to define groups and subgroups from scratch.

I've left this problem ambiguous on purpose. Good answers should use standard notational conventions in accurate and readable ways.