**Glossary of Logical Terms**

Abstraction

Ad hominem

Antecedent

Antisymmetric

Argument

Arity

Asymmetric

Atomic sentence

Begging the question

Binary

Bound variable

Cardinal

Cardinality

Cartesian coordinate plane

Cartesian product

Closed sentence

Compactness theorem

Completeness theorem

Complex abstraction

Composition

Conclusion

Constant

Conditional

Conditional proof

Connected

Connective

Consequent

Contingent

Contradictory

Converse

Decidable

Decision procedure

Deductive argument

Disjoint

Domain

Downward Lowenheim-Skolem theorem

Elimination of quantifiers

Expressive power

False dilemma

Free variable

Function

Gödel’s first incompleteness theorem

Gödel’s second incompleteness theorem

Image

Implication

Inconsistent

Indirect proof

Inductive argument

Inductive set

Informal fallacy

Injective

Integer

Intersection

Intransitive

Irreflexive

Liar paradox

Linear ordering

Löwenheim-Skolem theorems

Main connective

Modus ponens

Modus ponendo ponens

Modus ponendo tollens

Modus tollendo ponens

Modus tollendo tollens

Modus tollens

Monotonic

Naïve set theory

Natural number

Normal form

Open sentence

Ordering

Ordinal

Pairwise disjoint

Partial ordering

Peano axioms

Petitio principii

Post hoc ergo proctor hoc

Power set

Premise

Range

Rational number

Real number

Reductio ad absurdum

Reflexive

Relation

Restriction

Russell’s paradox

Satisfiable

Scope

Set

Sound

Special pleading

Strongly connected

Subset

Superset

Surjective

Syllogism

Symbols

Symmetric

Transitive

Truth-functional

Truth table

Ultraproduct

Unary

Union

Unsatisfiable

Upward Lowenheim-Skolem theorem

Valid (as a trait of sentences)

Valid (as a trait of arguments)

Well founded

Well ordering

Whole number

ZFC

Abstraction

Abstraction provides a way of specifying a set by specifying a property had by all and only members of that set. Given the property being prime, we can create the abstracted set name:

{x: x is prime}

This set name names the same set as the infinite list name:

{2, 3, 5, 7, 11, 13, 17, …}

In a formal language, a property is specified using any sentence with a single free variable. All of the following serve to specify properties:

Fx (the property of being F)

Fx & Gx (the property of being F and G)

Rxa (the property of bearing R to a)

” x(Rxy ® Gx) (the property of being such that everything that bears R to you is G)

Corresponding to each of these properties is an abstracted set:

{x: Fx}

{x: Fx & Gx}

{x: Rxa}

{y: ” x(Rxy ® Gx)}

The abstracted set names are given the proper meaning by the abstraction axioms. There are an infinite number of abstraction axioms – one for every pair of variable and property-specifying sentence-with-free-variable. Given a variable n

and a sentence j

(n

) with a free occurrence of n

, there is an axiom of the form:

S {n : j (n )} & ” z(z Î {n : j (n )} « j (z))

The first conjunct of this axiom simply asserts that the referent of the abstracted set name is in fact a set. The second conjunct then guarantees that that set will have the right members, by requiring that an object be a member of the abstracted set if and only if it has the property being abstracted.

Abstraction is not a universally valid process for forming sets, since it leads (by abstraction on “x Ï x”) to Russell’s paradox. In modern set theory, it is replaced with axioms of restricted abstraction.

Ad Hominem

An ad hominem argument is a type of informal fallacy of reasoning. Ad hominem arguments proceed by attacking the person advancing the contrary position rather than by addressing the merits of that position. Thus consider the following:

Bob: I think abortion is morally wrong because abortion is the killing of a human being, and it is always wrong to kill a human being.

Frank: You only think that because you’re Catholic. There’s nothing wrong with abortion.

Frank’s response to Bob is an example of argument ad hominem. Rather than provide any substantive response to Bob’s argument, he suggests that it can be dismissed because of features of Bob himself. However, since nothing in the argument depends on the nature of Bob, this is a fallacy.

Ad hominem arguments can take many forms, depending on the way in which the imputed characteristic of the opponent is taken to undercut the argument. Often – in a type of ad hominem argument called “ad hominem tu quoque” – the suggestion is that the advancer of an argument is himself acting inconsistently with that argument and hence that the argument can be dismissed. Thus consider:

Bob: SUVs are an environmental hazard, unnecessarily consuming huge amounts of fossil fuels. Thus they ought to be banned, or at least much more strictly regulated.

Frank: But Bob, you just bought a Ford Excursion last week. I can’t take your arguments seriously.

Again, Bob’s arguments should be evaluated on their own merits, independent of whether Bob is acting consistently with the argument he is advancing. Ad hominem arguments can also take the form of simply heaping abuse on the advancer of the original argument, as in:

Bob: I don’t think we should fund the new computer center, because technological process has led to the increasing mechanization and dehumanization of society, leads to over-urbanization, and ultimately threatens to disenfranchise labourers from their labour.

Frank: You’re sounding like another lunatic Unabomber, Bob.

If Frank’s response is intended to be a substance response to Bob, it fails, because regardless of what character flaws Bob suffers from, his argument can be evaluated on its own merits.

Antecedent

The antecedent of a conditional is that part of a conditional which appears to the left of the conditional arrow.

In the following sentences:

P ® Q

ØR ® (S & T)

(P « ØS) ® ØØU

the antecedents are, respectively:

P

ØR

(P « ØS)

The antecedent of a conditional states a sufficient condition for the truth of the consequent of that conditional. The falsity of the antecedent suffices for the truth of the conditional.

Antisymmetric

A relation is antisymmetric if, given any pair of objects, the relation holds in at most one direction (i.e., not in both directions) between those objects, except when the “pair” of objects is in fact the same object twice. The mathematical relation “£ ” is antisymmetric, because one can never have both:

a £ b

b £ a

except in the special case where a = b. Thus an alternative way of phrasing antisymmetry is: a relation is antisymmetric if the fact that it holds in both directions between a pair of objects entails that those “two” objects are identical. Formally, we have:

R is antisymmetric « ” x” y((Rxy & Ryx) ® x = y)

We can also specify that a relation is antisymmetric on a particular set:

R is antisymmetric on A « ” x” y(x,y Î A ® ((Rxy & Ryx) ® x = y))

Antisymmetric relations can be obtained by asymmetric relations by adding the identity relation. Thus, for example:

£ = (< È =)

Argument

An argument is a logical tool for reaching new information on the basis of old information.

An argument has two parts: premises and conclusion. The premises of an argument give the information already known, and the conclusion of the argument gives the new piece of information which the argument purports is rational to believe on the basis of the old information.

The following is an example of an argument:

We are not responsible for any of our actions. For if physical law governs our actions, then we lack freedom, and without freedom there is no responsibility. But if physical law does not govern our actions, then those actions are random. Random acts are either uncaused or unexplainable, and either way are no more capable than determined acts of giving rise to responsibility.

