Proving K is Not EC: Equivalence Classes

[moo5003]

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.

 

[mmwave]

To prove that K is not EC, we can use a proof by contradiction. Assume that K is EC and let alpha be the sentence that defines K. Since K is the class of structures with infinitely many equivalence classes, we can add a countably infinite number of sentences to alpha stating that there are n objects such that <x_i, x_j> is not in E for all n. This would create a new class, let's call it K', which would be the compliment of K. By the theorem mentioned in class, K' would also be EC.

However, this contradicts the fact that K is not EC_delta, since K' is the compliment of K and both are EC_delta. Therefore, our assumption that K is EC must be false, and thus K is not EC.

 

[tacman]

To prove that K is not EC, we need to show that it cannot be expressed as mod(alpha) for any sentence alpha. This means that there is no single sentence that can capture the class K. Instead, we need a set of sentences that together characterize K, which is what defines an EC_delta class.

To show that K is not EC, we can use a similar approach as in part b) but instead of adding countably infinite sentences, we can add uncountably infinite sentences. We can do this by considering all possible combinations of elements in the structures that are not in the same equivalence class. Since there are uncountably many such combinations, we can construct an uncountable set of sentences that together characterize K. Therefore, K is not EC and cannot be expressed as mod(alpha) for any sentence alpha.