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:

    • The Earth revolves around the Sun;
    • \(10 + 3 = 13;\)
    • If \(x\) is an even integer, then \({x^2}\) is also even.

    Examples of false propositions:

    • An electron is heavier than a proton;
    • \(1 + 2 \gt 3;\)
    • \(6\) is a prime number.

    Not all sentences are propositions:

    • \(x \gt 5\) (This may be true or false depending on \(x\))
    • Is it raining? (This is a question, not a declarative sentence)
    • Mondrian paintings are too abstract. (What is abstract and too abstract?)

    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:\) \(\large{\frac{2}{3}}\normalsize\) is a rational number (true)
    \(q:\) \(\large{\frac{\sqrt{2}}{5}}\normalsize\) is a rational number (false)
    \(p \lor q:\) Either \(\large{\frac{2}{3}}\normalsize\) or \(\large{\frac{\sqrt{2}}{5}}\normalsize\) 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:

    • \(p\) implies \(q\)
    • \(p\) is a sufficient condition for \(q\)
    • \(q\) is a necessary condition for \(p\)
    • \(q\) follows from \(p\)
    • \(p\) only if \(q\)

    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

    • The converse of \(p \to q\) is the proposition \(q \to p\)
    • The contrapositive of \(p \to q\) is the proposition \(\neg q \to \neg p\)
    • The inverse of \(p \to q\) is the proposition \(\neg p \to \neg q\)

    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)\)
    \(\require{AMSsymbols}\varnothing\) the empty set

  • Solved Problems

    Click a problem to see the solution.

    Example 1

    Prove De Morgan’s Laws: \[\neg \left( {p \land q} \right) \equiv \left( {\neg p} \right) \lor \left( {\neg q} \right),\] \[\neg \left( {p \lor q} \right) \equiv \left( {\neg p} \right) \land \left( {\neg q} \right).\]

    Example 2

    Show that the statement \[s = \left( {p \lor \neg q} \right) \lor \left( {\neg p \land q} \right)\] is a tautology.

    Example 3

    Show that the statement \[r = (\neg p \land q) \land (p \leftrightarrow q)\] is a contradiction.

    Example 4

    Prove the distributive law \[p \lor \left( {q \land r} \right) \equiv \left( {p \lor q} \right) \land \left( {p \lor r} \right).\]

    Example 5

    Let \(G\left( {x,y} \right)\) be the predicate “\(x\) goes to the gym \(y\) times a week.” Write the following propositions in predicate notation:
    1. Nick goes to the gym \(4\) times a week.
    2. Nicole goes to the gym \(2\) or \(3\) times a week.
    3. Max goes to the gym 2 times a week, but not every week.
    4. Amy sometimes goes to the gym.
    5. Some people go to the gym every day.
    6. Hardly anyone goes to the gym 15 times a week.

    Example 6

    Suppose \(x\) is a student, \(y\) is a math course, and \(M\left( {x,y} \right)\) is the predicate “\(x\) will take \(y\)”. Translate the following sentences into predicate notation:
    1. Every student will take Calculus.
    2. Every student will take a math course.
    3. Lora will take Calculus and Linear Algebra.
    4. There is a course that everybody will take.
    5. There is a course that nobody will take.
    6. Tom will take all math courses except Topology.

    Example 7

    Describe the following sets using set builder notation:
    1. \(\left\{ { – 27, – 8, – 1,0,1,8,27} \right\}\)
    2. \(\left\{ {\large{\frac{1}{2}}\normalsize, \large{\frac{2}{3}}\normalsize, \large{\frac{3}{4}}\normalsize, \large{\frac{4}{5}}\normalsize, \large{\frac{5}{6}}\normalsize} \right\}\)
    3. \(\left\{ {5,8,13,21,34,55} \right\}\)

    Example 1.

    Prove De Morgan’s Laws: \[\neg \left( {p \land q} \right) \equiv \left( {\neg p} \right) \lor \left( {\neg q} \right),\] \[\neg \left( {p \lor q} \right) \equiv \left( {\neg p} \right) \land \left( {\neg q} \right).\]

    Solution.

    We verify the \(1\text{st}\) De Morgan’s Law using truth table.

    First we write all possible combinations of the propositions \(p\) and \(q.\) The negations of \(p\) and \(q\) are their opposite values. The expression \(p \land q\) is conjunction of \(p\) and \(q.\) Then we determine the negation of conjunction \(\neg \left({p \land q}\right)\). The expression \(\left( {\neg p} \right) \lor \left( {\neg q} \right)\) is disjunction of \(\neg p\) and \(\neg q.\)

    Truth Table for the 1st De Morgan's Law
    1st De Morgan’s Law

    We see that the last two columns of the truth table are the same. This proves the \(1\text{st}\) De Morgan’s Law.

    Similarly, we can verify the \(2\text{nd}\) De Morgan’s Law:

    Truth Table for the 2nd De Morgan's Law
    2nd De Morgan’s Law

    Example 2.

    Show that the statement \[s = \left( {p \lor \neg q} \right) \lor \left( {\neg p \land q} \right)\] is a tautology.

    Solution.

    A tautology is defined as a proposition which is always true. So we make a truth table for the statement and check its truth values.

    The values of \(p,\) \(q,\) \(\neg p,\) and \(\neg q\) are easy to fill in. The next column \({p \lor \neg q}\) means disjunction of \(p\) and \(\neg q.\) Then we find conjunction \({\neg p \land q}.\) The final statement \(s\) is disjunction of two previous propositions.

    An example of tautology statement
    A tautology statement

    We see that all \(4\) values in the last column are true. Hence, the statement \(s = \left( {p \lor \neg q} \right) \lor \left( {\neg p \land q} \right)\) is a tautology.

    Example 3.

    Show that the statement \[r = (\neg p \land q) \land (p \leftrightarrow q)\] is a contradiction.

    Solution.

    A contradiction is a statement that is always false. Let’s construct a truth table to make sure that the statement \(r\) has only false values.

    The first expression \(\neg p \land q\) is conjunction of \(\neg p\) and \(q.\) The second expression \(p \leftrightarrow q\) is the biconditional of \(p\) and \(q\). The final operation is conjunction of two previous propositions.

    An example of contradiction statement
    A contradiction statement

    The last column contains only false values. Hence, the proposition \(r = (\neg p \land q) \land (p \leftrightarrow q)\) is a contradiction.

    Example 4.

    Prove the distributive law \[p \lor \left( {q \land r} \right) \equiv \left( {p \lor q} \right) \land \left( {p \lor r} \right).\]

    Solution.

    We construct a truth table to make sure that the left hand and right hand sides of the statement are equivalent.

    Let’s denote

    \[{s1 = p \lor \left( {q \land r} \right),\;\;}\kern0pt{s2 = \left( {p \lor q} \right) \land \left( {p \lor r} \right)}\]

    and find the truth values of \(s1\) and \(s2.\)

    Applying conjunction and disjunction operations we get the following table:

    Proving a distributive law for propositions
    A distributive law

    The last two columns of the table are identical. This means that

    \[{s1 \equiv s2,}\;\; \Rightarrow {p \lor \left( {q \land r} \right) \equiv \left( {p \lor q} \right) \land \left( {p \lor r} \right).}\]

    Example 5.

    Let \(G\left( {x,y} \right)\) be the predicate “\(x\) goes to the gym \(y\) times a week.” Write the following propositions in predicate notation:
    1. Nick goes to the gym \(4\) times a week.
    2. Nicole goes to the gym \(2\) or \(3\) times a week.
    3. Max goes to the gym 2 times a week, but not every week.
    4. Amy sometimes goes to the gym.
    5. Some people go to the gym every day.
    6. Hardly anyone goes to the gym 15 times a week.

    Solution.

    1. Nick goes to the gym \(4\) times a week.
    2. \[G\left( {Nick,4} \right)\]
    3. Nicole goes to the gym \(2\) or \(3\) times a week.
    4. \[G\left( {Nicole,2} \right) \lor G\left( {Nicole,3} \right)\]
    5. Max goes to the gym 2 times a week, but not every week.
    6. \[G\left( {Max,2} \right) \lor G\left( {Max,0} \right)\]
    7. Amy sometimes goes to the gym.
    8. \[\exists y G\left( {Amy,y} \right)\]
    9. Some people go to the gym every day.
    10. \[\exists x G\left( {x,7} \right)\]
    11. Hardly anyone goes to the gym 15 times a week.
    12. \[\neg \exists x G\left( {x,15} \right)\]

    Example 6.

    Suppose \(x\) is a student, \(y\) is a math course, and \(M\left( {x,y} \right)\) is the predicate “\(x\) will take \(y\)”. Translate the following sentences into predicate notation:
    1. Every student will take Calculus.
    2. Every student will take a math course.
    3. Lora will take Calculus and Linear Algebra.
    4. There is a course that everybody will take.
    5. There is a course that nobody will take.
    6. Tom will take all math courses except Topology.

    Solution.

    1. Every student will take Calculus.
    2. \[\forall x M\left( {x,Calculus} \right)\]
    3. Every student will take a math course.
    4. \[\forall x\exists yM\left( {x,y} \right)\]
    5. Lora will take Calculus and Linear Algebra.
    6. \[M\left( {Lora,Calculus} \right) \land M\left( {Lora,Linear Algebra} \right)\]
    7. There is a course that everybody will take.
    8. \[\exists y\forall xM\left( {x,y} \right)\]
    9. There is a course that nobody will take.
    10. \[\exists y\forall x\neg M\left( {x,y} \right)\]
    11. Tom will take all math courses except Topology.
    12. \[\forall yM\left( {Tom,y} \right) \land \neg M\left( {Tom, Topology} \right)\]

    Example 7.

    Describe the following sets using set builder notation:
    1. \(\left\{ { – 27, – 8, – 1,0,1,8,27} \right\}\)
    2. \(\left\{ {\large{\frac{1}{2}}\normalsize, \large{\frac{2}{3}}\normalsize, \large{\frac{3}{4}}\normalsize, \large{\frac{4}{5}}\normalsize, \large{\frac{5}{6}}\normalsize} \right\}\)
    3. \(\left\{ {5,8,13,21,34,55} \right\}\)

    Solution.

    1. The set \(\left\{ { – 27, – 8, – 1,0,1,8,27} \right\}\) contains integers from \(x = -3\) to \(x = 3\) cubed.
    2. \[\left\{ {x \in \mathbb{Z}\,|\,{x^3} \text{ and } – 3 \le x \le 3} \right\}\]
    3. The set \(\left\{ {\large{\frac{1}{2}}\normalsize, \large{\frac{2}{3}}\normalsize, \large{\frac{3}{4}}\normalsize, \large{\frac{4}{5}}\normalsize, \large{\frac{5}{6}}\normalsize} \right\}\) contains fractions where the denominator is greater than its numerator by \(1\) and the numerator ranges from \(1\) to \(5.\)
    4. \[\left\{ {x \in \mathbb{N}\,|\,\frac{x}{{x + 1}} \text{ and } 1 \le x \le 5} \right\}\]
    5. The set \(\left\{ {5,8,13,21,34,55} \right\}\) is a portion of the Fibonacci sequence \({F_n}\) from \(n = 6\) to \(n = 11.\)
    6. \[{\left\{ {x \in \mathbb{N}\,|\,x \in {F_n},}\right.}\kern0pt{\left.{\text{ where } n \in \mathbb{N} \text{ and } 6 \le n \le 11} \right\}}\]