This argument asserts the following premises:

P1: If physical law governs our actions, then we lack freedom.

P2: Without freedom there is no responsibility.

P3: If physical law does not govern our actions, then those actions are random.

P4: Random acts are either uncaused or unexplainable.

P5: Neither uncaused nor unexplainable acts are more capable than determined acts of giving rise to responsibility.

On the basis of these premises, the argument asserts the following conclusion:

We are not responsible for any of our actions.

The argument is a successful one if it is rational to accept the conclusion on the basis of the premises. Arguments can be considered successful when they are valid or when they are sound.

Arity

Arity is a measure of:

The number of constants a predicate requires to form a sentence.

The number of sentences a sentential connection combines.

The number of arguments a function requires.

A predicate is unary if it requires only one constant to form a sentence. In natural language, “snores” is unary:

Socrates snores.

In the formal language, F1 is unary:

F1a.

A predicate is binary if it requires two constants to form a sentence. In natural language, “admires” is binary:

Plato admires Socrates.

In the formal language, R2 is binary:

R2ab

A predicate is trinary if it requires three constants to form a sentence. In natural language, “is between” is trinary:

Chicago is between New York and Los Angeles.

In the formal language, M3 is trinary:

M3abc

Predicates can also be quaternary, quinternary, and in general n-ary for any n.

The sentential connective Ø is unary, because it combines with a single sentence to form a new sentence:

Ø P

The sentential connectives &, Ú , ® , « are all binary, because they each combine with two sentences to form a new sentence:

P & Q

P Ú Q

P ® Q

P « Q

In principle, languages can have trinary, quaternary, and in general n-ary connectives, but the formal language uses only unary and binary connectives.

The natural logarithm (ln) is a unary function, because it acts on a single number to create a new number:

ln(e) = 1

Addition and multiplication are binary functions, because they act on a pair of numbers to create a new number:

3 + 4 = 7

5 x 7 = 35

Trinary, quaternary, and in general n-ary functions can also be defined.

Asymmetric

A relation is asymmetric if, given any pair of objects, the relation always holds in at most one direction between those two objects. Formally:

R is asymmetric « ” x” y(Rxy ® Ø Ryx)

The relation “parent of” is asymmetric, since if X is the parent of Y, it follows that Y is not the parent of X (barring odd time travel scenarios). The mathematical relation “>” is also asymmetric, because if n > m, it follows that Ø (m < n).

To be asymmetric requires more than just not being symmetric. The relation “loves”, for example, is not symmetric, because not all love is reciprocated. However, that relation is also not asymmetric, because some love is reciprocated (some people do love those who love them). A relation that is asymmetric is not symmetric, but not all relations that are not symmetric are asymmetric – asymmetry is a stronger condition than lack of symmetry.

Atomic Sentence

An atomic sentence is a sentence which contains no other sentences as proper parts.

Consider the sentence:

The lion devoured his meal

No proper part of this sentence is itself a sentence:

“he”, “The lion”, “The lion devoured”, “The lion devoured his”, “lion”, “lion devoured”, “lion devoured his”, “lion devoured his meal”, “devoured”, “devoured his”, “devoured his meal”, “his”, “his meal”, “meal”

Thus the sentence is an atomic sentence.

Contrast the above sentence with:

If I can’t find a good movie to rent, I’ll stay home and read a book.

This sentence contains (at least) two proper parts that are themselves sentences:

I can’t find a good movie to rent

I’ll stay home and read a book

Thus it is a complex, rather than atomic, sentence.

In natural languages, it is only a rough-and-ready guide to being atomic that a sentence contains no other sentences as proper parts. Due to the complexities of the grammar of natural languages, sometimes what is genuinely a complex sentence does not contain any other sentences as proper parts. Thus consider:

Whales will probably become extinct soon.

This sentence is formed through the combination of the unary connective “probably” with the atomic sentence:

Whales will become extinct soon.

However, since the connective “probably” occupies an infix position, we cannot find a proper part of the original sentence which is a sentence. Thus the no-sentences-as-proper-parts test fails to give a sufficient condition for being atomic in natural langauges. Similarly, consider:

I slept all night.

This ought to count as an atomic sentence, but it contains the proper part:

I slept

which is a sentence. Thus the no-sentences-as-proper-parts test fails to give a necessary condition for being atomic in natural languages.

Some of these problems with the test for being atomic can be cleared up by bringing to bear a more sophisticated logical syntax, but fortunately in formal languages the situation is much more straightforward. In a sentential language, all and only sentence letters are atomic sentences. In a quantified language, both sentence letters and n-ary predicates followed by n terms are atomic sentences. Thus all of the following are atomic:

P

Q

F2ab

c=d

R3aad

The notion of an atomic sentence is a useful one because we can think of all sentences in the language as being built up from atomic sentences both in their syntactic properties (via the recursive grammatical rules for the language) and in their semantic properties (via the recursive definition of truth-in-an-interpretation.)

Begging the Question

An argument is said to beg the question if it uses a premise which would not be acceptable to someone who did not already accept the conclusion of the argument. Thus consider the following discussion:

A: Albert said that it would rain today. So we know it will, because everything Albert says is true.

B: How do you know that everything Albert says is true?

A: Why, he told me so himself!

A’s argument for the reliability of Albert combines the explicit premise that Albert said that he was reliable with the implicit premise that Albert is reliable. Obviously, though, this implicit premise will not be accepted by anyone who does not already accept the conclusion of the argument, since it just is that conclusion. Thus this argument will fail to persuade anyone who does not already accept its conclusion, and is said to beg the question.

Arguments which beg the question are not defective in their form – they will typically be deductively valid arguments. In fact, the simplest possible valid argument, the argument from to , is also a paradigm of begging the question. Begging the question is a matter of whether there is a route of evidence establishing the premises which does not run through the conclusion. In some sense, any deductively valid argument threatens to beg the question, since given the validity of the argument, anyone who has reason to accept its premises also has reason to accept its conclusion, so no rational person who does not accept the conclusion should accept all of the premises.

An argument which begs the question is also called a petition principii, or a circular argument. The phrase “beg the question” is also frequently used in the sense of “raises the question”, as in “The recent scandals beg the question: what did the president know, and when did he know it?”, but such usages are improper.

Binary

A logical operation (a predicate, a sentential connective, a function) is binary if it has an arity of two. Thus:

A predicate is binary if it combines with two constants to form a sentence.

admires is binary: Plato admires Socrates.

R2 is binary: R2ab

A sentential connective is binary if it combines with two sentences to form a new sentence.

because is binary: The window broke because a rock hit it.

® is binary: P ® Q

A function is binary if it takes two arguments.

+ is binary: 2 + 3

Bound Variable

A variable n in a sentence is called bound if it is in the scope of some n -quantifier. For example, the variable z is bound in each of the following sentences:

$ zFaz

” zFxz

” xFxx ® $ zRyz

It is possible to have only some occurrences of a given variable type be bound in a sentence. For example, in:

