# Thread: Fol 14

1. ## Fol 14

Enderton 2.2.25

Consider a fixed structure $\displaystyle A$. Expand the language by adding a new constant symbol $\displaystyle c_a$ for each $\displaystyle a \in |A|$. Let $\displaystyle A^+$ be the structure for this expanded language that agrees with $\displaystyle A$ on the original parameters and that assigns to $\displaystyle c_a$ the point $\displaystyle a$. A relation $\displaystyle R$ on $\displaystyle |A|$ is said to be definable from points in $\displaystyle A$ iff $\displaystyle R$ is definable in $\displaystyle A^+$. (This differs from ordinary definability only in that we now have parameters in the language for members of $\displaystyle |A|$.) Let $\displaystyle K=(\mathbb{Re}; <, +, \cdot)$.

(a) Show that if $\displaystyle X$ is a subset of $\displaystyle \mathbb{Re}$ consisting of the union of finitely many intervals, then $\displaystyle X$ is definable points in $\displaystyle K$.

(b) Assume that $\displaystyle A \equiv K$. Show that any subset of $\displaystyle |A|$ that is non-empty, bounded (in the ordering $\displaystyle <^A$), and definable from points in $\displaystyle A$ has a least upper bound in $\displaystyle |A|$.

(*)$\displaystyle A \equiv K$ iff for any sentence $\displaystyle \sigma$, $\displaystyle \models_A \sigma \Leftrightarrow \models_K\sigma$.

============================
To get started,

Why $\displaystyle c_a$ and $\displaystyle A^+$ are introduced in this problem?
How an open set and a closed set are defined by formulas in $\displaystyle A^+$?

Thanks.

2. ## Re: Fol 14

Originally Posted by logics
Why $\displaystyle c_a$ and $\displaystyle A^+$ are introduced in this problem?
Usually they don't ask such questions in mathematics. Every mathematical contribution starts with "Consider such and such objects." If the first question is, "Why are we supposed to consider them?", we would not get far.

Originally Posted by logics
How an open set and a closed set are defined by formulas in $\displaystyle A^+$?
Why do you need this? The problem does not mention open and closed sets (in the sense of topology). Do you mean open and closed intervals?

3. ## Re: Fol 14

The set of open intervals is a basis for the standard topology on $\displaystyle \mathbb{Re}$, so I assumed the standard topology on $\displaystyle \mathbb{Re}$. What I meant was that an open set in (the standard topology) $\displaystyle \mathbb{Re}$ is the union of open intervals in $\displaystyle \mathbb{Re}$.

However, you are correct in the sense that an open set is not defined in this problem.

4. ## Re: Fol 14

I think (a) is simple. For (b), I am not sure what $\displaystyle A\equiv B$ means and why B is not mentioned in the rest of the question. Also, the text before the questions defines a specific structure K and it is not clear how A and B are related to K.

5. ## Re: Fol 14

Originally Posted by emakarov
Usually they don't ask such questions in mathematics. Every mathematical contribution starts with "Consider such and such objects." If the first question is, "Why are we supposed to consider them?", we would not get far.

Why do you need this? The problem does not mention open and closed sets (in the sense of topology). Do you mean open and closed intervals?
We are only considering "finitely many intervals" instead of "arbitrary many intervals". It seems like I have to define an open and closed interval in $\displaystyle A^+$ first.
The question is how do we define an open and closed interval in $\displaystyle A^+$?

6. ## Re: Fol 14

Originally Posted by emakarov
I think (a) is simple. For (b), I am not sure what $\displaystyle A\equiv B$ means and why B is not mentioned in the rest of the question. Also, the text before the questions defines a specific structure K and it is not clear how A and B are related to K.
Sorry, I will edit the typo in the problem, and give the definition.

7. ## Re: Fol 14

Originally Posted by logics
The question is how do we define an open and closed interval in $\displaystyle A^+$?
The same as anywhere. An for two real numbers $\displaystyle a$, $\displaystyle b$, the interval $\displaystyle (a, b]$ is definable from points in $\displaystyle K$ using the formula $\displaystyle a<x\land (x<b\lor x=b)$. We can basically use all real numbers (or names for them) in formulas, so every interval is definable from points in $\displaystyle K$. A finite union of intervals can be expressed as a disjunction. To represent an infinite union may be a problem.

8. ## Re: Fol 14

Originally Posted by emakarov
The same as anywhere. An for two real numbers $\displaystyle a$, $\displaystyle b$, the interval $\displaystyle (a, b]$ is definable from points in $\displaystyle K$ using the formula $\displaystyle a<x\land (x<b\lor x=b)$. We can basically use all real numbers (or names for them) in formulas, so every interval is definable from points in $\displaystyle K$. A finite union of intervals can be expressed as a disjunction. To represent an infinite union may be a problem.
Why do we consider this definition,

"A relation $\displaystyle R$ on $\displaystyle |A|$ is said to be definable from points in $\displaystyle A$ iff $\displaystyle R$ is definable in $\displaystyle A^+$".

Why don't we just define in $\displaystyle A$ rather than $\displaystyle A^+$.

It seems like I am missing some fundamental concepts.

9. ## Re: Fol 14

Using elements of the structure domain in formulas can allow building more expressive formulas. A structure has a limited vocabulary and sometimes it does not have the means to refer to a particular domain element. This Wikipedia page refers to relations definable from points in A as relations definable in A with parameters. For example, in $\displaystyle (\mathbb{N},<)$ without parameters every singleton can be defined by a formula, while in $\displaystyle (\mathbb{Z},<)$ the only definable sets without parameters are $\displaystyle \emptyset$ and $\displaystyle \mathbb{Z}$.

10. ## Re: Fol 14

Originally Posted by emakarov
The same as anywhere. An for two real numbers $\displaystyle a$, $\displaystyle b$, the interval $\displaystyle (a, b]$ is definable from points in $\displaystyle K$ using the formula $\displaystyle a<x\land (x<b\lor x=b)$. We can basically use all real numbers (or names for them) in formulas, so every interval is definable from points in $\displaystyle K$. A finite union of intervals can be expressed as a disjunction. To represent an infinite union may be a problem.
Thank you for your help. Now I am getting to understand why parameters are needed in this problem. My another question is

Since constant symbols are not defined in $\displaystyle K$, doesn't $\displaystyle (a, b]$ have to be defined in $\displaystyle K^+$ using

$\displaystyle c_a<x\land (x<c_b\lor x=c_b)$?

11. ## Re: Fol 14

Originally Posted by logics
Since constant symbols are not defined in $\displaystyle K$, doesn't $\displaystyle (a, b]$ have to be defined in $\displaystyle K^+$ using

$\displaystyle c_a<x\land (x<c_b\lor x=c_b)$?
Yes, $\displaystyle (a, b]$ is definable in $\displaystyle K^+$, which, by definition, is the same thing as definable from points in K. You are right that instead of actual real numbers $\displaystyle a$, $\displaystyle b$ one has to use their constant symbols $\displaystyle c_a$, $\displaystyle c_b$ in formulas. After a while, though, it is convenient to leave out the bijection $\displaystyle a\mapsto c_a$ and to pretend to write numbers themselves.