Mixing
Question about Fraïssé's theorem
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
In Bruno Poizat's book "A course in model theory" pages 35,36, he says :
"we have no difficulty proving the first part of Fraïssé's theorem, that two $p$-equivalent tuples satisfy the same formulas of quantifier rank less than or equal to $p$".
He continues, "As the for converse, which depends on Lemma 2.3 ("there are only finitely many p-equivalence classes"), it is correct only if the signature can be reduced to a finite number of relations and and constants. In fact, one $single$ $function$ of nonzero arity allows the formation of infinitely many terms, and consequently infinltely many atomic formulas.
"Therefore, if we want to reduce elementary equivalence completely to finite back-and-forth criteria, we need to reduce it to finite signatures, and to replace each $n$-ary function by its graph, which is an $(n+1)$-ary relation. Doing this would preserve elementary equivalence, but change the notions of atomic formula, formula of quantifier rank $p$, $p-isomorphism$, etc."
I don't really understand what he says about functions here, about replacing them with their graphs. Can someone please explain why this is necessary? Am I missing something?
logic model-theory
asked Jul 30 at 8:08
Stonecipher
335
add a comment |Â
up vote
1
down vote
favorite
In Bruno Poizat's book "A course in model theory" pages 35,36, he says :
"we have no difficulty proving the first part of Fraïssé's theorem, that two $p$-equivalent tuples satisfy the same formulas of quantifier rank less than or equal to $p$".
He continues, "As the for converse, which depends on Lemma 2.3 ("there are only finitely many p-equivalence classes"), it is correct only if the signature can be reduced to a finite number of relations and and constants. In fact, one $single$ $function$ of nonzero arity allows the formation of infinitely many terms, and consequently infinltely many atomic formulas.
"Therefore, if we want to reduce elementary equivalence completely to finite back-and-forth criteria, we need to reduce it to finite signatures, and to replace each $n$-ary function by its graph, which is an $(n+1)$-ary relation. Doing this would preserve elementary equivalence, but change the notions of atomic formula, formula of quantifier rank $p$, $p-isomorphism$, etc."
I don't really understand what he says about functions here, about replacing them with their graphs. Can someone please explain why this is necessary? Am I missing something?
logic model-theory
asked Jul 30 at 8:08
Stonecipher
335
What is $p$-equivalence for tuples?
– Berci
Jul 30 at 8:23
In the first chapter, the theorem is stated for a relation. He says two tuples in the universes of $R$ and $R'$ are $p-equivalent$ if they correspond via a $p-$isomorphism from $R$ to $R'$. This is an equivalence relation, and he writes $(overrightarrowa,R)sim_p (overrightarrowb,R')$
– Stonecipher
Jul 30 at 9:10
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
In Bruno Poizat's book "A course in model theory" pages 35,36, he says :
"we have no difficulty proving the first part of Fraïssé's theorem, that two $p$-equivalent tuples satisfy the same formulas of quantifier rank less than or equal to $p$".
He continues, "As the for converse, which depends on Lemma 2.3 ("there are only finitely many p-equivalence classes"), it is correct only if the signature can be reduced to a finite number of relations and and constants. In fact, one $single$ $function$ of nonzero arity allows the formation of infinitely many terms, and consequently infinltely many atomic formulas.
"Therefore, if we want to reduce elementary equivalence completely to finite back-and-forth criteria, we need to reduce it to finite signatures, and to replace each $n$-ary function by its graph, which is an $(n+1)$-ary relation. Doing this would preserve elementary equivalence, but change the notions of atomic formula, formula of quantifier rank $p$, $p-isomorphism$, etc."
I don't really understand what he says about functions here, about replacing them with their graphs. Can someone please explain why this is necessary? Am I missing something?
logic model-theory
asked Jul 30 at 8:08
Stonecipher
335
In Bruno Poizat's book "A course in model theory" pages 35,36, he says :
"we have no difficulty proving the first part of Fraïssé's theorem, that two $p$-equivalent tuples satisfy the same formulas of quantifier rank less than or equal to $p$".
He continues, "As the for converse, which depends on Lemma 2.3 ("there are only finitely many p-equivalence classes"), it is correct only if the signature can be reduced to a finite number of relations and and constants. In fact, one $single$ $function$ of nonzero arity allows the formation of infinitely many terms, and consequently infinltely many atomic formulas.
"Therefore, if we want to reduce elementary equivalence completely to finite back-and-forth criteria, we need to reduce it to finite signatures, and to replace each $n$-ary function by its graph, which is an $(n+1)$-ary relation. Doing this would preserve elementary equivalence, but change the notions of atomic formula, formula of quantifier rank $p$, $p-isomorphism$, etc."
I don't really understand what he says about functions here, about replacing them with their graphs. Can someone please explain why this is necessary? Am I missing something?
logic model-theory
asked Jul 30 at 8:08
Stonecipher
335
edited Jul 30 at 8:48
asked Jul 30 at 8:08
Stonecipher
335
asked Jul 30 at 8:08
Stonecipher
335
asked Jul 30 at 8:08
Stonecipher
335
335
What is $p$-equivalence for tuples?
– Berci
Jul 30 at 8:23
In the first chapter, the theorem is stated for a relation. He says two tuples in the universes of $R$ and $R'$ are $p-equivalent$ if they correspond via a $p-$isomorphism from $R$ to $R'$. This is an equivalence relation, and he writes $(overrightarrowa,R)sim_p (overrightarrowb,R')$
– Stonecipher
Jul 30 at 9:10
add a comment |Â
What is $p$-equivalence for tuples?
– Berci
Jul 30 at 8:23
In the first chapter, the theorem is stated for a relation. He says two tuples in the universes of $R$ and $R'$ are $p-equivalent$ if they correspond via a $p-$isomorphism from $R$ to $R'$. This is an equivalence relation, and he writes $(overrightarrowa,R)sim_p (overrightarrowb,R')$
– Stonecipher
Jul 30 at 9:10
What is $p$-equivalence for tuples?
– Berci
Jul 30 at 8:23
What is $p$-equivalence for tuples?
– Berci
Jul 30 at 8:23
In the first chapter, the theorem is stated for a relation. He says two tuples in the universes of $R$ and $R'$ are $p-equivalent$ if they correspond via a $p-$isomorphism from $R$ to $R'$. This is an equivalence relation, and he writes $(overrightarrowa,R)sim_p (overrightarrowb,R')$
– Stonecipher
Jul 30 at 9:10
In the first chapter, the theorem is stated for a relation. He says two tuples in the universes of $R$ and $R'$ are $p-equivalent$ if they correspond via a $p-$isomorphism from $R$ to $R'$. This is an equivalence relation, and he writes $(overrightarrowa,R)sim_p (overrightarrowb,R')$
– Stonecipher
Jul 30 at 9:10
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
Long comment
Theorem 2.2, page 24 (Fraïssé's theorem) is stated for a relation $R$.
Ch.3.2 Functions (page 33-on) consider a language with also function symbols $f_j$.
The "trick" is to replace an $n$-ary function symbol $f$ with an $(n+1)$-ary relation symbol $R$.
Consider the simple example of arithmetic; the sum operation is a binary function : $+ : mathbb N to mathbb N$.
Thus, we need a binary function symbol : $+(x,y)=z$.
We may replace it with a ternary relation symbol $+^*(x,y,z)$ defined as follows :
$+^*(x,y,z)$ holds iff $z=+(x,y)$.
Compare with : Graph of a function :
in mathematics, the graph of a function $f$ is, formally, the set of all ordered pairs $(x, f(x))$, and, in practice, the graphical representation of this set.
In symbols : $text Graph(f) = (x, y) mid y=f(x) $.
answered Jul 30 at 8:32
Mauro ALLEGRANZA
60.6k346105
Okay, but I'm bothered when he says "single function of nonzero arity allows the formation of infinitely many terms, and consequently infinltely many atomic formulas" and whether it would affect Lemma 2.3 "there are only finitely many p-equivalence classes"?
– Stonecipher
Jul 30 at 8:45
I understood it. Thank you. Just I was confused with "infinitely many atomic formulas", where the lemma says it should be finite
– Stonecipher
Jul 30 at 9:02
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
Long comment
Theorem 2.2, page 24 (Fraïssé's theorem) is stated for a relation $R$.
Ch.3.2 Functions (page 33-on) consider a language with also function symbols $f_j$.
The "trick" is to replace an $n$-ary function symbol $f$ with an $(n+1)$-ary relation symbol $R$.
Consider the simple example of arithmetic; the sum operation is a binary function : $+ : mathbb N to mathbb N$.
Thus, we need a binary function symbol : $+(x,y)=z$.
We may replace it with a ternary relation symbol $+^*(x,y,z)$ defined as follows :
$+^*(x,y,z)$ holds iff $z=+(x,y)$.
Compare with : Graph of a function :
in mathematics, the graph of a function $f$ is, formally, the set of all ordered pairs $(x, f(x))$, and, in practice, the graphical representation of this set.
In symbols : $text Graph(f) = (x, y) mid y=f(x) $.
answered Jul 30 at 8:32
Mauro ALLEGRANZA
60.6k346105
Okay, but I'm bothered when he says "single function of nonzero arity allows the formation of infinitely many terms, and consequently infinltely many atomic formulas" and whether it would affect Lemma 2.3 "there are only finitely many p-equivalence classes"?
– Stonecipher
Jul 30 at 8:45
I understood it. Thank you. Just I was confused with "infinitely many atomic formulas", where the lemma says it should be finite
– Stonecipher
Jul 30 at 9:02
add a comment |Â
up vote
1
down vote
accepted
Long comment
Theorem 2.2, page 24 (Fraïssé's theorem) is stated for a relation $R$.
Ch.3.2 Functions (page 33-on) consider a language with also function symbols $f_j$.
The "trick" is to replace an $n$-ary function symbol $f$ with an $(n+1)$-ary relation symbol $R$.
Consider the simple example of arithmetic; the sum operation is a binary function : $+ : mathbb N to mathbb N$.
Thus, we need a binary function symbol : $+(x,y)=z$.
We may replace it with a ternary relation symbol $+^*(x,y,z)$ defined as follows :
$+^*(x,y,z)$ holds iff $z=+(x,y)$.
Compare with : Graph of a function :
in mathematics, the graph of a function $f$ is, formally, the set of all ordered pairs $(x, f(x))$, and, in practice, the graphical representation of this set.
In symbols : $text Graph(f) = (x, y) mid y=f(x) $.
answered Jul 30 at 8:32
Mauro ALLEGRANZA
60.6k346105
Okay, but I'm bothered when he says "single function of nonzero arity allows the formation of infinitely many terms, and consequently infinltely many atomic formulas" and whether it would affect Lemma 2.3 "there are only finitely many p-equivalence classes"?
– Stonecipher
Jul 30 at 8:45
I understood it. Thank you. Just I was confused with "infinitely many atomic formulas", where the lemma says it should be finite
– Stonecipher
Jul 30 at 9:02
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
Long comment
Theorem 2.2, page 24 (Fraïssé's theorem) is stated for a relation $R$.
Ch.3.2 Functions (page 33-on) consider a language with also function symbols $f_j$.
The "trick" is to replace an $n$-ary function symbol $f$ with an $(n+1)$-ary relation symbol $R$.
Consider the simple example of arithmetic; the sum operation is a binary function : $+ : mathbb N to mathbb N$.
Thus, we need a binary function symbol : $+(x,y)=z$.
We may replace it with a ternary relation symbol $+^*(x,y,z)$ defined as follows :
$+^*(x,y,z)$ holds iff $z=+(x,y)$.
Compare with : Graph of a function :
in mathematics, the graph of a function $f$ is, formally, the set of all ordered pairs $(x, f(x))$, and, in practice, the graphical representation of this set.
In symbols : $text Graph(f) = (x, y) mid y=f(x) $.
answered Jul 30 at 8:32
Mauro ALLEGRANZA
60.6k346105
Long comment
Theorem 2.2, page 24 (Fraïssé's theorem) is stated for a relation $R$.
Ch.3.2 Functions (page 33-on) consider a language with also function symbols $f_j$.
The "trick" is to replace an $n$-ary function symbol $f$ with an $(n+1)$-ary relation symbol $R$.
Consider the simple example of arithmetic; the sum operation is a binary function : $+ : mathbb N to mathbb N$.
Thus, we need a binary function symbol : $+(x,y)=z$.
We may replace it with a ternary relation symbol $+^*(x,y,z)$ defined as follows :
$+^*(x,y,z)$ holds iff $z=+(x,y)$.
Compare with : Graph of a function :
in mathematics, the graph of a function $f$ is, formally, the set of all ordered pairs $(x, f(x))$, and, in practice, the graphical representation of this set.
In symbols : $text Graph(f) = (x, y) mid y=f(x) $.
answered Jul 30 at 8:32
Mauro ALLEGRANZA
60.6k346105
edited Jul 30 at 8:41
answered Jul 30 at 8:32
Mauro ALLEGRANZA
60.6k346105
answered Jul 30 at 8:32
Mauro ALLEGRANZA
60.6k346105
answered Jul 30 at 8:32
Mauro ALLEGRANZA
60.6k346105
60.6k346105
Okay, but I'm bothered when he says "single function of nonzero arity allows the formation of infinitely many terms, and consequently infinltely many atomic formulas" and whether it would affect Lemma 2.3 "there are only finitely many p-equivalence classes"?
– Stonecipher
Jul 30 at 8:45
I understood it. Thank you. Just I was confused with "infinitely many atomic formulas", where the lemma says it should be finite
– Stonecipher
Jul 30 at 9:02
add a comment |Â
Okay, but I'm bothered when he says "single function of nonzero arity allows the formation of infinitely many terms, and consequently infinltely many atomic formulas" and whether it would affect Lemma 2.3 "there are only finitely many p-equivalence classes"?
– Stonecipher
Jul 30 at 8:45
I understood it. Thank you. Just I was confused with "infinitely many atomic formulas", where the lemma says it should be finite
– Stonecipher
Jul 30 at 9:02
Okay, but I'm bothered when he says "single function of nonzero arity allows the formation of infinitely many terms, and consequently infinltely many atomic formulas" and whether it would affect Lemma 2.3 "there are only finitely many p-equivalence classes"?
– Stonecipher
Jul 30 at 8:45
Okay, but I'm bothered when he says "single function of nonzero arity allows the formation of infinitely many terms, and consequently infinltely many atomic formulas" and whether it would affect Lemma 2.3 "there are only finitely many p-equivalence classes"?
– Stonecipher
Jul 30 at 8:45
I understood it. Thank you. Just I was confused with "infinitely many atomic formulas", where the lemma says it should be finite
– Stonecipher
Jul 30 at 9:02
I understood it. Thank you. Just I was confused with "infinitely many atomic formulas", where the lemma says it should be finite
– Stonecipher
Jul 30 at 9:02
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2866760%2fquestion-about-fra%25c3%25afss%25c3%25a9s-theorem%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
What is $p$-equivalence for tuples?
– Berci
Jul 30 at 8:23
In the first chapter, the theorem is stated for a relation. He says two tuples in the universes of $R$ and $R'$ are $p-equivalent$ if they correspond via a $p-$isomorphism from $R$ to $R'$. This is an equivalence relation, and he writes $(overrightarrowa,R)sim_p (overrightarrowb,R')$
– Stonecipher
Jul 30 at 9:10