Preliminaries and Notation

Rudiments of Logic

In logic, \(\,\) a \(\,\) sentence \(\,\) is a statement that is (on the grounds of a science or a theory) either true or false. The ‘true’ and ‘false’ being \(\,\) logical values , \(\,\) a sentence may be said to have a definite logical value. \(\,\) Sentences are here symbolized with letters \(\,p,\,q,\,r,\,\dots\)

The logical connectives : \(\quad \begin{array}{ccccc} \qquad\sim\qquad & \qquad\lor\qquad & \qquad\land\qquad & \quad\Rightarrow\qquad & \Leftrightarrow \\ \qquad\text{not}\qquad & \qquad\text{or}\qquad & \qquad\text{and}\qquad & \ \ \ \text{implies}\quad & \ \ \ \text{is equivalent} \end{array}\)

can be used to join component sentences into more complex ones. \(\\\) The most important complex sentences are:

negation: \(\quad\sim p\quad\) (not \(\,p\,;\ \ \) it is not the case that \(\,p\,\)) ;

disjunction: \(\quad p\lor q\quad\) (\(\,p\ \) or \(\ q\)) ;

conjunction: \(\quad p\land q\quad\) (\(\,p\ \) and \(\ q\)) ;

implication: \(\quad p\Rightarrow q\quad\) (if \(\ p\ \) then \(\ q\,;\ \ \) \(\ p\ \) implies \(\ q\,;\ \ \) \(\ p\ \) only if \(\ q\,\)) ;

equivalence: \(\quad p\Leftrightarrow q\quad\) (\(\ p\ \) if and only if \(\ q,\ \,\) in short: \(\ p\ \) iff \(\ q\,\)) .

If a theorem is formulated as an implication \(\ p\Rightarrow q\,,\ \) the following terminology is used:

• \(\ p\ \) is the premise (hypothesis) of the theorem (a sufficient condition for \(\ q\))

• \(\ q\ \) is the conclusion of the theorem (a necessary condition for \(\ p\)).

Tautologies \(\,\) are expressions (composed of sentence letters, connectives and parentheses) which become always true, regardless of logical values of their constituents. Examples thereof are:

\[\begin{split}\begin{array}{ccl} (p\Leftrightarrow q)\ \ \Leftrightarrow\ \ [\,(p\Rightarrow q) \land(q\Rightarrow p)\,] & \quad & \text{(equivalence is biconditional)} \\ \\ (p\Rightarrow q)\ \Leftrightarrow\ [\,(\sim q)\Rightarrow (\sim p)\,] & \quad & \text{(the contraposition law)} \\ \\ \sim (p\lor q)\ \Leftrightarrow\ [\,(\sim p) \land (\sim q)\,] & \quad & \text{(the negation of disjunction law)} \\ \sim (p\land q)\ \Leftrightarrow\ [\,(\sim p) \lor (\sim q)\,] & \quad & \text{(the negation of conjunction law)} \end{array}\end{split}\]

Notation of the Set Theory

Sets are usually denoted by capital letters: \(\ A,\,B,\,\dots,\,X,\,Y,\,Z,\,\dots\)

whereas their elements are symbolized with small ones: \(\ a,\,b,\,c,\,\dots,\,x,\,y,\,z,\,\dots\)

The set membership is denoted as follows:

\(\,a\in A\ \ \) - \(\ \ a\,\) is an element of the set \(\,A\,\) (\(a\,\) belongs to \(\,A\)) ;

\(\,a\notin A\ \ \) - \(\ \ a\,\) is not an element of the set \(\,A\,\) (\(a\,\) does not belong to \(\,A\)) .

The symbol \(\ \emptyset\ \) denotes \(\,\) the empty set : \(\,\) the unique set having no elements.

When we specify a set by enumerating its elements, we use curly brackets {braces}:

\(\,\{a_1,a_2,\dots,a_k\}\) \(\,\) - \(\,\) set composed of elements \(\,a_1,a_2,\dots,a_k\ \) (their order is undefined).

On the other hand, the round brackets (parentheses) denote a sequence:

\(\,(a_1,a_2,\dots,a_k)\) \(\,\) - \(\,\) sequence of elements \(\,a_1,a_2,\dots,a_k\ \) (their order is relevant).

A sequence of \(\,n\,\) elements is also called \(\,n\)-tuple, \(\ \) and a 2-tuple is named an ordered pair.

A denotement \(\ \{\,x\in X:\ \phi(x)\,\}\ \,\) represents the collection of elements \(\,x\,\) from the set \(\,X,\ \) which fulfill the condition \(\,\phi.\ \)

So, the record \(\ \{\,x\in R:\ x^2+x-2=0\,\}\,=\,\{-2,\,1\,\}\ \) asserts that the set of real numbers \(\,x,\ \)

for which \(\,x^2+x-2=0,\ \) is the 2-element set composed of numbers \(\,-2\ \) and \(\,1.\)

Suppose \(\,A\,\) and \(\,B\,\) are two sets. Then

• the union \(\,A \cup B\ \) is the set of all elements that are members of either \(\,A\,\) or \(\,B:\)

  \[A \cup B\ :\,=\ \{\,x:\ \ x\in A \ \lor\ x\in B\,\}\,;\]

• the intersection \(\,A \cap B\ \) is the set of all elements that are members of both \(\,A\,\) and \(\,B:\)

  \[A \cap B\ :\,=\ \{\,x:\ \ x\in A \ \land\ x\in B\,\}\,;\]

• the difference \(\,A \!\smallsetminus\! B\ \) is the set of elements that belong to \(\,A\,\) and don’t belong to \(\,B:\)

  \[A \!\smallsetminus\! B\ :\,=\ \{\,x:\ \ x\in A \ \land\ x\notin B\,\}\,;\]
