Is it possible to have perfectly secure public-key cryptography with oracles? It is a basic theorem of cryptography that it is impossible to have a perfectly secure public-key encryption scheme.  That’s because the adversary can search through all possible private keys.
But I’m wondering if it can be made possible using oracles.  My question is, do there exist sets of natural numbers $A$ and $B$ such that if Alice has access to an oracle for $A$ and Bob has access to an oracle for $B$, then these oracles can be used as private keys for a perfectly secure public-key encryption scheme?
I’m thinking that perfect security may be possible in this setting since there are uncountably many sets for the adversary to search through.
What you're saying is unclear... If you have uncountably many possible keys, if the scheme is computationally secure in the normal case (you're using an already-secure algorithm), your algorithm would fit your definition of being perfectly secure - the computation required to break it goes up with the key size, effectively creating an infinite search time for the key. The issue is, this basically equates to having a key of infinite size which is just as impossible to use for encryption, since the time to encrypt increases as well - just not as fast as the time to break it.
However, if we assume your oracles $A$ and $B$ operate in a finite amount of time (somehow you manage to encrypt using an infinitely large key) you would have a perfectly secure scheme, as you describe.