Questions tagged [first-order-logic]
The first-order-logic tag has no usage guidance.
28 questions
2
votes
2
answers
68
views
Are all cats and dogs mammals equivalent to all cats or dogs are mammals?
Are all cats and dogs mammals equivalent to all cats or dogs are mammals? I ask because it seems they are not. For let C be the predicate cat. Let D be the predicate dog. Let M be the predicate mammal....
3
votes
1
answer
43
views
Are there some propositions that cannot be expressed easily in first order logic and in higher order logics?
Are there some propositions, i.e. statements that are either true or false, that cannot be expressed easily in first order logic and in higher order logics? I ask because of the following: Let C be ...
0
votes
3
answers
86
views
Is there a formal logical structure to natural language?
Is there a formal logical structure to natural language?
I ask because of the following: Let C signify cats.
Let D signify dogs.
Let M signify mammals.
Let → signify is or are.
Let ∀(C→M) translate to ...
3
votes
1
answer
44
views
Formal Definition of Expressibility in Logic and Whether Propositional Logic Can Express Universality
Apparently, you are able to prove that graph reachability (whether a finite path exists from a vertex u to a vertex v in a graph G) cannot be expressed in first-order logic (FOL). This is done by ...
- 31
1
vote
1
answer
36
views
Is falsifiability precision, knowability, or both?
I have sometimes heard people say that there is merit in formulating claims that are “falsifiable”.
I can imagine that “falsifiable” means “can be falsified”, and “falsified” means “judged, determined,...
- 3,924
-2
votes
2
answers
59
views
Making first-order logic perspectival
How do linguists and computer scientists typically make propositions in first-order logic "perspectival", in the way that natural language gives us pronouns like "I", relative ...
- 3,924
3
votes
1
answer
38
views
what's means scope of further modal operators?
I am reading page 315 of Parsons' Sets, Classes, and Truth.
He presents the comprehension principle in the following form, but at the same time, he argues that this does not prevent Russell's paradox....
- 335
0
votes
0
answers
66
views
Disjoint predicates FOL: equivalence of normal forms
I'm interested in exploring a restriction of first-order logic (FOL) where each predicate is disjoint. Formally, for any predicates Pᵢ and Pⱼ where i ≠ j, we enforce the following condition:
¬∃x (Pᵢ(x)...
- 9
2
votes
1
answer
76
views
Can the rules of existential elimination and introduction be derived from the rules of universal elimination and introduction?
In my understanding, an existentially quantified predicate ∃xFx is defined as ~∀x~Fx but in introductory logic texts the elimination and introduction rules for existential and universal quantifiers ...
- 71
5
votes
2
answers
402
views
What would the correct answer be for Mendelson Exercise 1.4 (g)
In Elliot Mendelson’s “Introduction to Mathematical Logic”, he states, “Sentences may be combined in various ways to form more complicated sentences. We shall consider only truth-functional ...
- 251
-1
votes
2
answers
73
views
Question regarding 0-ary relations
EDIT-
Definition. A denotes a unary relation iff
∀x[if x∈ A then ∃y[x= (y)]]
Using this definition, since individuals don't contain elements, any individual is a unary relation. Since the empty set ...
- 1,550
-4
votes
2
answers
149
views
Is equality necessarily transitive? [duplicate]
I want to introduce three definitions into the philosophy of logic for the purpose of improving first order logic.
Consider the following three definitions.
Definitions
C is an arbitrary constant iff ∀...
- 1,550
10
votes
2
answers
1k
views
Why is completeness (as in Gödel completeness theorem) a desirable feature?
When justifying the dominance of first-order theory, an argument that is often made is that it is complete (as shown by Gödel).
This means that a theory formulated in first-order logic has a model if ...
- 225
4
votes
4
answers
276
views
How do you prove mathematical induction without the notion of a set?
EDIT - Peano's axioms for N can't be used to answer this question, because they assume induction. So what axioms can be used? I am thinking the following:
P1. x ∈ N iff x=1 ∨ ∃y (x=y' ∧ y ∈ N)
P2. 0'...
- 1,550
2
votes
0
answers
61
views
Translating a part of the Lowenheim-Skolem Theorem into first order logic
The part of the Lowenheim-Skolem theorem that I want to translate into first order logic is the following: For every signature A, every infinite A-structure B, and every infinite cardinal number C, ...
1
vote
0
answers
46
views
Can the modal logic S5 be reduced to Rosser's system for a first order function calculus?
From the SEP
In propositional logic, a valuation of the atomic sentences (or row of a truth table) assigns a truth value
(
T
or
F
)
to each propositional variable
p
. Then the truth values of the ...
- 1,550
3
votes
2
answers
208
views
On Relations Versus Relational Properties
According to the Stanford Encyclopedia of Philosophy, the following holds: Relations and relational properties can be distinguished. A relation is borne from one thing to another thing. A relational ...
1
vote
4
answers
226
views
Looking for a formal proof that x=x isn't a contingency
EDIT - My original question was answered, but not to my satisfaction. What I really want is a formal proof α = α isn't a contingency, using the modal logic version of Hao Wang's axiom of Identity. I ...
- 1,550
-2
votes
2
answers
118
views
What is the proper form of universal instantiation?
Definitions
C is a specific constant iff ∃! x [x=C]
C is a general constant iff ∀x [x=C]
C is an arbitrary constant iff ∀x [x=C] ∨ ∃! x [x=C]
Consider the commonly accepted form of the rule of ...
- 1,550
0
votes
3
answers
965
views
Is Frege's axiom of unrestricted comprehension actually true after all?
Consider the following demonstration whose first line is the assumption called the axiom of unrestricted comprehension.
∀F∃y ∀x[x ∈ y iff F(x)] [OSC1]
∀F∃y [α ∈ y iff F(α)] [UI]
∃y [α ∈ y iff α ∉ α] [...
- 1,550
2
votes
0
answers
151
views
Can the entirety of first order logic be reduced to the propositional calculus?
I've been wondering, whether or not first order logic can be reduced to the propositional calculus.
Rosser's system RS_1, described by Irving M. Copi in 'Symbolic Logic', has 5 axioms or postulates:
...
- 1,550
5
votes
4
answers
713
views
Must a domain of discourse always be specified in universally quantified statements?
Some logic texts formulate universally quantified statements without specifying a domain of discourse D.
For example
For any x: x isn't alive.
They take it for granted that x ∈ U, where it's true that
...
- 1,550
1
vote
1
answer
91
views
Can modal logic be used to define the notion of an “arbitrary constant” in FOL?
I was wondering if first-order logic can be reduced to propositional calculus if we eliminate quantification.
For example, instead of saying “for all x in a domain D, P(x)”, we could state “P(x)” for ...
- 1,550
6
votes
2
answers
308
views
What is the difference between a model and an interpretation in logic?
On page 319 of Irving M. Copi's 'Symbolic Logic', he states, "if we want our logical system to be applicable to any possible universe, regardless of the exact number of individuals it contains ...
- 1,550
-1
votes
1
answer
125
views
Can Frege's axiom of unrestricted comprehension be slightly modified to avoid the Russell paradox?
EDIT - The universal quantification of F should be at the far left, so the axiom I'm proposing is
PRINCIPLE OF RESTRICTED COMPREHENSION
∀F∃y [y is a set & ∀x[ not(F(x) ↔ x ∉ x ) → (x ∈ y ↔ F(x))]]
...
- 1,550
2
votes
0
answers
111
views
Does First order Logic require the subsistence/existence of a universal set, i.e. a set of all things? [closed]
In Irving M. Copi's 'Symbolic Logic' he postulates an unlimited set of individual constants. Each constant denotes an individual, so it seems he accounted for a set of all things U. First order logic ...
- 1,550
33
votes
5
answers
20k
views
How is first-order logic complete but not decidable?
Why doesn't completeness imply decidability for first-order logic?
First order logic is complete, which means (I think) given a set of sentences A and a sentence B, then either B or ~B can be arrived ...
- 447
37
votes
3
answers
5k
views
Is first-order logic the only fundamental logic?
I'm far from being an expert in the field of mathematical logic, but I've been reading about the academic work invested in the foundations of mathematics, both in a historical and objetive sense; and ...
- 656