From: lemma_one@my-deja.com Subject: Re: Definability with the empty language. Date: Sat, 07 Oct 2000 01:55:00 GMT Newsgroups: sci.math Summary: [missing] In article <39de57a3.37304276@nntp.sprynet.com>, ullrich@math.okstate.edu wrote: > On Fri, 06 Oct 2000 15:11:53 GMT, lemma_one@my-deja.com wrote: > > >In article <39ddd5f0.4095903@nntp.sprynet.com>, > > ullrich@math.okstate.edu wrote: > >> On Fri, 06 Oct 2000 08:28:39 GMT, lemma_one@my-deja.com wrote: > >> > >> >Okay, suppose we are using a language with no constants, functions, > >or > >> >predicates. Suppose that |M| is the universe of a structure M, and A > >is > >> >a subset of |M|. Then prove: A is definable in M iff A is finite or > >> >|M|-A is finite. > >> > >> I'm missing something here. Or maybe I'm not missing anything, > >> not sure. But if there are no constants, functions or predicates then > >> I don't see how _any_ set can be definable (for that matter I don't > >> see how there can be any formulas in the language. Oh - it's > >> first-order logic _with equality_???) > >> > >> For example, say |M| = the integers and A = {0}. How do > >> you define A? (Saying it's defined by the formula "x = 0" doesn't > >> work because there's no "0" in the language.) > > > >Instead of saying, "empty", I should have said "trivial". It was very > >late, and I got mixed up. There is equality, and it is said that the > >universe of the structure is nonempty, but there are no constants, > >functions, or predicates. > > > >For example, given all these conditions, A is definable in M without > >parameters iff A is the emptyset or A=M. For suppose that phi is a > >formula and x is the only free variable in phi. If there is no m in M > >such that M satisfies phi[m], then phi defines the emptyset in M. > >Otherwise, suppose that m is in |M| and M satisfies phi[m]. If n is > >another element of |M|, then the function e:|M| --> |M| obtained by > >transposing m and n is a bijection from |M| to |M|, and an isomorphism > >from M to M. By a familiar theorem (that if e is an isomorphism from M > >to N and v is an assignment then M satisfies some phi with v iff N > >satisfies phi with e*v (e composed with v)), since M satisfies phi[m] we > >also have M satisfies phi[e(m)], that is M satisfies phi[n]. > >Consequently, if phi defines a nonempty set, then that set is all of > >|M|. > > > >I hope that example clarifies things. Sorry to have been so confusing. > > Why not simply answer the question I asked? Say M is > the set of integers, and A = {0}. What formula defines A? That > would clarify the bits I'm confused about - that's why I asked. > Three times so far... Argh. I must be worse than I thought (because I thought I was addressing your question). As far as I can tell, given all the constraints my problem imposes, you could not define the set {0} if M is the integers. You could only define {0} if M={0}, as far as I can see. When you said, For example, say |M| = the integers and A = {0}. How do you define A? (Saying it's defined by the formula "x = 0" doesn't work because there's no "0" in the language.) I think I wanted my answer to be "you can't." That might not be the right answer though. I've already handed in a (most likely incorrect) "solution" for this problem, but I would really like to get down to the bottom of it anyways. I don't think I can answer your question, but I think I can supply you with the definitions I am working with enough precision so that you can answer your question. I'll reproduce all the relevant definitions right here (with the definition names in BOLD): Let L be a first-order language, M be a structure, |M| be its universe, X a subset of |M|. Then we say that the subset Y of |M|^n is DEFINABLE IN M WITH PARAMETERS FROM X iff there exists elements b_1,...,b_m of X and a L-formula phi(x_1,...,x_k) such that all of the following hold: (a) phi has n+m free variables: x_1,...,x_n and y_1,...,y_m. (b) for each in |M|^n, in Y iff there is an assignment v such that (i) For each i<=n, v(x_i)=a_i. (ii) For each i<=m v(y_i)=b_i. (iii) The structure M satisfies phi with v. A subset Y of |M|^n is DEFINABLE IN M WITHOUT PARAMETERS iff it is definable with parameters from the emptyset. When n=1, we identify |M|^1 with |M| and speak of definable subsets of |M|. > > >> The sentence above that ends in "?" is an actual question, > >> btw - I'm not sure whether I have some of the definitions wrong or > >> what. How _do_ you define {0} in Z with no constants, functions > >> or predicates? (Is the above _exactly_ what the problem asks?) > >> > >> >Okay, I probably want to use an isomorphism, right? I can see that > >any > >> >permutation of |M| is an isomorphism e:|M| --> |M|. I just don't know > >> >where to go from here, (if here is relevent.) > >> > > >> > > >> >Sent via Deja.com http://www.deja.com/ > >> >Before you buy. > >> > >> > > > > > >Sent via Deja.com http://www.deja.com/ > >Before you buy. > > Sent via Deja.com http://www.deja.com/ Before you buy. ============================================================================== From: ullrich@math.okstate.edu (David C. Ullrich) Subject: Re: Definability with the empty language. Date: Sat, 07 Oct 2000 13:41:28 GMT Newsgroups: sci.math On Sat, 07 Oct 2000 01:55:00 GMT, lemma_one@my-deja.com wrote: >In article <39de57a3.37304276@nntp.sprynet.com>, > ullrich@math.okstate.edu wrote: >> On Fri, 06 Oct 2000 15:11:53 GMT, lemma_one@my-deja.com wrote: >> >> >In article <39ddd5f0.4095903@nntp.sprynet.com>, >> > ullrich@math.okstate.edu wrote: >> >> On Fri, 06 Oct 2000 08:28:39 GMT, lemma_one@my-deja.com wrote: >> >> >> >> >Okay, suppose we are using a language with no constants, functions, >> >or >> >> >predicates. Suppose that |M| is the universe of a structure M, and A >> >is >> >> >a subset of |M|. Then prove: A is definable in M iff A is finite or >> >> >|M|-A is finite. >> >> >> >> I'm missing something here. Or maybe I'm not missing anything, >> >> not sure. But if there are no constants, functions or predicates then >> >> I don't see how _any_ set can be definable (for that matter I don't >> >> see how there can be any formulas in the language. Oh - it's >> >> first-order logic _with equality_???) >> >> >> >> For example, say |M| = the integers and A = {0}. How do >> >> you define A? (Saying it's defined by the formula "x = 0" doesn't >> >> work because there's no "0" in the language.) >> > >> >Instead of saying, "empty", I should have said "trivial". It was very >> >late, and I got mixed up. There is equality, and it is said that the >> >universe of the structure is nonempty, but there are no constants, >> >functions, or predicates. >> > >> >For example, given all these conditions, A is definable in M without >> >parameters iff A is the emptyset or A=M. For suppose that phi is a >> >formula and x is the only free variable in phi. If there is no m in M >> >such that M satisfies phi[m], then phi defines the emptyset in M. >> >Otherwise, suppose that m is in |M| and M satisfies phi[m]. If n is >> >another element of |M|, then the function e:|M| --> |M| obtained by >> >transposing m and n is a bijection from |M| to |M|, and an isomorphism >> >from M to M. By a familiar theorem (that if e is an isomorphism from M >> >to N and v is an assignment then M satisfies some phi with v iff N >> >satisfies phi with e*v (e composed with v)), since M satisfies phi[m] we >> >also have M satisfies phi[e(m)], that is M satisfies phi[n]. >> >Consequently, if phi defines a nonempty set, then that set is all of >> >|M|. >> > >> >I hope that example clarifies things. Sorry to have been so confusing. >> >> Why not simply answer the question I asked? Say M is >> the set of integers, and A = {0}. What formula defines A? That >> would clarify the bits I'm confused about - that's why I asked. >> Three times so far... > >Argh. I must be worse than I thought (because I thought I was addressing >your question). As far as I can tell, given all the constraints my >problem imposes, you could not define the set {0} if M is the integers. >You could only define {0} if M={0}, as far as I can see. That's the impression I got from your last post, yes. That's precisely why I found it only increased my confusion. At the beginning of all this you said that the problem was "Then prove: A is definable in M iff A is finite or |M|-A is finite." I suspected that I must be misunderstanding one of the definitions because I didn't see how {0} was a definable subset of Z under the given constraints. So I asked how you would define {0}, the point being to try to understand what I was missing regarding the definition of "definable". Now you say that {0} is _not_ a definable subset of Z as far as you can see? Are you suspecting that maybe {0} is infinite, or that the problem is wrong or what? In the meantime someone lurking has clarified the definition of "definable in M" in an email message. But in the present context I'm _really_ not supposed to say anything to you about the definitions of terms in your post - it was your question, so you're supposed to explain to me what the terms mean, because only you know exactly what you _did_ mean. You understand my confusion, when you say "Then prove: A is definable in M iff A is finite or |M|-A is finite", then say things that _sound_ as though you're saying that {0} is not a definable subset of Z (and then you confirm that as far as you can see {0} is not a definable subset of Z), right? We need to get the definitions straight first... >When you said, > > For example, say |M| = the integers and A = {0}. How do you define >A? (Saying it's defined by the formula "x = 0" doesn't work >because there's no "0" in the language.) > >I think I wanted my answer to be "you can't." That might not be the >right answer though. I've already handed in a (most likely incorrect) >"solution" for this problem, but I would really like to get down to the >bottom of it anyways. I don't think I can answer your question, but I >think I can supply you with the definitions I am working with enough >precision so that you can answer your question. I'll reproduce all the >relevant definitions right here (with the definition names in BOLD): Great. >Let L be a first-order language, > M be a structure, > |M| be its universe, > X a subset of |M|. > >Then we say that the subset Y of |M|^n is DEFINABLE IN M WITH PARAMETERS >FROM X iff there exists elements b_1,...,b_m of X and a L-formula >phi(x_1,...,x_k) such that all of the following hold: > > (a) phi has n+m free variables: x_1,...,x_n and y_1,...,y_m. > (b) for each in |M|^n, in Y iff there >is an assignment v such that > (i) For each i<=n, v(x_i)=a_i. > (ii) For each i<=m v(y_i)=b_i. > (iii) The structure M satisfies phi with v. Aha. So it's not just a formula that defines the set, it's a formula _together_ with a choice of elements b_1,...b_m. So then Y = {0} _is_ "definable in Z with parameters from Z": Let m = n = 1, b_1 = 0 and let phi be the formula "x_1=y_1". Then it's true that a_1 is in Y if and only if there exists a v satisfying (i), (ii), and (iii): Suppose that a_1 is in Y. Then a_1 = 0. Choose any v such that v(x_1) = a_1 ( = 0) and also v(y_1) = b_1 ( = 0). Then Z satisfies phi with v (because v(x_1) = v(y_1).) Suppose on the other hand that a_1 is in Z and v is an assignment such that v(x_1) = a_1, v(y_1) = b_1, and Z satisfies phi with v. Then we must have v(x_1) = v(y_1), hence a_1 = b_1, hence a_1 = 0 and so a_1 is in Y. The lurker in question said something to the effect that the usual definition of a definable subset of a structure allows the elements of the structure as formal constants. In the definition above we restrict to assignments v with v(y_i) = b_i; this is just a precise way of saying that we allow b_i as a formal constant (which is not allowed to be interpreted as anything exceot the real b_i.) >A subset Y of |M|^n is DEFINABLE IN M WITHOUT PARAMETERS iff it is >definable with parameters from the emptyset. So then presumably {0} is not definable in Z without parameters. >When n=1, we identify |M|^1 with |M| and speak of definable subsets of >|M|.