12:36 AM
@Zanna I've clicked "load older messages" several time to go back past that point, and looked at messages that way, in case there was something wrong with or confusing about the chat transcript... and I still haven't found it. Yet I remember your having replied to it. Strange...
@EliahKagan I think the aside--that is, that message and the one (non-deleted) message that precedes it--is either (a) extremely clear yet obvious to the point of not needing to be said, or (b) entirely inscrutable. I'll clarify/restate what I was saying in those messages, or not, depending on your feedback.
16 hours later…
4:26 PM
6 hours later…
10:48 PM
@EliahKagan We have reached, if you will pardon this pun, the moment of truth. The practical importance and conceptual value of the common truth-functional sentential connectives--"$\neg$", "$\wedge$", "$\vee$", "$\rightarrow$", and "$\leftrightarrow$"--can now be shown. (I alluded to this in that message.)
Consider again deductive arguments in which we start with some premises, $S_1, S_2, \ldots, S_n$, and infer some conclusion, $T$: $$S_1$$ $$S_2$$ $$\vdots$$ $$S_n$$ $$\therefore T$$ Specifically, consider the properties of deductive arguments that are valid.
Sometimes, we reason from premises we know to be true. Assuming our deduction is valid, if our premises are all true, our conclusion is true. If we already know that all of $S_1, S_2, \ldots, S_n$ hold, then what we learn by deriving $T$ as a valid inference from $S_1, S_2, \ldots, S_n$ is: $$T$$ Reasoning in this manner is known as direct proof.
However, we may reason from premises we don't know to be true. (Also, real life, including actual use of formal logic, is murkier than this. We may be convinced initially that our premises are true, but then wish to revise our beliefs in the face of new evidence or the insight that we made a mistake.) If we don't already know our premises to be true, but derive some conclusion as a valid inference from them, we still know that if our premises are all true, our conclusion is true.
That is, what we learn by deriving $T$ as a valid inference from $S_1, S_2, \ldots, S_n$ is the weaker sentence $$(S_1 \wedge S_2 \wedge \ldots \wedge S_n) \rightarrow T$$ which you'll recognize as the argument's corresponding conditional.
When we wish to prove some particular conditional $p \rightarrow q$, we often prove it in that way: by supposing that its antecedent, $p$, is true, and then based on that supposition, proving its consequent, $q$. Reasoning in this manner is known as conditional proof.
Sometimes when we have a valid argument, we don't know that all its premises are true, but we can still learn something more specific than the truth of the argument's corresponding conditional. This happens when, rather than knowing the premises are true, we know the conclusion is false.
After all, given a valid argument, if our premises are all true, our conclusion is true. So if, from $S_1, S_2, \ldots, S_n$, we conclude $T$ which we know to be false, then we know not all our premises are true.
One way to put this is that we know: $$\neg (S_1 \wedge S_2 \wedge \ldots \wedge S_n)$$ Another way to put it is that at least one of our premises is false, thus: $$\neg S_1 \vee \neg S_2 \vee \ldots \vee \neg S_n$$ Note the relationship between these equivalent ways of expressing the same information about our premises: either can be converted to the other by an application of one of De Morgan's laws for propositional logic.
One way to disprove something is to show that, if it is true, then something known to be false is true. So long as a conclusion is derived by valid inference and really is false, at least one of the premises used to derive it is false. If only one premise is in doubt (and the absence of doubt about the others is correct), one has disproved that premise.
Another way to put this, since $\neg \neg p$ is equivalent to $p$, is that one way to prove something is to show that, if it is false, then something known to be false is true. The best-case scenario for such an argument is if the conclusion is actually inconsistent (recall that a sentence or schema is inconsistent when its negation is valid).
If the conclusion is merely something you happen to know is false, though, then just introduce its negation as a premise. Then you can derive the conjunction of it and its negation--a sentence of the form $p \wedge \neg p$. That's a contradiction, which is inconsistent. Reasoning in this manner is known variously as indirect proof, proof by contradiction, and reductio ad absurdum (which, when talking about formal logic, is often called reductio for short).
You probably recall that I have used this form of proof here, when proving that $2$ has no rational square root.
Corresponding conditionals reveal the connection between some valid forms of argument on the one hand, and rules of inference involving conditionals (i.e., rules for "$\rightarrow$") on the other. Notice how direct proof is closely related to modus ponens, the rule of inference that, from $p \rightarrow q$ and $p$, one may infer $q$. Notice also how indirect proof is closely related to modus tollens, the rule of inference that, from $p \rightarrow q$ and $\neg q$, one may infer $\neg p$.
Expressing $p \rightarrow q$ in terms of negation and disjunction, and in terms of negation and conjunction, illuminates the relationship between a deductive argument's corresponding conditional and what can be known from and about the argument.
That $p \rightarrow q$ is equivalent to $\neg p \vee q$ is related to how every valid argument has either a false premise or a true conclusion.
That $p \rightarrow q$ is equivalent to $\neg (p \wedge \neg q)$ is related to how an argument with all true premises but a false conclusion is invalid. Neither these equivalences, nor the property that arguments have corresponding conditionals and that an argument is valid iff its corresponding conditional is valid, would hold if we defined "$\rightarrow$" (i.e., the conditional) in any other way.
Given a statement $p$, we can affirm it by asserting simply $p$. Denying it is only slightly more complicated: we assert $\neg p$. Having the unary connective "$\neg$" facilitates efficient and elegant denial. In describing the properties of valid deductive arguments, I made extensive use of affirmation and denial. I believe this demonstrates the central importance of negation.
The importance of the conditional can be observed in how, even to state the, um, conditions under which various truth-functional compounds (and more generally, sentences of various forms) are true and those under which they are false, one says things like, "If... then..."
In a metalogical theory--a theory used to study logic itself in a formal way--most or perhaps all of these ordinary-language conditionals can be formalized as actual $p \rightarrow q$ conditionals, as quantified conditionals, or as conditionals appearing in some more complex structure that is itself often a conditional.
(In a sentence like, "Given any argument, if it is valid then it has some false premise or has a true conclusion," the phrase "Given any argument" formalizes to "For all $x$, if $x$ is an argument...")
So it may seem unnecessary to argue for the importance of the conditional. Yet to many people it is the least intuitive of all the commonly used truth-functional sentential connectives, and it does not capture all ordinary-language uses of "If... then..."
That's why the conditional that appears in formal (deductive) logic is sometimes called the material conditional, to distinguish it from other conditionals, such as counterfactual conditionals like "If it were a bird, I would fly," which in English and some other languages are often expressed using the subjective mood. Both for that reason, and because the topic is quite illuminating, I think it's worth substantiating the value of "$\rightarrow$" rather than presuming it.
Every argument (but... see below) has a corresponding conditional. As shown above, that conditional is important. One way to read $p \rightarrow q$ is, "$q$ is as surely true as $p$." Reading "$\rightarrow$" as an expression of relative confidence jives with how, equipped with the knowledge that the conditional $p \rightarrow q$ holds for particular sentences $p$ and $q$, the truth of an antecedent (here, $p$) allows one to infer the truth of the consequent (here, $q$).
This holds for any true conditional, whether or not it is valid, but when the conditional is valid--that is, when its antecedent logically implies its consequent--we know that $q$ is as surely true as $p$ by virtue of the logical makeup of $p$ and $q$. (By this I of course mean the logical makeup of the sentences or schemata that $p$ and $q$ happen to stand for. After all, simply as a schema with two sentence letters, $p \rightarrow q$ is not valid.)
That is, no external information, besides the meaning of logical words and phrases (or, with sentences in a formal language: one's logical symbols), is needed to be convinced that this is so. Then, when the truth of $p$ is supplied, the truth of $q$ is guaranteed, to whatever degree of certainty that $p$ is true.
The importance of the biconditional, "$\leftrightarrow$", which holds between sentences just when they have the same truth value, can be seen through its relationship to logical equivalence and, specifically (as detailed above), how sentences that are logically equivalent can be interchanged without affecting which inferences that involve them are valid.
Besides its many other uses, conjunction, "$\wedge$", is important because we use it combine premises of an argument in a manner that does not affect the validity of the argument, and specifically because we use it to combine all of an argument's premises into the conjunction that serves as the antecedent in the argument's corresponding conditional.
And besides its many other uses, disjunction, "$\vee$", is important because of its relationship to conjunction, which makes it so that a valid argument with a false conclusion has some false premise, thus the disjunction of the negations of the premises is guaranteed in that situation. (That also sheds some more light on the conceptual centrality of negation.)
Furthermore, if an argument is valid, either at least one of its premises is true or its conclusion is false. This can be expressed as a disjunction in which the conclusion appears as a disjunct.
For "\neg", "$\wedge$", and "$\vee$", their relationships to formal deductive argument, as I just talked about, is one major way they are important. But another, which might be considered even more fundamental, becomes clear when one considers the meaning of truth-functional schemata in alternational normal form (a.k.a. disjunctive normal form) and conjunctional normal form (a.k.a. conjunctive normal form).
Since your chief interest is in set theory, and since this wall of text is giant (and I'm, uh, not done yet...), I think I'll hold off on that particular topic for now. This is moderately longer than I intended, and while there's value to me personally in writing it, I also don't want to continue too long without your input, as I can't be sure how much sense this is all making or how interested in it you remain.
However, those normal forms could later be examined in a way that illuminates their relationships to Venn diagrams, Boolean algebra, the intersection and union of sets, the connections between conjunction and multiplication and between disjunction and addition, and identity elements. (Also, I do not say that to dissuade you from looking into them now. I've dropped the names of those two normal forms in case you want to look them up; feel free also to ask me about them if you wish.)
Though it was not the main reason I've gone into all this, I did say it would illuminate the meaning of the empty conjunction and the empty disjunction. (Note: I say "the" instead of "a" as there's only one of each, since there is only one empty list, and thus only one empty list of sentences.) You may have been wondering what this was going to have to do with them. Or perhaps you have already guessed.
An argument consists of a collection of premises and a conclusion. Sometimes we have only one premise. Sometimes we have more than one. When we do, we can replace them by their conjunction if we wish, and get a single premise.
Sometimes that is useful--it is especially useful if we wish to write the argument's corresponding conditional, whose antecedent is that conjunction--but replacing a single premise that is a conjunction with multiple premises can also be useful, as during the course of deduction we may wish to use some or all of the conjuncts separately.
So far I have only treated arguments that have at least one premise. But the premises represent what we wish to assume, beyond the meaning of our logical words and phrases, in order to prove our conclusion. We may wish to assume no such thing. Our collection of premises may be empty.
For example, take $p$ to mean "Smith is away," and consider this argument, which has zero premises: $$\therefore p$$ Although that is an argument, it is an invalid argument. It is an error to conclude, based on that argument, that Smith is away. The problem is that, with no premises, we do not have sufficiently strong premises to show that Smith is away! We might consider adding premises.
But we can also make it into a valid argument by suitably weakening its conclusion: $$\therefore p \vee \neg p$$
An argument with no premises and a valid conclusion may seem silly--the conclusion is valid, so why do we have to infer it at all? But this is what one is doing when, in the course of a proof, one introduces a valid sentence based on its validity, without using any previously established facts or citing any premises or prior steps of the proof. A sentence that is itself valid can be inferred from any collection of premises, including an empty collection of premises.
But what is that argument's corresponding conditional? A corresponding conditional, after all, is a conditional whose antecedent is a conjunction of all the argument's premises and whose consequent is the argument's conclusion. Arguments with no premises are permitted, and some of them are even valid, but we cannot define their corresponding conditionals--or at least we cannot define them in the same way as for other arguments--unless we recognize the empty conjunction.
We can regard an argument with no premises as having no corresponding conditional, or we can define the corresponding conditional as $\top \rightarrow q$, where $q$ is the conclusion of the argument and $\top$ stands for "true." If pressed on what sentence "$\top$" is meant to signify, we can pick any true sentence whose truth is undisputed.
(For example, in place of "$\top$", we could write any valid sentence, such as "Jones is ill iff Jones is ill." If our argument with no premises is a valid argument, then its conclusion is itself a valid sentence--after all, we didn't need to know anything to validly infer it--but the valid sentence we put for the antecedent $\top$ need not resemble or relate semantically to our conclusion.)
In practice, even if we do recognize the empty conjunction, $\top \rightarrow q$ is how we'd express such a conditional.
As for the empty disjunction, this arises by considering the negation of the empty conjunction and applying one of De Morgan's laws, the one that says $\neg (S_1 \wedge S_2 \wedge \ldots \wedge S_n)$ is equivalent to $\neg S_1 \vee \neg S_2 \vee \ldots \vee \neg S_n$ (in this case, $n = 0$).
This may seem artificial and tortured, until one considers that this is how we answer the question, given a valid argument, of what it would take for the conclusion to be false. It requires at least one premise to be false. In an valid argument with no premises, we don't have any premises, so this cannot happen, which accords with how the empty disjunction is false.
You had already seen that if we wish to define the empty conjunction, we must have it come out true, since a conjunction of $n$ conjuncts is true iff all $n$ of them are true, and every property holds vacuously for all of $0$ items. And you had likewise seen that, if we wish to define the empty disjunction, we must have it come out false, since a disjunction of $n$ disjuncts is true iff at least $1$ of them is true, which cannot happen with only $0$ disjuncts, since $0 < 1$.
But I had not given a strong motivation for why we might actually wish to define the empty conjunction and the empty disjunction. Although they are often not formally defined--because we formally regard conjunction and disjunction as the binary sentential connectives "$\wedge$" and "$\vee$ respectively"--I hope I have shown how they are conceptually meaningful and (I hope) illuminating.
Another case where it would be nice to have the empty disjunction is when writing a definite description for $\{x_1, x_2, \ldots, x_n\}$. More precisely, that's a form of set notation, and I'm talking about writing the form each corresponding definite description takes. (That is, I'm talking about how one can define that notation as an alternate syntax for particular definite descriptions, as I alluded to a while ago.)
When $n > 0$, this works: $$\{x_1, x_2, \ldots, x_n\} := ɿS\, \forall y\, [y \in S \leftrightarrow (y = x_1 \vee y = x_2 \vee \ldots \vee y = x_n)]$$ For example, when $n = 3$: $$\{x_1, x_2, x_3\} = ɿS\, \forall y\, [y \in S \leftrightarrow (y = x_1 \vee y = x_2 \vee y = x_3)]$$ And when $n = 1$: $$\{x_1\} = ɿS\, \forall y\, (y \in S \leftrightarrow y = x_1)$$
Such cases, with $n > 0$, work fine, but when $n = 0$, it would only work if we permitted an empty disjunction, giving $$\{\} = ɿS\, \forall y\, (y \in S \leftrightarrow \bot)$$ where "$\bot$" represents falsehood in the same manner as "$\top$" represents truth, as described above. Then $y \in S \leftrightarrow \bot$ simplifies to $y \notin S$.
But lacking a formal empty disjunction is far from fatal; we can special-case $\{\}$ as $\varnothing$ if we've already defined that symbol, and as $ɿS\, \forall y\, (y \notin S)$ or equivalent (i.e., as however we'd define "$\varnothing$") otherwise. This is more of a demonstration that the empty disjunction is conceptually meaningful than that we should really permit it.
I think the empty conjunction and disjunction are not really interesting in and of themselves, but they have tendrils deep in several different interesting and important topics, and thus serve to reveal insights into those topics as well as the interrelationships between them. (Because of this, empty conjunctions and disjunctions may come up again in the future... :)
« first day (879 days earlier) ← previous day next day → last day (1520 days later) »
