QUESTION:(adsbygoogle = window.adsbygoogle || []).push({});

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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Equivalence Class

Can you offer guidance or do you also need help?

Draft saved
Draft deleted

**Physics Forums | Science Articles, Homework Help, Discussion**