I recently upgraded to macOS 13 Big Sur and found homebrew wouldn’t work.
I worked out you need new XCode command line tools:
sudo rm -rf /Library/Developer/CommandLineTools
sudo xcode-select --install
brew update
brew doctor
brew upgrade
This worked a treat – now brewing on Big Sur 🥸