Basic Logic

Notation: Negation

For any statement \(P\),

\[\neg P\]

denotes “\(P\) is not true”. This is called the negation of \(P\).

Notation: Logical And

For any statements \(P,Q\),

\[P \wedge Q\]

denotes “\(P\) and \(Q\)”. This is called the logical conjunction of \(P\) and \(Q\).

Notation: Logical Or

For any statements \(P,Q\),

\[P \vee Q\]

denotes “\(P\) or \(Q\)”. This is called the logical disjunction of \(P\) and \(Q\).

This is an inclusive logical disjunction, i.e., it need not mean that only one of the two statements is true.

Notation: Quantifiers

For any statements \(P,Q\),

\[\exists x \mid P \colon Q\]

denotes that there exists some object \(x\) such that \(P\) for which \(Q\) (i.e., for some object \(x\) such that \(P\), \(Q\)). We can also write

\[\exists x \colon Q\]

to simply denote that there exists some object \(x\) such that \(Q\).

One can also replace \(\exists\) with \(\exists!\) to denote “for exactly one” instead of “for some”, or with \(\forall\) to denote “for all”. However, this is not quite the “for all” we use colloquially; it’s more of an “evil twin” for \(\exists\). That is, while \(\exists\) denotes the existence of at least one example, \(\forall\) denotes the nonexistence of any counterexample; thus, it is possible for the statement

\[\forall x \mid P \colon Q\]

to be vacuously true, i.e., if \(P\) is impossible for all objects \(x\), the statement will be true due to the nonexistence of counterexamples where for some \(x\) \(P\) but not \(Q\).

\(\exists\), \(\exists!\), and \(\forall\) are all called quantifiers. In particular, \(\exists\) is called the existential quantifier, \(\exists!\) is called the unique existential quantifier, and \(\forall\) is called the universal quantifier.

Motivation. While we could just as well define \(\forall x \mid P \colon Q\) to match the colloquial meaning of “for all” (nonexistence of counterexamples as well as the existence of at least one example), we have gone with the definition we have chosen as it is a more fundamental “building block” in a certain sense. And anyway, it can be used to denote “for all” in the more colloquial sense via logical conjunction with

\[\exists x \mid P \colon Q.\]

Remark. We need not abandon our intuition when interpreting statements involving \(\forall\); we just need to keep in mind that \(\forall x \mid P \colon Q\) is true in the case that \(\exists x \colon P\) is false.

Notation: Implication

For any two statements \(P\) and \(Q\),

\[P \implies Q\]

denotes that \(P\) implies \(Q\) (or, more precisely, \(\forall x \mid P \colon Q\)),

\[P \impliedby Q\]

denotes the converse, i.e., that \(P\) is implied by \(Q\), and

\[P \iff Q\]

denotes that \(P\) and \(Q\) are equivalent, i.e., that each statement implies the other. This can also be written “\(P\) iff \(Q\)”, where “iff” is shorthand for “if and only if”.

Motivation. Since \(P \implies Q\) means there exists no case where \(P\) but not \(Q\) and \(P \impliedby Q\) means there exists no case where \(Q\) but not \(P\), \(P \iff Q\) means that either both are true or neither is true in all cases, that is, \(P\) and \(Q\) are totally interchangeable, hence their being called equivalent.

We write “if and only if” because by “\(P\) if \(Q\)” we mean \(P \impliedby Q\) and by “\(P\) only if \(Q\)” we mean \(P \implies Q\).

Remark. As with \(\forall\), we need not be too careful with \(\implies\); we just need to keep in mind that \(P \implies Q\) is true if \(P\) is never true.

Convention: Logical Order of Precedence

All logical symbols listed above are listed in order from highest to lowest precedence. \(\implies\), \(\impliedby\), and \(\iff\) are not given precedence over one another; that is, e.g., \(P \implies Q \implies R\) denotes that \(P\) implies \(Q\) which in turn implies \(R\) as opposed to denoting \(\left(P \implies Q \right) \implies R\).

Notation: Therefore

\(\therefore\) denotes “therefore”; conversely, \(\because\) denotes “because”.

Notation: Equality

For any two objects \(x\) and \(y\),

\[x = y\]

denotes that \(x\) and \(y\) are equal, i.e., the same object, and

\[x \neq y\]

denotes that \(x\) and \(y\) are not equal.

No \(=\) is given precedence over another. That is, \(x = y = z\), for example, denotes that \(x\) is equal to \(y\) which is in turn equal to \(z\) rather than denoting that the statement \(x = y\) is equal to \(z\). (In fact, we will never use \(=\) to denote equality of statements at all, favoring \(\iff\) instead.)

One can also use \(\coloneqq\) to denote equality by definition.