Pirates & Revolutionaries

[Search Blog Here. Index-tags are found on the bottom of the left column.]

[Logic & Semantics, Entry Directory]

[David Agler, entry directory]

[Agler’s Symbolic Logic, entry directory]

The following collects the brief summaries for all the main sections of David Agler’s Symbolic Logic Syntax, Semantics, and Proof, and in many cases some of Agler’s examples are replicated too. All the following is Agler’s work, boiled down for quick reference or review.

The entry directory without the brief summaries can be found here:

Agler’s Symbolic Logic, entry directory

A collection of the important rules and proof strategies can be found here:

Rules and Strategies for Logic Proofs (Alger, Nolt)

Collected Brief Summaries of

David W. Agler

Symbolic Logic: Syntax, Semantics, and Proof

Introduction / Ch.1:

Introduction
and
Ch.1: Propositions, Arguments, and Logical Properties
Sections 1.1-1.2: Propositions – Arguments

Logic studies the structures and mechanics of correct reasoning that takes an argumentative form. An argument is made of premises that lead to some conclusion. An argument may be (a) inductive, meaning that the conclusion is based on probabilities discerned from the premises, (b) abductive, meaning that the conclusion provides the best explanation (or theory) to account for the premises, or (c) deductively valid, meaning that the conclusion follows by logical necessity from the premises.

Section 1.3: Deductively Valid Arguments
and
Section 1.4: Summary

An argument is deductively valid if it is impossible for the premises to be true and the conclusion false, and it is invalid otherwise. An argument is sound if the premises in fact are true and as well it is valid. It is unsound if either it is invalid or if any of the premises are false.

Ch.2: Language, Syntax, and Semantics

2.1 Truth Functions

We will examine the language of propositional logic (PL). Propositions with no truth functional operators are are atomic propositions. A propositional operator makes a proposition more complex. If it does so by combining propositions, then it is a propositional connective. Propositional operators are truth-functional if the value of the more complicated proposition they make is entirely dependent on the truth value of the component parts.

2.2 The Symbols of PL and Truth-Functional Operators

The language of Propositional Logic (PL) is composed of (a) upper-case Roman letters (sometimes numerically subscripted) for propositions, (b) the truth-functional operators ∨, →, ↔, ¬, and ∧, and (c) scope indicators, namely, parentheses, brackets, and braces. A conjunction ∧ is true only if both conjuncts are true, and it is false otherwise. Negation ¬ inverts the truth value of the proposition. When determining the true value of a complex formula, we determine the operated values beginning with the operator with the least scope and work toward the one with the greatest scope, called the “main operator”. It can be determined by finding the operator that operates directly or indirectly on all other sentence parts.

2.3 Syntax of PL

Propositions in the language of propositional logic (PL) must be formed according to specific syntactical rules, and when they are, we consider them to be “well-formed formulas” or “wffs”. We form wffs by using uppercase Roman numerals, which can be modified, combined, and organized using logical operators ∨, →, ↔, ¬, ∧ or scope indicators like parentheses. The propositions within the language of PL are in our object language, and the English sentences we use to discuss these object language propositions is part of our metalanguage. In our metalanguage we might use metavariables, in this case, boldface Roman letters, to stand for any propositions in the object language. Using such metavariables and a metalanguage, we can state the rules for properly constructed wffs. Briefly, if a formula is an atomic formula, it is a wff. Or, if a proposition takes a negation symbol to its left, it is a wff. Or, if two formula have the symbols ∨, →, ↔, or ∧ placed between them, it is a wff. Nothing else, however, can be considered wffs. The literal negation of a proposition is the negation of the whole proposition; this means it could be a double negation in some cases, and in others the negation will go outside parentheses enclosing a complex proposition.

2.4 Disjunction, Conditional, Biconditional

A disjunction (∨) is true when at least one of the disjuncts is true, and it is false otherwise. The conditional (→) is false only when the antecedent is true but the consequent false. The biconditional (↔) is true when both sides have the same value, and it is false otherwise. The conditional is translatable using “if..., then...” formulations. However, not all “if..., then...” formulations conform to the material conditional’s truth-table. For example, when we use “if..., then...” formations to make statements of causality, both antecedent and conditional can be true and yet the whole proposition be false. Consider the example, “If John prays, then he will get an A”. Suppose that he both prayed and got an A. But suppose further that the real reason he got the A was not because he prayed (which he in fact did anyway) but rather because he cheated. Although both the antecedent and the consequent are true, the whole proposition is false; for, the proposition is stating that the cause of getting the high grade is praying, when in reality the cause is not that but instead is cheating.

2.5 Advanced Translation

We translate the following formulations in the following ways:
1) “Neither P nor Q” = ¬P∧¬Q
2) “Not both P and Q” = ¬(P∧Q)
3) “P only if Q” = P→Q
4) “P even if Q” = P, or = P∧(Q∨¬Q)
5) “not-P unless Q” = ¬P∨Q
6) “P unless Q” = ¬(P↔Q), or = (P∨Q)∧¬(P∧Q)

Ch.3: Truth Tables

3.1 Valuations (Truth-Value Assignments)

We can find the truth values of complex propositions on the basis of the value assignments for the atomic formula. We begin with the operators with the least scope and work progressively toward the main operator, whose truth value gives us that of the whole proposition.

Z∧¬J

v(Z) = T

v(J) = F

3.2 Truth Tables for Propositions

We can construct truth-table evaluations for all truth value assignments of a proposition. First we establish all possible value assignment combinations for the individual terms. Then we fill-out the atomic formula values within the proposition. Next we determine the values for the operators, working from those with the least scope progressively to the one with the greatest scope, which gives the value for the whole proposition.

(P∨¬P)→Q

3.3 Truth Tables Analysis of Propositions

We can use a decision procedure to determine whether a singular proposition is a tautology, a contradiction, or a contingency. It is a tautology if it is true under all value assignments; it is a contradiction if it is false under all value assignments, and it is a contingency if it is either true or false, depending on what the value assignments are.

Tautology

P→(Q→P)

Contradiction

¬P∧(Q∧P)

Contingency

P∧(Q→P)

3.4 Truth Tables Analysis of Sets of Propositions

We can use decision procedures with truth tables to determine whether or not a set of propositions are equivalent or consistent. If the truth table for a set of propositions shows them each to have identical truth values for any truth assignments, then they are logically equivalent. And they are not equivalent otherwise. Another way to conduct this test is to combine the propositions into one larger proposition using the biconditional operator. If the new proposition is a tautology, then the original two propositions are logically equivalent. A set of propositions are consistent if there is at least one value assignment that makes them all true. So on the truth table, we look for at least one line where all the propositions in question have the value true, and that tells us they are consistent. The propositions are inconsistent if no truth value assignment makes all the propositions jointly true. This can also be tested by combining a pair of propositions with a conjunction. If the new proposition is a contradiction, then the original propositions are inconsistent.

Equivalence (tested by comparison)

P→Q
Q∨¬P

Equivalence (tested by making biconditional)

P→Q

Q∨¬P

(P→Q) ↔ (Q∨¬P)

Consistency (tested by comparison)

P→Q
Q∨P
P↔Q

Inconsistency (tested by comparison)

(P∨Q)
¬(Q∨P)

Inconsistency (tested by conjunction)
(P∨Q)
¬(Q∨P)

3.5 The Material Conditional Explained (Optional)

It may not be immediately obvious why the material conditional has its particular truth evaluation. However, the reasons for it come to light when we see that the other possible evaluations would ascribe properties or behaviors to the conditional that our intuition tells us it should not have.

3.6 Truth Table Analysis of Arguments

There are a couple ways we can use truth tables to test for the validity of arguments. (a) We look for a row where all the premises are true and the conclusion false. If there is such a row, it is invalid. And it is valid otherwise. (b) We convert the argument into a set of propositions with the premises left intact but the conclusion is negated. If that set of propositions is inconsistent, that is, if there is no row where they are all true, then the original argument is valid. However, if that set is consistent, that is, if there is at least one row where they are all true, then the original argument is invalid.

Validity (tested by looking for a row where all premises are true and the conclusion, false. [below: there are none, so it is valid])

P→Q, ¬Q ⊢ ¬P

Validity (tested by looking for row where all premises are true and the conclusion, false. [below: there is in line 3, so it is invalid])

P → Q, Q ⊢ P

Validity (tested by negating the conclusion, making all just a set of propositions, and testing for inconsistency. [Below: since there is no valuation where all are true, the set is inconsistent, and thus the original argument with the unnegated conclusion is valid])

P → Q, P ⊢ Q

{P→Q, P, ¬Q}

3.7 Short Truth Table Test for Invalidity

There is a more efficient way to show the invalidity of an argument than merely filling out the full truth table. This technique is called “forcing”. We first evaluate the conclusion as false and the premises as true. Then, we work backward, finding the assignments for each component term that will make each premise true. If such assignments can be found, then the argument is invalid.

P→Q, R∧¬Q ⊢ Q

Ch.4: Truth Trees

4.1 Truth-Tree Setup and Basics in Decomposition

We will conduct decision procedures using truth-trees. There are three steps in this method: (a) set up the tree for decomposition, (b) decompose decomposable propositions into a non-decomposable form using the decomposition rules, and (c) analyze the completed truth-tree for certain logical properties. The trees are structured with three columns. The left one enumerates the line. The center one gives the proposition. And the right one lists the decomposition rule along with the line where the proposition we are decomposing was previously located. There are nine types of propositions that we can decompose: conjunction, disjunction, conditional, biconditional, negated conjunction [¬(P∧R)], negated disjunction [¬(P∨R)], negated conditional [¬(P→R)], negated biconditional [¬(P↔R)], and double negation. There are three sorts of decompositional patterns: (a) stacking, for when the proposition is true under just one truth-value assignment, (b) branching, for when the proposition is false under just one truth-value assignment, or (c) stacking and branching, for when the proposition is true under two truth-value assignments and false under two truth-value assignments.

Step 1: Set up the truth-tree for decomposition

(R∧¬M), R∧(W∧¬M)

Decomposable proposition types

Stacking Rule structure (its operator makes them true under only one assignment, meaning that they must both have some certain value)

Branching Rule structure (its operator makes them false under only one assignment, meaning that either one should have some certain value)

Branching and Stacking Rule structure (its operator makes them true under two assignments and false under two other assignments, thus it should have either of two pairings of certain values)

4.2 Truth-Tree Decomposition Rules

Using the conjunction decomposition rule (∧D), we can decompose a conjunction in a truth tree by stacking the conjuncts in new rows, like this:

We make a check mark on any proposition that we have decomposed. When we apply the disjunction decomposition rule (∨D) we decompose a disjunction by making two branches and placing one disjunct under each, like this:

A tree is fully decomposed when we have decomposed all decomposable propositions in it. A tree branch consists of all the propositions found when we begin with a proposition at the bottom and follow upward through the tree. A branch is a closed branch when it contains a proposition ‘P’ and its literal negation ‘¬P,’ and we place an X marking at the bottom of the branch. A branch is a completed open branch when it is completely decomposed and yet does not contain such a contradiction. At its bottom we place an 0 marking. We have a completed open tree only if it has at least one completed open branch. However, we have a closed tree when all branches are closed. According to the decomposition descending rule, we decompose a proposition under every open branch that descends from that proposition.

Conjunction decomposition rule (∧D)

Disjunction decomposition rule (∨D)

Branches

Closed branch (contains a formula and its negation)

Open branch (does not have contradiction)

Completed open branch (does not have contradiction, and fully decomposed [Below: left branch])

Completed open tree (has at least one completed open branch) [see above]

Closed tree (all branches are closed)

Decomposition descending rule (when decomposing a proposition, decompose it under all branches descending from that proposition)

4.3 The Remaining Decomposition Rules

With all the truth-tree decomposition rules covered, we may place them together in one table.

Conditional Decomposition (→D)

Biconditional Decomposition (↔D)

Negated Conjunction Decomposition (¬∧D)

