- #1
moo5003
- 207
- 0
QUESTION:
Let L be the language with = and one binary relation symbol E. Let epsilon be the class of all L-structures A such that E interpreted by A is an equivalence relation on |A|.
K = { A in epsilon | E interpreted by A has infinitley many equivalence classes }.
DEFINITIONS:
EC - There exists a sentance alpha such that the class K = mod(alpha)
EC_delta - There exists a set of sentances sigma such that the class K = mod(sigma)
ANSWERS:
a) Show epsilon is EC
This is pretty easy, just list the 3 things it E needs to satisfy for it to be an equivalence relation.
b) Show K is EC_delta
Also pretty straightforward, take the sentance for epsilon and add on countably infinite sentances saying that there are n things such that <x_i,x_j> is not in E.
c) Show K is not EC.
We had a homework problem prior that proves this though I forgot how I proved it, and this is a midterm review so I would like to know how to prove it directly. Any suggestions would be greatly appreciated.
We went over a theorem in class that said the follow where equivalent:
1) A class K is EC
2) A class K and its compliment K_2 are both EC_delta.
Maybe it would be better to prove that the compliment of K ie: All structures that are finite and all infinite structures that do not have infinitely many equivalence classes is not EC_delta.
We know that all finite structures is not EC_delta but I'm not sure how to show this for all finite structures AND all infinite structures without infinite equivalence classes.
Let L be the language with = and one binary relation symbol E. Let epsilon be the class of all L-structures A such that E interpreted by A is an equivalence relation on |A|.
K = { A in epsilon | E interpreted by A has infinitley many equivalence classes }.
DEFINITIONS:
EC - There exists a sentance alpha such that the class K = mod(alpha)
EC_delta - There exists a set of sentances sigma such that the class K = mod(sigma)
ANSWERS:
a) Show epsilon is EC
This is pretty easy, just list the 3 things it E needs to satisfy for it to be an equivalence relation.
b) Show K is EC_delta
Also pretty straightforward, take the sentance for epsilon and add on countably infinite sentances saying that there are n things such that <x_i,x_j> is not in E.
c) Show K is not EC.
We had a homework problem prior that proves this though I forgot how I proved it, and this is a midterm review so I would like to know how to prove it directly. Any suggestions would be greatly appreciated.
We went over a theorem in class that said the follow where equivalent:
1) A class K is EC
2) A class K and its compliment K_2 are both EC_delta.
Maybe it would be better to prove that the compliment of K ie: All structures that are finite and all infinite structures that do not have infinitely many equivalence classes is not EC_delta.
We know that all finite structures is not EC_delta but I'm not sure how to show this for all finite structures AND all infinite structures without infinite equivalence classes.
Last edited: