1.1. Logic and Sets

1.1.1. Logic

  • Let \(A\) and \(B\) be statements.

  • The negation of \(A\) is the statement (not \(A\)).

  • The both of \(A\) and \(B\) is the statement (\(A\) and \(B\)).

  • The either of \(A\) and \(B\) is the statement (\(A\) or \(B\)).

  • The statement (\(A\) or \(B\)) does not contradict (\(A\) and \(B\)).

  • Every statement is is assumed to be either true or false.

  • No statement can be both true and false.

  • The statements “\(A\) and \(B\) or \(C\)” and “\(A\) or \(B\) and \(C\)” are ambiguous.

  • We therefore write “\(A\) and either \(B\) or \(C\)” and “either \(A\) or both \(B\) and \(C\)”.

1.1.1.1. Implication

  • Let \(A\) and \(B\) be statements.

  • The implication statement “if \(A\) is satisfied, then \(B\) is satisfied” or, equivalently, “\(A\) implies \(B\)” is written as \(A \Rightarrow B\).

  • \(A \Leftrightarrow B\) is equivalent to \([(A \Rightarrow B) \text{ and } (A \Leftarrow B)]\)

  • \(A \Leftarrow B\) means \(B \Rightarrow A\).

1.1.1.2. Tautology

  • A tautology is a statement which is true regardless of whether the component statements are true or false.

  • E.g. the statement “(\(A\) and \(B\)) implies \(A\))” is a tautology.

1.1.1.3. Contradiction

  • A contradiction is a statement that is false regardless of whether the component statements are true or false.

1.1.1.4. Implication contd.

  • Suppose that \(A \Leftrightarrow B\).

  • Then, \(A\) is satisfied if and only if \(B\) is satisfied.

  • The implication \(A \Rightarrow B\) (the “only if” part) is necessity.

  • \(B \Rightarrow A\) (the “if” part) is sufficiency.

  • The converse statement of \(A \Rightarrow B\) is \(B \Rightarrow A\).

  • The statement \(A \Rightarrow B\) is equivalent to its contrapositive statement \((\text{not } B) \Rightarrow (\text{not } A)\).

1.1.1.5. Statements

  • A theorem is a significant statement.

  • A proposition is a theorem of less significance.

  • The primary role of a lemma is to support the proof of a theorem or proposition.

  • A corollary is a consequence of a theorem or proposition.

  • A fact is either a theorem or a proposition or a lemma or a corollary.

  • Theorems, propositions, lemmas, corollaries, and facts are provably true statements.

  • Suppose that \(A' \Rightarrow A \Rightarrow B \Rightarrow B'\).

  • Then, \(A' \Rightarrow B'\) is a corollary of \(A \Rightarrow B\).

  • Let \(A\), \(B\), and \(C\) be statements, and assume that \(A \Rightarrow B\).

  • Then, \(A \Rightarrow B\) is a strengthening of the statement \((A \text{ and } C) \Rightarrow B\).

  • If in addition \(A \Rightarrow C\), then the statement \((A \text{ and } C) \Rightarrow B\) has a redundant assumption.

1.1.2. Sets

  • A set is a collection of elements.

  • Let \(\mathcal{X} \triangleq = \{x,y,z\}\) be a set. Then

    \[x \in \mathcal{X}\]

    means that \(x\) is an element of \(\mathcal{X}\).

  • If \(w\) is not an element of \(\mathcal{X}\), then we write:

    \[w \notin \mathcal{X}\]

  • The set with no elements, denoted by \(\phi\), is the empty set.

  • If \(\mathcal{X} \neq \phi\), then \(\mathcal{X}\) is nonempty.

1.1.2.1. Cardinality

  • A set cannot have repeated elements. e.g. \(\{x,x\} = \{x\}\).

  • A multiset is a collection of elements that allows for repetition.

  • The multiset consisting of two copies of \(x\) is written as \({x,x}_{ms}\).

  • We do not assume that the listed elements \(x,y\) of the conventional set \(\{x,y\}\) are distinct.

  • The number of distinct elements of the set \(\mathcal{S}\) or not-necessarily-distinct elements of the multiset \(\mathcal{S}\) is the cardinality of \(\mathcal{S}\), which is denoted by \(\text{card}(\mathcal{S})\) or \(\left|\mathcal{S}\right|\).

1.1.2.2. Statements

  • There are two basic types of mathematical statements involving quantifiers.

  • An existential statement is of the form:

    there exists \(x \in \mathcal{X}\) such that statement \(Z\) is satisfied.

  • A universal statement has the structure

    for all \(x \in \mathcal{X}\), it follows that statement \(Z\) is satisfied.

    or equivalently

    statement \(Z\) is satisfied \(\forall x \in \mathcal{X}\).

1.1.2.3. Operations

  • Let \(\mathcal{X}\) and \(\mathcal{Y}\) be sets.

  • The intersection of \(\mathcal{X}\) and \(\mathcal{Y}\) is the set of common elements of \(\mathcal{X}\) and \(\mathcal{Y}\) given by

    \[\mathcal{X} \cap \mathcal{Y} \triangleq \{x : x \in \mathcal{X} \wedge x \in \mathcal{Y} \} = \{x : x \in \mathcal{Y} \wedge x \in \mathcal{X} \} = \mathcal{Y} \cap \mathcal{X}\]