1. What is Logic? Flashcards
Logic is about many things, but most centrally it is about _________.
logical consequence
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”.
logical consequence;
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.
“Grant is male”
________ is truth-preservation by virtue of form
Logical consequence
For φ to be a logical consequence of ψ, it is not enough that we all know that _________.
φ is true if ψ is
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?
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.
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.
“it’s not the case that φ; either φ or ψ; therefore ψ”
Just as logical consequence is truth-preservation by virtue of form, ________ is truth by virtue of form.
logical truth
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 ______.
necessity;
form, not content
It is plausible that logical truth and logical consequence are related thus: a logical truth is _______. One can infer a logical truth by _______.
a sentence that is a logical consequence of the empty set of premises;
using logic alone, without the help of any premises
A central goal of logic is to study ______ and ______.
logical truth;
logical consequence
Modern logic is called “mathematical” or “symbolic” logic because its method is ________.
the mathematical study of formal languages
Modern logicians use the tools of mathematics (especially the tools of very abstract mathematics, such as set theory) to ________.
treat sentences and other parts of language as mathematical objects
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?
P→P;
P→P
Why are formal languages called “formal”? (They’re also sometimes called “artificial” languages.)
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.
Metalogic proofs are phrased in _______ and employ _______.
natural language (perhaps augmented with mathematical vocabulary); informal (though rigorous!) reasoning of the sort one would encounter in a mathematics book
Proofs in formal systems, unlike metalogic proofs, are phrased using ________.
sentences of formal languages, and proceed according to prescribed formal rules
Logicians often distinguish the “_____language” from the “_____language”.
object ;
meta
The object language is the language that’s being studied. One example is…
the language of propositional logic. Its sentences look like this:
P∧Q
∼(P∨Q)↔R
The metalanguage is the language we use to talk about the object language.
One example is…
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.
i) is it a sentence of the object language or the metalanguage?
ii) is it true?
‘P∨∼P’ is a logical truth.
“‘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.)
i) is it a sentence of the object language or the metalanguage?
ii) is it true?
(P∨Q)→(Q∨P)
‘(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!)
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’.
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.”
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.
‘Attorney and lawyer are synonyms’ confuses use and mention; inserting quotation marks thus fixes the problem:
‘Attorney’ and ‘lawyer’ are synonyms.
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.
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
Corner quotes
┌ and ┐
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
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:
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)
Under the semantic/model-theoretic approach, one…
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.)
Under the proof-theoretic approach, …
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 φ.
Proof-theoretic approach:
φ is provable from sentences ψ1, ψ2, … if and only if _______.
there is some way of moving by acceptable transitions from ψ1, ψ2, … to φ
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 ___________.
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
There are alternate philosophical conceptions of logical consequence. For example, there is the modal account: φ is a logical consequence of ψ1, ψ2, … iff __________.
it is not possible for ψ1, ψ2, … to all be true without φ being true (under some suitable notion of possibility)
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?
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’.
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) _______
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.)
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?
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.
We can speak of ______ logical constants (‘and’, ‘or’, ‘all’, ‘some’…) as well as ______ logical constants (∧, ∨, ∀, ∃…).
natural language;
symbolic
Unlike P, Q, and so on, which are ________, ∧ and ∨ fixedly represent ‘and’ and ‘or’.
not symbolic logical constants, and which do not fixedly represent any particular natural language sentences
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 ________.
hold by virtue of logical form; logical constants (plus punctuation and schematic variables); logical constants
“Standard logic” is what is usually studied in introductory logic courses. It includes propositional logic (logical constants: _______), and predicate logic (logical constants: ________).
∀,∃, variables
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 ___________.
extensions, deviations, and variations
In an extension we…
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.
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?
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.
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.
Variations
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.
Sets have ______.
members
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.
nothing else;
∈;
2 ∈ A, 4 ∈ A, and 6 ∈ A;
putting names of its members between braces;
“{2, 4, 6}”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.
0 ∈ N, 1 ∈ N, and so on;
“{0, 1, 2, 3,… }”
The members of a set need not be mathematical entities; _______ can be a member of a set. Sets can contain __________.
anything;
people, or cities, or—to draw nearer to our intended purpose—sentences and other linguistic entities
There is the empty set, __. This is the one set with no members. That is, for each object u, _________.
∅;
u is not a member of ∅ (i.e.: for each u, u ∈/ ∅).
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:
- 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.
- 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.
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
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 ________.
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
Various other useful set-theoretic notions can be defined in terms of the notion of membership:
- Set A is a subset of set B _____ when every member of A is a member of B.
- The intersection of A and B _____ is the set that contains all and only those things that are members of both A and B.
- 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).
(“A ⊆ B”);
(“A ∩ B”);
(“A ∪ B”)
Various other useful set-theoretic notions can be defined in terms of the notion of membership:
- Set A is a subset of set B (“A ⊆ B”) when ________.
- The intersection of A and B (“A ∩ B”) is the set that contains ________.
- The union of A and B (“A ∪ B”) is the set containing ________.
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)
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:
“{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}
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: _______.)
“{Ted, Obama}”;
“{Obama, Ted}”;
sets are identical if and only if they have exactly the same members
Sometimes we need to talk about set-like things containing objects in a particular order. For this purpose we use _______.
ordered sets
Two-membered ordered sets are called _______.
ordered pairs
To name the ordered pair of Obama and Ted, we use: _______.
“〈Obama, Ted〉”;
Here, the order is significant; 〈Obama, Ted〉 and 〈Ted, Obama〉 are not the same ordered pair.
The three-membered ordered set of u, v, and w (in that order) is written: ______; and similarly for ordered sets of any finite size.
〈u, v, w〉
An n-membered ordered set is called an _______.
n-tuple.
For the sake of convenience, let’s define the 1-tuple 〈u〉 to be just the object u itself.
A relation is _______.
just a feature of multiple objects taken together
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: ________.
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
_______ relations apply to two objects at a time.
“Binary”
The taller-than and less-than relations are _____ relations, or _____ relations as we might say.
binary;
“two-place”;
We can also speak of three-place relations, four-place relations, and so on.
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.
betweenness
Definition of relation: ________.
An n-place relation is a set of n-tuples
A binary (two-place) relation is _______.
a set of ordered pairs
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:
________
〈u, v〉;
〈m, n〉;
{〈1, 2〉,〈1, 3〉,〈1, 4〉…〈2, 3〉,〈2, 4〉… }
When 〈u, v〉 is a member of relation R, we say, equivalently, that _______.
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”
Definition of domain, range, over: Let R be any binary relation and A be any set.
- The domain of R _______ is the set _______.
- The range of R _______ is the set ________.
- R is over A iff _______.
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.
Definition of kinds of binary relations: Let R be any binary relation over some set A.
- R is serial (in A) iff ________.
- · R is reflexive (in A) iff ________.
- R is symmetric iff ________.
- R is transitive iff ________.
- R is an equivalence relation (in A) iff ________.
- R is total (in A) iff ________.
- for every u ∈ A, there is some v ∈ A such that Ruv;
- for every u ∈ A,Ru u
- for all u, v, if Ruv then Rvu
- for any u, v, w, if Ruv and Rvw then Ruw
- R is symmetric, transitive, and reflexive (in A)
- for every u, v ∈ A,Ruv
R is reflexive (in A) iff ________.
for every u ∈ A,Ru u
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
R is an equivalence relation (in A) iff _________.
R is symmetric, transitive, and reflexive (in A)
R is total (in A) iff _________.
for every u, v ∈ A,Ruv
R is total (in A) iff _________.
for every u, v ∈ A,Ruv
Relativize
to make or treat as relative to or dependent on something else.
· 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?
· 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.
A function ______ an object or objects (in a certain order), and ______ a further object.
“takes in”;
“spits out”;
For example, the addition function takes in two numbers, and spits out their sum.
As with sets, ordered sets, and relations, functions are not limited to mathematical entities: they can take in and spit out ______.
any objects whatsoever
We can speak of the father-of function, for example, which takes in ______ and spits out the ______.
person;
father of that person
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.
two-place;
one-place
An n-place function is simply a one-place function that takes in only ______.
n-tuples;
Thus, if you give the addition function the ordered pair 〈2, 5〉, it spits out 7.
The objects that a function takes in are called its _______, and the objects it spits out are called its _______.
arguments;
values
If u is an ______ of f we write “f(u)” for the value of function f as applied to the argument u.
argument
f(u) is the _____ that f spits out, if you feed it u.
object;
For example, where f is the father-of function, since Ron is my father we can write: f(Ted) = Ron.
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: _______.
f(u1, …, un);
a(2, 3) = 5
The domain of a function is the set of its ______, and its range is the set of its ______.
arguments;
values
If u is not in function f ’s domain (i.e., u is not one of f’s arguments), then ________.
f is undefined for u;
The father-of function, for example, is undefined for numbers (since numbers have no fathers).
A one-place function f is one-to-one iff _______.
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).
Definition of function-theoretic notions:
- A function is a set of ordered pairs, f, obeying the condition that if ____ and ____ are both members of f, then v = w.
- When 〈u, v〉 ∈ f , we say that ________.
- The domain of a function is _______; its range is ________.
- A function is n-place when ________.
Thus, a function is just a certain kind of binary relation—one that ________.
- 〈u, v〉;
〈u, w〉 - 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”
- the set of its arguments;
the set of its values - every member of its domain is an n-tuple
never relates a single thing u to two distinct objects v and w
Definition of Equinumerosity:
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.
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 _______.
natural numbers;
natural numbers and m =/= 0
To show that N is equinumerous with the set Q of rational numbers, we must _________.
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)
We’ll prove that there are more real than natural numbers by proving that…
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)
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).
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.)
Exercise 1.5* Is N equinumerous with the set Z of all integers, negative, positive, and zero: {··· −3, −2, −1, 0, 1, 2, 3,… }?
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
