1. What is Logic?

Question 1

Logic is about many things, but most centrally it is about _________.

Answer 1

logical consequence

Question 2

The statement “someone is male” is a _______ of the statement “Grant is male”. If Grant is male, then it logically follows that someone is male.
Put another way: the statement “Grant is male” logically implies the statement “someone is male”.

Answer 2

logical consequence;

Question 3

The statement __________ is a logical consequence of the statements “It’s not the case that Leisel is male” and “Either Leisel is male or Grant is male” (taken together). The first statement follows from the latter two statements; they logically imply it.
Put another way: the argument whose premises are the latter two statements, and whose conclusion is the former statement, is a logically correct one.

Answer 3

“Grant is male”

Question 4

________ is truth-preservation by virtue of form

Answer 4

Logical consequence

Question 5

For φ to be a logical consequence of ψ, it is not enough that we all know that _________.

Answer 5

φ is true if ψ is

Question 6

We all know that an apple will fall if it is dropped, but the relationship between falling and dropping does not hold by virtue of logic.
Why not?

Answer 6

For one thing, “by virtue of logic” requires the presence of some sort of necessary connection, a connection that is absent in the case of the dropped apple (since it would be possible—in some sense—for a dropped apple not to fall). For another, it requires the relationship to hold by virtue of the forms of the statements involved, whereas the relationship between “the apple was dropped” and “the apple fell” holds by virtue of the contents of these statements and not their form.

Question 7

The inference from “It’s not the case that Leisel is male” and “Either Leisel is male or Grant is male” to “Grant is male” is said to hold in virtue of form since any argument of the form __________ is logically correct.

Answer 7

“it’s not the case that φ; either φ or ψ; therefore ψ”

Question 8

Just as logical consequence is truth-preservation by virtue of form, ________ is truth by virtue of form.

Answer 8

logical truth

Question 9

Logical truth is truth by virtue of form.
Examples might include: “it’s not the case that snow is white and also not white”, “All fish are fish”, and “If Grant is male then someone is male”. As with logical consequence, logical truth is thought to require some sort of ______ and to hold by virtue of ______.

Answer 9

necessity;

form, not content

Question 10

It is plausible that logical truth and logical consequence are related thus: a logical truth is _______. One can infer a logical truth by _______.

Answer 10

a sentence that is a logical consequence of the empty set of premises;
using logic alone, without the help of any premises

Question 11

A central goal of logic is to study ______ and ______.

Answer 11

logical truth;

logical consequence

Question 12

Modern logic is called “mathematical” or “symbolic” logic because its method is ________.

Answer 12

the mathematical study of formal languages

Question 13

Modern logicians use the tools of mathematics (especially the tools of very abstract mathematics, such as set theory) to ________.

Answer 13

treat sentences and other parts of language as mathematical objects

Question 14

The formal sentence _____ is a tautology, but since it is uninterpreted, we probably shouldn’t call it a logical truth. Rather, it represents logical truths like “If snow is white then snow is white.” A logical truth ought to at least to be true, after all, and _____ isn’t true, since it doesn’t even have a meaning—what’s the meaning of P?

Answer 14

P→P;

P→P

Question 15

Why are formal languages called “formal”? (They’re also sometimes called “artificial” languages.)

Answer 15

Because their properties are mathematically stipulated, rather than being pre-existent in flesh-and-blood linguistic populations. We stipulatively define a formal language’s grammar. We must stipulatively define any properties of the symbolic sentences that we want to study, for example, the property of being a tautology. Formal languages often contain abstractions, like the sentence letters P, Q, … of propositional logic.

Question 16

Metalogic proofs are phrased in _______ and employ _______.

Answer 16

natural language (perhaps augmented with mathematical vocabulary);
informal (though rigorous!) reasoning of the sort one would encounter in a mathematics book

Question 17

Proofs in formal systems, unlike metalogic proofs, are phrased using ________.

Answer 17

sentences of formal languages, and proceed according to prescribed formal rules

Question 18

Logicians often distinguish the “_____language” from the “_____language”.

Answer 18

object ;

meta

