The End of an Era - That of The Natural Numbers
in [Math]
|
From: Alan Smaill on 28 May 2010 10:22 Nam Nguyen <namducnguyen(a)shaw.ca> writes: > Alan Smaill wrote: >> Nam Nguyen <namducnguyen(a)shaw.ca> writes: >> >>> Alan Smaill wrote: >>>> Fine, take U = {0,1,2}, and take everything else as above. >>> Well, so far you've only spelled out U (and in effect <'A',U>). >>> You've not spelled out the mapping (ordered pair) <'blue',p_blue> >>> where p_blue is an actual _set_. Iow, if R is p_blue, can you >>> spell out the predicate-set R? >> >> The set is the extension of the relation R: >> >> { x in U | R(x) } = {1} > > Now then, let's extend the language L(t4) to L(T4b) so it > has another 1-ary symbol 'non-blue', and extend T4 into > T4b so it has another axiom: non-blue(c1) <-> ~blue(c1). > > Can we keep the model M4 for T4b? If not what can we keep, > and what should we add? You need to say what the meaning of the new predicate is. This can be done by extending the old structure, eg by takinh extension of not-blue as { x in U | not R(x) } = {0,2}, which then provides a different structure which is a model for T4b. >> Are you claiming that your notion of model is equivalent to >> Shoenfield's? > > Of course I do. It was not clear to me if you thing you are correcting Shoenfield, or following him. Several of your claims are just not consistent with what he wrote, as others have pointed out. > And I'm still in the process of doing the explanation > so I hope you don't mind answering the new question above. > >> >>>> Do you agree that it follows from his definition that a constant >>>> is interpreted as an element of the domain, >>> Suppose you have a theory T5 = {Ax[~(x=e)]}, which element of your >>> "domain" U (whatever U might be) would get interpreted as e? >> >> Could be any object in U. >> But whatever it is, the structure is not a model for >> T5, i.e. it will not satisfy the statement Ax[~(x=e)]. >> Just follow Tarski's definition. > > Not a true model of course. But there's a false model for it. "false model" is confusing terminology. If you mean a structure where every predicate has empty extension (is false everywhere), then something like "everywhere-false structure" makes more sense. There is then a separate question as to whether such a structure is a model of a given T or not, in Shoenfield's sense. p 22: "By a *model* of a theory T, we mean a structure for L(T) in which all the non-logical axioms of T are *valid*." > But let's settle the other issue above first and we'll come back > to address the existing of the false model for an inconsistent > theory. > >> >>>> and that therefore >>>> the domain is not empty whenever there is a constant in the >>>> language? >>> In his definition, as I had before, his structure is a non-empty >>> set of ordered pairs, in each of which the 2nd component _is a set_ >>> (un-formalized kind of set that should be taken a priori but which >>> nonetheless could be empty). >> >> That's for predicates, not for constants. >> Look at his treatment of constants (& function symbols). > > _Everything is n-ary_ in his treatment: including 0-ary (constant) > symbol, 0-tuple, 0-ary function value for a constant itself. Fine. > So if an > _n-ary predicate is a set of n-tuples_, then the predicate is always > a set (even if it's empty)!. So the 2nd component _is a set_ in all > cases. I was not asking about predicates, but about constants (0-ary function symbols). From p 18 of my copy: "Let L be a first-order language. A _structure_ *A* for L consists of the following things: (i) A nonempty set |*A*|, called the _universe_ of *A*. The elements of |*A*| are called the _individuals_ of *A*. (ii) For each n-ary function symbol f of L, an n-ary function f_a from |*A*| to |*A*|. (In particular, for each constant e of L, e_a is an individual of *A*.) (iii) For each n-ary predicate symbol p of L ..... " So, the meaning of a constant is an _individual_ of *A*, ie a _member_ of the universe. In particular, you cannot have the meaning of a constant as the empty set (unless the empty set itself is a member of the universe). -- Alan Smaill
From: Marshall on 28 May 2010 10:54 On May 27, 9:49 pm, Nam Nguyen <namducngu...(a)shaw.ca> wrote: > This is Tarski's concept of truth a > la set membership: if all predicates in the degenerated (false) > structure are empty, then non-membership will occur and, by definition, > all formulas will be interpreted as (assigned to) "false". ALL formulas are false if all predicates are empty? What about the formula that tests whether a predicate is empty? Marshall
From: Daryl McCullough on 28 May 2010 12:32 Nam Nguyen says... >Daryl McCullough wrote: >> If S is a structure for a language >> L, then truth in a structure is defined in such a way that >> every closed sentence of L (a sentence without free variables) >> is assigned a value "true" or "false", and the set of true sentences >> is disjoint from the set of false sentences. > >Yes, but you're referring only to the non-degenerated structures! Since most authors are uninterested in empty domains, they don't bother defining truth for them. But there is no difficulty in extending the notion of "truth" to empty domains in such a way that the true sentences are disjoint from the false sentences, and every sentence is true or false. I already told you how: Assign "true" to every closed sentence of the form "Ax Phi(x)" and assign "false" to every closed sentence of the form "Ex Phi(x)". >> In the case of the empty structure (no elements), this assignment >> is pretty simple: >> >> (1) Every sentence of the form "Ax Phi(x)" is assigned "true". >> (2) Every sentence of the form "Ex Phi(x)" is assigned "false". >> (3) There are no quantifier-free closed sentences. > >You're stipulating _one_ mapping between formulas and a set of 2 >binary values. That's what "truth in a structure" does. It maps formulas to "true" or "false". >Is it the only way that make sense? It's the natural way to do it. The nice thing about this approach is that it gives a convenient way to talk about relativized theories and substructures. Suppose I have a language L with no constant symbols and no function symbols (for simplicity), just relation symbols. (You can rewrite any theory with function symbols into an equivalent theory with only relation symbols, by converting an n-ary function into a n+1-ary relation). Suppose I have a unary relation symbol v(x). Suppose I have a structure S for language L. Let V be the interpretation in S for the relation v(x). Then there is a natural way to create a substructure S': (1) The domain of S' is V. (2) The relations of S' are the relations of S, restricted to domain V. There is also a natural way to "relativize" formulas of L to the subdomain V: If Phi is the original formula, then let Phi' be the transformed formula defined recursively as follows: (Ax Phi)' == Ax v(x) -> Phi' (Ex Phi)' == Ex v(x) & Phi' (for propositional operators, the transform just applies to each subformula separately) What would be nice is to have the following: for every formula Phi in L: Phi is true in S -> Phi' is true in S' With the semantics I described, this implication holds, even in the case V is the empty set. >And more to the point, would this way conform with Tarski's concept >of a being true and being false, using set membership? Yes. >> What about sentences that are *not* closed? Well, to interpret >> open sentences (ones with free variables), we also have to have >> an assignment function (one that assigns an element of the domain >> to each variable). In the case of the empty domain, there are >> no assignment functions, so the empty domain cannot be extended >> to give a truth value to open sentences. >> >> There is a subtle distinction between "true" and "valid" for >> a structure. If Phi is an open sentence, then it is considered >> "valid" for a structure if every assignment results in a sentence >> that is true. Under this definition, since there are no assignments >> for the empty structure, it follows vacuously that *every* formula >> (and its negation) is valid for the empty structure. >> >> So, the set of *true* formulas for the empty domain is a consistent >> set. The set of *valid* formulas for the empty domain is inconsistent. > >Except that a) it's supposed to be a set of binary (2) values that all >formulas would get mapped to, not quaternary (4) values; I don't know what you are talking about. Every (closed) formula is either true or false in a model. Open formulas are neither true nor false. For example: "x > 2". That's true for some interpretations for x, and false for other interpretations. A model is not going to assign true or false to such a sentence. However, we can talk about whether an open formula is valid or not. If it is true for all assignments of the variables, then it's valid, otherwise it is invalid. Invalid does *not* mean "false", though. "x > 2" is not false. If you want to collapse "true" and "valid", that's possible, by interpreting a formula with free variables as meaning the same thing as if its free variables are universally quantified over. That's a common approach when dealing with axioms that have free variables---treat Phi(x) as an axiom as meaning the same thing as "Ax Phi(x)". That's really just a convention. >and b) an inconsistent theory would have _all_ the formulas as its >theorems: the purportedly "true" as well as the "false" ones! For any model, the set of truths of that model is *always* a consistent theory (at least with my way of doing it). So there is no model for an inconsistent theory. The completeness theorem says that a theory is consistent if and only if it has a model. >> In any case, the open formula "x=x" is valid in every structure, >> including the empty structure. The open formula "~(x=x)" is only >> valid in the empty structure. > >The key question is how would we go from 4 to 2 and still make sense >in term of set-membership (to satisfy Tarski's)? The answer is we can't. What are you talking about? -- Daryl McCullough Ithaca, NY
From: Nam Nguyen on 29 May 2010 12:24 Alan Smaill wrote: > Nam Nguyen <namducnguyen(a)shaw.ca> writes: > >> Alan Smaill wrote: >>> Nam Nguyen <namducnguyen(a)shaw.ca> writes: >>> >>>> Alan Smaill wrote: >>>>> Fine, take U = {0,1,2}, and take everything else as above. >>>> Well, so far you've only spelled out U (and in effect <'A',U>). >>>> You've not spelled out the mapping (ordered pair) <'blue',p_blue> >>>> where p_blue is an actual _set_. Iow, if R is p_blue, can you >>>> spell out the predicate-set R? >>> The set is the extension of the relation R: >>> >>> { x in U | R(x) } = {1} >> Now then, let's extend the language L(t4) to L(T4b) so it >> has another 1-ary symbol 'non-blue', and extend T4 into >> T4b so it has another axiom: non-blue(c1) <-> ~blue(c1). >> >> Can we keep the model M4 for T4b? If not what can we keep, >> and what should we add? > > You need to say what the meaning of the new predicate is. What would you think "non-blue" usually mean? > This can be done by extending the old structure, > eg by takinh extension of not-blue as { x in U | not R(x) } = {0,2}, > which then provides a different structure which is a model for T4b. Right. But to be precise M4b now would have <'non-blue',C({1})> where C({1}) is the complemantary set of {1} (in U), which is {0,2}. The point is, Alan, the 1-ary predicate {0,2} is a common part of _both_ M4 and M4b, serving the same purpose: to interpret ~blue(c1) - or any equivalent formula - as true. Iow, difference on this between M4 and M4b is just the _name_ of first component of <x,{0,2}>: which name x should have? You could choose a "foreign" name by extending the language, or a "domestic" using FOL symbol redefinition, or in my case a variance of redefinition: an "intrinsic" name such as "the-complementary-set-in-U-of-the-predicate-symbolized- by-'blue'", which in this case I use an short alias '~blue'. And everything would still conform with the definition of structure (model). > >>> Are you claiming that your notion of model is equivalent to >>> Shoenfield's? >> Of course I do. > > It was not clear to me if you thing you are correcting Shoenfield, > or following him. Several of your claims are just not consistent with > what he wrote, as others have pointed out. Who are they, and _exactly_ what did they point out, in relation to my following structure definition as described by Shoenfield? Did they _exactly refute_ what I've said here? Have I countered those refutes? It's hard to know what you're referring to if you're precise. > >> And I'm still in the process of doing the explanation >> so I hope you don't mind answering the new question above. >> >>>>> Do you agree that it follows from his definition that a constant >>>>> is interpreted as an element of the domain, >>>> Suppose you have a theory T5 = {Ax[~(x=e)]}, which element of your >>>> "domain" U (whatever U might be) would get interpreted as e? >>> Could be any object in U. >>> But whatever it is, the structure is not a model for >>> T5, i.e. it will not satisfy the statement Ax[~(x=e)]. >>> Just follow Tarski's definition. >> Not a true model of course. But there's a false model for it. > > "false model" is confusing terminology. Is "a model in which the universe U is empty" very confusing to you? > If you mean a structure where every predicate has empty extension > (is false everywhere), then something like "everywhere-false structure" > makes more sense. I only meant every predicate is an empty set, which is a simple fact, given U = {}. And if a predicate of an empty U is empty, the so is its _complementary predicate_ which means all formulas would be interpreted as false in such (degenerated) structure! > There is then a separate question as to whether > such a structure is a model of a given T or not, in Shoenfield's sense. > > p 22: > > "By a *model* of a theory T, we mean a structure for L(T) in which > all the non-logical axioms of T are *valid*." Sure. that's what he said. But would there be any reasonable cause to believe it's not the case that by "mode" there he only meant T be assumed consistent hence "model" would refer to a non-degenerated structure? >> _Everything is n-ary_ in his treatment: including 0-ary (constant) >> symbol, 0-tuple, 0-ary function value for a constant itself. > > Fine. > >> So if an >> _n-ary predicate is a set of n-tuples_, then the predicate is always >> a set (even if it's empty)!. So the 2nd component _is a set_ in all >> cases. > > I was not asking about predicates, but about constants (0-ary function > symbols). Right. > > From p 18 of my copy: > > "Let L be a first-order language. A _structure_ *A* for L consists of > the following things: > > (i) A nonempty set |*A*|, called the _universe_ of *A*. The > elements of |*A*| are called the _individuals_ of *A*. > > (ii) For each n-ary function symbol f of L, an n-ary function f_a > from |*A*| to |*A*|. (In particular, for each constant e of L, e_a > is an individual of *A*.) > > (iii) For each n-ary predicate symbol p of L ..... " > > So, the meaning of a constant is an _individual_ of *A*, ie a _member_ of > the universe. In particular, you cannot have the meaning of a constant > as the empty set (unless the empty set itself is a member of the universe). If you reflect on pg. 10 where he said about "predicate", "0-tuple", "0-ary function" and the like you'd see that in the degenerated case of U = {}, and _only_ in that case, all predicates and individuals would be defined as the empty set. It'd would also help if you notice that for a non-empty U, an n-ary predicate is always of a different type than that of an (n+1)-ary predicate. In fact, the 2 predicates can't even be equal, given that the individuals in U are treated here as "urelements". But why they, including the 0-ary function value for an individual constant symbol, all in a sudden become equal here? Because that's the nature of the empty set {}, and because that's what we mean in the meta level by the word "degenerated". Hope this has helped you to understand the essence of Shoendfield's wording on the definition of structure, model of a language, which would be used for theories in general, including the degenerated theory, for each language.
From: Nam Nguyen on 29 May 2010 13:32
Daryl McCullough wrote: > Nam Nguyen says... > >> You're stipulating _one_ mapping between formulas and a set of 2 >> binary values. > > That's what "truth in a structure" does. It maps formulas to "true" > or "false". Right. But note in the degenerated structure of a language, it's still true that "It maps formulas to 'true' or 'false'"! > >> Is it the only way that make sense? > > It's the natural way to do it. The nice thing about this approach > is that it gives a convenient way to talk about relativized theories > and substructures. Note my "the only way" in the question. If FOL, by the technicalities vested in all of its layers, doesn't insist that that's the only way, then technically other ways are equally possible, and Marshall's counter stipulation that x=x is true in all contexts of FOL is incorrect in one of those possible ways Whether or not any way is natural or not, is actually debatable and questionable depending on contexts we're talking about: model-theoretically context, or otherwise. > Invalid does *not* mean "false", though. "x > 2" is not false. > > If you want to collapse "true" and "valid", that's possible, by > interpreting a formula with free variables as meaning the same > thing as if its free variables are universally quantified over. > That's a common approach when dealing with axioms that have free > variables---treat Phi(x) as an axiom as meaning the same thing > as "Ax Phi(x)". That's really just a convention. But are meaning and truth (interpretation) are identical, in general? "There's a unicorn eating hay in the zoo" is quite meaningful, but is there anything being true in that statement when the zoo is _factually_ empty? >> The key question is how would we go from 4 to 2 and still make sense >> in term of set-membership (to satisfy Tarski's)? The answer is we can't. > > What are you talking about? Let me make a little detour but hopefully by doing that my explanation would be more "crisp". We know if A df= (B and C) then whether or not A is true would depend on _both_ B and C right? Suppose the following 3 statements are _not_ FOL formulas but meta statements and as stipulated as: "F is model-theoretically true" df= "T is true" and "F is interpreted as true" where F is _any_ FOL formula and T is a meta assertion that the universe U of a structure is non-empty (per a language L of course). Do you see the pattern now? Indeed, let's let: A = "F is model-theoretically true" B = "T is true" C = "F is interpreted as true" Note in FOL the individuals of an U and U itself are off-limit to FOL expressibility: in the sense that they're of the kind of unformalized entities that we can only have a priori and that if we try to formalize them what we've formalized just aren't they. Iow, B is _not_ FOL expression. Would you see in now? It doesn't matter whether or not F is _syntactically_ tautologous or contradictory, the meta statement A, by definition of structure, will also depend on B. And if B is false by virtual of the factual U's being empty then A is false. |