Negated Disjunction Decomposition (¬∨D)

Negated Conditional Decomposition (¬→D)

Negated Biconditional Decomposition (¬↔D)

Double Negation Decomposition (¬¬D)

4.4 Basic Strategies

In order to decompose a proposition in a truth-tree as efficiently as possible, we should follow certain rules, namely:

Strategic rule 1: Use no more rules than needed.
Strategic rule 2: Use rules that close branches.
Strategic rule 3: Use stacking rules before branching rules.
Strategic rule 4: Decompose more complex propositions before simpler propositions.

For the first rule, if for example we just need to know if the tree is open, we only need to find one completed open branch, and we can leave the rest unfinished. For the second rule, we can minimize the amount of decompositions by closing off branches as early as possible. For the third rule, we minimize the decompositions by stacking before branching; for, if we branch first, we have to repeat more operations, as we have more branches along which to stack formula. And for the fourth rule, by decomposing complex propositions first, we do not have to repeat complex ones further down, as we multiply the branches as we go.

4.5 Truth-Tree Walk Through

By using the four rules of truth-tree decomposition that Agler lays out, we can more efficiently decompose a tree, as seen in a number of examples. In certain cases, we will not even need to decompose all the propositions, on account of the fact that we were able to close all branches as early as possible.

4.6 Logical Properties of Truth Trees

By using truth trees we can test for logical properties of individual propositions, sets of propositions, and arguments.

Consistency: a set of propositions is consistent if their truth tree is completed open, that is to say, if we find at least one open branch.

Inconsistency: a set of propositions is inconsistent when their truth tree is closed, that is to say, when all its branches are closed.

Tautology: a singular proposition is a tautology when the truth tree for its negation is closed.

Contradiction: a singular proposition is a contradiction, when its truth tree is closed.

Contingency: supposing that we have already determined that a singular proposition is not a tautology, then it is a contingency rather than a contradiction, if its truth tree is open. In other words, if the neither the tree for the proposition nor for its negation is closed, then it is a contingency.

Equivalence: two propositions are equivalent if the tree for their negated biconditional combination is closed.

Validity: an argument is valid if the set of propositions made of the premises and the negated conclusion makes a closed tree.

On a completed open branch, we can determine truth values for atomic formula which together will make the original formulation true. Unnegated atomic formula get the value true, and negated atomic formula get the value false.

v(R) = T

v(W) = T

v(M) = F

We ignore closed branches, because they give us inconsistent values.

v(M) = T

v(W) = T

v(R) = T

Sometimes a letter is missing on a branch, in which case it is arbitrary which value it has.

[Valuation set 1 and 2 are for the left branch where the S value is arbitrary. Valuation sets 3 and 4 are for the right branch where the R value is arbitrary. Valuation sets 1 and 4 are redundant and do not need to be restated.]

Consistency. A truth-tree shows a set of propositions to be consistent when it is a completed open tree, that is, if there is at least one completed open branch. [In other words, there is at least one valuation for all the formulas that makes them all true.]

[Below: there is one open branch, so they are consistent.]

[Below: there are no open branches, so they are inconsistent]

Tautology. Iff a formula’s negated form creates a closed tree, then it is a tautology. [A formula is a tautology iff it is true under all valuations.]

[Below: the formula’s negation creates a closed tree and is thus a tautology.]

P∨¬P

[Below: the negated form creates an open tree, so it is not a tautology.]

P→(Q∧¬P)

Contradiction. Iff a formula’s truth tree is closed (that is, when all branches close), it is a contradiction. [A formula is a contradiction iff it is false under all valuations.]

Contingency. Iff a formula’s truth-tree is not closed and if the tree for the formula’s negated form is not closed, then it is a contingency. [A formula is a contingency iff it is neither always false under all valuations nor always true.] [Below: we determined this formula above to not be a tautology. We now test it for contradiction and contingency. Since it makes an open tree, that means it is not a contradiction, and since it is not also a tautology, it is a contingency.]

P→(Q∧¬P)

Equivalence. Iff the negated biconditional of two formulas creates a closed tree, then they are equivalent. [Two formula are equivalent if they have identical truth values under every valuation.] [Below: the pair’s negated biconditional creates a closed tree, so they are equivalent.]

P∨¬P

¬(P∧¬P)

Validity. Iff a truth-tree for the premises and negated conclusion is closed, then it is a valid argument. [An argument is valid if it is impossible for its premises to be true and its conclusion false.] [Below: the tree for the premises with the negated conclusion is closed and thus the argument is valid.]

P→Q, P ⊢ Q

Ch.5: Propositional Logic Derivations

5.1 Proof Construction

We can use a natural deduction system in order to make proofs for the conclusions of arguments. Such a system provides derivation rules, which allow us to move forward in a proof by obtaining new propositions on the basis of previously established ones. When a conclusion is provable by means of such a system, we say that the conclusion is a syntactical consequence of, or that that it is syntactically entailed by, the premises. And to signify this we use the turnstile symbol, as for example in this argument: R∨S, ¬S ⊢ R. If we have simply ⊢P, that means there is a proof of P or that P is a theorem. In our proofs, there are three columns. The left column gives the line number. The central column shows the proposition. And the right column gives the justification, which is either that the proposition is a premise, in which case we write ‘P’, or that it is derived from other propositions, in which case we list the line numbers of those other propositions and write the abbreviation for the derivation rule that was used.

5.2 Premises and the Goal Proposition

In a proof, we can for convenience write the goal proposition, which is also the conclusion, next to the ‘P’ for the final premise, in the justification column.

5.3 Intelim Derivation Rules

In a proof we can use derivation rules to derive the conclusion through some number of steps. One set of such rules are introduction and elimination rules, called intelim derivation rules. (introduction-elimination). In some cases we will need to make subproofs that begin with assumed propositions.

In a subproof, we will use our rules to make more derivations. Eventually we can arrive upon a proposition to which we may apply certain other rules that will allow us to make a derivation in an outer proof. Upon doing so we discharge the assumption (rendering it inoperable) thereby closing the subproof. There can be subproofs within other subproofs. We can use propositions within one layer of proof, so long as it is one unbroken subproof. And we can import into a subproof any propositions from outer layers to the left.

However, we cannot export propositions from a subproof to another separate subproof at the same level, nor can we export a proposition from a subproof into layers to the left of it.

However, certain derivation rules allow us to make a derivation in an outer level of a proof on the basis of what was derived in a subproof one level to the right of it. The intelim derivation rules are summarized in the following chart:

Conjunction Introduction (∧I)

W, Q, R ⊢ W∧R

Conjunction Elimination (∧E)

(A→B)∧(C∧D) ⊢ D

Conditional Introduction (→I)

Q ⊢ P→Q

Conditional Elimination (→E)

(A∨Β)→C, A, A∨B ⊢ C

Reiteration (R)

Negation Introduction (¬I) and Negation Elimination (¬E)

Disjunction Introduction (∨I)

Disjunction Elimination (∨E)

Biconditional Elimination and Introduction (↔E and ↔I)

P→Q,Q→P ⊢ P↔Q

5.4 Strategies for Proofs

Certain guidelines can enable us to figure out proofs more effectively. There are two rules that do not involve assumptions, called strategic proof rules (SP#). They are:

SP#1(E)

First, eliminate any conjunctions with ‘∧E,’ disjunctions with ‘∨E,’ conditionals with ‘→E,’ and biconditionals with ‘↔E.’ Then, if necessary, use any necessary introduction rules to reach the desired conclusion.

SP#2(B)

First, work backward from the conclusion using introduction rules (e.g., ‘∧I,’ ‘∨I,’‘ →I,’ ‘↔I’). Then, use SP#1(E).

And there are four rules that do involve assumptions:

SA#1(P,¬Q)

If the conclusion is an atomic proposition (or a negated proposition), assume the negation of the proposition (or the non-negated form of the negated proposition), derive a contradiction, and then use ‘¬I’ or ‘¬E.’

SA#2(→)

If the conclusion is a conditional, assume the antecedent, derive the consequent, and use ‘→I.’

SA#3(∧)

If the conclusion is a conjunction, you will need two steps. First, assume the negation of one of the conjuncts, derive a contradiction, and then use ‘¬I’ or ‘¬E.’ Second, in a separate subproof, assume the negation of the other conjunct, derive a contradiction, and then use ‘¬I’ or ‘¬E.’ From this point, a use of ‘∧I’ will solve the proof.

SA#4(∨)

If the conclusion is a disjunction, assume the negation of the whole disjunction, derive a contradiction, and then use ‘¬I’ or ‘¬E.’

SP#1(E) [First, eliminate any conjunctions with ‘∧E,’ disjunctions with ‘∨E,’ conditionals with ‘→E,’ and biconditionals with ‘↔E.’ Then, if necessary, use any necessary introduction rules to reach the desired conclusion.]

P→(R∧M), (P∧S)∧Z ⊢ R

SP#2(B) [First, work backward from the conclusion using introduction rules (e.g., ‘∧I,’ ‘∨I,’‘ →I,’ ‘↔I’). Then, use SP#1(E).]

P→R, Z→W, P ⊢ R∨W

SA#1(P,¬Q) [If the conclusion is an atomic proposition (or a negated proposition), assume the negation of the proposition (or the non-negated form of the negated proposition), derive a contradiction, and then use ‘¬I’ or ‘¬E.’]

P→Q, ¬Q ⊢ ¬P

SA#2(→) [If the conclusion is a conditional, assume the antecedent, derive the consequent, and use ‘→I.’]

R ⊢ P→R

SA#3(∧) [If the conclusion is a conjunction, you will need two steps. First, assume the negation of one of the conjuncts, derive a contradiction, and then use ‘¬I’ or ‘¬E.’ Second, in a separate subproof, assume the negation of the other conjunct, derive a contradiction, and then use ‘¬I’ or ‘¬E.’ From this point, a use of ‘∧I’ will solve the proof.]

¬(P∨Q) ⊢ ¬P∧¬Q

SA#4(∨) [If the conclusion is a disjunction, assume the negation of the whole disjunction, derive a contradiction, and then use ‘¬I’ or ‘¬E.’]

¬(¬P∧¬Q) ⊢ P∨Q

5.5 Additional Derivation Rules (PD+)

The set of 11 “intelim” propositional derivation rules, called PD, just by themselves can lead to lengthy proofs, so to them we add six more rules, to make a system called PD+. The following chart shows all of PD+, with the new ones being 13-17.

Disjunctive Syllogism (DS)

P∨Q, ¬Q ⊢ P

Modus Tollens (MT)

(P∧Z)→(Q∨Z), ¬(Q∨Z) ⊢ ¬(P∧Z)

Hypothetical Syllogism (HS)

P→Q, Q→R ⊢ P→R

[no image for this]

Double Negation (DN)

[no image/example]

De Morgan’s Laws (DeM)

¬(P∧Q) ⊢ ¬P∨¬Q

¬(P∨Q) ⊢ ¬P

Implication (IMP)

¬(P→Q) ⊢ ¬Q

5.6 Additional Derivation Strategies

After revising our strategic rules for proof solving, they are in their entirety the following [the first three being this section’s modifications]:

SP#1(E+): First, eliminate any conjunctions with ‘∧E,’ disjunctions with DS or ‘∨E,’ conditionals with ‘→E’ or MT, and biconditionals with ‘↔E.’ Then, if necessary, use any introduction rules to reach the desired conclusion.

SP#2(B): First, work backward from the conclusion using introduction rules (e.g., ‘∧I,’‘∨I,’‘→I,’‘↔I’). Then, use SP#1(E).

SP#3(EQ+): Use DeM on any negated disjunctions or negated conjunctions, and then use SP#1(E). Use IMP on negated conditionals, then use DeM, and then use SP#1(E).

SA#1(P,¬Q): If the conclusion is an atomic proposition (or a negated proposition), assume the negation of the proposition (or the non-negated form of the negated proposition), derive a contradiction, and then use ‘¬I’ or ‘¬E.’

SA#2(→): If the conclusion is a conditional, assume the antecedent, derive the consequent, and use ‘→I.’

SA#3(∧): If the conclusion is a conjunction, you will need two steps. First, assume the negation of one of the conjuncts, derive a contradiction, and then use ‘¬I’ or ‘¬E.’ Second, in a separate subproof, assume the negation of the other conjunct, derive a contradiction, and then use ‘¬I’ or ‘¬E.’ From this point, a use of ‘∧I’ will solve the proof.

SA#4(∨): If the conclusion is a disjunction, assume the negation of the whole disjunction, derive a contradiction, and then use ‘¬I’ or ‘¬E.’

SP#1(E+) [First, eliminate any conjunctions with ‘∧E,’ disjunctions with DS or ‘∨E,’ conditionals with ‘→E’ or MT, and biconditionals with ‘↔E.’ Then, if necessary, use any introduction rules to reach the desired conclusion. ]

P→Q, ¬Q, P∨R, R→W ⊢ W

SP#3(EQ+) [Use DeM on any negated disjunctions or negated conjunctions, and then use SP#1(E). Use IMP on negated conditionals, then use DeM, and then use SP#1(E).]

¬[P∨(R∨M)], ¬M→T ⊢ T

Ch.6: Predicate Language, Syntax, and Semantics

6.1 The Expressive Power of Predicate Logic

While everything in the language of propositional logic (PL) can be expressed in English, not everything in English can be expressed in PL. In PL, propositions are treated as whole units (symbolized as singular letters) without regard to logical properties internal to the sentences, as for example between subject and predicate and with respect to quantification. Thus we will examine a more expressive language of predicate logic (RL), which is a logic of relations.

[In PL, for the argument:

All humans are mortal.

Socrates is a human.

Therefore Socrates is a mortal.

Each line gets a letter, but the inference cannot be represented.]

6.2 The Language of RL

There are five elements in the language of predicate logic (RL).

1) Individual constants or names of specific items, and they are represented with lower case letters spanning from ‘a’ to ‘v’ (and expanded with subscript numerals).