Question 19

The object language is the language that’s being studied. One example is…

Answer 19

the language of propositional logic. Its sentences look like this:
P∧Q
∼(P∨Q)↔R

Question 20

The metalanguage is the language we use to talk about the object language.
One example is…

Answer 20

English, as it is used in this book.
Here are some example sentences of the metalanguage:
“P∧Q” is a formal sentence with three symbols

Every sentence of propositional logic has the same number of left parentheses as right parentheses

Every provable formula is a tautology

Thus, we formulate metalogical claims about an object language in the metalanguage, and prove such claims by reasoning in the metalanguage.

Question 21

i) is it a sentence of the object language or the metalanguage?
ii) is it true?
‘P∨∼P’ is a logical truth.

Answer 21

“‘P∨∼P’ is a logical truth” is a sentence of the metalanguage, and (I would say) is false. ‘P∨∼P’ contains the meaningless letter ‘P’, so it isn’t a logical truth. Rather, it represents logical truths (assuming the law of the excluded middle is correct! See chapter 3.)

Question 22

i) is it a sentence of the object language or the metalanguage?
ii) is it true?
(P∨Q)→(Q∨P)

Answer 22

‘(P∨Q)→(Q∨P)’ is a sentence of the object language. Since it contains meaningless expressions (‘P’, ‘Q’), it isn’t true. (Not that it’s false!)

Question 23

i) is it a sentence of the object language or the metalanguage?
ii) is it true?
‘Frank and Joe are brothers’ logically implies ‘Frank and Joe are siblings’.

Answer 23

This is a bit of a trick question. “‘Frank and Joe are brothers’ logically implies ‘Frank and Joe are siblings’” is a sentence of English, which is talking about further sentences of English. So English is functioning here both as the object language and as the metalanguage. As for whether the sentence is true, I would say no, since the implication is not “formal.”

Question 24

Each of the following sentences confuses use and mention. In each case, fill in quotation marks to x the problem.
* Attorney and lawyer are synonyms.

Answer 24

‘Attorney and lawyer are synonyms’ confuses use and mention; inserting quotation marks thus fixes the problem:
‘Attorney’ and ‘lawyer’ are synonyms.

Question 25

Each of the following sentences confuses use and mention. In each case, fill in quotation marks to x the problem.
* If S1 is an English sentence and S2 is another English sentence, then the string S1 and S2 is also an English sentence.

Answer 25

How can we insert quotation marks to remove the use-mention confusion in ‘If S1
is an English sentence and S2 is another English sentence, then the string S1
and S2 is also an English sentence’? This is again a bit of a trick question. You might think to do it this way:

If S1 is an English sentence and S2 is another English sentence, then the string ‘S1 and S2’ is also an English sentence.

But this isn’t right. It makes the (false) claim that the string of letters ‘S1 and S2’ (a string that contains the variables ‘S1’ and ‘S2’) is an English sentence, whereas the intention of the original sentence was to say that strings like ‘Snow is white and grass is green’ and ‘Roses are red and violets are blue’ are English sentences. Really, what we want is something like this:

If S1 is an English sentence and S2 is another English sentence, then the string consisting of S1, followed by ‘and’, followed by S2, is also an English sentence.

Quine (1940, 36) invented a device for saying such things more concisely. In his notation, we could write instead:
If S1 is an English sentence and S2 is another English sentence, then ┌S1 and S2┐ is also an English sentence.

His “corner quotes”, ‘┌’ and ‘┐’, work like regular quotation marks, except when it comes to variables of the metalanguage such as ‘S1’ and ‘S2’. Expressions other than such variables simply refer to themselves within corner quotes, just as all expressions do within regular quotation marks. But metalanguage variables refer to their values—i.e., the linguistic expressions they stand for—rather than themselves, within Quine’s corner quotes. Thus,

┌S1 and S2┐

means the same as:

the string consisting of S1, followed by ‘and’, followed by S2

Question 26

Corner quotes

Answer 26

┌ and ┐

Question 27

Semantic/Model-theoretic approach:

φ is represented as being a logical consequence of ψ1, ψ2, … if and only if _______.

