# Equivalence Class

1. Nov 20, 2007

### 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)

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: Nov 20, 2007