Satisfiability vs Elementary equivalence

In summary, the concept of elementary equivalence in logic states that two structures, A and B, are considered equivalent if they satisfy the same sentences. This is also true if B satisfies the theory of A. However, it is important to note that elementary equivalence only refers to the first-order theory of a structure, not to specific properties such as the Archimedean property.
  • #1
Logic Cloud
23
0
Hi, I have stumbled upon PF many times through Google, but this is my first time posting. Hopefully, someone will be able to help me out.

My question is about the concept of elementary equivalence in logic. According to my book, two structures A and B are elementary equivalent if: for every sentence s: A satisfies s if and only if B satisfies s. However, in my book it is also said that if B satisfies the theory of A, then A and B are elementary equivalent.

It is obvious that if this A satisfies s, then B also satisfies s (since s is in the theory of A). But I don't see how to get the other side of the "if and only if". If B satisfies s, I see no reason for s to be also satisfied by A. If B satisfies the theory of A, B could just as well satisfy other sentences too, right?
 
Physics news on Phys.org
  • #2
If B satisfies s, then it doesn't satisfy -s, hence A doesn't satisfy -s, hence A satisfies s.
 
  • #3
Just a small point: elementary equivalence refers to, in my experience,to the

first-order theory of a structure. So the non-standard reals are EE to the

standard reals, but Archimedean property is not satisfied in non-standard.
 

Related to Satisfiability vs Elementary equivalence

1. What is the difference between satisfiability and elementary equivalence?

Satisfiability and elementary equivalence are two concepts in mathematical logic that are often confused. Satisfiability refers to the question of whether a logical formula can be satisfied by assigning truth values to its variables, while elementary equivalence is the question of whether two logical formulas have the same set of models.

2. How do satisfiability and elementary equivalence relate to each other?

Satisfiability and elementary equivalence are closely related but distinct concepts. If two formulas are elementary equivalent, they must also be satisfiable. However, the reverse is not necessarily true - two formulas can be satisfiable but not elementary equivalent.

3. Can satisfiability and elementary equivalence be proven?

In general, determining satisfiability and elementary equivalence is an undecidable problem. This means that there is no algorithm that can always provide a correct answer for any given logical formula. However, for specific cases and simplified formulas, it is possible to prove satisfiability and elementary equivalence.

4. How are satisfiability and elementary equivalence used in mathematical logic?

Satisfiability and elementary equivalence are important concepts in mathematical logic because they provide a way to compare and classify logical formulas. They are often used in the study of model theory, which explores the relationships between logical formulas and their corresponding models.

5. What are some examples of satisfiability and elementary equivalence in real-world applications?

Satisfiability and elementary equivalence have many practical applications, particularly in computer science and artificial intelligence. They are used in automated reasoning systems, database query optimization, and circuit design. For example, satisfiability can be used to determine the validity of a computer program while elementary equivalence can be used to optimize database queries for faster execution.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
14
Views
4K
  • Set Theory, Logic, Probability, Statistics
Replies
11
Views
612
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
926
Replies
2
Views
376
  • Calculus and Beyond Homework Help
Replies
1
Views
364
  • Set Theory, Logic, Probability, Statistics
Replies
13
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Quantum Interpretations and Foundations
3
Replies
79
Views
5K
  • Classical Physics
Replies
6
Views
716
Back
Top