Answer 27

φ is true in any model in which each of ψ1, ψ2, … is true

Question 28

Semantic/Model-theoretic approach:
φ is represented as being a logical consequence of ψ1, ψ2, … if and only if φ is true in any model in which each of
ψ1, ψ2, … is true.
This isn’t a theory of genuine logical consequence. It’s only _________. What theory of genuine logical consequence lies behind it? Perhaps one like this:

Answer 28

a way of representing logical consequence using formal languages;

“φ is a logical consequence of ψ1, ψ2 … if and only if the meanings of the logical expressions in φ and ψ1, ψ2 … guarantee that φ is true whenever ψ1, ψ2 … are all true.” (Nonlogical expressions are expressions other than ‘and’, ‘or’, ‘not’, ‘some’, and so on)

Question 29

Under the semantic/model-theoretic approach, one…

Answer 29

chooses a formal language, defines a notion of model (or interpretation) for the chosen language, defines a notion of truth-in-a-model for sentences of the language, and then finally represents logical consequence for the chosen language as truth-preservation in models (φ is represented as being a logical consequence of ψ1, ψ2, … if and only if φ is true in any model in which each of ψ1, ψ2, … is true.)

Question 30

Under the proof-theoretic approach, …

Answer 30

logical consequence is more a matter of provability than of truth-preservation. As with the semantic account, there is a question of whether we have here a proper theory about the nature of logical consequence (in which case we must ask: what is provability? by which rules?
and in which language?) or whether we have merely a preference for a certain approach to formalizing logical consequence. In the latter case, the approach to formalization is one in which we define up a relation of provability between sentences of formal languages. We do this, roughly speaking, by dening certain acceptable “transitions” between sentences of formal languages, and then saying that a sentence φ is provable from sentences ψ1, ψ2, … if and only if there is some way of moving by acceptable transitions from ψ1, ψ2, … to φ.

Question 31

Proof-theoretic approach:

φ is provable from sentences ψ1, ψ2, … if and only if _______.

Answer 31

there is some way of moving by acceptable transitions from ψ1, ψ2, … to φ

Question 32

There are alternate philosophical conceptions of logical consequence. For example, there is the view of W. V. O. Quine: φ is a logical consequence of ψ1, ψ2, … iff ___________.

Answer 32

there is no way to (uniformly) substitute expressions for nonlogical expressions in φ and ψ1, ψ2, … so that ψ1, ψ2, … all become true but φ does not

Question 33

There are alternate philosophical conceptions of logical consequence. For example, there is the modal account: φ is a logical consequence of ψ1, ψ2, … iff __________.

Answer 33

it is not possible for ψ1, ψ2, … to all be true without φ being true (under some suitable notion of possibility)

Question 34

Let sentence S1 be ‘There exists an x such that x and x are identical’, and let S2 be ‘There exists an x such that there exists a y such that x and y are not identical’. Does S1 logically imply S2 according to the modal criterion? According to Quine’s criterion?

Answer 34

Let sentence S1 be ‘There exists an x such that x and x are identical’, and let S2 be ‘There exists an x such that there exists a y such that x and y are not identical’.
Does S1 logically imply S2 according to the modal criterion? Well, that depends. It depends on what is possible. You might think that there could have existed only a single thing, in which case S1 would be true and S2 would be false. If this is indeed possible, then S1 doesn’t logically imply S2 (given the modal criterion). But some people think that numbers exist necessarily, and in particular that it’s necessarily true that the numbers 0 and 1 exist and are not identical. If this is correct, then it wouldn’t be possible for S1 to be true while S2 is false (since it wouldn’t be possible for S2 to be false.) And so, S1 would logically imply S2, given the modal criterion.
How about according to Quine’s criterion? Again, it depends—in this case on which expressions are logical expressions. If (as is commonly supposed) ‘there exists an x such that’, ‘there exists a y such that’, ‘not’, and ‘are identical’ are all logical expressions, then all expressions in S1 and S2 are logical expressions. So, since each sentence is in fact true, there’s no way to substitute nonlogical expressions to make S1 true and S2 false. So S1 logically implies S2 (according to Quine’s criterion). But suppose ‘are identical’ is not a logical expression. Then S1 would not logically imply S2, according to Quine’s criterion. For consider the result of substituting the predicate ‘are both existent’ for ‘are identical’. S1 then becomes true: ‘There exists an x such that x and x are both existent’, whereas S2 becomes false: ‘There exists an x such that there exists a y such that x and y are not both existent’.

