Preliminaries

# Sets

Presentations of logic vary in how much set theory they use. Some are heavily laden with set theory. Though most are not, it is nearly impossible to avoid it completely. It will not be a very important focal point for this book, but we will use a little set theory vocabulary here and there. This section introduces the vocabulary and notation used.

## Sets and elements

Mathematicians use 'set' as an undefined primitive term. Some authors resort to quasi-synonyms such as 'collection'.

A set has elements. 'Element' is also undefined in set theory. We say that an element is a member of a set, also an undefined expression. The following are all used synonymously:

x is a member of y
x is contained in y
x is included in y
y contains x
y includes x

### Notation

A set can be specified by enclosing its members within curly braces.

$\{1,2,3\}\,\!$ is the set containing 1, 2, and 3 as members. The curly brace notation can be extended to specify a set using a rule for membership.

$\{x:x=1{\text{ or }}x=2{\text{ or }}x=3\}\,\!$ (The set of all x such that x = 1 or x = 2 or x = 3)

is again the set containing 1, 2, and 3 as members.

$\{x:x{\text{ is a positive integer}}\}\,\!$ , and
$\{1,2,3,\ldots \}\,\!$ both specify the set containing 1, 2, 3, and onwards.

A modified epsilon is used to denote set membership. Thus

$x\in y\,\!$ indicates that "x is a member of y". We can also say that "x is not a member of y" in this way:

$x\notin y\,\!$ ### Characteristics of sets

A set is uniquely identified by its members. The expressions

$\{x:x\ \mathrm {is\ an\ even\ prime} \}\,\!$ $\{x:x\ \mathrm {is\ a\ positive\ square\ root\ of} \ 4\}\,\!$ $\{2\}\,\!$ all specify the same set even though the concept of an even prime is different from the concept of a positive square root. Repetition of members is inconsequential in specifying a set. The expressions

$\{1,\ 2,\ 3\}\,\!$ $\{1,\ 1,\ 1,\ 1,\ 2,\ 3\}\,\!$ $\{x:\mathrm {x\ is\ an\ even\ prime\ or} \ x\ \mathrm {is\ a\ positive\ square\ root\ of} \ 4\ \mathrm {or} \ x=1\ \mathrm {or} \ x=2\ \mathrm {or} \ x=3\}\,\!$ all specify the same set.

Sets are unordered. The expressions

$\{1,\ 2,\ 3\}\,\!$ $\{3,\ 2,\ 1\}\,\!$ $\{2,\ 1,\ 3\}\,\!$ all specify the same set.

Sets can have other sets as members. There is, for example, the set

$\{\{1,\ 2\},\{2,\ 3\},\ \{1,\ \mathrm {George\ Washington} \}\}\,\!$ ### Some special sets

As stated above, sets are defined by their members. Some sets, however, are given names to ease referencing them.

The set with no members is the empty set. The expressions

$\{\}\,\!$ $\varnothing \,\!$ $\{x:x\neq x\}\,\!$ all specify the empty set. Empty sets can also express oxymora ("four-sided triangles" or "birds with radial symmetry") and factual non-existence ("the King of Czechoslovakia in 1994").

A set with exactly one member is called a singleton. A set with exactly two members is called a pair. Thus {1} is a singleton and {1, 2} is a pair.

ω is the set of natural numbers, {0, 1, 2, ...}.

## Subsets, power sets, set operations

### Subsets

A set s is a subset of set a if every member of s is a member of a. We use the horseshoe notation to indicate subsets. The expression

$\{1,\ 2\}\subseteq \{1,\ 2,\ 3\}\,\!$ says that {1, 2} is a subset of {1, 2, 3}. The empty set is a subset of every set. Every set is a subset of itself. A proper subset of a is a subset of a that is not identical to a. The expression

$\{1,\ 2\}\subset \{1,\ 2,\ 3\}\,\!$ says that {1, 2} is a proper subset of {1, 2, 3}.

### Power sets

A power set of a set is the set of all its subsets. A script 'P' is used for the power set.