” zGz ® $ xRzx

only the first occurrence of z is free, since the later occurrence of z is not within the scope of the ‘”

z’ quantifier. Similarly, in:

” x(Rxz ® $ zFzz)

only the final two occurrence of z are bound, since the first occurrence is not within the scope of the ‘$ z’ quantifier.

A variable that is not bound is called free.

A sentence in which all variables are bound is called a closed sentence. Only closed sentences are assigned truth values by interpretations.

Cardinal

Informally, cardinals represent the use of numbers to indicate amount – one, two, three, and so on. They thus contrast with ordinals, which represent the use of numbers to indicate position in a sequence – first, second, third, and so on. The two notions coincide on the finite realm, but come apart on the infinite realm.

More formally, a cardinal is an ordinal which is not in 1-1 correspondence with any ordinal less than it.

The first infinite cardinal is , which is the set of all natural numbers. The next infinite cardinal is 1, which is the first uncountable cardinal.

Cardinality

The cardinality of a set is a measure of how many objects are in that set. The cardinality of a set is defined to be the unique cardinal such that there is a 1-1 function from the set onto the cardinal. (That there always is a unique such cardinal is guaranteed by the Axiom of Choice.) Two sets have the same cardinality if there is a 1-1 function between the two.

Cartesian coordinate plane

The Cartesian coordinate plane is Â 2, or Â ´ Â , the Cartesian product of the real numbers with themselves. The Cartesian coordinate plane is thus the collection of all ordered pairs <x,y>, where both x and y are real numbers. It can be represented geometrically as an infinite plane.

Cartesian Product

The Cartesian product of two sets is the set of all ordered pairs, the first element of which is drawn from the first set and the second element of which is drawn from the second set. Given sets A and B:

A = {1,2,3}

B = {4,5}

the Cartesian product of A and B is:

A x B = {<1,4>, <1,5>, <2,4>, <2,5>, <3,4>, <3,5>}

The Cartesian coordinate plane is the Cartesian product of the set of real numbers with itself.

Formally, Cartesian products are defined as follows:

” x” y(X ´ Y = {<x,y>: x Î X & y Î Y}

Closed Sentence

A closed sentence is a sentence with no free variables. Only closed sentences are assigned truth values by interpretations.

Compactness Theorem

The Compactness Theorem states that if a collection of sentences imply some conclusion , then there is some finite subset * of which also implies . Equivalently, it holds that a collection of sentences is satisfiable if every finite subset * of is satisfiable.

Completeness Theorem

The Completeness Theorem states that if a collection imply some conclusion (that is, if |= ), then there is a proof of from (that is, that |- ). Equivalently, it states that any collection of sentences from which no contradiction can be derived using the proof rules is a satisfiable collection, and hence true in some interpretation.

The Completeness Theorem shows that the proof system is strong enough to derive all desired results. Together with the Soundness Theorem it shows that the proof system is of exactly the right strength.

Complex Abstraction

Complex abstraction is a variant on the procedure of abstraction for creating new set names. In regular abstraction, a property is specified, and used to name a set of all and only those objects which have that property. In complex abstraction, some properties and/or relations are specified and used to determine one or more objects. Some function is then applied to those objects to obtain some new object, which is then added to the set specified by complex abstraction.

For example, given sets A and B, we can use complex abstraction to name the set:

{<x,y>: x Î A & y Î B}

Here two properties are specified – being in A and being in B. These two properties then serve pick out two objects (one in A and one in B). The ordered pair function is then applied to these two objects to yield a new object (the ordered pair of the member of A and the member of B). That new object is then added to the set specified by complex abstraction. In this manner, all ordered pairs in which the first element is a member of A and the second element is a member of B are added to the set.

Similarly, we can use the relation x + y = 5 to determine a set by complex abstraction:

{xy: x + y = 5}

Here we locate all pairs of numbers which add to 5, and then place their product in the set specified by complex abstraction. Thus we obtain the following set:

{0, 4, 6, -6, -14, …}

To generalize, given any variables n 1, …, n n, and any sentence j with n 1, …, n n free, and any n-ary function z , we can form the following set by complex abstraction:

{z (n 1, …, n n): j (n 1, …, n n)}

This set name is then defined as follows:

{z (n 1, …, n n): j (n 1, …, n n)} = {x: $ n 1…$ n n(x = z (n 1, …, n n) & j (n 1, …, n n))}

Since set names given by complex abstraction can be defined in terms of set names given by regular abstraction, complex abstraction does not extend the expressive power of the language.

Composition

The composition of two relations R and S is a third relation R S. Two objects a and b stand in this third relation if there is some third object c such that a stands in the S relation to c, and c stands in the R relation to b. The composition of the “father of” relation with the “brother of” relation is the “uncle of” relation.

Formally, we say:

R S = {<x,y>: z(<x,z> S & <x,y> R)}

When the relations composed are functions, composition amounts to running the input through the second function, and then running the output of that function through the first function. If f(x) = 2x, and g(x) = x2 + 1, then fg(x) = 2×2 + 2, while gf(x) = 4×2 + 1.

Conclusion

The conclusion of a proof is the statement whose truth is supposed to be guaranteed by the truth of the premises.

Consider the following argument:

In a definition certain characteristics would have to be specified. And in application to any particular case the question would always arise whether it were true that the characteristics were present. So we should be going round in a circle. So it seems likely that the content of the word ‘true’ is sui generis and indefinable. [Frege, “The Thought”]

The conclusion of this argument is:

The content of the word ‘true’ is sui generis and indefinable.

If the argument is a valid one, then that conclusion must be true if the premises are true. If the argument is a sound one, then the premises are true, so the conclusion must also be true.

Conditional

A conditional is a sentence in which the main connective is “if…then”, or ® in the formal language.

The following sentences are conditionals:

If Bush is elected president in 2004, the Republicans will be happy.

I’ll come to the movie if Mel Gibson isn’t in it.

P ® (Q Ú R)

Ø (P « Q) ® (S « Ø (T & R))

Conditional Proof

Conditional proof is a proof strategy than can be invoked to prove conditional statements. In a conditional proof, one starts with a “Show” line in which the sentence to be shown has ® as its main connective. One then takes the antecedent of that conditional as an additional assumption (using the rule ACP), and attempts to derive the consequent of the conditional. Once the consequent has been derived, the conditional proof is completed and the “Show” can be cancelled, making the conditional available for use in the proof.

The following is a simple proof using the strategy of conditional proof:

(1) P ® Q A

(2) Q ® R A

(3) Show P ® R

(4) P ACP

(5) Q ® E, 1,4

(6) R ® E, 2,5

Conditional proof is invoked on line 3 as the strategy for proving the “Show” line. On line 4, P is taken as an additional assumption, since it is the antecedent of the conditional to be proved. The conditional proof then concludes on line 6, where R, the consequent of the conditional to be proved, is derived, thus allowing the “Show” to be cancelled.

Conditional proof is a sensible strategy for the following reason. We’d like to show that some conditional of the form X ®

Y must be true, given our assumptions. We don’t know, of course, whether X itself is true. But we do know the following:

If X is true, then the conditional X ® Y is true if Y is true (since a true antecedent and a true consequent make a true conditional).

If X is not true, then the conditional X ® Y is true regardless of whether Y is true (since a false antecedent makes a true conditional).

Thus the only way that we can go wrong in asserting X ® Y is if it is possible for X to be true and Y not to be true. It is this possibility that we rule out through the conditional proof, by showing that the truth of X necessitates the truth of Y. This is enough to show us that if X is true, Y is true, and hence X ® Y is true. This combines with our prior knowledge that if X is false, then X ® Y is trivially true to show us that X ® Y is definitely true.

Connected

A relation R is connected if any two objects stand in the relation in one direction or another. “Is taller than” is a connected relation, while “admires” is not. Formally, we say:

R is connected xy(x y (Rxy Ryx))

We can also define the connectedness of a relation on a particular set:

R is connected on A xy(x,y A (x y (Rxy Ryx)))

Connective

A connective is a lexical item which combines with one or more sentences to form a complex sentence. Some examples of connectives in English and their application:

not Jupiter is not a small planet.

and Frege is a great philosopher and Russell is almost as great as Frege.

before Reagan was president before Bush was president.

possibly Possibly, the moon is inhabited.

but The weather is lousy but we’re going to the lake anyway.

James believes that James believes that the physical world is only an illusion.

Natural languages contain both truth-functional and non-truth-functional connectives.

In the formal language, there are five connectives, all of them truth-functional:

Ø Negation

& Conjunction

Ú Disjunction

® Conditional

« Biconditional

Consequent

The consequent of a conditional is that part of a conditional which appears to the right of the conditional arrow.

In the following sentences:

P ® Q

ØR ® (S & T)

(P « ØS) ® ØØU

the consequents are, respectively:

Q

(S & T)

ØØU

The truth of the consequent suffices for the truth of the conditional.

Constant

A constant is an expression in a quantified language used to pick out an object. In most quantified languages, lower-class letters from the Roman alphabet serve as constants. In an interpretation, each constant is assigned to some member of the domain.

Contingent

A sentence is called contingent if it is possible for it to be true and possible for it to be false. Being contingent thus stands between being valid (necessarily being true) and being contradictory (necessarily being false).

The following sentences are examples of contingent sentences:

George Bush is president.

The earth orbits the sun.

Martin Scorcese directed Taxi Driver.

The following sentences are not contingent:

1 + 1 = 2. [This sentence is valid – it cannot be false.]

Austin both is and is not in Texas. [This sentence is contradictory – it cannot be true.]

If 1 + 1 = 3, then the moon is made of green cheese [This sentence is valid – it cannot be false.]

In a formal language, a contingent sentence is one which is true relative to some interpretations and false relative to other interpretations. For example, every sentence letter is contingent (since a sentence letter can be assigned either true or false by an interpretation). The following sentences are also contingent:

P & Q

P ® ØP

“x”y(Rxy ® ØRyx)

The following sentences are not contingent:

P « ØP [This sentence is contradictory – it is false in every interpretation.]

(P « Q) Ú (P « R) Ú (Q « R) [This sentence is valid – it is true in every interpretation.]

“x(Fx ® Fx) [This sentence is valid – it is true in every interpretation.]

Contradictory

A sentence is called contradictory if it is impossible for it to be true. Contradictory is thus one end of a spectrum which runs from valid (being necessarily true) to contingent (being able to be true and able to be false) to contradictory.

The following sentences are examples of contradictory sentences:

There is an oak tree in my yard, and there are no oak trees in my yard.

God is a necessarily existent being who, while he does not actually exist, could have existed.

Socrates is not the same person as Socrates.

In a formal language, a contradictory sentence is one which is false relative to every interpretation. The following sentences are contradictory:

Ø(P Ú ØP)

P « ØP

$x(Fx & ØFx)

Converse

The converse of a relation R is another relation R-1 which is formed by reversing the direction of each ordered pair in the relation. Informally, the converse relation reverses the direction of the relation. The converse of the “parent of” relation is the “child of” relation; the converse of the “admires” relation is the “is admired by” relation. Formally, we say:

R-1 = {<y,x>: <x,y> R}

Decidable

A set is decidable if there is a computational procedure which, when applied to any potential element of the set, will indicate in a finite number of computational steps whether or not the potential element is in fact a member of the set. The set of even integers, for example, is decidable, since any number can be quickly tested for membership by dividing it by two. On the other hand, the set:

{n: a string of n consecutive 7’s occurs in the decimal expansion of }

is not decidable. There is no way to settle membership in this set other than via calculation of the decimal expansion of , and if in fact for some n no string of n consecutive 7’s occurs in that decimal expansion, no finite computation will show so (since any finite computation will leave an infinite number of decimal places still uncalculated, and thus leave open the possibility that in some as-yet-uncomputed stretch a string of n consecutive 7’s occurs).

Disjoint

Two sets are disjoint if their intersections are empty.

Each of the following pairs of sets is disjoint:

{1,3,5}, {2,4,6}

{x: x is prime}, {x: x is composite}

{<1,2>, <2,3>, <3,4>}, {<2,1>, <3,2>, <4,3>}

Domain

The domain of a relation is the set of all things which stand in the relation to anything. Thus the domain of the relation reads is the set of all people who read anything. Formally, we say:

D(R) = {x: y <x,y> R}

Since a function is a type of relation, this definition can also be applied to functions. The result will then be that if f: A B, D(f) = A.

Downward Löwenheim-Skolem Theorem

The downward Löwenheim-Skolem theorem states that if a set of sentences in a countable language are true in any interpretation, then they are true in some interpretation with a countable domain. The theorem follows trivially from the Henkin construction used in proving completeness.

Free Variable

A variable n in a sentence is called free if it is not in the scope of any n -quantifier. For example, the variable z is free in each of the following sentences:

Faz

” xFxz

” xFxx ® $ yRyz

It is possible to have only some occurrences of a given variable type be free in a sentence. For example, in:

” zGz ® $ xRzx

only the final occurrence of z is free, since the earlier occurrence of z is within the scope of the ‘” z’ quantifier. Similarly, in:

” x(Rxz ® $ zFzz)

only the first occurrence of z is free, since the later occurrence is within the scope of the ‘$ z’ quantifier.

A variable that is not free is called bound.

A sentence with one or more free variables is called an open sentence. Open sentences are not assigned truth values by interpretations.

Function

A function is a relation which relates any given object to at most one other object. Formally, we say that f is a function from A to B, or f:A B, if the following conditions are met:

f A B

x(x A y(y B & <x,y> f)

xyz((<x,y> f & <x,z> f) y = z)

Thus f is a relation between A and B, such that everything in A stands in the relation to something in B, and nothing in A stands in the relation to more than one thing.

Image

The image of a set A under a relation R is the set of all objects such that something in A stands in the relation to them. Thus the image of the set {Alex Rodriguez, Shaquille O’Neal} , under the teammate relation, is the set of all players on the Texas Rangers and the Los Angeles Lakers. Formally, we say:

the image of A under R = R[A] = {x: y(y A & Ryx)}

The image of a set A under a function f is the set formed by mapping each member of A using f.

Injective

A function f is injective if it never maps two members of the domain to the same member of the range. Formally:

f:A B is injective xy((x,y A & x y) f(x) f(y))

The function f(x) = 2x, defined on the reals, is injective. The function f(x) = x2, also defined on the reals, is not injective.

Indirect Proof

Indirect proof is a proof strategy for stabling “Show” lines in a proof. In an indirect proof, one follows a “Show” line with an additional assumption (using the rule AIP) which is the opposite of the claim to be shown. Thus if one is trying to show X, the assumption for indirect proof is X, and if one is trying to show X, the assumption for indirect proof is X. The goal is then to derive a contradiction – two lines of the form Y and Y. Once the contradiction has been derived, the indirect proof is completed and the “Show” line can be cancelled, making the claim available for use in the proof.

The following is a simple proof using the strategy of indirect proof:

(1) (P Q) A

(2) Show P

(3) P AIP

(4) P Q I, 3

(5) (P Q) R, 1

Indirect proof is invoked on line 2 as the strategy for proving the “Show” line. On line 3, P is taken as an additional assumption, since it is the opposite of the claim to be proved. The indirect proof then concludes on line 5, at which point an explicit contradiction has been derived, with line 5 contradicting line 4.

Indirect proof is a sensible strategy for the following reason. We’d like to show that some claim X is true. We thus start by assuming, perversely, that its opposite X is in fact true. Reasoning from this assumption, we reach an impossible position by deriving a contradiction. Since a contradiction cannot be true, an assumption which leads to a contradiction also cannot be true. We thus reject the extra assumption X. But if X is not true, then X must be true.

Inconsistent

A sentence is inconsistent if it is false in every interpretation. The sentence:

P & P

is inconsistent. A set of sentences is inconsistent if there is no interpretation in which every member of the set is true. The set:

{P, P}

is inconsistent. There are interpretations in which P is true, and interpretations in which P is true, but no interpretations in which both P and P are true.

Integer

An integer is a member of the set {…,-3,-2,-1,0,1,2,3,…} – the set consisting of all natural numbers and their additive inverses.

Formally, the integers can be treated as a set of ordered pairs of natural numbers. The first position of the ordered pair is then used to indicate the sign of the integer, and the second position indicates the magnitude of the integer. Thus -3 is represented as <0,3>, and +7 is represented as <1,7> Addition is then defined as follows:

<a,b> + <c,d> =

<a,b+d> if a = c

<a,b-d> if b > d

<c,d-b> if d > b

Multiplication is defined as follows:

<a,b> x <c,d> =

<1,bd> if a=c

<0,bd> if a c

To avoid having 0 in the integers twice, only one of <0,0> and <1,0> should be included.

Intersection

The intersection of two sets is a third set containing everything which is a member of both of the original sets. Formally, we say:

R S = {x: x R & x S}

Thus {1,2,3} {3,4,5} = {3}.

Intransitive

A relation is intransitive if, whenever it holds between a first object and a second object, and between a second object and a third object, it never holds between the first object and the third object. Formally:

R is intransitive xyz((Rxy & Ryz) Rxz)

The relation “is one greater than” is intransitive, as is the relation “is a parent of” when incest is not involved.

To be intransitive requires more than just not being transitive. The relation “loves”, for example, is not transitive, because A can love B and B can love C without A loving C. However, that relation is also not intransitive, because A could love C.

Irreflexive

A relation is irreflexive if it never holds between an object and itself. Formally:

R is irreflexive « ” xØ Rxx

“Sibling” is irreflexive, since no person is their own sibling. The mathematical relation “>” is also irreflexive, since no number is greater than itself.

To be irreflexive requires more than just not being reflexive. The relation “loves”, for example, is not reflexive, because some people do not love themselves. However, that relation is also not irreflexive, because not all people fail to love themselves (some people do love themselves). A relation that is irreflexive is not reflexive, but not all relations that are not reflexive are irreflexive – irreflexivity is a stronger condition than lack of reflexivity.

Linear Ordering

A linear ordering is a relation which is either:

reflexive

antisymmetric

transitive

strongly connected

or:

irreflexive

asymmetric

transitive

connected

The first is a loose linear ordering; the second is a strict linear ordering. A linear ordering fully orders a collection of objects, placing them on a single line. The relation < on the natural numbers is a linear ordering.

Main Connective

The main connective of a sentence is the connective of widest scope.

The following table gives some examples of sentences and their main connectives.

P ® (Q Ú R) ®

(P ® Q) Ú R Ú

Ø (P ® Q) & S &

Ø ((P ® Q) & S) Ø

” x(Fx ® Gx) ” x

” xFx ® ” xGx ®

Ø $ x($ yRx « Gx) Ø

The main connective of a sentence determines what proof rules can be applied to that sentence.

Modus Ponens:

Modus ponens is a historically popular name for the inference rule we are calling ®E.

Modus ponens is thus the inference form used in the following argument:

If Austin is in Texas, it is in the United States.

Austin is in Texas.

\ Austin is in the United States.

Modus ponens thus allows one, from the combination of a conditional with the antecedent of the conditional, to derive the consequent of that conditional. Schematically, the inference form is:

P ® Q

P

\ Q

Modus ponens is an appropriate proof rule because the truth of the conditional requires either the truth of the consequent or the falsity of the antecedent. Since the second premise in the argument form prevents the antecedent from being false, the only way to make both premises true is by making the consequent – which is also the conclusion of the argument – true.

In truth table form:

P Q P ® Q P Q

T T T T T

T F F T F

F T T F T

F F T F F

Modus ponens is sometimes called modus ponendo ponens, to distinguish it from the inference rule modus tollendo ponens.

Modus Ponendo Ponens:

Modus ponendo ponens is an alternative name for the inference rule modus ponens, used to distinguish it from the inference rule modus tollendo ponens.

Modus Ponendo Tollens

Modus ponendo tollens is a historically popular name for an inference pattern exemplified in the following argument:

George Bush and Al Gore aren’t both president.

George Bush is president

\ Al Gore is not president.

Schematically, the inference form is either of the following:

Ø(P & Q)

P

\ ØQ

Ø(P & Q)

Q

\ ØP

Modus ponendo tollens is neither a primitive nor a derived rule in our proof system, but it is quite straightforward to give a proof which captures its effect.

Modus Tollendo Tollens

Modus tollendo tollens is an alternative name for the inference rule modus tollens, used to distinguish it from the inference rule modus ponendo tollens.

Modus Tollendo Ponens

Modus tollendo ponens is a historically popular name for the derived inference rule we are calling ÚE*.

Modus tollendo ponens is thus the inference used in the following argument:

Austin is either in Texas or in Oklahoma.

Austin is not in Oklahoma.

\ Austin is in Texas.

Modus tollendo ponens thus allows one, from a disjunction and the falsity of one disjunct, to conclude the truth of the other disjunct. Schematically, the inference form is either of the following:

P Ú Q

ØP

\ Q

P Ú Q

ØQ

\ P

Modus tollendo ponens is an appropriate inference rule because the disjunction requires at least one of the two disjuncts to be true. Given that one disjunct is false, it then follows that the second must be true, in order to preserve the truth of the disjunction.

In truth table form:

P Q P Ú Q ØP Q

T T T F T

T F T F F

F T T T T

F F F T F

Modus Tollens

Modus tollens is a historically popular name for the inference rule we are calling ®E*.

Modus tollens is thus the inference used in the following argument:

If Albert is the murderer, then he owns a gun.

Albert doesn’t own a gun.

\ Albert is not the murderer.

Modus tollens thus allows one, from a conditional and the falsity of the consequent of that conditional, to infer the falsity of the antecedent of the conditional. Schematically, the inference form is:

P ® Q

ØQ

\ ØP

Modus tollens is an appropriate rule of inference because the truth of the conditional requires either the falsity of the antecedent or the truth of the consequent. The second premise gives one the falsity of the consequent and rules out the possibility that the conditional is true by virtue of a true consequent. The truth of the conditional then requires the falsity of the antecedent.

In truth table form:

P Q P ® Q ØQ ØP

T T T F F

T F F T F

F T T F T

F F T T T

Modus tollens is also sometimes called modus tollendo tollens, to distinguish it from the inference rule modus ponendo tollens.

Naïve Set Theory

Naïve set theory is a simple and intuitive version of the theory of sets. Naïve set theory uses two primitive pieces of vocabulary:

The unary predicate ‘S’, intended to mean “is a set”.

The binary predicate ‘Î’, intended to mean “is a member of”.

These two predicates are then governed by:

The axiom of extensionality: “x”y((Sx & Sy) ® (“z(z Î x « z Î y) ® x = y)

The axiom schema of naïve abstraction: S{n : S(n )} & “z(z Î {n : S(n )} « S(n ))

The axiom schema of naïve abstraction secures the existence of a universe of sets, by guaranteeing that for every property there is a set of all and only those things having that property. The axiom of extensionality then settles the identity conditions for those sets, specifying that sets X and Y are to count as one and the same set if they have all the same members.

While naïve set theory has the virtue of being easy to use, it has the disadvantage of being inconsistent. Naïve abstraction on the property “is not a member of itself” will give the set {x: x Ï x}. However, the reasoning of Russell’s Paradox shows that there can be no such set, so naïve abstraction must be a false principle. Contemporary set theory repairs the contradiction of naïve set theory in any of a variety of ways, the most common of which is the move to the more constrained ZFC axioms.

Natural Number

A natural number is a member of the collection:

{0, 1, 2, 3, 4, …}

Formally, we say that the set of natural numbers is the intersection of all inductive sets, and that a natural number is then any member of the set of natural numbers.

Open Sentence

An open sentence is one which contains one or more free variables. Open sentences are not assigned truth values by interpretations. An open sentence can be thought of as analogous to a natural language sentence which contains a pronoun with no anaphor, such as:

He is a nice person.

In the absence of some information specifying to whom “he” refers, a truth value cannot be assigned to this sentence.

Ordinal

Informally, ordinals represent the use of numbers to indicate position in a sequence – first, second, third, and so on. They thus contrast with cardinals, which represent the use of numbers to indicate amount – one, two, three, and so on. The two notions coincide on the finite realm, but come apart on the infinite realm.

More formally, an ordinal is a set which is:

Transitive

Well-ordered by set membership

It follows that the collection of all ordinals is itself well-ordered by set membership, giving a unique and linear ordinal hierarchy.

The first infinite ordinal is , which is the set of all natural numbers. The next infinite ordinal is +1, which is the set containing all of the natural numbers and also .

Pairwise disjoint

A collection of sets is pairwise disjoint just in case any two elements of that collection are disjoint.

The following collection is pairwise disjoint:

{{1,2}, {3,6}, {5,8}, {7}, {10,11,12}}

The following collection is not pairwise disjoint:

{{1,2}, {3,4}, {2,5}}

Partial Ordering

A partial ordering is a relation which is either:

reflexive

antisymmetric

transitive

or:

irreflexive

asymmetric

transitive

The first is a loose partial ordering; the second is a strict partial ordering. A partial ordering does some of the work of placing a set of objects in order, but can allow some members of the set to be incomparable, with neither coming before the other in the ordering. Adding the condition of connectedness to a partial ordering creates a linear ordering.

The subset relation on a collection of sets is a loose partial ordering. Every set is a subset of itself, so is reflexive. If x y and y x, then x and y have the same members and are the same set, so is antisymmetric. If x y and y z, then x z, so is transitive. Since there can be two sets neither of which is a subset of the other, such as {1,2} and {2,3}, does not order all sets, and is not a linear ordering. The proper subset relation is a strict partial ordering.

Peano Axioms

The Peano axioms state the basic principles of arithmetic reasoning. They are expressed in a quantified logic using a unary predicate N, meaning “is a natural number”, and a monadic function s, meaning “successor”. The first four axioms are:

0 is a natural number: N0

The successor of any natural number is a natural number: x(Nx Ns(x))

0 is not the successor of any natural number: x(Nx & 0=s(x))

Different natural numbers have different successors: xy((Nx & Ny) (x y s(x) s(y)))

In addition to these four axioms, there is the axiom scheme of induction. Given any formula with only x free, there is an induction axiom of the form:

((0) & x((x) (s(x)))) x(x)

This axiom states that if (a) 0 has the property expressed by and (b) if a natural number has the property expressed by , its successor also has the property expressed by , then every natural number has the property expressed by . Since first-order quantified logic does not allow quantification over properties, separate induction axioms must be given for each property.

Petitio Principii

An alternative name for an argument that begs the question.

Power Set

The power set of a set is another set consisting of all subsets of the original set. Formally, we have:

“x Ã(X) = {y: y Í X}

For example, the set {1,2,3} has the following eight subsets:

Æ

{1}

{2}

{3}

{1,2}

{1,3}

{2,3}

{1,2,3}

Thus its power set is:

{Æ , {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}

The existence of the power set is guaranteed in the set theory we are using by the abstraction axioms, since given any set X, the set:

{y: y Í X}

is the power set of X, and is guaranteed by the appropriate instance of the abstraction axiom to exist.

Premise

A premise is a part of an argument – a sentence used in inferring a conclusion. In the argument:

Socrates is human.

All humans are mortal.

Socrates is mortal.

The sentences “Socrates is human” and “All humans are mortal”, and the two of them taken together imply the conclusion “Socrates is mortal”.

An argument can have any number of premises – no premises at all (in which case the argument claims that the conclusion is a logical truth), only a single premise, some larger finite number of premises, or even an infinite number of premises. In every case, all of the premises are taken together in evaluating the validity of the argument. What matters to validity is the status of the conclusion when all of the premises are true.

Range

The range of a relation R is the set of all things which something stands in the relation to. Thus the range of the reads relation is the set of all things which are read. Formally, we say:

R(R) = {x: y <y,x> R}

In the case of a function f:A B, the range of f is a subset of B.

Reflexive

A relation is reflexive if it always holds between an object and itself. “Is at least as tall as” is thus a reflexive relation, while “is taller than” is not a reflexive relation. Formally, we say:

R is reflexive xRxx

We can also define the reflexivity of a relation on a particular set:

R is reflexive on A x(x A Rxx)

Relation

A relation is a feature connecting two or more objects. Thus the relation of admiration connects two people X and Y if X admires Y.

In formal contexts, a relation is a set of ordered n-tuples, each of which indicates that some n objects stand in the relation to each other. A relation which relates pairs of objects, and which is thus a set of ordered pairs, is a binary relation.

If a binary relation R is a subset of A B for two sets A and B, it is called a relation between A and B. If it s a subset of A A for some set A, it is called a relation on A.

Satisfiable

A set of sentences is called satisfiable if it is possible for all of them to be true together. Formally, a set of sentences is true if there is an interpretation that makes all of them true.

The following set of sentences is satisfiable:

{P ® Q, Q ® R, Ø R}

Each member of this set is made true by the following interpretation:

P: F

Q: F

R: F

The following set of sentences is not satisfiable:

{P ® Q, Q ® P, ØP, ØQ}

While each sentence in this set is contingent and thus can be true, there is no interpretation that makes all four of the sentences true.

In the limiting case, a single sentence can be called satisfiable just in case the singleton set having that sentence as its only member is satisfiable. Thus, a single sentence is satisfiable if it is possible for that sentence to be true – that is, if it is valid or contingent.

No set of sentences containing a contradictory sentences is satisfiable. Any set of sentences containing only valid sentences is satisfiable. Given a set of contingent sentences, or a mixture of valid and contingent sentences, the set may or may not be satisfiable depending on the particular case, as the two examples above show.

Scope

The scope of an expression is a syntactic measurement of the extent of semantic impact of that expression.

In the formal languages of sentential and quantified logic, the scope of an expression is the smallest formula containing that expression. Thus we have the following:

In “P ® Ø(P Ú ØR)”

Scope of ® is “P ® Ø(P Ú ØR)”

Scope of first “Ø” is “Ø (P Ú ØR)”

Scope of “Ú” is “(P Ú ØR)”

Scope of second “Ø” is “ØR”

In “”x($yRxy « Ø$zRzx)”

Scope of “”x” is “”x($yRxy « Ø$zRzx)”

Scope of “$y” is “$yRyx”

Scope of “«” is “$yRxy « Ø$zRzx”

Scope of “Ø” is “Ø$zRzx”

Scope of “$z” is “$zRzx”

One expression is said to have wider scope than another if the scope of the second is a proper part of the scope of the first.

Formal languages typically use parentheses to make scope distinctions clear. Thus consider:

Ø P & Q

Ø (P & Q)

In the first sentence, “&” has wider scope than “Ø “. In the second sentence, “Ø ” has wider scope than “&”. The difference between the two is the parentheses: in the second sentence, the parentheses explicitly mark the scope of the “&” as limited to “P & Q” and thus allow the “Ø ” to take wide scope.

The scope of a connective determines what part of the sentence it has a semantic effect on. Thus consider again the above pair of sentences. In the first, the scope of the “Ø ” is limited to “P”, and only “P” is negated. In the second sentence, the scope of the “Ø ” covers the whole sentence, and it is the whole sentence that is negated.

In natural languages, in which there are no parentheses, there can often be scope ambiguities. Thus consider:

It’s not true that I stole the lamp and Fred broke it.

This sentence is ambiguous between:

The claim that I stole the lamp and Fred broke it, is not true.

Fred broke the lamp, and it is not true that I stole it.

The ambiguity centers on the relative scopes of the negation and conjunction. On the first reading, the sentence is analyzed as:

Ø (P & Q)

On the second reading, it is analyzed as:

Ø P & Q

In the absence of parentheses, context must often be used to make scope determinations. Quantified expressions in natural language create similar scope ambiguities. Thus consider:

Someone is mugged every five minutes in New York City.

This sentence is ambiguous between a natural reading on which the universal “every five minutes” has wider scope than the existential “someone”:

” x(Fx ® $ yMynx)

and a less natural reading on which the existential “someone” has wider scope than the universal “every five minutes”:

$x”y(Fy ® Mynx)

Set

A set is an arbitrary collection of objects. The notion is a very basic one, and difficult to define in words which aren’t either simple synonyms or misleading. Georg Cantor, the founder of modern set theory, described a set as “any collection…into a whole of definite, well-distinguished objects..of our intuition or thought”.

Sets can be specified either intensionally or extensionally. In an intensional specification, a set is identified by giving a property and taking the set of all and only things having that property. Thus:

{x: x is prime}

is the set of all prime numbers. In an extensional specification, a set is identified by giving an explicit list of its members, as in:

{2,3,5,7}

It is natural to assume (a) that sets are identical if they have exactly the same members and (b) that for any property, there is a set of all and only things having that property. The theory which results from these two assumptions is called naïve set theory. Unfortunately, it is known to be inconsistent, due to Russell’s Paradox. A more complicated axiomatization of set theory can be given by ZFC set theory, or by any number of alternative set theories.

Sound

An argument is sound if it is valid and all of its premises are true.

The following argument is sound:

Austin is in Texas.

Everything in Texas is in the United States.

\ Austin is in the United States.

A sound argument is always a valid argument, but not all valid arguments are sound arguments.

Since valid arguments preserve truth (cannot have true premises and a false conclusion), in a sound argument, where the premises are true, it is impossible for the conclusion to be false.

Strongly Connected

A relation R is strongly connected if any two objects stand in the relation in one direction or another and every object stands in the relation to itself. “Is at least as tall as” is a connected relation, while “admires” is not. A strongly connected relation can be formed out of a connected relation by adding all ordered pairs of the form <x,x> (the minimal reflexive relation). Formally, we say:

R is strongly connected xy(Rxy Ryx)

We can also define the connectedness of a relation on a particular set:

R is strongly connected on A xy(x,y A (Rxy Ryx))

Subset

One set is a subset of another if every member of the first set is also a member of the second set.

For example, the set:

{1,3,5}

is a subset of the set:

{1,2,3,4,5}

We thus write:

{1,3,5} Í {1,2,3,4,5}

Formally, the binary subset relation is defined as follows:

“x”y(x Í y « (Sx & Sy & “z(z Î x ® z Î y)))

Some additional examples of correct subset claims:

{1, {1}} Í {1, {1}, {{1}}, {{{1}}}}

{x: x is a mammal} Í {x: x is an animal}

{<x,y>: x< y} Í {<x,y>: x £ y}

Superset

One set is a superset of another if every member of the second set is also a member of the first set.

For example, the set:

{1,2,3,4,5}

is a superset of the set:

{1,3,5}

We thus write:

{1,2,3,4,5} Ê {1,2,3,4,5}

Formally, the binary superset relation is defined as follows:

“x”y(x Ê y « (Sx & Sy & ” z(z Î y ® z Î x)))

Some additional examples of correct superset claims:

{1, {1}, {{1}}, {{{1}}}} Ê {1, {1}}

{x: x is an animal} Ê {x: x is a mammal}

{<x,y>: x £ y} Ê {<x,y>: x< y}

The superset relation is the converse of the subset relation.

Surjective

A function f:A B is surjective if it covers its entire range B. Formally,

f: A B is surjective x(x B y(y A & f(y) = x))

Symbols

The following chart gives the meanings of many commonly-used logical and mathematical symbols:

Symbol Sample Use (If Applicable) Meaning

« (P « Q) Biconditional (“if and only if”)

º (P º Q) Biconditional (“if and only if”)

´ {1,2} ´ {2,3} Cartesian product

° f ° g(x) Composition

® (P ® Q) Conditional (“if…then”)

É (P É Q) Conditional (“if…then”)

& (P & Q) Conjunction (“and”)

Ù (P Ù Q) Conjunction (“and”)

. (P.Q) Conjunction (“and”)

· (P · Q) Conjunction (“and”)

^ Contradiction

BOX® P BOX® Q Counterfactual conditional (“If it had been the case that…it would have been the case that”)

à ® P à ® Q Counterfactual conditional (“If it had been the case that…it might have been the case that”)

i (i x)Fx Definite description (“the”)

Ú (P Ú Q) Disjunction (“or)

| (P|Q) Disjunction (“or”)

$ $ xFx Existential quantifier (“there exists”)

: ® f:A ® B Functional mapping

= 2 + 2 = 4 Identity

|= P & Q |= P Implies

Z Integers

Ç {1,2} Ç {2,3} Intersection

º P º Ø Ø P Logical equivalence

N Natural numbers

BOX BOXP Necessarily

L Lp Necessarily

Ø Ø P Negation (“not”)

~ ~P Negation (“not”)

Æ Null set

< > <a,b> Ordered pair (or ordered n-tuple)

à à P Possibly

M Mp Possibly

Ã Ã ({1,2,3}) Power set

|- P & Q |- P Proves

Â Real numbers

Î 1 Î {1,2} Set membership

{ } {x: Fx} Set name

– {1,2,3} – {2} Set subtraction

Í {1} Í {1,2} Subset

succ( ) succ(0) Successor function

‘ 0’ Successor function

Ê {1,2} Ê {1} Superset

\ P & Q, \

P Therefore

È {1} È {2} Union

” ” xFx Universal quantifier (“for all”)

( ) (x)Fx Universal quantifier (“for all”)

Symmetric

A relation is symmetric if, any time it holds in one direction between a pair of objects, it also holds in the other direction between that same pair of objects. “Is a relative of” is thus a symmetric relation, because any time A is a relative of B, it is also the case that B is a relative of A. Formally, we say:

R is symmetric « ” x” y(Rxy ® Ryx)

We can also define the symmetry of a relation on a particular set:

R is symmetric on A « ” x” y(x,y Î A ® (Rxy ® Ryx))

Truth-Functional

A connective is truth-functional if the truth value of a sentence formed using that connective is fully determined by the truth value of the component sentences linked by the connective. The connective “&”, for example, is truth functional. If is true and is true, then & is true; otherwise, & is false:

&

T T T

T F F

F T F

F F F

The connective “before”, on the other hand, is not truth-functional. From the truth values of and , nothing about the truth value of “ before ” can be determined. This truth value depends on the temporal relations between and in addition to their simple truth values.

Transitive

A relation is transitive if, any time it holds between some first object and a second object, and also holds between that second object and some third object, it also holds between the first object and the third object. “Later than” is thus a transitive relation, because if time t1 is later than time t2, and time t2 is later than time t3, then time t1 is later than time t3. Formally, we say:

R is transitive xyz((Rxy & Ryx) Rxz)

We can also define the transitivity of a relation on a particular set:

R is transitive on A xyz(x,y,z A ((Rxy & Ryx) Rxz))

Union

The union of two sets is a third set which contains everything which is in either one of the original two sets. Formally, we say:

R S = {x: x R x S}

Thus {1,2,3} {3,4,5} = {1,2,3,4,5}.

Unsatisfiable

A set of sentences is called unsatisfiable if it is not satisfiable. Thus an unsatisfiable set of sentences is one all of whose members cannot be true together. Formally, an unsatisfiable set is a set such that no interpretation makes true all of its members.

A single sentence can be called unsatisfiable just in case the singleton set having that sentence as its only member is unsatisfiable. Thus, a single sentence is satisfiable if it is contradictory.

Unsatisfiability and validity of arguments are closely linked. Given an argument with premises P1, …, Pn and conclusion C, the argument is valid if and only if the set:

{P1, …, Pn, Ø C}

is unsatisfiable.

Valid (as a trait of sentences)

A sentence is called valid if it is impossible for it to be false. Valid is thus one end of a spectrum which runs from valid to contingent (being able to be true and able to be false) to contradictory (being necessarily false).

The following sentences are examples of valid sentences:

If it’s going to rain, it’s going to rain.

Someone is such that if anyone is perfect, he is.

Either tomorrow is Wednesday, or it isn’t.

In a formal language, a valid sentence is one which is true relative to every interpretation. The following sentences are valid:

P ® (Q ® P)

P Ú ØP

“x” y(x = y « y = x)

Valid (as a trait of arguments)

An argument is called valid if the truth of the premises guarantees the truth of the conclusion.

The following is a valid argument:

Socrates is human.

All humans are mortal.

\ Socrates is mortal.

In any possible situation in which the two premises are true, the conclusion must also be true.

Valid arguments are of logical interest because they demand rational assent and allow us logically to obtain new beliefs. If one knows that some claims are true, and there is a valid argument with those claims as premises and some new claims as conclusion, then one is rationally justified in believing the new claim, because it must be true if the premises are true.

The existence of a valid argument does not in itself guarantee the truth of the conclusion. If there is a valid argument in which some or all of the premises are true, nothing can be determined about the truth of the conclusion – it can be either true or false. Only when all of the premises are true must the conclusion be true. Therefore we distinguish between valid arguments – which have the right logical form – and sound arguments, which are valid arguments in which all the premises (and hence, of necessity, also the conclusion) are true.

In a formal language, the rough-and-ready notion of validity given above is made precise by calling an argument valid just in case every interpretation that makes all of the premises of the argument true also makes the conclusion of the argument true.

Whole Number

A whole number is any member of the set:

{1, 2, 3, 4, 5, …}

Formally, we say that the set of whole numbers is the set of natural numbers without 0, and a whole number is any member of the set of whole numbers.