Question 35

Consider an implication that, one is inclined to say, does hold by virtue of form; the implication from ‘Leisel is a swimmer and Leisel is famous’ to ‘Leisel is a swimmer’. This holds by virtue of form, one might think, because i) _______ and ii) _______. But the defender of the modal conception of logical consequence could say the following:
The inference from ‘Grant is a bachelor’ to ‘Grant is unmarried’ also holds in virtue of form. For: i) _______ and ii) _______

Answer 35

it has the form “φ and ψ; so, φ”;
for any pair of sentences of this form, the first logically implies the second;
it has the form “α is a bachelor; so, α is unmarried”;
for any pair of sentences of this form, the first sentence logically implies the second (since it’s impossible for the first to be true while the second is false.)

Question 36

We normally think of the “forms” of inferences as being things like “φ and ψ; so, φ”, and not things like “α is a bachelor; so, α is unmarried”, but why not?

Answer 36

When we assign a form to an inference, we focus on some phrases while ignoring others. The phrases we ignore disappear into the schematic letters (φ, ψ, and α…); the phrases on which we focus remain (‘and’, ‘bachelor’, ‘unmarried’). Now, logicians do not focus on just any old phrases. They focus on ‘and’, ‘or’, ‘not’, ‘if then’, and so on, in propositional logic; on ‘all’ and ‘some’ in addition in predicate logic; and on a few others. But they do not focus on ‘bachelor’ and ‘unmarried’. Call the words on which logicians focus—the words they leave intact when constructing forms, and the words for which they introduce special symbolic correlates, such as ∧, ∨, and ∀—the logical constants.

Question 37

We can speak of ______ logical constants (‘and’, ‘or’, ‘all’, ‘some’…) as well as ______ logical constants (∧, ∨, ∀, ∃…).

Answer 37

natural language;

symbolic

Question 38

Unlike P, Q, and so on, which are ________, ∧ and ∨ fixedly represent ‘and’ and ‘or’.

Answer 38

not symbolic logical constants, and which do not fixedly represent any particular natural language sentences

Question 39

In terms of the notion of a logical constant, we can say why the inference from ‘Grant is a bachelor’ to ‘Grant is unmarried’ is not a logical one. When we say that logical implications hold by virtue of form, we mean that they _______; and the form “α is a bachelor; so, α is unmarried” is not a logical form. A logical form must consist exclusively of _______; and the fact is that logicians do not treat ‘bachelor’ and ‘unmarried’ as ________.

Answer 39

hold by virtue of logical form;
logical constants (plus punctuation and schematic variables);
logical constants

Question 40

“Standard logic” is what is usually studied in introductory logic courses. It includes propositional logic (logical constants: _______), and predicate logic (logical constants: ________).

Answer 40

∀,∃, variables

Question 41

Non-classical logics (and sometimes alternative logics) is the name given to formal systems that differ in a significant way from standard logical systems such as propositional and predicate logic. There are several ways in which this is done, including by way of ___________.

Answer 41

extensions, deviations, and variations

Question 42

In an extension we…

Answer 42

add to standard logic. We add new symbolic logical constants (for example, the ✷ of modal logic), and new cases of logical consequence and logical truth that we can model using the new logical constants. We do this in order to represent more facets of the notion of logical consequence. We extend propositional logic, after all, to get predicate logic. Propositional logic is great as far as it goes, but it cannot represent the logical implication of ‘someone is male’ by ‘Grant is male’. That is why we add quantifiers, variables, predicates, and so on, to propositional logic (new symbols), and add means to deal with these new symbols in semantics and proof theory (new cases of logical consequence and logical truth we model), to obtain predicate logic.