${\mathcal {P}}\{1,\ 2,\ 3\}=\{\varnothing ,\ \{1\},\ \{2\},\ \{3\},\ \{1,\ 2\},\ \{1,\ 3\},\ \{2,\ 3\},\ \{1,\ 2,\ 3\}\}\,\!$ ### Union

The union of two sets a and b, written ab, is the set that contains all the members of a and all the members of b (and nothing else). That is,

$a\cup b=\{x:x\in a\ \mathrm {or} \ x\in b\}\,\!$ As an example,

$\{1,\ 2,\ 3\}\ \cup \ \{2,\ 3,\ 4\}=\{1,\ 2,\ 3,\ 4\}\,\!$ ### Intersection

The intersection of two sets a and b, written ab, is the set that contains everything that is a member of both a and b (and nothing else). That is,

$a\cap b=\{x:x\in a\ \mathrm {and} \ x\in b\}\,\!$ As an example,

$\{1,\ 2,\ 3\}\ \cap \ \{2,\ 3,\ 4\}=\{2,\ 3\}\,\!$ ### Relative complement

The relative complement of a in b, written b \ a (or ba) is the set containing all the members of b that are not members of a. That is,

$b\setminus a=\{x:x\in b\ \mathrm {and} \ x\notin a\}\,\!$ As an example,

$\{2,\ 3,\ 4\}\setminus \{1,\ 3\}=\{2,\ 4\}\,\!$ ## Ordered sets, relations, and functions

The intuitive notions of ordered set, relation, and function will be used from time to time. For our purposes, the intuitive mathematical notion is the most important. However, these intuitive notions can be defined in terms of sets.

### Ordered sets

First, we look at ordered sets. We said that sets are unordered:

$\{a,\ b\}=\{b,\ a\}\,\!$ But we can define ordered sets, starting with ordered pairs. The angle bracket notation is used for this:

$\langle a,\ b\rangle \ \neq \ \langle b,\ a\rangle \,\!$ Indeed,

$\langle x,\ y\rangle \ =\ \langle u,\ v\rangle \ {\mbox{if and only if}}\ x=u\ {\mbox{and}}\ y=v\,\!$ Any set theoretic definition giving ⟨a, b⟩ this last property will work. The standard definition of the ordered paira, b⟩ runs:

$\langle a,\ b\rangle \ =\ \{\{a\},\ \{a,\ b\}\}\,\!$ This means that we can use the latter notation when doing operations on an ordered pair.

There are also bigger ordered sets. The ordered triplea, b, c⟩ is the ordered pair ⟨⟨a, b⟩, c⟩. The ordered quadruplea, b, c, d⟩ is the ordered pair ⟨⟨a, b, c⟩, d⟩. This, in turn, is the ordered triple ⟨⟨⟨a, b⟩, c⟩, d⟩. In general, an ordered n-tuplea1, a2, ..., an⟩ where n greater than 1 is the ordered pair ⟨⟨a1, a2, ..., an-1⟩, an⟩.

It can be useful to define an ordered 1-tuple as well: ⟨a⟩ = a.

These definitions are somewhat arbitrary, but it is nonetheless convenient for an n-tuple, n ⟩ 2, to be an n-1 tuple and indeed an ordered pair. The important property that makes them serve as ordered sets is:

$\langle x_{1},\ x_{2},\ ...,\ x_{n}\rangle \ =\ \langle y_{1},\ y_{2},\ ...,\ y_{n}\rangle \ \mathrm {if\ and\ only\ if} \ x_{1}=y_{1},\ x_{2}=y_{2},\ ...,\ x_{n}=y_{n}\,\!$ ### Relations

We now turn to relations. Intuitively, the following are relations:

x < y
x is a square root of y
x is a brother of y
x is between y and z

The first three are binary or 2-place relations; the fourth is a ternary or 3-place relation. In general, we talk about n-ary relations or n-place relations.

