Galileo's famous argument against the Aristotle's theory of falling bodies goes like this. "Let's say heavy objects do fall faster than light ones. Then it seems the heavier weight will fall with the lighter weight acting, as it were, a bit like a parachute. In that case, the two balls will together fall more slowly than the heavy weight would on its own. On the other hand, once the two weights are tied together and held out over the parapet, they have effectively combined their weights, becoming one greater weight... they must therefore fall even faster than the heavy weight would on its own." Contradiction. Hence weight has no effect on falling rates.
Some philosophers are very fond of this argument. Gendler uses it as a prototypical example of how "reasoning about particular entities within the context of an imaginary scenario can lead to rationally justified conclusions". Snooks goes further saying "it is striking that one leaves the falling balls example with something approaching certainty for its outcome". And Brown goes all the way and claims that Aristotle's theory is "self-contradictory", and we gain a priori knowledge here. The argument does give off that flavor of "synthetic a priori" reasoning, as in geometry but without images. But is it a proof or a fallacy? Even Gendler admits that some "obvious" premises are missing, and Atkinson even calls it a "non-sequitur" for similar reasons. But Galileo's logic is not questioned it seems. Shouldn't it be?
Let's replace weight with cross-section. If objects with smaller cross section do fall faster let's strap two together (next to each other, so that the cross-sections add up) and argue as above. Ergo, cross section can not affect the falling rate either. But objects with smaller cross section do fall faster, because of air resistance, and two objects strapped together with added cross sections will fall slower than each one separately, for the same reason. Something is wrong here, but the reasoning leading to a contradiction is essentially identical to the one above.
I don't think presence/absence of air matters, not that Galileo mentions anything about vacuum. What is most suspicious about his argument is exactly that it is so general. If it works the falling rate should not depend on any (additive) characteristic of objects whatsoever, regardless of the missing extra conditions. We could give those objects electric charges and turn on electric field of our liking, and the argument still seems to go through. But leads to a wrong conclusion that the falling rate is independent of the charges.
Question: It is assumed that Galileo's argument should work with something like "free fall in a vacuum" premise properly spelled out. But I don't see where such premise could be used, or how non-vacuum would alter the conclusion, or why Aristotle's theory is self-contradictory rather than just empirically wrong. Is the problem just in unspelled premises or is the reasoning itself logically flawed? Is there a logically correct "a priori" argument?
EDIT: I believe Quentin's answer gives the right reconstruction of what the a priori aspect of Galileo's argument amounts to. I'll rephrase it somewhat. Suppose bodies move under a single "motive cause" that determines the "fastness" of motion (this formalizes fall in a vacuum). The "cause" could be Newtonian force that determines acceleration, or something else that determines velocity as Aristotle thought, etc., as long as "the stronger the cause the faster the motion" holds. Suppose further that the cause is additive, i.e. its values add up when the bodies are strapped together. Then Galileo's argument shows that the proportionality constant ("weight" in the argument) between the cause and the rate can not also be additive (a.k.a. extensive).
The weakest link is the "additivity of cause" premise. It is true of Newtonian forces, but that part is empirical, and not in an intuitive way, unlike geometry. Quentin points out that two narrowly separated bodies falling differently than two touching ones leads to a counterintuitive discontinuity. That is true, but "touching" is not the same as "strapped together". The strapping introduces rigidity that turns two bodies into a single item, it is not a priori clear that the cause should move this item just as it would two bodies that are only touching. Aristotle would probably reject this premise, especially since to him falling is a "natural" motion rather than "forced". So his theory is not exactly self-contradictory or counterintuitive, but Galileo's argument is still valid under broader assumptions than just Newtonian physics.
EDIT 2: Found this paper that analyzes Galileo's argument in detail, and reaches the same conclusion.