Question 43

In a deviation we retain the usual set of logical constants, but change what we say about them. We keep standard logic’s symbols, but alter its proof theory and semantics, thereby offering a different model of logical consequence and logical truth. Why do this?

Answer 43

Perhaps because we think that standard logic is wrong. For example, the standard semantics for propositional logic counts the sentence P∨∼P as a tautology. But some philosophers resist the idea that natural language sentences like the following are logically true:

Either I am tall or I am not tall
Either there will be a sea battle tomorrow or there will
not be a sea battle tomorrow

If these philosophers are right, then the standard notion of a tautology is an imperfect model of genuine logical truth, and we need a better model.

Question 44

In a deviation we…

Answer 44

retain the usual set of logical constants, but change what we say about them. We keep standard logic’s symbols, but alter its proof theory and semantics, thereby offering a different model of logical consequence and logical truth.

Question 45

Variations

Answer 45

Variations also change standard logic, but here the changes are, roughly speaking, merely notational; they leave the content of standard logic unaltered.
For example, in Polish notation, instead of writing P→(Q∧R), we write →P∧QR; binary connectives go in front of the sentences they connect rather than between them.

Question 46

Sets have ______.

Answer 46

members

Question 47

Consider the set, A, of even integers between 2 and 6. 2 is a member of A, 4 is a member of A, 6 is a member of A; and ______ is a member of A. We use the expression “__” for membership; thus, we can say:
________. We often name a set by ________: ______ is another name of A.

Answer 47

nothing else;
∈;
2 ∈ A, 4 ∈ A, and 6 ∈ A;
putting names of its members between braces;
“{2, 4, 6}”

Question 48

We can speak of sets with infinitely many members. Consider N, the set of natural numbers. Each natural number is a member of N; thus, ______. We can informally name this set with the brace notation as well: ______, so long as it is clear which continued series the ellipsis signifies.

Answer 48

0 ∈ N, 1 ∈ N, and so on;

“{0, 1, 2, 3,… }”

Question 49

The members of a set need not be mathematical entities; _______ can be a member of a set. Sets can contain __________.

Answer 49

anything;

people, or cities, or—to draw nearer to our intended purpose—sentences and other linguistic entities

Question 50

There is the empty set, __. This is the one set with no members. That is, for each object u, _________.

Answer 50

∅;

u is not a member of ∅ (i.e.: for each u, u ∈/ ∅).

Question 51

Though the notion of a set is an intuitive one, the Russell Paradox (discovered by Bertrand Russell) shows that it must be employed with care. Let R be the set of all and only those sets that are not members of themselves. That is, R is the set of non-self-members. Russell asks the following question: is R a member of itself? There are two possibilities:

Answer 51

1. R ∈/ R. Thus, R is a non-self-member. But R was said to be the set of all non-self-members, and so we’d have R ∈ R. Contradiction.
2. R ∈ R. So R is not a non-self-member. R, by denition, contains only non-self-members. So R ∈/ R. Contradiction.

Thus, each possibility leads to a contradiction. But there are no remaining possibilities—either R is a member of itself or it isn’t! So it looks like the very idea of sets is paradoxical.

Question 52

Since Russell’s time, set theorists have developed theories of sets that avoid Russell’s paradox (as well as other related paradoxes). They do this chiefly by _________.

Answer 52

imposing rigid restrictions on when sets exist

Question 53

Since Russell’s time, set theorists have developed theories of sets that avoid Russell’s paradox (as well as other related paradoxes). They do this chiefly by imposing rigid restrictions on when sets exist. So far we have been blithely assuming that there exist various sets: the set N, sets containing people, cities, and sentences, Russell’s set R. That got us into trouble. So what we want is ________.

Answer 53

a theory of when sets exist that blocks the Russell paradox by saying that set R simply doesn’t exist (for then Russell’s argument falls apart), but which says that the sets we need to do mathematics and metalogic do exist

Question 54

Various other useful set-theoretic notions can be defined in terms of the notion of membership:

1. Set A is a subset of set B _____ when every member of A is a member of B.
2. The intersection of A and B _____ is the set that contains all and only those things that are members of both A and B.
3. The union of A and B _____ is the set containing all and only those things that are members of either A or B (or both).

Answer 54

(“A ⊆ B”);
(“A ∩ B”);
(“A ∪ B”)

Question 55

Various other useful set-theoretic notions can be defined in terms of the notion of membership:

1. Set A is a subset of set B (“A ⊆ B”) when ________.
2. The intersection of A and B (“A ∩ B”) is the set that contains ________.
3. The union of A and B (“A ∪ B”) is the set containing ________.

Answer 55

every member of A is a member of B;
all and only those things that are members of both A and B;
all and only those things that are members of either A or B (or both)

Question 56

Suppose we want to refer to the set of the so-and-sos—that is, the set containing all and only objects, u, that satisfy the condition “so-and so”. We’ll do this with the term _______. Thus, we could write: _______. And we could restate the definitions of ∩ and ∪ as follows:

Answer 56

“{u: u is a so-and-so}”;

“N = {u : u is a natural number}”;

A∩B = {u : u ∈ A and u ∈ B}
A∪B = {u : u ∈ A or u ∈ B}

Question 57

Sets have members, but they don’t contain them in any particular order. For example, the set containing me and Barack Obama doesn’t have a “first” member. _______ and _______ are two different names for the same set—the set containing just Obama and me. (This follows from the “criterion of identity” for sets: _______.)

Answer 57

“{Ted, Obama}”;
“{Obama, Ted}”;
sets are identical if and only if they have exactly the same members

Question 58

Sometimes we need to talk about set-like things containing objects in a particular order. For this purpose we use _______.

Answer 58

ordered sets

Question 59

Two-membered ordered sets are called _______.

Answer 59

ordered pairs

Question 60

To name the ordered pair of Obama and Ted, we use: _______.

Answer 60

“〈Obama, Ted〉”;

Here, the order is significant; 〈Obama, Ted〉 and 〈Ted, Obama〉 are not the same ordered pair.

Question 61

The three-membered ordered set of u, v, and w (in that order) is written: ______; and similarly for ordered sets of any finite size.

Answer 61

〈u, v, w〉

Question 62

An n-membered ordered set is called an _______.

Answer 62

n-tuple.

For the sake of convenience, let’s define the 1-tuple 〈u〉 to be just the object u itself.

Question 63

A relation is _______.

Answer 63

just a feature of multiple objects taken together

Question 64

A relation is just a feature of multiple objects taken together.
The taller-than relation is one example: ________.
Another example is the less-than relation for numbers: ________.

Answer 64

When one person is taller than another, that’s a feature of those two objects taken together;

When one number is less than another, that’s a feature of those two numbers taken together

Question 65

_______ relations apply to two objects at a time.

Answer 65

“Binary”

Question 66

The taller-than and less-than relations are _____ relations, or _____ relations as we might say.

Answer 66

binary;
“two-place”;
We can also speak of three-place relations, four-place relations, and so on.

Question 67

An example of a three-place relation would be the ______ relation for numbers:
the relation that holds among 2, 5, and 23 (in that order), for example.

Answer 67

betweenness

Question 68

Definition of relation: ________.

Answer 68

An n-place relation is a set of n-tuples

Question 69

A binary (two-place) relation is _______.

Answer 69

a set of ordered pairs

Question 70

The taller-than relation may be taken to be the set of ordered pairs _____ such that u is a taller person than v.
The less-than relation for positive integers is the set of ordered pairs _____ such that m is a positive integer less than n, another positive integer. That is, it is the following set:
________

Answer 70

〈u, v〉;

〈m, n〉;
{〈1, 2〉,〈1, 3〉,〈1, 4〉…〈2, 3〉,〈2, 4〉… }

Question 71

When 〈u, v〉 is a member of relation R, we say, equivalently, that _______.

Answer 71

u and v “stand in” R, or R “holds between” u and v, or that u “bears” R to v. Most simply, we write “Ruv”

Question 72

Definition of domain, range, over: Let R be any binary relation and A be any set.

