How do you prove that a certain logical fallacy is a fallacy indeed? Are there "fallacies" about which there is a controversy if it is a fallacy or not? And if in the future, a new fallacy will be discovered, what will be the outline of the proof that one will have to use to prove that it exists? (Just an application of the first question.)
Nicholas Smith provides an answer that I think is dubious:
From the point of view of deductive logic, your question is very easily answered: a fallacy is an argument form in which the premises may all be true, but the conclusion false. To prove this, one provides what is called a "counterexample," which is simply a substitution instance that has the above characteristics.
We need to distinguish between two kinds of deductive systems. In a monotonic system, which is deductive in the strict sense, something like this answer is at least plausible, but in a nonmonotonic system it certainly would not. I suspect that Smith would classify nonmonotonic systems under 'inductive logic'; this would not be unheard of, although it is misleading given that nonmonotonic systems generally have nothing to do with induction, or at least no more to do with it than monotonic systems do.
But more than this, even with a monotonic system, the plausible answer is not right if we are not merely operating within the system but applying it to actual arguments. For to apply formal systems to actual arguments we must allow for implicit premises and enthymemes, and once this is recognized there turns out to be no good way to answer the first question. In particular cases you can show that there is no way to salvage an argument with implicit premises that would not be either unreasonable or provably wrong. But Smith's argument conflates 'invalid argument form' with 'fallacy' and this is untenable as a practical matter. Even a formal fallacy as straightforward as the one Smith gives (affirming the consequent) can be salvaged in particular applications with implicit premises, e.g., premises that combined with the other premises make the relation between p and q to be one of mutual implication (equivalence). Counterexamples are not generally useful for analyzing enthymemes; and nobody commits a fallacy simply by not stating all of the premises and assumptions of the argument. At least, if we identified fallacies with formally invalid argument forms, we make the label 'fallacy' completely useless in practice. What counts as invalid is relative to the formal system we use; whenever we apply formal systems to actual arguments we have to allow ourselves so much room for the implicit and assumed that merely identifying the explicit form as invalid tells us virtually nothing about whether it is a good argument or not. (As I always tell my students, it is very, very useful to know that an argument is valid. It is at best only somewhat useful to know that it is invalid.) We can prove that particular arguments are fallacies; there appear, however, to be no generally applicable methods for doing this, because an invalid argument form that is fallacious in one context may not be in another because the second context is, so to speak, 'rigged' so that the invalid argument form, despite not being generally truth-preserving, is so in contexts like that one.
A straightforward example of this is found with fallacies of composition. An argument form like this is both formally invalid as it stands (the explicit premise does not require the conclusion) and admits of many, many counterexamples:
Each part of the wall is red; therefore the wall is red.
But we all know that under particular conditions this type of inference is not only good but certain. But pinning down these conditions is always extraordinarily tricky; what you are really trying to do is to prove something by division of possibilities, and as Aristotle pointed out long ago, even when arguments by division are certainly right they are not rigorously demonstrative.
My own view is that in the strictest sense you can't have a fallacy without an application -- that is, no argument form is fallacious as such. Rather, there are only fallacious and non-fallacious applications of argument forms. There are, of course, argument forms that are especially subject to abuse because they are not usually reliable but look superficially like argument forms that are -- the fallacy of affirming the consequent is a good example -- and we can, by a sort of metonymy, call these fallacies because their non-fallacious applications are rare enough that we can usually neglect them. But this is a metonymy; and a 'fallacy' in this sense may admit of rare cases in which an argument of exactly that form would be a perfectly good argument, and thus by definition not a fallacy at all.
Moreover, one has only to look at disputes raised by paraconsistent logical systems to see that there are problems with the counterexample approach even if the above points are set aside. Disjunctive syllogism, for instance, is valid in some formal systems and invalid in others; what counts as a counterexample to it in one system will not count as one in another. We are left with the question of whether disjunctive syllogism is really best modeled as strictly valid, or as valid only under limited conditions, like the inferences from composition; and the method of counterexamples is necessarily useless for this question.
Thus I would suggest the proper answers to the questions are, in order:
Except in a formal system there is no general method to prove that a logical fallacy is a fallacy indeed.
There are indeed argument forms whose status as fallacious is open to dispute; indeed, even disjunctive syllogism and modus ponens, which are standard inference forms, have been questioned in ways that would imply that at least some of their applications are fallacious.
It may genuinely be possible to prove that the new fallacy really is a fallacy, but without a general method for doing so, it is impossible to forecast how one would do it.