• alcontali
    1.3k
    Consider any non-standard model of PA. How can we capture this non-standard model in a set of sentences?Nagase

    It implies that if a countable first-order theory has an infinite model, then for every infinite cardinal number κ it has a model of size κ, and that no first-order theory with an infinite model can have a unique model up to isomorphism.Wikipedia on Löwenheim–Skolem theorem

    A nonstandard model is created by throwing a symbol κ into the fray; the result of which is the creation of lots of new sentences in such extended grammar.
  • Nagase
    197


    Well, it is true that if a first-order theory has a model of a given infinite cardinality, then it has models of every infinite cardinality. But a theory may have only one finite model, say of cardinality n for some natural number n. In that case, it may have no infinite models at all.
  • GrandMinnow
    169
    "The set theory" in my post is indeed "the theory of hereditarily finite sets".alcontali

    Then you're much better saying it rather than depending a very confused "context".

    I was not aware of the fact that the meaning of the terms "language" and "sentence" in computer science would be so out of place in mathematical logic.alcontali

    If your usage is is indeed standard computer science, then, yes, the terminology of computer science is radically different from basic mathematical logic. If you insist on using the terminology differently from the way it is used in ordinary discussions about hereditarily finite sets and PA, then you need to clearly state your system of terminology from your own basics rather than, without due specification, mixing it up with ordinary usage.
  • Nagase
    197


    This is to miss the point. You can pick two non-standard models of the same cardinality and which satisfy the same sentences, but which are nevertheless distinct. So no first-order sentence, indeed not even a set of such sentences, will distinguish them.

    Incidentally, note that the procedure you quoted for creating non-standard models is not achieved by introducing just one symbol, k, but by introducing k many symbols; this k can be any infinite cardinal.
  • GrandMinnow
    169
    In terms of computability, it is not incorrect.alcontali

    The headline reads onto itself and is incorrect. You do somewhat correct it in your post (though, even there, you mistate by saying "ZF minus infinity" rather than "ZF with infinity replaced by the axiom of infinity").
  • GrandMinnow
    169
    if a first-order theory has a model of a given infinite cardinality, then it has models of every infinite cardinality.Nagase

    I'm not referring to the cardinality of the universe. I'm referring to the cardinality of each member of the universe.
  • Nagase
    197


    Well, if a given model has cardinality n, then it has no members of cardinality n+1... unless you're just saying that we can always replace one of the elements of model by a set of any cardinality, treated as a black box. Is this what you have in mind?
  • GrandMinnow
    169
    A nonstandard model is created by throwing a symbol κ into the frayalcontali

    This is a notion of non-standard model not in model theory (in mathematical logic) but in computer science?

    It is clearly not the notion in model theory.
  • alcontali
    1.3k
    If your usage is is indeed standard computer science, then, yes, the terminology is radically different from basic mathematical logic. If you insist on using the terminology differently from the way it is used in ordinary discussions about hereditarily finite sets and PA, then you need to clearly state your system of terminology from your own basics rather than, without due specification, mixing it up with ordinary usage.GrandMinnow

    I only get to figure that out by actually doing it. If I don't do it, then I will never figure out what the problems are, not even the problems with the terminology.

    Furthermore, I do not investigate all topics in computer science, many of which are not necessarily interesting to me. An example of how the term "formal language" may appear in this realm:

    Automata theory is closely related to formal language theory. An automaton is a finite representation of a formal language that may be an infinite set. Automata are often classified by the class of formal languages they can recognize, typically illustrated by the Chomsky hierarchy, which describes the relations between various languages and kinds of formalized logics.

    Automata play a major role in theory of computation, compiler construction, artificial intelligence, parsing and formal verification.
    Wikipedia on automata theory

    The meaning of "formal language" in automata theory is not necessarily the same as in mathematical logic:

    For instance, a language can be given as:
    those strings generated by some formal grammar;
    those strings described or matched by a particular regular expression;
    those strings accepted by some automaton, such as a Turing machine or finite-state automaton;
    those strings for which some decision procedure (an algorithm that asks a sequence of related YES/NO questions) produces the answer YES.
    Wikipedia on formal languages

    In fact, now I see that I should probably use the term "word" instead of "sentence" for natural numbers, but also not necessarily, because in terminology compiler construction they would still be sentences ("The automaton accepts a sentence"). The term sentence in mathematical logic is probably the most closely related to "those strings for which some decision procedure produces the answer YES".
  • GrandMinnow
    169
    I only get to figure that out by actually doing it. If I don't do it, then I will never figure out where the problems are, not even the problems with the terminology.alcontali

    Your improvised public "figuring out", with confusions conflating terminology from two different areas of stusy, results in posts that are misinformation.

    The term sentence in mathematical logic is probably the most closely related to "those strings for which some decision procedure produces the answer YES".alcontali

    That is very incorrect as far as mathematical logic is concerned.
  • alcontali
    1.3k
    This is a notion of non-standard model not in model theory (in mathematical logic) but in computer science?GrandMinnow

    That would be impossible in computer science.

    Computer science can fundamentally not handle infinite cardinalities, because they are generally not computable. They are sometimes handled symbolically, though.

    In computing, NaN, standing for not a number, is a member of a numeric data type that can be interpreted as a value that is undefined or unrepresentable, especially in floating-point arithmetic. Systematic use of NaNs was introduced by the IEEE 754 floating-point standard in 1985, along with the representation of other non-finite quantities such as infinities.Wikipedia on NaN

    I do not believe that there is any guarantee that this NaN symbol makes sense in a model-theoretical sense. These symbols may show up, but it really depends on the implementation standard what exactly they mean. Furthermore, that symbol is mostly considered to be the result of a bug, which should not even show up ...
  • GrandMinnow
    169
    impossible in computer science.alcontali

    Then it's model theory. And your statement about it is plainly incorrect.
  • alcontali
    1.3k
    Much better to figure it out by reading a textbook that develops the concepts and terminology systematically, rather than posting misleading confusions for other people to read.GrandMinnow

    The confusion is merely in the lack of formality; but that was actually expected by the reader. Furthermore, what you write, does not necessarily help anybody to understand the subject either.
  • alcontali
    1.3k
    Then it's model theory. And your statement about it is plainly incorrect.GrandMinnow

    Many infinite-size models cannot be handled by any grammar, because their sentences are necessarily countable, while these models may not have a countable cardinality. It can only work for something like ZF-inf, of countable cardinality.

    So, no, I actually agree, throwing that symbol into the fray, won't make it work.
  • GrandMinnow
    169
    The confusion is merely in the lack of formalityalcontali

    Very much not merely a lack of formality. It is dreadful confusion and misinformation.

    what you write, does not necessarily help anybody to understand the subject either.alcontali

    I try to write correct statements, as best I can within the limits of posts. Much of that is merely point blank stating what is correct without necessarily giving an explanation, let alone an entire explanation. I cannot, in the space of posts, wind backwards through the trail of concepts to primitives for every concept. But at least, most importantly, I try not to write misinformation.

    For actual understanding, one needs to read the basic textbooks in the subject, not just posts in a forum.
  • GrandMinnow
    169
    throwing that symbol into the fray, won't make it workalcontali

    Adding a symbol is not relevant, not due to whatever you said about sizes of models, but rather more simply that it is not even involved in the notion of a non-standard model.
  • GrandMinnow
    169
    Infinite-size models cannot be handled by any grammar, because their sentences are necessarily countable, while these models may not have a countable cardinality. It can only work for something like ZF-inf, of countable cardinality.alcontali

    That's computer science, or a special bland of computer science and model theory that you are working out live?
  • Qwex
    366
    Why can't 1, 2, 3, 4 be spelt, 4, 2, 3, 1 and be a natural number sequence? Where does positivity come from?

    I predict all formats of 1-9 creates a number more like 8 on averages.

    If I used the universe as a computer and list all categories a pattern would emerge of a pyramid common and uncommon shape, creating links with numbers. There would be the times that it's normative and times that it isn't.

    It's a pattern we can notice about even more oddly defined natural number 1-9.

    In not using the universe as a judge you would lose track of symmetrical nature of physical, written list. Writing randomly about a page would create too much harmony.

    I can imagine numbers swirling in, they happen to have this special relationship.

    True positivity.

    8 when defined, but thought of in pespective with base 8 planting 8 in base 4, because base 8 is possible ( A good view of all sectors of number if positivity not implied).

    A view inside the square as a symbol or math.

    Base 8 is just that number out qualifies base 4, and it's written sequence can be created with an answer, and in base 8 this answer has a locale.

    Control over energy, knowledge is significance.

    The method of equalization.

    Did you know? Game producers have been making critical engine mistakes. 3D is not done like it's thought.

    Experienced 3D has negative and postive depth, we understand it wrong. There is no perfectly centred cube. When you make game engines you focus more on an upgradable net.
  • alcontali
    1.3k
    Adding a symbol is not relevant, not due to whatever you said about sizes of models, but rather more simply that it is not even involved in the notion of a non-standard model.GrandMinnow

    A non-standard model is one that has additional elements outside this initial segment. The construction of such models is due to Thoralf Skolem (1934).Wikipedia on construction of nonstandard models

    This is typically represented by adding a symbol ω. If such model were of countable size then adding that symbol would be enough to represent these additional elements as: ... ω-2, ω-1, ω, ω+1, ω+2, ...

    In her slides, Victoria Gitman explains this literally as:

    slide 10: "Expand LA by adding a constant c to obtain the language LA∗ = (+,·,<,0,1,c)."
    slide 11: "M has c+ 1,c+ 2,c+ 3 ,... as well as c−1,c−2,c−3,...."

    So, what is wrong with her slides?

    Again, as I have said already, it would be enough to expand the grammar of the model with a constant, if the size of the model remained countable. It does not work for larger models because grammar cannot represent uncountable models.

    That's computer science, or a special bland of computer science and model theory that you are working out live?GrandMinnow

    Look, if you do not want to make constructive remarks, then why do you make any remarks at all?
  • GrandMinnow
    169
    This is typically represented by adding a symbol walcontali

    No, you have it very wrong.

    The universe has additional members. We don't add symbols that engender sentences not already in the theory.

    You are completely confused about this and other topics in mathematical logic. Please stop and instead first read an introductory textbook in the subject.

    if you do not want to make constructive remarksalcontali

    My remarks have corrected your misinformation. That is constructive. And a further constructive remark is that you need to read a basic textbook in the subject instead of spreading wanton misinformation about it.

    Anyway my question stands: In the earlier passage, what are you talking about? Model theory, computer science or your own blend of them?

    And I have no idea what you mean by w-1 and w-2 in the context of saying w-1, w-2, w, w+1, w+2. Do you have a definition of some kind of operation of ordinal subtraction that allows subtracting 1 or 2 from a limit ordinal? What exact set or ordinal type do you mean by w-1 and w-2? Actually, nevermind, better you should instead get a book on working in the first order precicate calculus, then an intro book on set theory and then an intro book on mathematical logic.
  • GrandMinnow
    169
    A non-standard model of PA I guess can be visualized through the method Gitman mentions, but literally a model of PA is itself a model for the language of PA, not for a language with an added symbol. The elements with 'c' in her slides are just elements of the universe. Again: A non-standard model of a theory is a model for the language of the theory (not with added symbols or sentences) such that the model differs from (or is at least not isomorphic with) some agreed upon standard model.

    That you reference those slides to misunderstand them, is a function of relying on various Wikipedia articles and Google searches for various presentation, out of context of a systematic treatment such as in a good textbook.
  • alcontali
    1.3k
    No, you have it very wrong. The universe has additional members. We don't add symbols that engender sentences not already in the theory.GrandMinnow

    I asked you what is wrong with Victoria Gitman's slides.

    And I have no idea what you mean by w-1 and w-2 in the context of saying w-1, w-2, w, w+1, w+2.GrandMinnow

    You can find that literally in her slides. Did you even look at them?

    A non-standard model of PA I guess can be visualized through the method Gitman mentions, but literally a model of PA is itself a model for the language of PA, not for a language with an added symbol. The elements with 'c' in her slides are just elements of the universe.GrandMinnow

    I like her slides.

    Unlike your vitriolic remarks, they add to the understanding of the topic. In fact, I do not care about what you may think about her slides, because she turns out to be useful while you are not. Her representation of ... ω-2, ω-1, ω, ω+1, ω+2, ... is also quite clarifying, unlike what you are doing.

    You are completely confused about this and other topics in mathematical logic. Please stop and instead first read an introductory textbook in the subject.GrandMinnow

    It is my OP. I posted the topic. If you do not like it, feel free to unceremoniously fuck off, will you?
  • GrandMinnow
    169
    I should add that study of non-standard models of PA usually considers not merely that the models are not isomorphic to the standard model but also the “blocks” of linear orderings. And, yes, these do resemble the standard ordering of the integers (negative and non-negative). But I took your w-1 to mean omega minus one - maybe yoh didt mean that?

    And I looked at the Wikipedia page you referenced. The method of adding a constant is a step in proving the existence of non-standard models of PA. But the actual non-standard model is on a language that does not include the constant.
  • GrandMinnow
    169
    I didn’t say there is anything wrong with Gitman. You seemed to have skipped what I said about it. Actually, I should be sharper by saying that it appears to be a step in proving existence - and, again, an actual non-standard model of PA is a model for the language of PA, not a model for a different language with an additional symbol.

    And what you wrote is not, as you are claiming, literally what she wrote. She mentions an arbitrary constant ‘c’. But you introduced in particular ‘w’ (omega), so I would think you have in mind omega (the set of natural numbers).

    So, by w-1, do you mean some kind of ordinal subtraction, or something else?

    It’s not vitriolic to point out that you are posting misinformation and that you would do better to read a textbook.

    That you posted a topic doesn’t provide that people should not correct your misinformation nor advise that you wouldn’t be so prone to confusions if you read a textbook.
  • alcontali
    1.3k
    I didn’t say there is anything wrong with Gitman. You seemed to have skipped what I said about it. Actually, I should be sharper by saying that it appears to be a step in proving existence - and, again, an actual non-standard model of PA is a model for the language of PA, not a model for a different language with an additional symbol.GrandMinnow

    She extends the language of the model in slide 10: "Expand LA by adding a constant c to obtain the language LA∗ = (+,·,<,0,1,c)."

    The term "language" in her slides is something that can have an uncountable number of sentences. Her model cannot have a CS grammar, unlike the standard model, because CS grammars can only represent a countable number of sentences.

    And by w-1, do you mean some kind of ordinal subtraction, or something else?GrandMinnow

    Ask Victoria Gitman about what she means with that term in her slide. I think that I understand it, but better ask her instead.

    It’s not vitriolic to point out that you are posting misinformation ...GrandMinnow

    Since you are not much useful in correcting errors, besides merely criticizing other people, your contribution is simply worthless and just annoying. I am not an expert on model theory. I just gave my understanding on something it investigates. What you are doing, however, is completely worthless. In what sense do you believe that your vitriolic remarks would be helpful in any way? If they successfully prevent people from discussing the topic, will you have achieved your nefarious goals? You are not here to discuss anything. You are here to point out that you believe that you know the subject better than anybody else here, mostly by putting them down. Don't you see that nobody needs or even appreciates your presence? Your obnoxious attitude turns you into a worthless individual whom nobody likes to be around.
  • GrandMinnow
    169
    Moreover, indeed Gitman, just as the Wikipedia article, uses the method of adding a constant as a step in the proof of existence, but then she says explicitly that a non-standard model of PA is a model of the axioms of PA.

    The axioms of PA do not have the added constant. There is a difference between (1) a proof of existence through a detour via another language and (2) an actual model of PA.
  • GrandMinnow
    169
    an actual non-standard model of PA is a model for the language of PA, not a model for a different language with an additional symbol.GrandMinnow

    What I wrote there (and with similar remarks on this particular point) may be too strict. It belies that there may be a less narrow notion of 'model of'.

    Narrow:

    A model M of a theory T is model for the language of T, such that every sentence in T is true in M (a theory being a set of sentences closed under deduction). So a model of PA is model for the language of PA (which does not include an added constant 'c'). So a model M that, for example, Gitman proves to exist is not itself for the language of PA and therefore not a model of PA, but then we restrict such a model to the language of PA and that restriction is a model of PA.

    Less Narrow:

    We could allow that a model M of a theory T is model for a language that includes the language of T, such that every sentence in T is true in M. So a model M that, for example, Gitman first proves to exist is itself a model of PA, and we don't need to then restrict the the model.

    The term "language" in her slides is something that can have an uncountable number of sentences.alcontali

    She doesn't preclude uncountable languages in general. But where she proves the existence of non-standard models of PA, the languages mentioned are countable languages. Uncountability does not have a role in it.
  • alcontali
    1.3k
    She doesn't preclude uncountable languages in general. But where she proves the existence of non-standard models of PA, the languages mentioned are countable languages. Uncountability does not play a role in it.GrandMinnow

    This is the point where I somehow backtracked on what Gitman wrote, while I initially thought it was actually really good. I really ran off with the idea that a model is a language. It clarified the difference between a theory, i.e. a set of axioms, and a model, i.e. a CS-like grammar describing sentences. I still think of things like that for countable models, but I have to leave it open if the concept properly applies to models that are larger than that, such the nonstandard models of PA.

    Countability is often assumed to be an inherent property of any language in other arguments such as in Richard's paradox:

    Thus there is an infinite list of English phrases (such that each phrase is of finite length, but the list itself is of infinite length) that define real numbers unambiguously. We first arrange this list of phrases by increasing length, then order all phrases of equal length lexicographically (in dictionary order, e.g. we can use the ASCII code, the phrases can only contain codes 32 to 126), so that the ordering is canonical. This yields an infinite list of the corresponding real numbers: r1, r2, ... . Now define a new real number r as follows. The integer part of r is 0, the nth decimal place of r is 1 if the nth decimal place of rn is not 1, and the nth decimal place of r is 2 if the nth decimal place of rn is 1.Wikipedia on Richard's paradox

    The argument is clearly very similar to Cantor's diagonal argument. In the explanation above, language itself is clearly considered countable.

    I think that it would be useful for Gitman to explain why such uncountable nonstandard model would still be a legitimate language.

    I currently see it more as some kind of dense cloud, centred around a choice for ω, of number symbols/strings, that cannot be adequately captured by the concept of language.
  • GrandMinnow
    169
    a theory, i.e. a set of axiomsalcontali

    Writers might differ on the definition of 'theory', but it turns roughly the same with whatever adjustments we need:.

    (1) A theory is a set of sentences closed under deduction. The theorems of the theory are the members of the theory.

    That definition has the advantage that we can consider theories without having a particular set of axioms in mind. For example, given a model M, we have Th(M), which is the set of sentences true in M. So an axiomatization doesn't have to be specified.

    (2) A theory is the set of theorems derivable from a particular set of axioms.

    With that definition, given a set of axioms S, the theory axiomatized by S is the set of sentences derivable from S.

    a model, i.e. a CS-like grammar describing sentencesalcontali

    I don't claim that is not a notion in computer science, but in context such as Gitman, which is set_theoretic/mathematical_logic/model_theory, that is not how the concept of a model is formulated.

    countable models, but I have to leave it open if the concept properly applies to models that are larger than that, such the nonstandard models of PA.alcontali

    The particular nonstandard models of PA that Gitman is discussing are countable models. There are countable nonstandard models of PA and uncountable nonstandard models of PA. And, in the first definition of 'model of' I mentioned in the earlier post, the language is countable, and with the second definition, an uncountable language for a model of PA can be restricted to a countable language.

    it would be useful for Gitman to explain why such uncountable nonstandard model would still be a legitimate language.alcontali

    A model is not a language.

    An uncountable model is one in which the universe for the model is an uncountable set. Every theory that has an infinite model has both countable and uncountable models, even as the language for the theory is countable.
  • alcontali
    1.3k
    A model is not a language.GrandMinnow

    Well, Gitman clearly mentions that she considers a model to be (some kind of) language:

    slide 10: "Expand LA by adding a constant c to obtain the language LA∗ = (+,·,<,0,1,c)."

    So, that is why I first said something similar: "Just add a Löwenheim-Skolem ω symbol to the model's language."

    It implies that if a countable first-order theory has an infinite model, then for every infinite cardinal number κ it has a model of size κ, and that no first-order theory with an infinite model can have a unique model up to isomorphism.Wikipedia on Löwenheim-Skolem

    These infinite cardinals are clearly an element in Cantor's (or ) sequence.

    Therefore, Gitman's "language" does not always have a countable number of sentences. So, what kind of "language" is it supposed to be?
bold
italic
underline
strike
code
quote
ulist
image
url
mention
reveal
youtube
tweet
Add a Comment