1. The domain of R _______ is the set _______.
2. The range of R _______ is the set ________.
3. R is over A iff _______.

Answer 72

1. (“dom(R)”);
 {u: for some v,Ruv}
2. (“ran(R)”);
{u: for some v,Rv u}
3. dom(R) ⊆ A and ran(R) ⊆ A;

In other words, the domain of R is the set of all things that bear R to something; the range is the set of all things that something bears R to; and R is over A iff the members of the ’tuples in R are all drawn from A.

Question 73

Definition of kinds of binary relations: Let R be any binary relation over some set A.

1. R is serial (in A) iff ________.
2. · R is reflexive (in A) iff ________.
3. R is symmetric iff ________.
4. R is transitive iff ________.
5. R is an equivalence relation (in A) iff ________.
6. R is total (in A) iff ________.

Answer 73

1. for every u ∈ A, there is some v ∈ A such that Ruv;
2. for every u ∈ A,Ru u
3. for all u, v, if Ruv then Rvu
4. for any u, v, w, if Ruv and Rvw then Ruw
5. R is symmetric, transitive, and reflexive (in A)
6. for every u, v ∈ A,Ruv

Question 74

R is reflexive (in A) iff ________.

Answer 74

for every u ∈ A,Ru u

Question 75

R is symmetric iff ________.

Answer 75

for all u, v, if Ruv then Rvu

Question 76

R is transitive iff _________.

Answer 76

for any u, v, w, if Ruv and Rvw then Ruw

Question 77

R is an equivalence relation (in A) iff _________.

Answer 77

R is symmetric, transitive, and reflexive (in A)

Question 78

R is total (in A) iff _________.

Answer 78

for every u, v ∈ A,Ruv

Question 79

R is total (in A) iff _________.

Answer 79

for every u, v ∈ A,Ruv

Question 80

Relativize

Answer 80

to make or treat as relative to or dependent on something else.

Question 81

· R is symmetric iff for all u, v, if Ruv then Rvu
· R is transitive iff for any u, v, w, if Ruv and Rvw then Ruw

Why don’t symmetry and transitivity have to be relativized to a set?

Answer 81

· R is symmetric iff for all u, v, if Ruv then Rvu
· R is transitive iff for any u, v, w, if Ruv and Rvw then Ruw

Because they only say what must happen if R holds among certain things. Symmetry, for example, says merely that if R holds between u and v, then it must also hold between v and u, and so we can say that a relation is symmetric absolutely, without implying that everything is in its domain.

Question 82

A function ______ an object or objects (in a certain order), and ______ a further object.

Answer 82

“takes in”;
“spits out”;

For example, the addition function takes in two numbers, and spits out their sum.

Question 83

As with sets, ordered sets, and relations, functions are not limited to mathematical entities: they can take in and spit out ______.

Answer 83

any objects whatsoever

Question 84

We can speak of the father-of function, for example, which takes in ______ and spits out the ______.

Answer 84

person;

father of that person

Question 85

Some functions must take in more than one object before they are ready to spit out something.
For example, you need to give the addition function two numbers in order to get it to spit out something; for this reason it is called a ______ function. The father-of function, on the other hand, needs to be given only one object, so it is a ______ function.

Answer 85

two-place;

one-place

Question 86

An n-place function is simply a one-place function that takes in only ______.

Answer 86

n-tuples;

Thus, if you give the addition function the ordered pair 〈2, 5〉, it spits out 7.

Question 87

The objects that a function takes in are called its _______, and the objects it spits out are called its _______.

Answer 87

arguments;

values

Question 88

If u is an ______ of f we write “f(u)” for the value of function f as applied to the argument u.

Answer 88

argument

Question 89

f(u) is the _____ that f spits out, if you feed it u.

Answer 89

object;

For example, where f is the father-of function, since Ron is my father we can write: f(Ted) = Ron.

Question 90

When f is an n-place function—i.e., its arguments are n-tuples—instead of writing f(〈u1, …, un〉) we write simply _______.
So where a is the addition function, we can write: _______.

Answer 90

f(u1, …, un);

