First-Order Logic: Finite & Infinite Domains

Click For Summary
SUMMARY

The discussion focuses on first-order logic with a unary function symbol f, exploring sentences that exhibit specific properties in finite and infinite domains. A satisfiable sentence χ exists in infinite domains but is false in finite ones, indicating that models of χ must have infinite domains. Additionally, a sentence ρ is defined such that any finite model A satisfying ρ contains an even number of elements, while ¬ρ pertains to models with odd-sized domains. The participants seek clarification on the interpretation of the equality symbol in first-order languages.

PREREQUISITES
  • Understanding of first-order logic and its syntax
  • Familiarity with model theory concepts
  • Knowledge of finite and infinite domains in logic
  • Proficiency in constructing logical sentences and their satisfiability
NEXT STEPS
  • Study the properties of first-order languages, particularly unary function symbols
  • Research model theory, focusing on finite and infinite structures
  • Learn about the implications of the equality symbol in first-order logic
  • Explore the construction of logical sentences that define properties of finite sets
USEFUL FOR

Logicians, mathematicians, and computer scientists interested in model theory, particularly those working with first-order logic and its applications in finite and infinite domains.

kazuyak
Messages
3
Reaction score
0
Let L = {f } be a first-order language containing a unary function
symbol f , and no other non-logical symbols.
1.Write down a sentence χ of L which is satisfiable in some structure
with an infinite domain but is false in every structure with a finite domain.
What can you say about the size of the domains of the models of the sentence
2.Write down a sentence ρ such that whenever A |= ρ and A is finite,
then A contains an even number of elements and, further, every finite set
with an even number of elements is the domain of some model of ρ. What
can you say about the size of the domains of the models of the sentence ¬ρ?

Could anyone please give me some hints how to deal with this problem? I'm not sure where to start. Any help is appreciated!
 
Physics news on Phys.org
Does your definition of a first order language include the symbol "=", and is this to be interpreted as the identity in the models (i.e. are they "normal" models)?
 

Similar threads

Convert sentences into First Order Logic
  • · Replies 3 ·
Replies
3
Views
2K
Prove every subset of countable set is either finite or else countable
  • · Replies 1 ·
Replies
1
Views
2K
Convert statements into first order logic
  • · Replies 35 ·
2
Replies
35
Views
5K
MHB Infinite Natural Numbers: First-Order Logic Formula Explained
  • · Replies 2 ·
Replies
2
Views
2K
Examples of L-structures in First-Order Logic
  • · Replies 6 ·
Replies
6
Views
3K
Undergrad On the meaning of logical implication within specific context/models
  • · Replies 22 ·
Replies
22
Views
4K
Propositional Logic -- expressing in formal logic notataion
  • · Replies 4 ·
Replies
4
Views
2K
How many distinct L-structures can be constructed using this method?
  • · Replies 12 ·
Replies
12
Views
2K
Graduate Are formal systems of first order logic incomplete?
  • · Replies 14 ·
Replies
14
Views
4K
First order logic: definability
  • · Replies 15 ·
Replies
15
Views
5K