Calculus

Set Theory

Set Theory Logo

Logic and Set Notation

Set theory is a branch of mathematical logic. Therefore, it is natural that logical language and symbols are used to describe sets. In this section, we will look at the basic logical symbols and ways of defining sets.

Propositional Logic

A proposition is a declarative statement which is either true or false. If a proposition is true, then we say it has a truth value of true. Respectively, if a proposition is false, its truth value is false. So, for example, the following statements have a truth value of true:

Examples of false propositions:

Not all sentences are propositions:

To represent propositions, we denote them by letters. The most common letters are \(p,\) \(q,\) \(r,\) \(s,\) \(t.\)

Using logical operators or connectives, we can build compound propositions.

Logical Operators and Truth Tables

Let \(p\) and \(q\) be two propositions. Each of these statements can take two values - true (\(T\)) and false (\(F\)). So there are \(4\) pairs of input values: \(TT,\) \(TF,\) \(FT,\) and \(FF.\)

Suppose that a new proposition \(r\) is composed of \(p\) and \(q.\) The truth values of the proposition \(r\) can take different values (\(T\) or \(F\)) for each pair of input values.

Logic gate of a binary input variable
Figure 1.

There are total \(2^4 = 16\) possible output combinations (truth functions) for \(2\) binary input variables. Each of these combinations is represented by a certain logical operator.

Further we'll look at the most important operators.

Negation

Negation is a unary logical operator. If \(p\) is a proposition, then the negation of \(p\) is called not \(p\) and is denoted by \(\lnot p.\)

To represent the meaning of a logical expression, it is convenient to use a truth table. Each row of the table contains one possible configuration of the input variables and truth values of the output proposition(s).

In case of the negation operator, the truth table is very simple:

Truth table for negation

As you can see, the logical negation operator reverses the truth value of the input proposition.

Example 1:

\(p:\) A trapezoid is a quadrilateral (true)
\(\lnot p:\) A trapezoid is not a quadrilateral (false)

Example 2:

\(p:\) \(2\) is a prime number (true)
\(\lnot p:\) \(2\) is not a prime number (false)

Сonsider now some binary operators.

Conjunction

If \(p\) and \(q\) are two propositions, then their conjunction means \(p\) and \(q\) and is denoted by \(p \land q.\)

The conjunction \(p \land q\) is true only when both \(p\) and \(q\) are true. Otherwise, it is false. Thus, the truth table for conjunction looks as follows:

Truth table for conjunction

Example 1:

\(p:\) United Kingdom is a member of European Union (false)
\(q:\) Ireland is a member of European Union (true)
\(p \land q:\) United Kingdom and Ireland are members of European Union (false)

Example 2:

\(p:\) \(3\) is prime (true)
\(q:\) \(3\) is odd (true)
\(p \land q:\) \(3\) is prime and odd (true)

Disjunction

If \(p\) and \(q\) are two propositions, then their disjunction means \(p\) or \(q\) and is denoted by \(p \lor q.\)

The disjunction \(p \lor q\) is true when either \(p\) is true, \(q\) is true, or both are true. It is false, if both \(p\) and \(q\) are false.

Truth table for disjunction:

Truth table for disjunction

Example 1:

\(p:\) A proton has a negative charge (false)
\(q:\) A neutron has a negative charge (false)
\(p \lor q:\) A proton or a neutron has a negative charge (false)

Example 2:

\(p:\) \(\frac{2}{3}\) is a rational number (true)
\(q:\) \(\frac{\sqrt{2}}{5}\) is a rational number (false)
\(p \lor q:\) Either \(\frac{2}{3}\) or \(\frac{\sqrt{2}}{5}\) or both the numbers are rational (true)

Material Conditional

The material conditional of \(p\) and \(q\) means the statement if \(p\) then \(q\) and is denoted by \(p \to q.\) This logical operator is also called just a conditional statement.

If \(p\) is true, then the conditional \(p \to q\) takes the truth value of \(q.\) If \(p\) is false, then the conditional \(p \to q\) is assumed to be true by default.

Here is the truth table for conditional statement:

Truth table for implication

The conditional \(p \to q\) can be expressed by different sentences, some of them are listed below:

Example:

\(p:\) \(x\) is divisible by \(2\) and \(3\)
\(q:\) \(x\) is divisible by \(6\)
\(p \to q:\) If \(x\) is divisible by \(2\) and \(3,\) then \(x\) is divisible by \(6.\)
\(x = 12:\) \(p\) is true, \(q\) is true, and \(p \to q\) is true.
\(x = 13:\) \(p\) is false, \(q\) is false, and \(p \to q\) is true.

Special Conditional Propositions

If the statement \(p \to q\) is true, then the contrapositive is also true. If the converse is true, then the inverse is also true.

The special conditional operators are defined by the following truth table:

Truth table for special conditional statements

Example:

Statement \(p\)
A quadrilateral is a rectangle (false)
Statement \(q\)
The sum of interior angles of a quadrilateral is \(360\) degrees (true).
Conditional statement \(p \to q\)
If a quadrilateral is a rectangle, then the sum of its interior angles is \(360\) degrees (true).
Converse of \(p \to q:\) \(q \to p\)
If the sum of interior angles of a quadrilateral is \(360\) degrees, then it is a rectangle (false).
Inverse of \(p \to q:\) \(\neg p \to \neg q\)
If a quadrilateral is a not a rectangle, then the sum of its interior angles is not \(360\) degrees (false).
Contrapositive of \(p \to q:\) \(\neg q \to \neg p\)
If the sum of interior angles of a quadrilateral is not \(360\) degrees, then it is not a rectangle (true).

Material Biconditional

The material biconditional or logical biconditional of \(p\) and \(q\) means the statement \(p\) if and only if \(q\) and is denoted by \(p \leftrightarrow q.\)

The biconditional statement has the same truth value as the compound logical operator \(\left( {p \to q} \right) \land \left( {q \to p} \right),\) which means \(p\) implies \(q\) and \(q\) implies \(p.\)

The truth table for biconditional statement has the form

Truth table for biconditional implication.

Example 1:

\(p:\) Three vectors are coplanar (true)
\(q:\) The scalar triple product of three vectors is zero (true)
\(p \leftrightarrow q:\) Three vectors are coplanar if and only if their scalar triple product is zero (true)

Example 2:

\(p:\) The tennis match will be played outdoors (false)
\(q:\) It is raining (true)
\(p \leftrightarrow q:\) The tennis match will be played outdoors if and only if it is raining (false)

Logical Equivalence

Propositions \(p\) and \(q\) are said to be logically equivalent if they have the same truth tables. The logical equivalence of \(p\) and \(q\) is denoted as \(p \equiv q,\) or sometimes by \(\Leftrightarrow\) depending on the notation being used.

Predicates and Quantifiers

So far, we considered propositions which are defined as statements that can be either true or false.

To extend the simple propositional logic, we introduce the concept of predicate.

A predicate is a logical statement that contains one or more variables or parameters. The predicates are denoted by a capital letter and the variables listed as arguments, like \(P\left( x \right)\) or \(Q\left( {x,y} \right).\) The truth value of a predicate depends on the values of its variables.

Example 1:

Predicate \(P\left( x \right)\)
\(P\left( x \right):\) \(x\) is a planet
\(x\) = VenusTrue proposition
\(P\left( \text{Venus} \right):\) Venus is a planet
\(x\) = AntaresFalse proposition
\(P\left( \text{Antares} \right):\) Antares is a planet

Example 2:

Predicate \(Q\left( {x,y} \right)\)
\(Q\left( {x,y} \right): {x^2} + {y^2} \le 4\)
\(x = 1, y = -1\)True proposition
\(Q\left( {1,-1} \right): {1^2} + {\left( { - 1} \right)^2} \le 4\)
\(x = 1, y = 2\)False proposition
\(Q\left( {1,2} \right): {1^2} + {2^2} \le 4\)

Similarly to propositions, predicate take two values - true or false. Therefore, all operations of logic algebra are applicable to them. Using the operators \(\neg, \land, \lor, \rightarrow,\) and \(\leftrightarrow,\) we can form more complex predicates.

There is also an additional operation defined on predicates and called quantification. Quantification allows us to specify the extent of validity of a predicate, that is, the range of values of variables for which the predicate should hold.

There are two types of quantifiers in predicate logic − universal quantifier and existential quantifier.

Universal Quantifier

The universal quantifier is used to express sentences with words like all or every. It is denoted by the symbol \(\forall.\) The notation \(\forall x P\left({x}\right)\) means "for every value of \(x\) in a particular domain, the predicate \(P\left({x}\right)\) is true". The domain is called the universe of discourse or domain of discourse.

Existential Quantifier

The existential quantifier is used to express sentences with words like some or there is a. It is denoted by the symbol \(\exists.\) The notation \(\exists x P\left({x}\right)\) means "there is some value of \(x\) such that \(P\left({x}\right)\) is true".

Predicates, logical operators, and quantifiers are a powerful set of tools for describing mathematical objects and for modeling the real world.

Set Builder Notation

The set builder notation is used to specify a set of objects by means of a predicate. The common notation includes \(3\) parts: a variable \(x,\) a colon or vertical bar separator, and a logical predicate \(P\left({x}\right):\)

\[S = \left\{ {x|P\left( x \right)} \right\},\]

where \(S\) denotes the set of objects.

The single variable \(x\) can be replaced with a term that may include one or more variables, combined with functions acting on them. The predicate \({P\left( x \right)}\) may be represented by a complex logical formula.

Some Other Definitions and Notations

\(\{\;\} \) is a set
\(x \in S\) \(x\) is an element or member of \(S\)
\(x \notin S\) \(x\) is not an element of \(S\)
\(S \subseteq T\) \(S\) is a subset of \(T\)
\(S = T\) is equivalent to \(\left({S \subseteq T}\right) \land \left({T \subseteq S}\right)\)
\(S \subset T\) \(S\) is a proper subset of \(T.\) This means \(\left({S \subseteq T}\right) \land \left({T \ne S}\right)\)
\(\varnothing\) the empty set

See solved problems on Page 2.

Page 1 Page 2