Proposition

From CS2800 wiki
(Redirected from Statement)


Definition: Proposition
A proposition is a statement that is either true or false.

For example, [math]3 \gt 5 [/math] is a proposition, as is [math]3 \lt 5 [/math]. "Professor George is taller than 5'" is a proposition. If [math]x [/math] is known to be 5, then "[math]x \gt 5 [/math]" is a proposition.

If a fact depends on a variable, we will not consider it to be a proposition. For example, "[math]x \gt 5 [/math]" by itself is not a proposition. Neither is "[math]x \gt x-1 [/math]". These statements are called properties of [math]x [/math], or predicates on [math]x [/math]. Similarly, we can have properties of two variables (e.g. [math]x \gt y [/math]).

Predicates can be turned into propositions by quantifying them; stating that they must be true either for all [math]x [/math] or for some [math]x [/math].

For example, "for any sets [math]A [/math] and [math]B [/math], [math]A \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B [/math]" is a proposition, as is "there exists some [math]x [/math] with [math]x \gt 0 [/math]".

This process can be repeated: "for all [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math], [math]x \geq y [/math]" is a predicate, because it depends on [math]y [/math] (but not [math]x [/math]!). But "there exists [math]y \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math] such that for every [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math], [math]x ≥ y [/math]" is a proposition.

We are often lazy and leave off the quantification of a variable in a statement. When we have an undefined variable [math]x [/math] in a claim, we implicitly mean "for all [math]x [/math]". For example, if I ask you to prove or disprove that [math]A \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B [/math], I implicitly mean to prove or disprove that, for all sets [math]A [/math] and [math]B [/math], [math]A \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B [/math].