First consider binary relations. A binary relation is a set of ordered pairs. The less than relation would have among its members ⟨1, 2⟩, ⟨1, 3⟩, ⟨16, 127⟩, etc. Indeed, the less than relation defined on the natural numbers ω is:

$\{\langle x,\ y\rangle :x\in \omega ,\ y\in \omega ,\ \mathrm {and} \ x Intuitively, ⟨x, y⟩ is a member of the less than relation if x < y. In set theory, we do not worry about whether a relation matches an intuitive concept such as less than. Rather, any set of ordered pairs is a binary relation.

We can also define a 3-place relation as a set of 3-tuples, a 4-place relation as a set of 4-tuples, etc. We only define n-place relations for n ≥ 2. An n-place relation is said to have an arity of n. The following example is a 3-place relation.

$\{\langle 1,\ 2,\ 3\rangle ,\ \langle 8,\ 2,\ 1\rangle ,\ \langle 653,\ 0,\ 927\rangle \}\,\!$ Because all n-tuples where n > 1 are also ordered pairs, all n-place relations are also binary relations.

### Functions

Finally, we turn to functions. Intuitively, a function is an assignment of values to arguments such that each argument is assigned at most one value. Thus the + 2 function assigns a numerical argument x the value x + 2. Calling this function f, we say f(x) = x + 2. The following define specific functions.

$f_{1}(x)=x\times x\,\!$ $f_{2}(x)=\ \mathrm {the\ smallest\ prime\ number\ larger\ than} \ x\,\!$ $f_{3}(x)=6/x\ \!$ $f_{4}(x)=\ \mathrm {the\ father\ of\ x} \,\!$ Note that f3 is undefined when x = 0. According to biblical tradition, f4 is undefined when x = Adam or x = Eve. The following do not define functions.

$f_{5}(x)=\pm {\sqrt {x}}\,\!$ $f_{6}(x)=\ \mathrm {a\ son\ of\ x} \,\!$ Neither of these assigns unique values to arguments. For every positive x, there are two square roots, one positive and one negative, so f5 is not a function. For many x, x will have multiple sons, so f6 is not a function. If f6 is assigned the value the son of x then a unique value is implied by the rules of language, therefore f6 will be a function.

A function f is a binary relation where, if ⟨x, y⟩ and ⟨x, z⟩ are both members of f, then y = z.

We can define many place functions. Intuitively, the following are definitions of specific many place functions.

$f_{7}(x,\ y)=x+y\,\!$ $f_{8}(x,\ y,\ z)=(x+y)\times z\,\!$ Thus ⟨4, 7, 11⟩ is a member of the 2-place function f7. ⟨3, 4, 5, 35⟩ is a member of the 3 place function f8

The fact that all n-tuples, n ≥ 2, are ordered pairs (and hence that all n-ary relations are binary relations) becomes convenient here. For n ≥ 1, an n-place function is an n+1 place relation that is a 1-place function. Thus, for a 2-place function f,

$\langle x,\ y,\ z_{1}\rangle \ \in f\ \mathrm {and} \ \langle x,\ y,\ z_{2}\rangle \ \in f\ \mathrm {if\ and\ only\ if} \ z_{1}=z_{2}\,\!$ Sentential Logic

Sentential Logic

# Goals

## Sentential logic

Sentential logic attempts to capture certain logical features of natural languages. In particular, it covers truth-functional connections for sentences. Its formal language specifically recognizes the sentential connections

It is not the case that _____
_____ and _____
Either _____ or _____
_____ or _____ (or both)
if _____, then _____
_____ if and only if _____

The blanks are to be filled with statements that can be true or false. For example, "it is raining today" or "it will snow tomorrow". Whether the final sentence is true or false is entirely determined on whether the filled statements are true or false. For example, if it is raining today, but it will not snow tomorrow, then it is true to say that "Either it is raining today or it will snow tomorrow". On the other hand, it is false to say "it is raining today and it will snow tomorrow", since it won't snow tomorrow.

"Whether a statement is true or false" is called the truth value in logician slang. Thus "Either it is raining today or it is not raining today" has a truth value of true and "it is raining today and it is not raining today" has truth value of false.

Note that the above listed sentential connections do not include all possible truth value combinations. For example, there is no connection that is true when both sub-statements are true, both sub-statements are false or the first sub-statement is true while the other is false, and that is false else. However, you can combine the above connections together to build any truth combination of any number of sub-statements.

## Issues

Already we have tacitly taken a position in ongoing controversy. Some questions already raised by the seemingly innocuous beginning above are listed.

• Should we admit into our logic only sentences that are true or false? Multi-valued logics admit a greater range of sentences.
• Are the connections listed above truly truth functional? Should we admit connections that are not truth functional sentences into our logic?
• What should logic take as its truth-bearers (objects that are true or false)? The two leading contenders today are sentences and propositions.
• Sentences. These consist of a string of words and perhaps punctuation. The sentence 'The cat is on the mat' consists of six elements: 'the', 'cat', 'is', 'on', another 'the', and 'mat'.
• Propositions. These are the meanings of sentences. They are what is expressed by a sentence or what someone says when he utters a sentence. The proposition that the cat is on the mat consists of three elements: a cat, a mat, and the on-ness relation.
Elsewhere in Wikibooks and Wikipedia, you will see the name 'Propositional Logic' (or rather 'Propositional Calculus', see below) and the treatment of propositions much more often than you will see the name 'Sentential Logic' and the treatment of sentences. Our choice here represents the contributor's view as to which position is more popular among current logicians and what you are most likely to see in standard textbooks on the subject. Considerations as to whether the popular view is actually correct are not taken up here.
Some authors will use talk about statements instead of sentences. Most (but not all) such authors you are likely to encounter take statements to be a subset of sentences, namely those sentences that are either true or false. This use of 'statement' does not represent a third position in the controversy, but rather places such authors in the sentences camp. (However, other—particularly older—uses of 'statement' may well place its authors in a third camp.)

Sometimes you will see 'calculus' rather than 'logic' such as in 'Sentential Calculus' or 'Propositional Calculus' as opposed to 'Sentential Logic' or 'Propositional Logic'. While the choice between 'sentential' and 'propositional' is substantive and philosophical, the choice between 'logic' and 'calculus' is merely stylistic.

# The Sentential Language

This page informally describes our sentential language which we name ${\mathcal {L_{S}}}\,\!$ . A more formal description will be given in Formal Syntax and Formal Semantics

## Language components

### Sentence letters

Sentences in ${\mathcal {L_{S}}}\,\!$ are represented as sentence letters, which are single letters such as $\mathrm {P} ,\ \mathrm {Q} ,\ \mathrm {R} ,$ and so on. Some texts restrict these to lower case letters, and others restrict them to capital letters. We will use capital letters.

Intuitively, we can think of sentence letters as English sentences that are either true or false. Thus, $\mathrm {P} \,\!$ may translate as 'The Earth is a planet' (which is true), or 'The moon is made of green cheese' (which is false). But $\mathrm {P} \,\!$ may not translate as 'Great ideas sleep furiously' because such a sentence is neither true nor false. Translations between English and ${\mathcal {L_{S}}}\,\!$ work best if they are restricted to timelessly true or false present tense sentences in the indicative mood. You will see in the translation section below that we do not always follow that advice, wherein we present sentences whose truth or falsity is not timeless.

### Sentential connectives

Sentential connectives are special symbols in Sentential Logic that represent truth functional relations. They are used to build larger sentences from smaller sentences. The truth or falsity of the larger sentence can then be computed from the truth or falsity of the smaller ones.

${\mbox{Conjunction:}}\ \land \,\!$ • Translates to English as 'and'.
• $\mathrm {P} \land \mathrm {Q} \,\!$ is called a conjunction and $\mathrm {P} \,\!$ and $\mathrm {Q} \,\!$ are its conjuncts.
• $\mathrm {P} \land \mathrm {Q} \,\!$ is true if both $\mathrm {P} \,\!$ and $\mathrm {Q} \,\!$ are true—and is false otherwise.
• Some authors use an & (ampersand), (heavy dot) or juxtaposition. In the last case, an author would write
$\mathrm {PQ} \,\!$ $\mathrm {P} \land \mathrm {Q} \ .\,\!$ ${\mbox{Disjunction:}}\ \lor \,\!$ • Translates to English as 'or'.
• $\mathrm {P} \lor \mathrm {Q} \,\!$ is called a disjunction and $\mathrm {P} \,\!$ and $\mathrm {Q} \,\!$ are its disjuncts.
• $\mathrm {P} \lor \mathrm {Q} \,\!$ is true if at least one of $\mathrm {P} \,\!$ and $\mathrm {Q} \,\!$ are true—is false otherwise.
• Some authors may use a vertical stroke: |. However, this comes from computer languages rather than logicians' usage. Logicians normally reserve the vertical stroke for nand (alternative denial). When used as nand, it is called the Sheffer stroke.

${\mbox{Negation:}}\ \lnot \,\!$ • Translates to English as 'it is not the case that' but is normally read 'not'.
• $\lnot \mathrm {P} \,\!$ is called a negation.
• $\lnot \mathrm {P} \,\!$ is true if $\mathrm {P} \,\!$ is false—and is false otherwise.
• Some authors use ~ (tilde) or . Some authors use an overline, for example writing
${\bar {\mathrm {P} }}\ \ {\mbox{and}}\ \ ({\overline {(\mathrm {P} \land \mathrm {Q} )}}\lor \mathrm {R} )\,\!$ $\lnot \mathrm {P} \ \ {\mbox{and}}\ \ (\lnot (\mathrm {P} \land \mathrm {Q} )\lor \mathrm {R} )\ .\,\!$ ${\mbox{Conditional:}}\ \rightarrow \,\!$ • Translates to English as 'if...then' but is often read 'arrow'.
• $\mathrm {P} \rightarrow \mathrm {Q} \,\!$ is called a conditional. Its antecedent is $\mathrm {P} \,\!$ and its consequent is $\mathrm {Q} \,\!$ .
• $\mathrm {P} \rightarrow \mathrm {Q} \,\!$ is false if $\mathrm {P} \,\!$ is true and $\mathrm {Q} \,\!$ is false—and true otherwise.
• By that definition, $\mathrm {P} \rightarrow \mathrm {Q} \,\!$ is equivalent to $(\lnot \mathrm {P} )\lor \mathrm {Q} \,\!$ • Some authors use (hook).

${\mbox{Biconditional:}}\ \leftrightarrow \,\!$ • Translates to English as 'if and only if'
• $\mathrm {P} \leftrightarrow \mathrm {Q} \,\!$ is called a biconditional.
• $\mathrm {P} \leftrightarrow \mathrm {Q} \,\!$ is true if $\mathrm {P} \,\!$ and $\mathrm {Q} \,\!$ both are true or both are false—and false otherwise.
• By that definition, $\mathrm {P} \leftrightarrow \mathrm {Q} \,\!$ is equivalent to the more verbose $(\mathrm {P} \land \mathrm {Q} )\lor ((\lnot \mathrm {P} )\land (\lnot \mathrm {Q} ))\,\!$ . It is also equivalent to $(\mathrm {P} \rightarrow \mathrm {Q} )\land (\mathrm {Q} \rightarrow \mathrm {P} )\,\!$ , the conjunction of two conditionals where in the second conditional the antecedent and consequent are reversed from the first.
• Some authors use .

### Grouping

Parentheses $(\,\!$ and $)\,\!$ are used for grouping. Thus

$((\mathrm {P} \land \mathrm {Q} )\rightarrow \mathrm {R} )\,\!$ $(\mathrm {P} \land (\mathrm {Q} \rightarrow \mathrm {R} ))\,\!$ are two different and distinct sentences. Each negation, conjunction, disjunction, conditional, and biconditionals gets a single pair or parentheses.