[madamepsychosis]

My intuition – proof by contradiction means we have to use one step that inverts the set of values for which the statement is true – so whether we need a contradiction step depends on the cardinality of this truth set. Perhaps it depends on the relationship between the ‘truth set’ of our premises and our conclusions (e.g. the square root of 2 is one number, but all of the rationals is infinite) Supporting this intuition, getting rid of proof by contradiction leaves us unable to construct uncountable sets. Maybe some proofs need several contradiction steps (i.e., when their truth set cardinality is aleph-2,3, etc.)

[mattxxx]

Yea, but, I mean, the isn't the diagonal argument just an extension of proof-by-contradiction into countable sets?

The same way that induction is the extension of syllogism into countable sets?