First order logic: definability

[ky2345]

Homework Statement

What subsets of the real line R are definable in (R,<)? What subsets of the plane RxR are definable in (R,<)?

Homework Equations

A subset is definable if there is a formula in first order logic that is true only of the elements of that subset. For example, in the Natural numbers N, {0} is definable in (N,<), because the formula \forall n(v_{1}<n) is true only if v_{1}=0.

If a subset is definable, then it is preserved under automorphisms.

The Attempt at a Solution

The only two subsets of R which are definable are R itself and the empty set. For R, the formula v_{1}=v_{1} is true no matter what v_{1} is. For the empty set, the formula \lnot(v_{1}=v_{1}) is true of no number in R. For any subset S of R which is not R or the empty set, there is an automorphism which takes elements of S to elements not in S. Indeed, there is an p in S and a q not in S, since S is neither R nor the empty set. Let f(x)=x+(q-p). f is an automorphism, it is easy to check. Then, f(p)=q, so that f takes an element of S to an element not in S. Thus, S is not a definable set.

Now, for RxR, I'm confused about what it means for a subset of RxR to be definable in (R,<).

 

[Hurkyl]

Just to be clear -- you are considering the language with '<' as the only nonlogical symbol? (as opposed to the language with '<' and all elements of R as nonlogical symbols)

 

[ky2345]

the variables can vary over all of R, and < is the only relation. So, automorphisms need to preserve <. I am viewing R as an ordered set. I'm not sure what you mean by "nonlogical symbols"

 

[bcrowell]

I think what Hurkyl was asking was the same thing that I wondered when I read your OP. If < is the only relation allowed, then isn't your example "the formula v_{1}=v_{1} is true no matter what v_{1} is" a formula that isn't a sentence in the formal language, since you use the symbol =? Does your language include "and" and "or?"

 

[Hurkyl]

I'm not sure what you mean by "nonlogical symbols"

The symbols of your language that aren't specified by first-order logic itself. e.g. any constant, function, or relation symbols you want to add to to the language of first-order logic.

The reason I ask is that if you can't use the elements of R as constant symbols, then it is a little superfluous to even mention it at all, so I wanted to be sure you were sure what your homework problem meant.

Now, for RxR, I'm confused about what it means for a subset of RxR to be definable in (R,<).

What do you mean?

Does this mean you know a suitable definition of "definable" and are unsure how to apply the definition to the situation?

Does this mean you have never seen a definition of "definable" stated for anything other than unary predicates, and

have made an (unstated) educated guess, and would like to have it confirmed?

been having difficulty coming up with an educated guess?

think that speculating as to what the definition might be wouldn't be useful and are just asking for a definition?​

Something else entirely?

 

[ky2345]

My language includes all five formula building operations, so or, and, implies, iff, and not. There are no constants. The two place predicate symbol < is the only predicate symbol I have.

I have a definition of definable, and am having difficultly applying what it means for a subset of RxR to be definable in (R,<).

 

[ky2345]

Oh, and also I have equality, =

 

[Hurkyl]

My language includes all five formula building operations, so or, and, implies, iff, and not. There are no constants. The two place predicate symbol < is the only predicate symbol I have.

I have a definition of definable, and am having difficultly applying what it means for a subset of RxR to be definable in (R,<).

Well, what is the definition of definable you are using?

 

[ky2345]

I am using the definition of definable that I mentioned in my first post. Then, a formula with n free variables defines the set of n-tuples that make the formula true in the given structure. So, in RxR for example, we are looking at ordered pairs. An example of a set being definable can be seen by looking at the formula v_{1}<v_{2}. This the set of all ordered pairs (x,y) where x<y.

To show that a subset S is not definable, we need to show that there is an automorphism that takes elements from S to elements not in S.

I'm having trouble figuring out which sets of RxR are decidable and which aren't, because I am having difficulty understanding what an automorphism is on RxR where < is preserved on R. For example, let's say that a function f takes (x,y) to (a,b) and (w,z) to (c,d). If x<y, must it be so that a<b for f to be an automorphism? If x<w and y<z, must it be so that a<c and b<d for f to be an automorphism?

 

[eabod]