• \(\,A\ \,\) is a subset of \(\,\) (or is included in) \(\ \,B\,:\ \) \(\ A\subset B,\ \ \) when

  each element of \(\,A\,\) is also an element of \(\,B\,:\ \ \) for all \(\,x,\ \ x\in A\ \Rightarrow\ x\in B\,.\)

We adopt the following notation for the basic numerical sets:

• \(\ N\ \) - \(\,\) set of natural numbers; \(\ N\,=\,\{1,2,\ldots\}\,\);

• \(\ Z\ \) - \(\,\) set of integer numbers; \(\ Z\,=\,\{0,\pm 1,\pm 2,\ldots\}\,\);

• \(\ Q\ \) - \(\,\) set of rational numbers;

• \(\ R\ \) - \(\,\) set of real numbers;

• \(\ C\ \) - \(\,\) set of complex numbers.

Mappings and Operations

A mapping \(\ f:\, X\to Y\ \) from \(\,X\,\) to \(\,Y\,\) is a relation between the two sets with the property that each \(\,x\in X\ \) is related to exactly one \(\,y\in Y.\ \) If an element \(\,x\in X\,\) is related to \(\,y\in Y,\ \) one says that \(\,y\,\) is the image of \(\,x\,\) under the mapping \(\,f:\ \ y=f(x).\)

The set \(\,X\,\) is called \(\,\) the domain \(\,\) (or set of arguments) \(\,\) of the mapping \(\,f,\ \,\) the set \(\,Y\,\) is \(\,\) the codomain, \(\,\) and \(\,\) the set \(\,f(X)\,:\,=\,\{\,f(x)\,:\,x\in X\}\ \) is named \(\,\) the image \(\,\) (or set of values) \(\,\) of the mapping.

A mapping \(\ f: X\to Y\ \) is:

• Surjective \(\,\) (\(\,f\,\) maps \(\,X\,\) onto \(\,Y\,\)) \(\,\) when \(\ f(X)=Y\,.\ \)

  Then every \(\,y\in Y\,\) has \(\,\) at least one \(\,\) matching \(\,x\in X.\)
• Injective \(\,\) (\(\,f\,\) is a one-to-one mapping), \(\,\) when \(\ \ x_1\neq x_2\ \Rightarrow\ f(x_1)\neq f(x_2)\ \)

  (if arguments \(\ x_1,\,x_2\ \) are different, so are their images \(\ f(x_1),\,f(x_2)\,\)).

  Then every \(\,y\in Y\,\) has \(\,\) at most one \(\,\) matching \(\,x\in X.\)
• Bijective \(\,\) (one-to-one correspondence) \(\,\) when it is both surjective and injective.

  Then each \(\,y\in Y\,\) is associated with \(\,\) exactly one \(\,x\in X.\)

The Cartesian product of two sets \(\,A\,\) and \(\,B\,\) is by definition \(\,\) the set of all ordered pairs \(\,(a,b)\,\) such that \(\,a\,\) belongs to \(\,A\,\) and \(\,b\,\) belongs to \(\,B:\)

\[A\times B\ :\,=\ \{\,(a,b):\ a\in A \,\land\, b\in B\,\}\,.\]

This definition can be extended to the case of more than two sets. Given sets \(\,A_1,A_2,\ldots,\,A_n\,,\ \) the Cartesian product \(\ A_1\times A_2\times \ldots\times A_n\ \) is defined as the set of all \(\,n\)-tuples whose consecutive components belong to the respective sets:

\[A_1\times A_2\times \ldots\times A_n\ :\,=\ \{\,(a_1,a_2,\ldots,a_n)\,:\ \ \ a_i\in A_i,\ \ i=1,2,\ldots,n.\,\}.\]

In particular, an \(\,n\)-th Cartesian power of a set \(\,A\ \) is given by

\[A^n\,\equiv\ \underbrace{A \times A \times \ldots \times A}_{n}\ =\ \{\,(a_1,a_2,\ldots,a_n)\,:\ \ \ a_i\in A,\ \ i=1,2,\ldots,n.\,\}.\]

An internal (binary) operation \(\,\odot\,\) defined in the set \(\,A\,\) is a mapping \(\,\odot:\, A\times A\to A.\ \) \(\\\) If \(\,\odot\,(a_1,a_2)=a_3\ \) for some \(\,a_1,a_2,a_3\in A,\,\) then we say that \(\,a_3\,\) is the result of the operation \(\,\odot\,\) on the elements \(\,a_1\ \) and \(\,a_2\,:\ \) \(\ a_3=a_1\odot a_2.\ \) Examples are: addition of natural numbers, subtraction of inegers, addition and cross-multiplying (but not dot-multiplying) of geometric vectors. In these examples each ordered pair of elements of a set \(\,A\,\) is mapped on an element of the same set \(\,A\).

An external operation \(\,\boxdot\,\) (precisely: left external binary operation) defined in the set \(\,A\,\) \(\\\) is a mapping \(\,\boxdot:\, K\times A\to A,\ \) where \(\,K\,\) is another set. \(\\\) The result \(\ \boxdot\,(\lambda,a)\ \) of the operation \(\,\boxdot\,\) on elements \(\,\lambda\in K\ \) and \(\,a\in A\,\) is written as \(\,\lambda\boxdot a.\ \) Examples are: multiplication of geometric vectors by real numbers, multiplication of matrices by scalars, multiplication of functions by numbers. Now each ordered pair of elements of sets \(\,K\,\) and \(\,A\,\) is mapped on an element of the set \(\,A.\)