2) n-place predicates, which predicate a constant or variable, or they relate constants or variables to one another. They are represented with capital letters from ‘A’ to ‘Z’ (and expanded with subscript numerals).

3) Individual variables, which can be substituted by certain constants, and they are represented with lowercase (often italicized) letters spanning from ‘w’ to ‘z’ (and expanded with subscript numerals).

4) Truth functional operators and scope indicators from the language of propositional logic (PL), namely, ¬, ∧, ∨, →, ↔, (, ), [, ], {, }.

5) Quantifiers, which indicate what portion of the set of items that can stand for a variable are to be taken into consideration in a part of a formulation. When indicating that the full portion is to be considered in some instance of a variable in a formula, we use the universal quantifier ∀. We can understand it to mean “all,” “every,” and “any.” But if we are to consider only a portion of the possible items that can substitute in for a variable, then we use the existential quantifier ∃, which can mean “some,” “at least one,” and the indefinite determiner “a.”

The purpose of the language of predicate logic is to express logical relations holding within propositions. There is the simple relation of predication to a subject, which would be a one-place predicate. There are also the relations of items within a predicate, as in “... is taller than ...”, which in this case is a two-place predicate, and so on. To say John is tall we might write Tj, and to write John is taller than Frank we could write Tjf. The number individuals that some predicate requires to make a proposition is called its adicity. And when all the names have been removed from a predicational sentence, what remains is called an unsaturated predicate or a rheme. We might also formulate those above propositions using variables rather than constants, as in Tx and Txy. When dealing with variables, the domain of discourse D is the set of items that can be substituted for the variables in question, and this possible substitutions are called substitution instances for variables or just substitution instances. The domain is restricted if it contains only certain things and it is unrestricted if it includes all things. We may either explicitly stipulate what the domain is, which is common in formal logic, or the context of a discussion might implicitly determine the domain, and this domain can fluidly change as the discussion progresses. Also, in these cases with variables, we might further specify the quantities of the variables that we are to consider. So to say, everyone is taller than Frank we might write, (∀x)Txf. Someone is taller than Frank might be (∃x)Txf. Quantifiers have a scope in the formulation over which they apply. They operate just over the propositional contents to the immediate right of the quantifier or just over the complex propositional contents to the right of the parentheses.

Individual Constants (Names) and n-Place Predicates.

John is standing between Frank and Marry.

j = John

f = Frank

m = Mary

S = __ is standing between __ and __

Sjfm

Domain of Discourse, Individual Variables, and Quantifiers.

The domain of discourse D is all of the objects we want to talk about or to which we can refer.

D: positive integers

Individual variables are placeholders whose possible values are the individuals in the domain of discourse.

Bxyz = x is between y and z.

Universal quantifier: ∀. In English, “all,” “every,” and “any.”

(∀x)Mx

Everyone is mortal.

For every x, x is mortal.

All x’s are mortal.

For any x, x is mortal.

Every x is mortal.

Existential quantifier: ∃. In English, “some,” “at least one,” and the indefinite determiner “a.”

(∃x)Hx

Someone is happy.

For some x, x is happy.

Some x’s are happy.

For at least one x, x is happy.

There is an x that is happy.

Parentheses and Scope of Quantifiers

The ‘∀’ and ‘∃’ quantifiers operate over the propositional contents to the immediate right of the quantifier or over the complex propositional contents to the right of the parentheses. (Agler 254, quoting)

(∃x)Fx

[Above: ∃x ranges over Fx]

¬(∃x)(Fx∧Mx)

[Above: ¬(∃x) ranges over (Fx∧Mx)]

¬(∀x)Fx∧(∃y)Ry

[Above: ¬(∀x) ranges over Fx and (∃y) rangers over Ry]

(∃x)(∀y)(Rx↔My)

[Above: (∃x) ranges over (∀y)(Rx↔My) and (∀y) ranges over (Rx↔My)]

6.3 The Syntax of RL

In the language of predicate logic (RL), variables are either bound or free. They are bound if they fall under the scope of a quantifier that is quantifying specifically for that particular variable, and it is a free variable otherwise. An open sentence or an open formula is one with an n-place predicate P followed by n terms, where at least one of those variables is free. However, a closed sentence or a closed formula is one with an n-place predicate P followed by n terms, where none of those terms are free variables. The main operator in a well formed formula (wff) in RL is the one with the greatest scope, which means that the one that falls under no other operator’s scope is the main one. We consider the quantifiers as operators. Thus in (∃x)(Px∧Qx) the main operator is ∃x, because all the rest of the formula falls under the quantifier’s scope, and in ¬(∃x)(Px∧Qx) the main operator is the negation, because the quantifier falls under its scope, and the rest of the formula falls under the quantifier’s scope. And there are five rules that determine a wff in RL: (i) An n-place predicate ‘P’ followed by n terms (names or variables) is a wff. (ii) If ‘P’ is a wff in RL, then ‘¬P’ is a wff. (iii) If ‘P’ and ‘Q’ are wffs in RL, then ‘P∧Q,’ ‘P∨Q,’ ‘P→Q,’ and ‘P↔Q’ are wffs. (iv) If ‘P’ is a wff in RL containing a name ‘a,’ and if ‘P(x/a)’ is what results from substituting the variable x for every occurrence of ‘a’ in ‘P,’ then ‘(∀x)P(x/a)’ and ‘(∃x)P(x/a)’ are wffs, provided ‘P(x/a)’ is not a wff. (v) Nothing else is a wff in RL except that which can be formed by repeated applications of (i) to (iv).

Free and Bound Variables

(∀x)(Fx→Bx)∨Wx

[Above: Wx does not fall under the scope of the quantifier and thus its variable is free.]

(∃z)(Pxy∧Wz)

[Above: only the z of Wz is bound.]

Main Operator in Predicate Wffs

[The main operator has the greatest scope.]

(∃x)(Px∧Qx)

[Above: (∃x) is the main operator.]

(∃x)(Px)∧(∃x)(Qx)

[Above: ∧ is the main operator.]

¬(∃x)(Px∧Qx)

[Above: ¬ is the main operator.]

(∀y)(∃x)(Rx→Py)

[Above: (∀y) is the main operator.]

The Formal Syntax of RL: Formation Rules.

Open formula: An open formula is a wff consisting of an n-place predicate ‘P’ followed by n terms, where one of those terms is a free variable.

Closed formula: A closed formula is a wff consisting of an n-place predicate ‘P’ followed by n terms, where every term is either a name or a bound variable.

Rule (iv): If ‘P’ is a wff in RL containing a name ‘a,’ and if ‘P(x/a)’ is what results from substituting the variable x for every occurrence of ‘a’ in ‘P,’ then ‘(∀x)P(x/a)’ and ‘(∃x)P(x/a)’ are wffs, provided ‘P(x/a)’ is not a wff.

Consider the wff:

Pb

Were we to say that we substitute every instance of the constant ‘b’ with the variable ‘x’, we would write:

P(x/b)

And we would obtain:

Px

It becomes a wff when we add a quantifier:

(∀x)Px

(∃x)Px

6.4 Predicate Semantics

In the language of predicate logic (RL) we will want to give interpretations for constants and for predicate formulations and also to give truth evaluations for well-formed formulas (wffs), including when they involve quantifiers. To do these things, we construct models, which specify the domain as well as the interpretation functions that assign objects in the domain to names, and n-tuples of objects to n-place predicates. On their basis, we valuate truth and falsity for formulas using a function that assigns T for when the named objects are among the tuples in the predicate’s interpretation, and F otherwise. When truth-evaluating quantified wffs in RL, we, intuitively speaking, give a universally quantified formula the value T if all substitutions for the variables make the formula true, and it is F otherwise; and for existentially quantified formulas, if there is at least one substitution that makes the formula true, it is evaluated as T, and F otherwise. For certain technical reasons, the actual procedure cannot involve substituting every possible name or object into the variables. We instead need to test for every object in the domain by thinking of each one being a potential interpretation for a constant, then seeing if these variant interpretations make the formula true or not. Despite the differences in notation, however, the more proper procedure conducts basically the same operation as the intuitive one. The evaluation rules for wffs in RL are the following:

1 v(Ra_i) = T if and only if the interpretation of ‘a_i’ is in ‘R.’

2 v(¬P) = T iff v(P) = F

v(¬P) = F iff v(P) = T

3 v(P∧Q) = T iff v(P) = T and v(Q) = T

v(P∧Q) = F iff v(P) = F or v(Q) = F

4 v(P∨Q) = T iff either v(P) = T or v(Q) = T

v(P∨Q) = F iff v(P) = F and v(Q) = F

5 v(P→Q) = T iff either v(P) = F or v(Q) = T

v(P→Q) = F iff v(P) = T and v(Q) = F

6 v(P↔Q) = T iff either v(P) = T and v(Q) = T or v(P) = F and v(Q) = F

v(P↔Q) = F iff either v(P) = T and v(Q) = F or v(P) = F and v(Q) = T

7 v(∀x)P = T iff for every name ‘a’ not in ‘P’ and every a-variant interpretation ‘P(a/x) = T.’

v(∀x)P = F iff for at least one ‘a’ not in ‘P’ and at least one a-variant interpretation ‘P(a/x) = F.’

8 v(∃x)P = T iff for at least one name ‘a’ not in ‘P’ and at least one a-variant interpretation ‘P(a/x) = T’.

v(∃x)P = F iff for every name ‘a’ not in ‘P’ and every a-variant interpretation ‘P(a/x) = F.

6.5 Translation from English to Predicate Logic

To translate between the language of predicate logic RL and colloquial English, we need to make a translation key to assign symbols to text, and we would follow the pattern given in this table:

6.6 Mixed and Overlapping Quantifiers

