§ 1. Fundamental Concepts

Definition 1.1 : Objects (Elements) of a Set

If an object \(a\) belongs to a set \(A\), we express this fact by the notation

\[ a \in A. \]

If \(a\) does not belong to \(A\), we express this fact by writing

\[ a \notin A. \]

Definition 1.2 : Subset / Proper Subset

We say that \(A\) is a subset of \(B\) if every element of \(A\) is also an element of \(B\), and we express this fact by writing

\[ A \subset B. \]

If \(A \subset B\) and \(A\) is different from \(B\), we say that \(A\) is a proper subset of \(B\), and we write

\[ A \subsetneq B . \]

The relations \(\subset\) and \(\subsetneq\) are called inclusion and proper inclusion, respectively. If \(A \subset B\), we also write \(B \supset A\), which is read "\(B\) contains \(A\)."

Definition 1.3 : The Union of Sets

Given two sets \(A\) and \(B\), the set that consists of all the elements of \(A\) together with all the elements of \(B\) is called the union of \(A\) and \(B\) and is denoted by \(A \cup B\). Formally, we define

\[ A \cup B=\{x \mid x \in A \text { or } x \in B\} . \]

Definition 1.4 : The Intersection of Sets

Given sets \(A\) and \(B\), the set formed by taking the common part of \(A\) and \(B\) is called the intersection of \(A\) and \(B\) and is denoted by \(A \cap B\). Formally, we define

\[ A \cap B=\{x \mid x \in A \text { and } x \in B\} . \]

Definition 1.5 : Empty Set

The empty set, denoted by \(\varnothing\) is the set having no elements.

Definition 1.6 : Disjoint Sets

We express the statement that \(A\) and \(B\) have no elements in common by saying that \(A\) and \(B\) are disjoint.

\[ A \cap B=\varnothing . \]

Definition 1.7 : Statement / Hypothesis / Conclusion

A statement of the form "If \(P\), then \(Q\)" means that if \(P\) is true, \(Q\) is true also, but if \(P\) is false, \(Q\) may be either true or false. It is read "\(P\) implies \(Q\).", and denoted by

\[ P \Longrightarrow Q. \]

\(P\) is called the hypothesis of the statement, and \(Q\) is called the conclusion of the statement.

Definition 1.8 : Vacuously True

For a statement, if there are no cases for which the hypothesis holds, the statement is said to be vacuously true.

Definition 1.9 : Contrapositive

Given a statement of the form "If \(P\), then \(Q\)," its contrapositive is defined to be the statement "If \(Q\) is not true, then \(P\) is not true."

\[ (\operatorname{not} Q) \Longrightarrow(\operatorname{not} P) \]

A statement and its contrapositive are logically equivalent.

Definition 1.10 : Converse

Given a statement of the form "If \(P\), then \(Q\)," its converse is defined to be the statement "If \(Q\), then \(P\)."

\[ Q \Longrightarrow P \]

A statement and its converse are not necessarily logically equivalent.

Definition 1.11 : If and Only If

If both the statement \(P \Rightarrow Q\) and its converse \(Q \Rightarrow P\) are true, we express this fact by the notation

\[ P \Longleftrightarrow Q, \]

which is read "\(P\) holds if and only if \(Q\) holds."

Definition 1.12 : Negation

The statement "not \(P\)," is called the negation of \(P\).

The negation of logical quantifier "for every" is "for at least one".

Definition 1.13 : The Difference of Two Sets

The difference of two sets, denoted by \(A-B\), and defined as the set consisting of those elements of \(A\) that are not in \(B\). Formally,

\[ A-B=\{x \mid x \in A \text { and } x \notin B\} . \]

It is sometimes called the complement of \(B\) relative to \(A\), or the complement of \(B\) in \(A\).

Theorem 1.1 : Distributive Law

\[ A \cap(B \cup C)=(A \cap B) \cup(A \cap C) \]

\[ A \cup(B \cap C)=(A \cup B) \cap(A \cup C) \]

Theorem 1.2 : DeMorgan's Law

\[ A-(B \cup C)=(A-B) \cap(A-C) \]

\[ A-(B \cap C)=(A-B) \cup(A-C) \]

Definition 1.14 : Power Set / Collection of Sets

Given a set \(A\), we can consider the set of all subsets of \(A\). This set is sometimes denoted by the symbol \(\mathcal{P}(A)\) and is called the power set of \(A\).

When we have a set whose elements are sets, we shall often refer to it as a collection of sets and denote it by a script letter such as \(\mathcal{A}\) or \(\mathcal{B}\).

Definition 1.15 : Arbitrary Unions

Given a collection \(\mathcal{A}\) of sets, the union of the elements of \(\mathcal{A}\) is defined by the equation

\[ \bigcup_{A \in \mathcal{A}} A=\{x \mid x \in A \text { for at least one } A \in \mathcal{A}\}. \]

Definition 1.16 : Arbitrary Intersections

Given a collection \(\mathcal{A}\) of sets, the intersection of the elements of \(\mathcal{A}\) is defined by the equation

\[ \bigcap_{A \in \mathcal{A}} A=\{x \mid x \in A \text { for every } A \in \mathcal{A}\}. \]

We shall not define the intersection when \(\mathcal{A}\) is empty.

Definition 1.17 : Cartesian Product

Given sets \(A\) and \(B\), we define their cartesian product \(A \times B\) to be the set of all ordered pairs \((a, b)\) for which \(a\) is an element of \(A\) and \(b\) is an element of \(B\). Formally,

\[ A \times B=\{(a, b) \mid a \in A \text { and } b \in B\} \]