I think what Hurkyl was asking was the same thing that I wondered when I read your OP. If < is the only relation allowed, then isn't your example "the formula v_{1}=v_{1} is true no matter what v_{1} is" a formula that isn't a sentence in the formal language, since you use the symbol =? Does your language include "and" and "or?"

The language doesn't include "and", "or" or "=", since those are covered by the (language of the!) underlying logic, which in this case I assume is first order logic (with equality). In model theory, when one speaks of "language", the underlying logic will already have been established, so "language" means the non-logical symbols; in this case just <.

 

[eabod]

I have a definition of definable, and am having difficultly applying what it means for a subset of RxR to be definable in (R,<).

I am using the definition of definable that I mentioned in my first post. Then, a formula with n free variables defines the set of n-tuples that make the formula true in the given structure. So, in RxR for example, we are looking at ordered pairs. An example of a set being definable can be seen by looking at the formula v_{1}<v_{2}. This the set of all ordered pairs (x,y) where x<y.

On one hand you said you don't know what it means for a subset of $$\mathbb{R}\times \mathbb{R}$$ to be definable, yet here you've (correctly) explained what it means and even given an example of one, namely $$\{ (x,y) \mid x<y\}$$. Thus I will assume that you do know what it means for for a subset of $$\mathbb{R}\times \mathbb{R}$$ to be definable, and your real issue is with the theorem about automorphisms (setwise) fixing definable sets.

To show that a subset S is not definable, we need to show that there is an automorphism that takes elements from S to elements not in S.

I'm having trouble figuring out which sets of RxR are decidable and which aren't, because I am having difficulty understanding what an automorphism is on RxR where < is preserved on R. For example, let's say that a function f takes (x,y) to (a,b) and (w,z) to (c,d). If x<y, must it be so that a<b for f to be an automorphism? If x<w and y<z, must it be so that a<c and b<d for f to be an automorphism?

The automorphism should still be an automorphism of $$\mathbb{R}$$ (not $$\mathbb{R}\times \mathbb{R}$$). So the theorem says that if $$f \colon \mathbb{R} \to \mathbb{R}$$ is an automorphism, then for any definable $$S \subseteq \mathbb{R} \times \mathbb{R}$$, it must be the case that $$(x,y) \in S$$ if and only if $$(f(x),f(y)) \in S$$.

 

[Hurkyl]

I'm having trouble figuring out which sets of RxR are decidable and which aren't, because I am having difficulty understanding what an automorphism is on RxR where < is preserved on R.

Ah! This is why I ask -- I would have never guessed this as the particular problem you were having.

As eabod said, the automorphisms that are relevant are automorphisms of the model -- so you're not looking for an "automorphism on RxR", but instead looking at the effects that an "automorphism of (R, <)" has on the set RxR.

I'm not entirely sure that every subset of RxR that is preserved by automorphisms of (R,<) is going to be definable, though. Is this the only method you have for computing what is definable?

 

[ky2345]

Ok, I think the automorphism definition is really what I was confused about. So, a function f((x,y))=(x+c,y+c) would be an example of an automorphism, but f((x,y))=(x+c,y+d) where c and d are not equal would not be an automorphism.

Now, I think I've figured out some of the definable sets. I'll list them below:
1) {(x,y)|x<y}
2) {(x,y)|x>y}
3) {(x,y)|x=y}
4) {(x,y)|x<y or x=y}
5) {(x,y)|x>y or x=y}
6) {(x,y)|x<y or x>y}All of these sets are sets I can define in my language. Now, what I can't quite figure out is whether or not a strip that is symmetrical about the line y=x is definable or not. I can't think of an automorphism that doesn't preserve it, nor can I think of a formula that describes it.

 

[ky2345]

Oh and thanks for being patient- I guess I wasn't confused about what I thought I was confused about!

 

[Hurkyl]

I will point out that you could consider a new structure (R, RxR, <, p1, p2) where p1 and p2 are the two projection maps from R to RxR. There ought to be a direct correspondence between things definable in (R, <) and things definable in (R, RxR, <, p1, p2). I'm not sure it helps, though.

 

[ky2345]

I'm pretty sure all I need is an automorphism that stretches everything about the line y=x.