Ubuntu 16.04 Completely broken python3 + dpkg + apt-get!

We generally recommend against changing your installed version of Python3 for precisely this reason.

When folks want to use multiple versions or newer versions of Python, we recommend isolation methods (like VMs, containers, python(3)-virtualenv, or chroots) to prevent damage to your system. There are other methods not in the Ubuntu repositories -- we don't provide support for those.

It's likely possible to fix your system, but may not be worthwhile. Many dependencies may be missing. dpkg does NOT depend upon Python3, but apt definitely does. The basic strategy is to use dpkg to reinstall the missing packages you need for apt.

Visit http://packages.ubuntu.com, and download the python-minimal and python3-minimal and apt packages, then install those packages using dpkg. It may take a few iterations, as dpkg complains about other missing dependencies that you must download and install in the correct order.

Generally, most users who have broken or missing Python find it faster and easier to simply backup their data and do a clean-install.