a(2, 3) = 5

Question 91

The domain of a function is the set of its ______, and its range is the set of its ______.

Answer 91

arguments;

values

Question 92

If u is not in function f ’s domain (i.e., u is not one of f’s arguments), then ________.

Answer 92

f is undefined for u;

The father-of function, for example, is undefined for numbers (since numbers have no fathers).

Question 93

A one-place function f is one-to-one iff _______.

Answer 93

for any u and v in its domain, if u =/= v then f(u) =/= f(v). (The function of natural numbers f defined by the equation f(n) = n + 1 is an example).

Question 94

Definition of function-theoretic notions:

1. A function is a set of ordered pairs, f, obeying the condition that if ____ and ____ are both members of f, then v = w.
2. When 〈u, v〉 ∈ f , we say that ________.
3. The domain of a function is _______; its range is ________.
4. A function is n-place when ________.

Thus, a function is just a certain kind of binary relation—one that ________.

Answer 94

1. 〈u, v〉;
   〈u, w〉
2. u is an argument of f, v is a value of f , and that f maps u to v; and we write: “f (u) = v”
3. the set of its arguments;
   the set of its values
4. every member of its domain is an n-tuple

never relates a single thing u to two distinct objects v and w

Question 95

Definition of Equinumerosity:

Answer 95

Sets A and B are equinumerous iff there exists some one-to-one function whose domain is A and whose range is B.

Intuitively: sets are equinumerous when each member of either set can be associated with a unique member of the other set. You can line their members up.

For example, comparing the set N of natural numbers and the set E of even natural numbers. These sets have the same size:
N: 0 1 2 3 4 5 …
E: 0 2 4 6 8 10 …
If two sets can be “lined up” in this way, then they have the same size.
Mathematically, this function, f, may be defined thus:
f (n) = 2n (for any n ∈ N)
It’s quite surprising that a set can be equinumerous with a mere subset of itself. But that’s how it goes with infinity.

Question 96

Rational numbers are equinumerous with the _______. A (nonnegative) rational number is a number that can be written as a fraction n/m where n and m are _______.

Answer 96

natural numbers;

natural numbers and m =/= 0

Question 97

To show that N is equinumerous with the set Q of rational numbers, we must _________.

Answer 97

find a one-to-one function whose domain is N and whose range is Q.
Each rational number is represented in the grid on page 32

(Note: review pages 32-36 later)

Question 98

We’ll prove that there are more real than natural numbers by proving that…

Answer 98

there are more real numbers between 0 and 1 than there are natural numbers. Let R be the set of real numbers in this interval. Now, consider the function f which maps each natural number n to 1/(n+2). This is a one-to-one function whose domain is N and whose range is {1/2, 1/3, 1/4, …}. But this latter set is a subset of R. So R is at least as big as N. So all we need to do is show that R is not the same size as N. And we can do this by showing that the assumption that N and R are the same size would lead to a contradiction.
(Check page 36)

Question 99

Exercise 1.4* For any set, A, the powerset of A is defined as the set of all A’s subsets. Write out the definition of the powerset of A in the “{u : … }” notation. Write out the powerset of {2, 4, 6} in the braces notation (the one where you list each member of the set).

Answer 99

Here is the definition of the powerset of A: {u : u ⊆ A}. The powerset of {2, 4, 6} is {∅, {2}, {4}, {6}, {2, 4}, {2, 6}, {4, 6}, {2, 4, 6}}. Notice that the powerset of a set always contains both the null set and the set itself (look at the definition of ‘subset’ to see why this is so.)

Question 100

Exercise 1.5* Is N equinumerous with the set Z of all integers, negative, positive, and zero: {··· −3, −2, −1, 0, 1, 2, 3,… }?

Answer 100

N and Z are equinumerous, because of the following function
f : f (0) = 0, f (1) = 1, f (2) = −1, f (3) = 2, f (4) = −2, f (5) = 3, f (6) = −3,….
This function can be defined more rigorously as follows:
(for any n ∈ N)
-n/2 if n is even
f(n) = {
(n+1)/2 if n is odd