Catalina introduced changes to the way the file system files are stored, i.e. it puts them on a separate read-only APFS volume. The pre-installed apps are also found on this partition. More details can be found in this ars technica article. In short, you need a slightly different method compared to previous versions to get at those pesky pre-installed apps.
(Information taken from this reddit thread)
Boot into recovery by holding cmd + R while the system is booting
Open up terminal (found in one of the menus at the top), and type the command
csrutil disable. This will turn off the SIP
Reboot into Catalina
In terminal run
sudo mount -uw /
You should now be able to delete the pre-installed apps. I used AppCleaner to do this. It will let you delete them, but you'll have to click remove twice.
Boot into recovery again and in the terminal type
csrutil enable to re-enable the SIP. I’m not sure if this step is necessary as some things I’ve read suggest that it is automatically re-enabled, but that’s what I did.
You should now find that the apps are gone.
Note: I have found that the apps can reappear, I suspect this might be related to updates, but I don’t know. You should always install updates, but you might have to delete these apps again after updating.