There is no simple and universally reliable procedure for translating all English sentences with quantifiers into the language of predicate logic (RL). Agler offers four steps that can help us make translations [quoting:] {1} Identify and symbolize any English expressions that represent quantifiers (and their bound variables) and propositional operators. {2} Translate any ordinary language predicates into predicates of RL. {3} Use the quantifiers from step 1 and the predicates from step 2 and represent the proposition that (1) expresses. {4} Read the predicate logic wff in English and check to see whether it captures the meaning of the sentence undergoing translation. When we have two quantifiers and they are both the same kind, their order will not matter. However, if one is universal and the other is existential, their order can change the meaning of the proposition. Here are four scenarios that illustrate:

(∀x)(∃y)Lxy “Crush scenario”

Everyone loves someone.

[For any person, that person loves one (and/or another) person.]

(∃y)(∀x)Lxy “Santa Claus scenario”

Someone is loved by everyone.

[There is one (and/or another) person who is loved by all other people.]

(∀y)(∃x)Lxy “Stalker scenario”

Everyone is loved by someone.

[Each person is loved by at least one (and/or another) person.

(∃x)(∀y)Lxy “Loving God scenario”

Someone loves everyone.

[One (and/or another) person loves every other person.]

Ch.7: Predicate Logic Trees

7.1 Four New Decomposition Rules

We can decompose quantified propositions of the language of predicate logic (RL) into logic trees, by using additional rules.

Negated Existential Decomposition (¬∃D)	Negated Universal Decomposition (¬∀D)
¬(∃x)P✔ (∀x)¬P	¬(∀x)P✔ (∃x)¬P

[Note that when the negation is moved, if there is a quantifier to the right, the negation is moved to the quantifier rather than jumping over to the proposition further to the right. So ¬(∃x)(∀y)Pxy becomes (∀x)¬(∀y)Pxy and not (∀x)(∀y)¬Pxy.]

Existential Decomposition
(∃D)

Universal Decomposition (∀D)

(∃x)P✔
P(a/x)

where ‘a’ is an individual constant (name) that does not previously occur in the branch.

(∀x)P
P(a/x)

where ‘a’ is any individual constant
(name).

[Note that the universal quantifier is not checked, because for infinite domains, not all possible substitutions can be given in the tree.] The universal decomposition is further specified as:

Universal Decomposition (∀D)

(∀x)P
P(a . . . v/x)

Consistently replace every bound x with any individual constant (name) of your choosing (even if it already occurs in an open branch) under any (not necessarily both) open branch of your choosing.

Four kinds of decomposable propositions.

Four Decomposable Proposition Types

Existential                   (∃x)P

Universal                    (∀x)P

Negated existential      ¬(∃x)P

Negated universal        ¬(∀x)P

Negated Existential and Universal Decomposition.

Negated Existential
Decomposition (¬∃D)

Negated Universal
Decomposition (¬∀D)

¬(∃x)P✔
(∀x)¬P

¬(∀x)P✔
(∃x)¬P

1
¬(∃x)Px✔

P

2
¬(∀y)Wy✔

P

3
(∀x)¬Px

1¬∃D

4
(∃y)¬Wy

2¬∀D

Existential and Universal Decomposition.

Existential Decomposition
(∃D)

Universal Decomposition (∀D)

(∃x)P✔
P(a/x)

where ‘a’ is an individual constant (name) that does not previously occur in the branch.

(∀x)P
P(a/x)

where ‘a’ is any individual constant
(name).

According to (∃D) and (∀D), an individual constant (name) is substituted for a bound variable in a quantified expression. This procedure is symbolized as ‘P(a/x)’ (i.e., replace x with ‘a’). Thus, if there is a quantified expression of the form ‘(∀x)P’ or ‘(∃x)P,’ a substitution instance of ‘P(a/x)’ replaces x’s bound by the quantifier with ‘a.’ (quoting Agler 286)

Universal Decomposition (∀D)

(∀x)P
P(a . . . v/x)

Consistently replace every bound x with any individual constant (name) of your choosing (even if it already occurs in an open branch) under any (not necessarily both) open branch of your choosing.

1
(∀x)(Px→Rx)
P

2
Pa∨Ra✔
P

3
/               \
Pa              Ra

2∨D

4
Pa→Ra         Pa→Ra
1∀D

Existential Decomposition
(∃D)

(∃x)P✔
P(a/x)

where ‘a’ is an individual constant (name) that does not previously occur in the branch.

1
(∃x)Px✔
P

2
Pa
P

3
Pb
1∃D

7.2 Strategies for Decomposing Trees

To decompose propositions in the language of predicate logic (RL) the most efficiently in truth trees, we should follow these rules.

Strategic Rules for Decomposing Predicate Truth Trees

1. Use no more rules than needed.

2. Decompose negated quantified expressions and existentially quantified expressions first.

3. Use rules that close branches.

4. Use stacking rules before branching rules.

5. When decomposing universally quantified propositions, use constants that already occur in the branch.

6. Decompose more complex propositions before simpler propositions.

7.3 Logical Properties

Truth trees can determine logical properties of singular propositions, sets of propositions, and arguments in the language of predicate logic (RL). To test a proposition to see if it is a contradiction, we see if it makes a closed tree. If and only if it does is it a contradiction. To test a proposition to see if it is a tautology, we make a tree for its negation. If and only if it makes a closed tree is the original proposition a tautology. If it fails both these tests, it is a contingency. To check for the consistency of sets of propositions, we see if their tree has at least one open branch. If so, they are consistent. If instead the tree is closed, then they are inconsistent. To test for the validity of an argument, we negate the conclusion and make a tree for the full set of sentences. If they determine a closed tree, the original argument was valid. If it determines a tree with at least one completed open branch, it is invalid.

Completed open branch: A branch is a completed open branch if and only if (1) all complex propositions that can be decomposed into atomic propositions or negated atomic propositions are decomposed; (2) for all universally quantified propositions ‘(∀x)P’ occurring in the branch, there is a substitution instance ‘P(a/x)’ for each constant that occurs in that branch; and (3) the branch is not a closed branch.

1	(∀x)(¬Px→¬Rx)	P
2	(∀x)(Rx→Px)	P
3	¬Pa→¬Ra✔	1∀D
4	Ra→Pa✔ / \	2∀D
5	¬¬Pa ¬Ra / \ / \	3→D
6	¬Ra Pa ¬Ra Pa O O O O	4→D

Closed tree: A tree is a closed tree if and only if all branches close.

Closed branch: A branch is a closed branch if and only if there is a proposition and its literal negation (e.g., ‘P’ and ‘¬P’). (quoting Agler 294)

1	(∀x)(Px→Qx)	P
2	(∃x)(Px∧¬Qx)✔	P
3	Pa→Qa✔	1∀D
4	Pb∧¬Qb✔	2∃D
5	Pb	4∧D
6	¬Qb / \ / \	4∧D
7	¬Pa Qa	3→D
8	Pb→Qb Pb→Qb / \ / \	1∀D
9	¬Pb Qb ¬Pb Qb X X X X	8→D

“Consistency: A set of propositions ‘{A, B, C, ..., Z}’ is consistent in RL if and only if there is at least one interpretation such that all of the propositions in the set are true.” (Agler 296)

to show that ‘{(∀x)Px, (∃x)Rx}’ is consistent in RL involves showing that there is at least one interpretation in a model where v(∀x)Px = T and v(∃x)Rx = T. Here is an example of such a model:

D = positive integers

P = {x | x is greater than 0}

R = {x | x is even}

(Agler 296)

“Thus, the presence of a completed open branch tells us that we can construct a model such that every proposition in the stack is true” (Agler 297).

[“Completed open branch: A branch is a completed open branch if and only if (1) all complex propositions that can be decomposed into atomic propositions or negated atomic propositions are decomposed; (2) for all universally quantified propositions ‘(∀x)P’ occurring in the branch, there is a substitution instance ‘P(a/x)’ for each constant that occurs in that branch; and (3) the branch is not a closed branch.”]

1

(∃x)Px

P

2

Pa

P

3

Pb

O

1∃D

Inconsistency: A set of propositions ‘{P, Q, R, ..., Z}’ is shown by the truth-tree method to be inconsistent if and only if a tree of the stack of ‘P,’ ‘Q,’ ‘R,’ . . ., ‘Z’ is a closed tree; that is, all branches close.

(∀x)(Px→Rx), ¬(∀x)(¬Rx→¬Px)

1

(∀x)(Px→Rx)

P

2

¬(∀x)(¬Rx→¬Px)✔
P

3

(∃x)¬(¬Rx→¬Px)✔

2¬∀D

4

¬(¬Ra→¬Pa)

3∃D

5

Pa→Ra✔

1∀D

6

¬Ra

4¬→D

7

¬¬Pa✔

4¬→D

8

Pa

/                  \

7¬¬D

9

¬Pa                    Ra

X                      X

5→D

“the truth-tree method can be used to determine whether a proposition ‘P’ is a tautology, contradiction, or contingency. In testing ‘P’ to see if it is a tautology, begin the tree with ‘¬P.’ If the tree closes, you know that it is a tautology. If the tree is open, then ‘P’ is either a contradiction or a contingency. Similarly, in testing ‘P’ to see if it is a contradiction, begin the tree with ‘P.’ If the tree closes, you know that it is a contradiction. If the tree is open, then ‘P’ is either a tautology or a contingency. Lastly, if the truth-tree test shows that ‘P’ is neither a contradiction nor a tautology, then ‘P’ is a contingency” (Agler 147).

(∃x)¬(∀y)[Px→(Qx∨¬Ry)]

[Below: There is at least one completed open branch, so it is not a contradiction.]

1
(∃x)¬(∀y)[Px→(Qx∨¬Ry)]✔
p

2

¬(∀y)[Pa→(Qa∨¬Ry)]✔

1∃D

3

(∃y)¬[Pa→(Qa∨¬Ry)]✔

2¬∀D

4

¬[Pa→(Qa∨¬Rb)]✔
3∃D

5

Pa

4¬→D

6

¬(Qa∨¬Rb)✔

4¬→D

7

¬Qa

6¬∨D

8

¬¬Rb

6¬∨D

[Below: Since the above tree is not closed, the original form is not a tautology. Since it is neither a contradiction nor a tautology, it is therefore a contingency.]

1	¬(∃x)¬(∀y)[Px→(Qx∨¬Ry)]✔	P
2	(∀x)¬¬(∀y)[Px→(Qx∨¬Ry)]✔	1¬∃D
3	¬¬(∀y)[Pa→(Qa∨¬Ry)]✔	2∀D
4	(∀y)[Pa→(Qa∨¬Ry)]	3¬¬D
5	Pa→(Qa∨¬Ra) / \	4∀D
6	¬Pa Qa∨¬Ra✔ O / \	5→D
7	Qa ¬Ra O O	6∨D

Equivalence: A pair of propositions ‘P’ and ‘Q’ is shown by the truth-tree method to be equivalent if and only if the tree of the stack of ‘¬(P↔Q)’ determines a closed tree; that is, all branches for ‘¬(P↔Q)’ close.

(∀x)Px

¬(∃x)Px

[Below: The negated biconditional makes an open tree and thus they are not equivalent.]

1

¬[(∀x)Px↔¬(∃x)Px]✔

/                            \

P

2

                    (∀x)Px                ¬(∀x)Px

1¬↔D

3

               ¬¬(∃x)Px✔             ¬(∃x)Px

1¬↔D

4
                    (∃x)Px✔
3¬¬D

5
                         Pa
4∃D

6
                         Pa
                          O
2∀D

(∀x)¬(Px∨Gx)

(∀y)(¬Py∧¬Gy)

[Below: Their negated biconditional makes a closed tree, and thus they are equivalent.]

1	¬{[(∀x)¬(Px∨Gx)]↔[(∀y)(¬Py∧¬Gy)]}✔ / \	P
2	(∀x)¬(Px∨Gx) ¬(∀x)¬(Px∨Gx)	1¬↔D
3	¬(∀y)(¬Px∧¬Gx)✔ (∀y)(¬Px∧¬Gx)	1¬↔D
4	(∃y)¬(¬Px∧¬Gx)✔ \|	3¬∀D
5	¬(¬Pa∧¬Ga)✔ \| / \ \|	4∃D
6	¬¬Pa✔ ¬¬Ga✔ \|	5¬∧D
7	Pa Ga \|	6¬¬D
8	¬(Pa∨Ga)✔ ¬(Pa∨Ga)✔ \|	2∀D
9	¬Pa ¬Pa \|	8¬∨D
10	X ¬Ga \| X \|	8¬∨D
11	(∃x)¬¬(Px∨Gx)✔	2¬∀D
12	Pa∨Ga✔ / \	11∃D
13	Pa Ga	12∨D
14	¬Pa∧¬Ga ¬Pa∧¬Ga	3∀D
15	¬Pa ¬Ga X X	14∧D

7.4 Undecidability and the Limits of the Predicate Tree Method

When we deal with the problem of universal instantiation causing us to repeat over and over a combination of existential and universal decomposition rules, we can instead apply the following new existential decomposition rule.

Unlike PL, RL is undecidable. That is, there is no mechanical procedure that can always, in a finite number of steps, deliver a yes or no answer to questions about | whether a given proposition, set of propositions, or argument has a property like consistency, tautology, validity, and the like. For some trees, the application of predicate decomposition rules will result in a process of decomposition that does not, in a finite number of steps, yield a closed tree or a completed open branch. (quoting Agler 317-318)

A use of (N∃D) requires that whenever we decompose an existentially quantified proposition ‘(∃x)P,’ we create a separate branch for any substitution instance for any substitution instance P(a₁/x), P(a₂/x), ..., P(a_n/x), already occurring in the branch containing ‘(∃x)P’ and branch a substitution instance ‘P(a_n+1/x)’ that is not occurring in that branch. (quoting Agler 318)

1

(∀x)(∃y)(Pxy)

P

2

(∃y)Pay✔

/                 \

1∀D

3

Paa                  Pab

2N∃D

4

            O                 (∃y)Pby

                             /           |           \

1∀D

5

                              Pba        Pbb       Pbc

                            O              O            .

                                                              .

                                                              .

4N∃D

Ch.8: Predicate Logic Derivations

8.1 Four Quantifier Rules

For the language of predicate logic (RL), there are four proof derivation rules to add to those of propositional logic (PL), namely:

Universal Elimination (∀E)

From any universally quantified proposition ‘(∀x)P,’ we can derive a substitution instance ‘P(a/x)’ in which all bound variables are consistently replaced with any individual constant (name).

(∀x)P
P(a/x)

∀E

Existential Introduction (∃Ι)

From any possible substitution instance ‘P(a/x),’ an existentially quantified proposition ‘(∃x)P’ can be derived by consistently replacing at least one individual constant (name) with an existentially quantified variable.

P(a/x)
(∃x)P

∃I

Universal Introduction (∀Ι)

A universally quantified proposition ‘(∀x)P’ can be derived from a possible substitution instance ‘P(a/x)’ provided (1) ‘a’ does not occur as a premise or as an assumption in an open subproof, and (2) ‘a’ does not occur in ‘(∀x)P.’

P(a/x)
(∀x)P

∀I

Existential Elimination (∃E)

From an existentially quantified expression ‘(∃x)P,’ an expression ‘Q’ can be derived from the derivation of an assumed substitution instance ‘P(a/x)’ of ‘(∃x)P’ provided (1) the individuating constant ‘a’ does not occur in any premise or in an active proof (or subproof) prior to its arbitrary introduction in the assumption ‘P(a/x),’ and (2) the individuating constant ‘a’ does not occur in proposition ‘Q’ discharged from the subproof.

(∃x)P
   | P(a/x)
   | .
   | .
   | .
   | Q
Q

∃E

This new system of derivation is called RD. And corresponding to these are four additional strategic rules for making proofs in RL.

SQ#1(∀E): When using (∀E), the choice of substitution instances ‘P(a/x)’ should be guided by the individual constants (names) already occurring in the proof and any individual constants (names) occurring in the conclusion.
(Agler 328)

SQ#2(∃I): When using (∃I), aim at deriving a substitution instance ‘P(a/x)’ such that a use of (∃I) will result in the desired conclusion. (In other words, if the ultimate goal is to derive ‘(∃x)Px,’ aim to derive a substitution instance of ‘(∃x)Px,’ like ‘Pa,’ ‘Pb,’ ‘Pr,’ so that a use of (∃I) will result in ‘(∃x)Px.’)

SQ#3(∀I): When the goal proposition is a universally quantified proposition ‘(∀x)P,’ derive a substitution instance ‘P(a/x)’ such that a use of (∀I) will result in the desired conclusion.

SQ#4(∃E) Generally, when deciding upon a substitution instance ‘P(a/x)’ to assume for a use of (∃E), choose one that is foreign to the proof.

Universal Elimination (∀E).

Universal Elimination (∀E)

(∀x)P
P(a/x)

∀E

1	(∀x)Px	P
2	Pa	1∀E

Existential Introduction (∃I)

Existential Introduction (∃Ι)

P(a/x)
(∃x)P

∃I

Zr ⊢ (∃x)Zx

1 Zr P

2 (∃x)Zx 1∃I

Universal Introduction (∀I)

Universal Introduction (∀Ι)

P(a/x)
(∀x)P

∀I

(∀x)Px ⊢ (∀y)Py

1	(∀x)Px	P
2	Pa	1∀E
3	(∀y)Py	2∀I

Existential Elimination (∃E)

Existential Elimination (∃E)

(∃x)P
   | P(a/x)
   | .
   | .
   | .
   | Q
Q

∃E

1	(∃x)Px	P
2	\| Pa	A/∃E
3	\| (∃y)Py	2∃I
4	(∃y)Py	1,2–3∃E

8.2 Quantifier Negation (QN)

The four underived quantifier rules for making proofs in the language of predicate logic (RL) made a derivation system called RD. To this we add the derived equivalence rule quantifier negation (QN) to make the deduction system RD+. And since it is an equivalence rule, QN can apply to quantifiers that are not main operators.

Quantifier Negation (QN)

From a negated universally quantified expression ‘¬(∀x)P,’ an existentially quantified expression ‘(∃x)¬P’ can be derived, and vice versa. Also, from a negated existentially quantified expression ‘¬(∃x)P,’ a universally quantified expression ‘(∀x)¬P’ can be inferred, and vice versa.

¬(∀x)P

⊣ ⊢

(∃x)¬P

¬(∃x)P

⊣ ⊢

(∀x)¬P

QN

QN

1	¬(∀x)Px	P
2	(∃x)¬Px	1QN
3	¬(∀x)Px	2QN

1	¬(∃z)(Wzz∧Mz)	P
2	(∀z)¬(Wzz∧Mz)	1QN
3	¬(∃z)(Wzz∧Mz)	2QN

8.3 Sample Proofs

Agler illustrates the rules of the derivation system for making proofs in the language of predicate logic with a set of examples.

Agler, David. Symbolic Logic: Syntax, Semantics, and Proof. New York: Rowman & Littlefield, 2013.

14 Mar 2017

Suppes’ Introduction to Logic, collected brief summaries

[Search Blog Here. Index-tags are found on the bottom of the left column.]

[Logic & Semantics, Entry Directory]

[Patrick Suppes, entry directory]

[Suppes, Introduction to Logic, entry directory]

[The following collects the brief summaries for certain sections of Patrick Suppes’ Introduction to Logic, and in some cases Suppes’ examples are replicated too. All the following is Suppes’ work, boiled down for quick reference or review.]

The entry directory without the brief summaries can be found here:

Suppes, Introduction to Logic, entry directory

Collected Brief Summaries of

Patrick Suppes

Introduction to Logic

Ch. 3 Symbolizing Everyday Language

§3.2 Terms

A term is an expression that either (a) names or describes some object, or (b) generates a name or a description for some object whenever we replace the expression’s variables with names or with descriptions. Thus “x + y” both contains terms, namely, x and y, because these variables can be replaced with specific numerals, and also, the whole expression “x + y” itself is a term, because after its variables are substituted, it expresses the value 5.

§3.3 Predicates

Predication can be expressed as a relation. In this text, we use lower-case letters for variables and upper-case letters for relations. We would write “For every x, x is red or x is not red” as: For every x, Rx ∨ –Rx. Predicates can be either one-place, two-place, or n-place, depending on the number of terms the predicate relates.

§3.4 Quantifiers

The variables in our propositions can be quantified. If the variable applies to all such things, it is universally quantified. The sentence “Everyone is a miser” could be expressed “For all x, x is a miser” and rendered symbolically [in Suppes’ text] as: (x)(x is a miser). If however the variable applies to some or to just one such thing, it is existentially quantified. The sentence “something is greater than zero” could be expressed “there is an x such that x is greater than 0” and symbolically rendered as: (∃x)(x > 0). More quantifiers can be added, as in (∃x)(∃y)(∃z)(x + y = z + 2). To symbolize common nouns, we can use relational predicates and quantifiers. First consider an example with universal quantification, “All freshmen are intelligent”. It should be written with the conditional as: (x)(Fx → Ix), meaning “For all x, if x is a freshman then x is intelligent”. But the structure is different for existential quantification. “Some freshmen are intelligent” should be rendered with the conjunction as: (∃x)(Fx & Ix).

§3.5 Bound and Free variables

Atomic formulas are predicates followed or flanked by the appropriate number of terms as arguments. A formula more generally is either an atomic formula or a more complex formula built by adding or being combined by operators (–, &, ∨, →, ↔) or quantifiers ([the universal quantifier has no symbol before the variable here], ∃). The scope of the quantifier is the smallest formula following it, when that formula has no parentheses. Or it is whatever lies within the left-most parenthesis following the quantifier(s) and its right- sided partner. A variable in a formula is bound when it falls within the scope of the quantifier that uses it, and it is free otherwise. A sentence is a formula with no free variables in it.

Ch. 9 Sets

§9.1 Introduction

and

§9.2 Membership

A set is any kind of a collection of entities of any sort, and the members are said to “belong to” the set. This membership relation is symbolized ∈, and the set members are listed between braces, {}. If two sets have the same members, then those two sets are identical. This is the principle of extensionality for sets. There is an empty set, which has no members, and it is here symbolized Λ. Set {{1,2}} is not identical with set {1,2}, because the first set has one member, namely, {1,2}, and the second has these two members: 1,2. Most sets do not include themselves as members. And the membership relation is not symmetric, so from A ∈ B it does not follow that B ∈ A. The order of the members does not matter, so {1,3,5}={1,5,3}. And we do not count an element of a set twice, so {1,1,3,5}={1,3,5}. Also, the relation of set membership is not transitive. So from A∈B and B∈C, it does not follow that A∈C. For example, 2∈{1,2} and {1,2}∈{{1,2},{3,4}}. However, 2∉{{1,2},{3,4}}. We can understand properties in terms of set membership by saying that a thing has a given property if and only if it belongs to the set of things having this property. And finally, we can express the principle of the identity of indiscernibles in terms of set membership by saying that if y belongs to every set to which x belongs, then y=x.

§9.3 Inclusion

Set inclusion is different from set membership. To say one set is included in another is to say that all the terms belonging to the first also belong to the second. However, to say that one set is a member of another set is to say that the first set as a singular whole is one of the terms in the other set. We symbolize set inclusion with the ⊆ symbol. And if all the members of one set are included in a second, but not all of the second are included in the first, then we call the first a proper subset of the second, and we symbolize it with ⊂. We can distinguish set identity, set membership, and set inclusion with these examples, respectively: “Elizabeth II = the present Queen of England,” “Elizabeth II ∈ the class of women,” and “The class of women ⊆ the class of human beings”, noting that despite this symbolic distinction, in everyday language the symbols (=, ∈, and ⊆) in these sentences can all be substituted with the same word, “is”. We can also distinguish set identity, membership, and inclusion using the concepts of symmetry and transitivity. (a) Identity ≠ inclusion, because identity is symmetric but inclusion is not. (b) Inclusion ≠ membership, because inclusion is transitive, but membership is not. And (c) identity ≠ membership, because identity is both symmetric and transitive, but membership is neither.

§9.4 The Empty Set

The empty set has no members. It is a subset of all other sets, even if it is not explicitly specified as a member. And the empty set is the only set that can be a subset of the empty set.

§9.5 Operations on Sets

Certain operations can be performed on sets. If we find all the members shared in common between two sets, we are finding their intersection (∩):

(x)(x ∈ A ∩ B ↔ x ∈ A & x ∈ B)

When two intersecting sets share no members in common, that is, when they are mutually exclusive sets, their intersection is the empty set. The set containing all the members in total from two sets is their union (∪):

(x)(x ∈ A ∪ B ↔ x ∈ A ∨ x ∈ B)

All the members in set A that are not in set B is the difference (∼) of A and B.

(x)(x ∈ A ∼ B ↔ x ∈ A & x ∉ B)

These operations can be iterated.

§9.6 Domains and Individuals

A domain of individuals (also called a domain of discourse) is a specific set. For example, in sociology, if we speak of the set of albinos, we implicitly mean only those albinos within the specific set (within the domain) of humans. We use the symbol “V” to denote a domain. Suppose we have a domain V and a set A. The complement of A relative to the domain are all those items in the domain that are not in A. We symbolize it either as V∼A or just ∼A.

§9.7 Translating Everyday Language

Formulations of the sort “All ... are ...” as in “All Americans are philosophers” can be translated into set notation as A ⊆ P. In this and in the other cases, either both blanks would be filled by common nouns or the first with a common noun and the second with an adjective. When the second blank is filled by an adjective, we need to convert it to a set name. So “All Americans are mortal” would be translated as “The class of Americans are included in the class of mortal beings” or A ⊆ M. “Some ... are ...” formulations, like, “Some Americans are philosophers”, can be translated to A ∩ P ≠ Λ. (Here Λ is the empty set.) Note, from the “Some S are P” formulations, we can infer that their intersection is not an empty set. However, for “All S are P” formulations, their intersection can in fact be an empty set. We translate “No ... are ...” formulations, like “No Americans are philosophers” as A ∩ P = Λ. And “Some ... are not ...” formulations, like “Some Americans are not philosophers”, are translated A ∩ ∼P ≠ Λ. More complicated expressions need more complicated interpretations. “All Americans are clean and strong” could be A ⊆ C ∩ S. “Fools and drunk men are truth tellers” could be (F ∪ D) ⊆ T. “Some Frenchmen drink wine” could be F ∩ W ≠ Λ. “Some Americans drink both coffee and milk” could be A ∩ C ∩ M ≠ Λ. And “Some Americans who drink tea do not drink either coffee or milk” could be (A ∩ T) ∩ ∼(C ∪ M) ≠ Λ.

§9.8 Venn Diagrams

We may depict sets and their relations and properties using Venn diagrams. A rectangle signifies the domain of individuals. Inside it we draw circles to represent sets. These circles may overlap to designate intersections. We can shade regions to mean there are no members there. An x-shaped cross signifies that a particular region has at least one member. However, if an x-shaped cross is linked by a line to another cross, that means at least one of the crosses’ connected regions is non-empty (and thus some, but not all, of the linked cross regions can be empty, despite them having a cross marking). When statements about the set-relations are logically consistent, then a crossed region that is also shaded as empty is really empty, because the shading dominates the crossing. However, if the statements are inconsistent, then this inconsistency might be apparent in a dually shaded and crossed region that should still retain its member despite the shading. Syllogistic inferences can be tested by constructing a diagram for the premises, and then we see if the conclusion is compatible with what is depicted.

Two mutually exclusive sets.

A ∩ B = Λ

All A are B.

A ⊆ B

A ⊆ B (all A are B) and B ∩ C = Λ, (i.e., no B are C)

A ∩ B = Λ

A ⊆ B; “for to say that A is a subset of B means that no part of A lies outside B” (197).

A ∩ B = Λ and A ⊆ B.

Some A are B: A ∩ B ≠ Λ. [x means the regions is not empty.]

Some A are either B or C: A ∩ (B ∪ C) ≠ Λ

A ∪ B ≠ Λ        (Something is either A or B)
A ∪ ~C ≠ Λ     (Something is either A or not C)

A ∩ C ≠ Λ     (Some A are C)
C ⊆ B               (All C are B)

Checking syllogisms.

(1) No B are C
(2) All A are B
(3) Therefore no Aare C

[Since all the shared regions between A and C are shaded, it is a valid inference.]

§9.9 Elementary Principles About Operations on Sets

There are a number of tautological equivalences that can be useful when making proofs about sets. Here is a list [note that Λ is the empty set and V is the domain of discourse]:

As we can see, the list expresses a number of properties, like identity, commutativity, distributivity, associativity, excluded middle, non-contradiction, idempotency, absorption, and De Morgan’s laws.

Ch. 10. Relations

§10.1 Ordered Couples

An ordered couple is two objects given in a fixed order. We list the items in a series, separated by commas and placed between angle brackets, for example: ⟨x, y⟩. Two ordered couples are identical just when the first member of one is identical with the first member of the other, and the second member of one is identical with the second member of the other:

⟨x, y⟩ = ⟨u, v⟩ ↔ (x = u & y = v)

We can have ordered triples, quadruples, and so on. Generally speaking, we can have any-numbered ordered n-tuples. We define them all on the basis of ordered couples. An ordered triple, for example, would be:

⟨x, y, z⟩ = ⟨⟨x, y⟩, z⟩

and an ordered n-tuple:

⟨x₁, x₂, ..., x_n⟩ = ⟨⟨x₁, x₂, ..., x_n-1⟩, x_n⟩

In sets, the repetition of members does not add new members, but in ordered n-tuples it does. So {1,2,2}={1,2}, but ⟨1,2,2⟩≠⟨1,2⟩. S is a finite sequence only if S is an ordered n-tuple, for example: ⟨Socrates, Plato, Democritus, Aristotle⟩. A Cartesian product is all the possible ordered pairs made by taking each element from one set and pairing it with each member of another. So if A={1,2} and B={Gandhi,Nehru} then

A × B = {⟨1, Gandhi⟩, ⟨1, Nehru⟩, ⟨2, Gandhi⟩, ⟨2, Nehru⟩}

§10.2 Definition of Relations

The order of the terms in a relation is often important. So we cannot just think of a predicate taking more than one term as relating members of some set. For, that set needs to have a fixed order. For example, if the relation is love, then it matters who loves whom, as the feeling is not always mutual. We designate such ordered n-tuples with angle brackets: ⟨x, y⟩. The set that can be substituted for the first term is the domain, for the second term, the counterdomain, and the union of both the domain and the counterdomain is the field.

(I) A binary relation is a set of ordered couples.

According to this definition the relation of loving is the set of ordered couples ⟨x, y⟩ such that x loves y. The relation of being less than is the set of all ordered couples ⟨x, y⟩ of numbers such that, for some positive number z,

x + z = y.

The obvious extension of (I) is that a relation which holds among three things is a set of ordered triples, and a relation which holds among n things is a set of ordered n-tuples.

A relation is called ‘n-ary’ if its members are n-tuples. For the special cases n = 2 and n = 3 we use special names, speaking of ‘binary’ and ‘ternary’ relations.

Since a relation is a set of ordered n-tuples, we can also use the “∈” notation to indicate that certain things stand in a given relation. Thus we can write:

⟨John, Mary⟩ ∈ L, instead of:

John L Mary

to indicate that John loves Mary. Similarly we can write:

⟨George, Mary, Elizabeth⟩ ∈ P,

instead of :

P(George, Mary, Elizabeth)

to indicate, let us say, that George and Mary are the parents of Elizabeth.

It is necessary to remember that an ordered couple is not a relation, but the set consisting of the ordered couple is. For instance,

⟨Thomas Aquinas, 4⟩ is not a relation;

{⟨Thomas Aquinas, 4⟩} is a relation;

{{⟨Thomas Aquinas, 4⟩}} is not a relation.

The last example of the three is not a relation because the only member of the set is itself a set, which is not an ordered couple.

(quoting Suppes 211)

If R is a binary relation, then the domain of R – in symbols: D(R) – is the set of all things x such that, for some y, ⟨x, y⟩ ∈ R. Thus if M is the | relation which consists of all couples ⟨x, y⟩ such that x is the mother of y, then the domain of M is the set of all women who are not childless. If

R₁= {⟨Λ, Plato⟩, ⟨Jane Austen, 101⟩, ⟨the youngest bride in Tibet, Richelieu⟩},

then

D(R₁) = {Λ, Jane Austen, the youngest bride in Tibet}.

The counterdomain (or converse domain) of a binary relation R (in symbols : C(R)) is the set of all things y such that, for some x, ⟨x, y⟩ ∈ R. The counterdomain of the relation M considered just above is the set of all people – since everyone has a mother. If B is the relation which consists of all couples ⟨x, y⟩ such that x is the brother of y, then the domain of B is the set of all men who have at least one brother or sister, and the counterdomain is the set of all people who have at least one brother. We have for the relation R₁defined above:

C(R₁) = {Plato, 101, Richelieu}.

The field of a binary relation R (in symbols: F(R)) is the union of its domain and its counterdomain. Thus z belongs to the field of a binary relation R if and only if either ⟨x, z⟩ ∈ R for some x or ⟨z, y⟩ ∈ R for some y. The field of the relation B considered just above is the set of all people who belong to families containing at least two children, at least one of which is male. As another example,

F(R₁) = {Λ, Jane Austen, the youngest bride in Tibet, Plato, 101, Richelieu}.

(quoting Suppes 212)

§10.3 Properties of Binary Relations

There are a number of sorts of binary relations. If a relation that relates things to themselves holds for all things, then it is reflexive, and if it holds for no things, then it is irreflexive.

A (binary) relation R is reflexive in the set A if for every x in A, xRx (i.e., ⟨x, x⟩ ∈ R):

R reflexive in A ↔ (x)(x ∈ A → xRx).

A relation R is irreflexive in the set A if, for every x in A it is not the case that xRx:

R irreflexive in A ↔ (x)(x ∈ A → –(xRx)).

When there is a two-place relation, if the order of the relation can be switched for all substitutions, then it is symmetric. If for all substitutions it cannot be switched and still be true, then it is asymmetric.

A relation R is symmetric in the set A if for every x and y in A, whenever xRy, then yRx:

R symmetric in A ↔ (x)(y)[x ∈ A & y ∈ A & xRy → yRx].

A relation R is asymmetric in the set A if, for every x and y in A, whenever xRy, then it is not the case yRx:

R asymmetric in A ↔ (x)(y)[x ∈ A & y ∈ A & xRy → –(yRx)].

Now ≤ is not symmetric, because although 3 ≤ 3 and 3 ≤ 3, that invertibility does not hold for 2 ≤ 3. It is also not antisymmetric, because although the invertibility does not hold in most cases, it does for 3 ≤ 3. However, it is always symmetric under the condition that both terms are equal to one another. It is thus antisymmetric.

A relation R is antisymmetric in the set A if for every x and y in A, whenever xRy and yRx, then x=y:

R antisymmetric in A ↔ (x)(y)[x ∈ A & y ∈ A & xRy & yRx → x=y].

A relation can also be neither symmetric, asymmetric, nor antisymmetric. One example is the love relation. It is not symmetric, because not every person loves the people who love them. It is also not asymmetric, because there are many cases of mutual love. It is furthermore not antisymmetric, because it is not the case that the only people who are in love are those who love themselves.

A relation is transitive if it carries over through a middle term.

A relation R is transitive in the set A if, for every x, y, and z in A, whenever xRy and yRz, then xRz:

R transitive in A ↔ (x)(y)(z)[x ∈ A & y ∈ A & z ∈ A & xRy & yRz → xRz].

A relation is intransitive if for no things that it relates does the relation of a first item to a second one along with and the second one to a third imply that the relation holds as well for the first to the third. Another idea is the difference between intransitive and non-transitive.

A relation R is intransitive in the set A if for every x, y, and z in A, whenever xRy and yRz, then it is not the case that xRz:

R intransitive in

A ↔ (x)(y)(z)[x ∈ A & y ∈ A & z ∈ A & xRy & yRz → –(xRz)].

Note that a relation can be non-transitive without being intransitive, because for some relations, there is transitivity between some triplets of terms but not between others.

A relation is connected if it relates any member to any other member.

A relation R is connected in the set A if for every x and y in A, whenever x ≠ y, then xRy or yRx:

R connected in A ↔ (x)(y)(x ∈ A & y ∈ A & x ≠ y → xRy ∨ yRx).

A relation is strongly connected if it holds for any member with any other member and as well with any member and itself.

A relation R is strongly connected in the set A if for every x and y in A, either xRy or yRx:

R strongly connected in A ↔ (x)(y)(x ∈ A & y ∈ A → xRy ∨ yRx).

§10.4 Equivalence Relations

A relation is equivalent if it is reflexive (it holds for some object in relation to itself), symmetric (when it holds for one object to a second, it also holds from the second to the first), and transitive (when it holds for one object to a second, and a second to a third, it as well holds for the first object to the third one). Within a set of members, certain groupings can be formed on the basis of equivalent relations holding among all the members of a particular subgrouping. These are equivalence classes. Forming such classes can allow us to reduce a large set of data to a more manageable size, when the differences between the members within an equivalence class are irrelevant to the particular analysis being conducted.

A relation which is reflexive, symmetric, and transitive in the set A is an equivalence relation in A. The relation of identity is an equivalence relation.

(218)

§10.5 Ordering Relations

There are a variety of what are called “ordering relations.” A relation is:

quasi-ordering only if it is both reflexive and transitive;

partial ordering only if is reflexive, antisymmetric, and transitive;

simple ordering only if it is reflexive, antisymmetric, transitive, and connected;

strict partial ordering only if it is asymmetric and transitive;

strict simple ordering only if it is asymmetric, transitive, and connected;

weak ordering only if it is transitive and strongly connected.

§10.6 Operations on Relations

Relations can be understood as those subsets they produce when they relate members of some set.

Universal Relation. We find every possible coupling of the members of one set with those same members. The resulting set is that of the universal relation. All other relations as sets will be subsets of the universal relation’s set. Formally:

If V is any domain of individuals, then by the universal relation over V we mean the set of all ordered couples (x, y) where x ∈ V and y ∈ V, that is, the Cartesian product V × V.

(Suppes 225)

Empty set relation. It is the relation whose corresponding set is empty.

The empty set Λ is the relation which never holds. If R, for instance, is the relation which holds between x and y if and only if x is the mother of y, and y is the mother of x, then R = Λ, for no one is his own grandmother.

(225)

With these notions in mind, we can then see how we apply the normal operations on sets to our relations as sets.

Intersection of relations.

if R and S are relations, then R ∩ S is the relation which consists of the intersection of R and S: i.e., x(R ∩ S)y if and only if both xRy and xSy.

(Suppes 225)

Union of relations.

R ∪ S is the union of R and S: x(R ∪ S)y if and only if either xRy or xSy.

(Suppes 225)

Difference of Relations.

R ~ S is the relation such that x(R ~ S)y if and only if xRy and not xSy.

(Suppes 225)

Subrelation.

If R ⊆ S we call R a subrelation of S. Thus brotherhood is a subrelation of siblinghood; for whenever x is a brother of y, then x is a sibling of y. Every relation is a subrelation of the universal relation over its own field.

(Suppes 226)

There are also operations for binary relations that are not based on these set operators.

Converse of a relation.

The converse of a relation R

is the relation such that, for all x and y, xRy if and only if yRx. Thus the converse of a relation is obtained simply by reversing the order of all the ordered couples which constitute it.

(Suppes 226)

Relative product of two relations. This operation combines two separate relations by finding ones where the second member of one couple (in the first relation) is the same as the first member of the second couple (in the other relation). From these pairings of couples, you make a new couple that takes the first member of the first couple and the second member of the second couple. Being an aunt is an example, with you and your aunt being the end-terms of separate relations (you being the child of your parent, and your parent being the sibling of your aunt), with your parent being the middle term that gets excluded.

If R and S are binary relations, then by the relative product of R and S (in symbols: R/S) we mean the relation which holds between x and y if and only if there exists a z such that R holds between x and z, and S holds between z and y. Symbolically,

x R/S y ↔ (∃z) (xRz & zSy).

If xPy means that x is a parent of y, and xSy means that x is a sister of y, then x(S/P)y means that there is a z such that x is a sister of z and z is a parent of y, and hence such that x is an aunt of y.

(Suppes 226)

Furthermore, the relative product relation can be a reiteration of the same relation.

If xPy when x is a parent of y, then x(P/P)y if and only if x is a grandparent of y; x[(P/P)/P]y if and only if x is a great-grandparent of y; and so on.

(Suppes 226)

Ch. 11. Functions

§11.1 Definition

A function is a binary relation that relates to each element of its domain a unique element of its counterdomain:

A function R is a binary relation such that if xRy and xRz then y = z.

Consider the following cases of binary relations:

R₁= {<1, 2>, <Madison, Pinckney>}

R₂= {<1, 2>, <1, 3>, <Plato, Aristotle>}

R₁is a function, but R₂is not, because in R₂, the number 1 is related to two members of the counterdomain, namely, 2 and 3, and thus the member of the domain is not related to a unique member of the counterdomain. We often used lowercase letters to symbolize functions, and they normally take the form f(x) = [something]. The domain of a function is called the domain of definition and the counterdomain, the range of values. A function is sometimes said to map its domain onto its range, and thus a function is also called a mapping. And when x is an element of the domain of f, then f(x) is the image of x. A binary operation on the set A is a function whose domain is A × A and whose range is a subset of A. For example, N = the positive integers and + is the binary operation of addition applied to positive integers. In this case, + is a binary operation from N × N to N. The range of + is N ~ {1}, as no two positive integers add up to one.

§11.2 Operations on Functions

The converse of a function has for its pairings of outcomes the same as those of the function except with the order of the couples’ members inverted. Note two things. {1} A function can assign many different members of the domain to the same member of the counterdomain. {2} A function cannot assign the same member of the domain to more than one member of the counter domain. Thus the converse of a function may not itself be a function, if the original function assigned more than one member of the domain to the same member of the counterdomain. However, when the converse of a function is in fact itself a function then we call it the inverse and we note it with a superscript ‘–1’. When solving for an inverse function, there are two important principles:

For every x in the domain of f

(I) f^–1(f(x)) = x,

and for every x in the range of f

(II) f(f^–1(x)) = x.

And a simple, but in some cases flawed, strategy for solving for the inverse has three phases: (i) Substitute ‘f^–1(x)’ for ‘x’; (ii) Apply (II);(iii) Solve the resulting equation for ‘f^–1(x)’.

Suppes, Patrick. Introduction to Logic. New York: Van Nostrand Reinhold / Litton Educational, 1957.

Proust (§15/16) Swann’s Way. [The narrator enjoyed his mother’s goodnight kisses, and M. Swann often came alone for dinner]

[Search Blog Here. Index-tags are found on the bottom of the left column.]

[Proust, entry directory]

[Proust. À la recherche du temps perdu, entry directory]

[Proust. Du côté de chez swann / Swann’s Way, entry directory]

[The following is summary, with my own bracketed comments. Proofreading is incomplete, so I apologize in advance for my distracting typos.]

Marcel Proust

Du côté de chez swann. À la recherche du temps perdu. Tome I

Swan's Way. Vol. 1 of Remembrance of Things Past

Première partie

Overature

Combray I.

§15 / §16

[The narrator enjoyed his mother’s goodnight kisses, and M. Swann often came alone for dinner.]

Brief summary:

The narrator as a boy cherished the nightly ritual of his mother kissing him goodnight. Sometimes M. Swann would could for dinner, but normally without his wife, on account of their unfortunate marriage.

Summary

The narrator as a boy enjoyed his mother’s loving attention when she would come up to his bedroom to give him a goodnight kiss. Sometimes as she was about to leave the room, he would call her back for another kiss, which she would reluctantly do, because this annoyed the father. When they had dinner guests, she did not come for the nightly ritual. Normally they had just one guest, M. Swann. Because he had an unfortunate marriage, his wife was less welcome to come too. The family would sit outside waiting for his arrival.

From the English translation:

§16

My sole consolation when I went upstairs for the night was that Mamma would come in and kiss me after I was in bed. But this good night lasted for so short a time: she went down again so soon that the moment in which I heard her climb the stairs, and then caught the sound of her garden dress of blue muslin, from which hung little tassels of plaited straw, rustling along the double-doored corridor, was for me a moment of the keenest sorrow. So much did I love that good night that I reached the stage of hoping that it would come as late as possible, so as to prolong the time of respite during which Mamma would not yet have appeared. Sometimes when, after kissing me, she opened the door to go, I longed to call her back, to say to her “Kiss me just once again,” but I knew that then she would at once look displeased, for the concession which she made to my wretchedness and agitation in coming up to me with this kiss of peace always annoyed my father, who thought such ceremonies absurd, and she would have liked to try to induce me to outgrow the need, the custom of having her there at all, which was a very different thing from letting the custom grow up of my asking her for an additional kiss when she was already crossing the threshold. And to see her look displeased destroyed all the sense of tranquillity she had brought me a moment before, when she bent her loving face down over my bed, and held it out to me like a Host, for an act of Communion in which my lips might drink deeply the sense of her real presence, and with it the power to sleep. But those evenings on which Mamma stayed so short a time in my room were sweet indeed compared to those on which we had guests to dinner, and therefore she did not come at all. Our ‘guests’ were practically limited to M. Swann, who, apart from a few passing strangers, was almost the only person who ever came to the house at Combray, sometimes to a neighbourly dinner (but less frequently since his unfortunate marriage, as my family did not care to receive his wife) and sometimes after dinner, uninvited. On those evenings when, as we sat in front of the house beneath the big chestnut-tree and round the iron table, we heard, from the far end of the garden, not the large and noisy rattle which heralded and deafened as he approached with its ferruginous, interminable, frozen sound any member of the household who had put it out of action by coming in ‘without ringing,’ but the double peal — timid, oval, gilded — of the visitors’ bell, everyone would at once exclaim “A visitor! Who in the world can it be?” but they knew quite well that it could only be M. Swann. My great-aunt, speaking in a loud voice, to set an example, in a tone which she endeavoured to make sound natural, would tell the others not to whisper so; that nothing could be more unpleasant for a stranger coming in, who would be led to think that people were saying things about him which he was not meant to hear; and then my grandmother would be sent out as a scout, always happy to find an excuse for an additional turn in the garden, which she would utilise to remove surreptitiously, as she passed, the stakes of a rose-tree or two, so as to make the roses look a little more natural, as a mother might run her hand through her boy’s hair, after the barber had smoothed it down, to make it stick out properly round his head.

From the French:

§15

Ma seule consolation, quand je montais me coucher, était que maman viendrait m’embrasser quand je serais dans mon lit. Mais ce bonsoir durait si peu de temps, elle redescendait si vite, que le moment où je l’entendais monter, puis où passait dans le couloir à double porte le bruit léger de sa robe de jardin en mousseline bleue, à laquelle pendaient de petits cordons de paille tressée, était pour moi un moment douloureux. Il annonçait celui qui allait le suivre, où elle m’aurait quitté, où elle serait redescendue. De sorte que ce bonsoir que j’aimais tant, j’en arrivais à souhaiter qu’il vînt le plus tard possible, à ce que se prolongeât le temps de répit où maman n’était pas encore venue. Quelquefois quand, après m’avoir embrassé, elle ouvrait la porte pour partir, je voulais la rappeler, lui dire «embrasse-moi une fois encore», mais je savais qu’aussitôt elle aurait son visage fâché, car la concession qu’elle faisait à ma tristesse et à mon agitation en montant m’embrasser, en m’apportant ce baiser de paix, agaçait mon père qui trouvait ces rites absurdes, et elle eût voulu tâcher de m’en faire perdre le besoin, l’habitude, bien loin de me laisser prendre celle de lui demander, quand elle était déjà sur le pas de la porte, un baiser de plus. Or la voir fâchée détruisait tout le calme qu’elle m’avait apporté un instant avant, quand elle avait détruisait vers mon lit sa figure aimante, et me l’avait tendue comme une hostie pour une communion de paix où mes lèvres puiseraient sa présence réelle et le pouvoir de m’endormir. Mais ces soirs-là, où maman en somme restait si peu de temps dans ma chambre, étaient doux encore en comparaison de ceux où il y avait du monde à dîner et où, à cause de cela, elle ne montait pas me dire bonsoir. Le monde se bornait habituellement à M. Swann, qui, en dehors de quelques étrangers de passage, était à peu près la seule personne qui vînt chez nous à Combray, quelquefois pour dîner en voisin (plus rarement depuis qu’il avait fait ce mauvais mariage, parce que mes parents ne voulaient pas recevoir sa femme), quelquefois après le dîner, à l’improviste. Les soirs où, assis devant la maison sous le grand marronnier, autour de la table de fer, nous entendions au bout du jardin, non pas le grelot profus et criard qui arrosait, qui étourdissait au passage de son bruit ferrugineux, intarissable et glacé, toute personne de la maison qui le déclenchait en entrant «sans sonner», mais le double tintement timide, ovale et doré de la clochette pour les étrangers, tout le monde aussitôt se demandait: «Une visite, qui cela peut-il être?» mais on savait bien que cela ne pouvait être que M. Swann; ma grand’tante parlant à haute voix, pour prêcher d’exemple, sur un ton qu’elle s’efforçait de rendre naturel, disait de ne pas chuchoter ainsi; que rien n’est plus désobligeant pour une personne qui arrive et à qui cela fait croire qu’on est en train de dire des choses qu’elle ne doit pas entendre; et on envoyait en éclaireur ma grand’mère, toujours heureuse d’avoir un prétexte pour faire un tour de jardin de plus, et qui en profitait pour arracher subrepticement au passage quelques tuteurs de rosiers afin de rendre aux roses un peu de naturel, comme une mère qui, pour les faire bouffer, passe la main dans les cheveux de son fils que le coiffeur a trop aplatis.

Proust, Marcel. Du côté de chez swann. À la recherche du temps perdu. Tome I.
Available online at:
http://ebooks.adelaide.edu.au/p/proust/marcel/p96d/index.html

Proust, Marcel. Swan’s Way. Vol. 1 of Remembrance of Things Past. Transl. C.K. Scott Moncrieff.
Available online at:
http://ebooks.adelaide.edu.au/p/proust/marcel/p96s/index.html

13 Mar 2017

Proust (§14/15) Swann’s Way. [Grandmother’s seeming concern about Grandfather’s drinking and real concern for the narrator’s well-being and future]

[Search Blog Here. Index-tags are found on the bottom of the left column.]

[Proust, entry directory]

[Proust. À la recherche du temps perdu, entry directory]

[Proust. Du côté de chez swann / Swann’s Way, entry directory]

[The following is summary, with my own bracketed comments. Proofreading is incomplete, so I apologize in advance for my distracting typos.]

Marcel Proust

Du côté de chez swann. À la recherche du temps perdu. Tome I

Swan's Way. Vol. 1 of Remembrance of Things Past

Première partie

Overature

Combray I.

§14 / §15

[Grandmother often returns from walks to deal with a repeated, artificial crisis at home; all the while, her real concern was with problems in the narrator’s character, health, and future]

Brief summary:

Grandmother’s walks would often be interrupted when great-aunt tempted grandfather to drink a few forbidden drops of brandy, upon which great-aunt would call grandmother back to deal with the crisis. The narrator, who was just a child at the time, did not realize this was merely teasing behavior, and in his horror he ran off to cry alone. In reality, grandmother was less worried about grandfather’s drinking and more worried about the narrator’s weaknesses in character and health and his consequent uncertain future.

Summary

[Previously we noted how the narrator’s grandmother would often go for walks after dinner, even if it was raining.] One thing that would always draw grandmother back to the house from her after-dinner walks was if she was warned that her husband was drinking brandy again. This was really a trick played by the narrator’s great-aunt. Grandfather was not allowed to drink, and great-aunt would tempt him to drink just a few drops so to create a crisis for grandmother to hurry back to. Although in later years the narrator would come to regard this as more playful teasing of grandmother, at that time he was horrified by his great-aunt’s tormenting behavior and would often run off to cry alone at a private place. The narrator then notes that grandmother was in fact less concerned with grandfather’s drinking and more so with the narrator’s lack of will-power, his delicate health, and the uncertainty regarding his future.

From the English translation:

§15

When these walks of my grandmother’s took place after dinner there was one thing which never failed to bring her back to the house: that was if (at one of those points when the revolutions of her course brought her, moth-like, in sight of the lamp in the little parlour where the liqueurs were set out on the card-table) my great-aunt called out to her: “Bathilde! Come in and stop your husband from drinking brandy!” For, simply to tease her (she had brought so foreign a type of mind into my father’s family that everyone made a joke of it), my great-aunt used to make my grandfather, who was forbidden liqueurs, take just a few drops. My poor grandmother would come in and beg and implore her husband not to taste the brandy; and he would become annoyed and swallow his few drops all the same, and she would go out again sad and discouraged, but still smiling, for she was so humble and so sweet that her gentleness towards others, and her continual subordination of herself and of her own troubles, appeared on her face blended in a smile which, unlike those seen on the majority of human faces, had no trace in it of irony, save for herself, while for all of us kisses seemed to spring from her eyes, which could not look upon those she loved without yearning to bestow upon them passionate caresses. The torments inflicted on her by my great-aunt, the sight of my grandmother’s vain entreaties, of her in her weakness conquered before she began, but still making the futile endeavour to wean my grandfather from his liqueur-glass — all these were things of the sort to which, in later years, one can grow so well accustomed as to smile at them, to take the tormentor’s side with a happy determination which deludes one into the belief that it is not, really, tormenting; but in those days they filled me with such horror that I longed to strike my great-aunt. And yet, as soon as I heard her “Bathilde! Come in and stop your husband from drinking brandy!” in my cowardice I became at once a man, and did what all we grown men do when face to face with suffering and injustice; I preferred not to see them; I ran up to the top of the house to cry by myself in a little room beside the schoolroom and beneath the roof, which smelt of orris-root, and was scented also by a wild currant-bush which had climbed up between the stones of the outer wall and thrust a flowering branch in through the half-opened window. Intended for a more special and a baser use, this room, from which, in the daytime, I could see as far as the keep of Roussainville-le-Pin, was for a long time my place of refuge, doubtless because it was the only room whose door I was allowed to lock, whenever my occupation was such as required an inviolable solitude; reading or dreaming, secret tears or paroxysms of desire. Alas! I little knew that my own lack of will-power, my delicate health, and the consequent uncertainty as to my future weighed far more heavily on my grandmother’s mind than any little breach of the rules by her husband, during those endless perambulations, afternoon and evening, in which we used to see passing up and down, obliquely raised towards the heavens, her handsome face with its brown and wrinkled cheeks, which with age had acquired almost the purple hue of tilled fields in autumn, covered, if she were walking abroad, by a half-lifted veil, while upon them either the cold or some sad reflection invariably left the drying traces of an involuntary tear.

From the French:

§14

Quand ces tours de jardin de ma grand’mère avaient lieu après dîner, une chose avait le pouvoir de la faire rentrer: c’était, à un des moments où la révolution de sa promenade la ramenait périodiquement, comme un insecte, en face des lumières du petit salon où les liqueurs étaient servies sur la table à jeu — si ma grand’tante lui criait: «Bathilde! viens donc empêcher ton mari de boire du cognac!» Pour la taquiner, en effet (elle avait apporté dans la famille de mon père un esprit si différent que tout le monde la plaisantait et la tourmentait), comme les liqueurs étaient défendues à mon grand-père, ma grand’tante lui en faisait boire quelques gouttes. Ma pauvre grand’mère entrait, priait ardemment son mari de ne pas goûter au cognac; il se fâchait, buvait tout de même sa gorgée, et ma grand’mère repartait, triste, découragée, souriante pourtant, car elle était si humble de cœur et si douce que sa tendresse pour les autres et le peu de cas qu’elle faisait de sa propre personne et de ses souffrances, se conciliaient dans son regard en un sourire où, contrairement à ce qu’on voit dans le visage de beaucoup d’humains, il n’y a avait d’ironie que pour elle-même, et pour nous tous comme un baiser de ses yeux qui ne pouvaient voir ceux qu’elle chérissait sans les caresser passionnément du regard. Ce supplice que lui infligeait ma grand’tante, le spectacle des vaines prières de ma grand’mère et de sa faiblesse, vaincue d’avance, essayant inutilement d’ôter à mon grand-père le verre à liqueur, c’était de ces choses à la vue desquelles on s’habitue plus tard jusqu’à les considérer en riant et à prendre le parti du persécuteur assez résolument et gaiement pour se persuader à soi-même qu’il ne s’agit pas de persécution; elles me causaient alors une telle horreur, que j’aurais aimé battre ma grand’tante. Mais dès que j’entendais: «Bathilde, viens donc empêcher ton mari de boire du cognac!» déjà homme par la lâcheté, je faisais ce que nous faisons tous, une fois que nous sommes grands, quand il y a devant nous des souffrances et des injustices: je ne voulais pas les voir; je montais sangloter tout en haut de la maison à côté de la salle d’études, sous les toits, dans une petite pièce sentant l’iris, et que parfumait aussi un cassis sauvage poussé au dehors entre les pierres de la muraille et qui passait une branche de fleurs par la fenêtre entr’ouverte. Destinée à un usage plus spécial et plus vulgaire, cette pièce, d’où l’on voyait pendant le jour jusqu’au donjon de Roussainville-le-Pin, servit longtemps de refuge pour moi, sans doute parce qu’elle était la seule qu’il me fût permis de fermer à clef, à toutes celles de mes occupations qui réclamaient une inviolable solitude: la lecture, la rêverie, les larmes et la volupté. Hélas! je ne savais pas que, bien plus tristement que les petits écarts de régime de son mari, mon manque de volonté, ma santé délicate, l’incertitude qu’ils projetaient sur mon avenir, préoccupaient ma grand’mère, au cours de ces déambulations incessantes, de l’après-midi et du soir, où on voyait passer et repasser, obliquement levé vers le ciel, son beau visage aux joues brunes et sillonnées, devenues au retour de l’âge presque mauves comme les labours à l’automne, barrées, si elle sortait, par une voilette à demi relevée, et sur lesquelles, amené là par le froid ou quelque triste pensée, était toujours en train de sécher un pleur involontaire.

Proust, Marcel. Du côté de chez swann. À la recherche du temps perdu. Tome I.
Available online at:
http://ebooks.adelaide.edu.au/p/proust/marcel/p96d/index.html

Proust, Marcel. Swan’s Way. Vol. 1 of Remembrance of Things Past. Transl. C.K. Scott Moncrieff.
Available online at:
http://ebooks.adelaide.edu.au/p/proust/marcel/p96s/index.html

Proust. À la recherche du temps perdu. Entry Directory

[Search Blog Here. Index-tags are found on the bottom of the left column.]

[Proust, entry directory]

Entry Directory for

Marcel Proust

À la recherche du temps perdu

(In Search of Lost Time / Remembrance of Things Past)

Du côté de chez swann [À la recherche du temps perdu. Tome I]
Swan's Way [Vol. 1 of Remembrance of Things Past]

Marcel Proust, entry directory

[Search Blog Here. Index-tags are found on the bottom of the left column.]