Questions about mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Consider using one of the following tags: (model-theory), (set-theory), (computability), (proof-theory) if they fit the question.

learn more… | top users | synonyms (1)

3
votes
1answer
100 views

Borel linear order cannot have uncountable increasing chain

I am trying to make sense of what this theorem from C.I. Steinhorn, Borel Structures and Measure and Category Logics, says. Theorem 1.3.3. A Borel linear order cannot have an uncountable increasing ...
4
votes
4answers
595 views

Neither provable nor disprovable theorem

I wonder about a theorem which can be proven that this theorem is $neither\, provable$ nor $disprovable$ using any kind of mathematical knowledge. Questions: 1- Is there any such theorem? or is it ...
2
votes
3answers
330 views

Find an equivalent to $(P \lor Q) \land (P \to R) \land (Q \to S)$

I need some help regarding solving a logic. The question is to find an equivalent to the following logic. $$(P \lor Q) \land (P \to R) \land (Q \to S)$$ The choices are (a) $S \land R$ (b) $S ...
2
votes
1answer
108 views

On the Decision Problem for Two-variable First-Order Logic

I have a question concerning the model construction of the $\forall \forall \land \forall \exists$ - Scott sentence on page 6 in this paper: www.cs.rice.edu/~vardi/papers/basl96.ps.gz Why do we ...
2
votes
1answer
1k views

Truth Tables - How to identify normals in Knights, Knaves and Normals problems?

To describe my question, I'll illustrate an example of a Knights, Knaves and Normals problem and the way I solve it. Question Knights always tell the truth. Knaves always lie. Normals sometimes lie ...
2
votes
1answer
4k views

Finding Satisfiability, Unsatisfiability and Valid well formed formula

I have a confusion regarding how to check whether a wff is satisfiable, unsatisfiable and valid. As far as I understood, valid means the truth table must be a tautology, otherwise it is not a valid ...
0
votes
2answers
552 views

What is actually “relatively consistent”?

Gödel's incompleteness theorem states that: "if a system is consistent, it is not complete." And it's well known that there are unprovable statements in ZF, e.g. GCH, AC, etc. However, why does this ...
5
votes
3answers
607 views

Is the negation of the Gödel sentence always unprovable too?

The incompleteness theorem says that certain theories+deduction system contain at least one sentence (the Gödel sentence "$G$"), which can't be proven (in the system in which it holds). (i) Is ...
53
votes
10answers
13k views

How is a system of axioms different from a system of beliefs?

Other ways to put it: Is there any faith required in the adoption of a system of axioms? How is a given system of axioms accepted or rejected if not based on blind faith?
2
votes
1answer
200 views

A qualitative, yet precise statement of Godel's incompleteness theorem?

I read online a statement to the effect that (I'm paraphrasing): Goedel's incompleteness theorem shows that we cannot even have a complete and consistent theory for the natural numbers. I am ...
2
votes
1answer
117 views

Questions about adjointness of quantifiers in first-order logic

I have a category theory homework problem which asks: "In first-order logic, why does $\forall$ not have a right adjoint?" The typical argument is that: If for some operator $\cdot$ it could be ...
1
vote
1answer
299 views

Can Horn's algorithm be generalized for all logic expressions?

The following is an algorithm to find truth assignments for Horn Formulas: Input: A Horn Formula Output: A satisfying assignment, if one exists Set all variables to false While ...
1
vote
1answer
404 views

Errata for Mendelson's Introduction to Mathematical Logic (5th ed)?

I'm hoping that there exists a prepared errata list for Elliott Mendelson's Introduction to Mathematical Logic (5th ed). If so, how does one locate it? (It does not seem to be available from the ...
2
votes
1answer
112 views

Is failing to admit an axiom equivalent to proof when the axiom is false?

Often, mathematicians wish to develop proofs without admitting certain axioms (e.g. the axiom of choice). If a statement can be proven without admitting that axiom, does that mean the statement is ...
2
votes
1answer
404 views

Exponentiation and Set of Functions Notation.

Given arbitrary sets $A$ and $B$, the notation $A^{B}$ is mostly clear from context to mean $A^{B} = \{f : f : B \rightarrow A\}$. However, when these sets are ordinal or cardinals, especially ...
4
votes
2answers
237 views

Is there notation for “some two of the three statements are true”?

There are three propositions A, B, C and another condition "some two of these propositions are true and the third one is false", or, in other words, "exactly 2 of 3 propositions are true". Using truth ...
6
votes
5answers
2k views

Express logic puzzles with proposition calculus notation

I’m trying to solve a logic puzzle that goes like this: The police have three suspects for the murder of Mr. Cooper: Mr. Smith, Mr. Jones, and Mr. Williams. Smith, Jones, and Williams each declare ...
4
votes
4answers
6k views

What is the name of the logical puzzle, where one always lies and another always tells the truth?

So i was solving exercises in propositional logic lately and stumbled upon a puzzle, that goes like this: Each inhabitant of a remote village always tells the truth or always lies. A villager will ...
5
votes
1answer
454 views

Is there a difference between a model and a representation?

I'm thinking of models in logic here, vs. e.g. group representations. Is there a difference between a model and a representation? Could one not explain both at the same time? A model gives an ...
3
votes
2answers
1k views

Formation sequence for a logic formula

I will start with some definitions from An Introduction to Mathematical Logic and Type Theory: To Truth through Proof by Peter B. Andrews then give the exercise that I am working along with my attempt ...
5
votes
2answers
310 views

What interpretations exists for the singleton of the singleton of the empty set $\{\{\varnothing\}\}$ and its singleton $\{\{\{\varnothing\}\}\}$?

What I know I know from Peano's axioms that the empty set is equivalent to the natural number $0$ and that the singleton of the empty set is equivalent to the natural number $1$. ( ...
3
votes
1answer
155 views

Reference request for examples of probabilistic heuristics, help put some examples in a broader context.

I was thinking about how probability is used in heuristic arguments, an example being the argument that there are an infinite number of twin primes: the probability that $n$ is the first of two twin ...
4
votes
2answers
467 views

Induction without integers (aka Structural Induction)

While composing the following question, I had an "ah-ha" moment. I still want to post the question along with my answer to show what I have learned. Any comments or additional answers will be greatly ...
1
vote
2answers
425 views

Proving a relation between 2 sets as antisymmetric

Let $U = \{1,...,n\}$ And let $A$ and $B$ be partitions of the set $U$ such that: $\bigcup A = \bigcup B = U$ and $|A|=s, |B|=t$ Let's define a relation between the sets $A$ and $B$ as follows: $B ...
1
vote
1answer
148 views

prenex normal form quantifiers predicates

Are these if and only if equalities always true ? 1 - $\exists x \exists y \;(P(x) \;and \;Q(y))\Leftrightarrow \exists x P(x) \; and \;\exists y \;Q(y)$ 2- $\exists x \exists y \;(P(x) \;or ...
0
votes
1answer
54 views

Knotted up over “unique”

"Every boy has a unique shirt." Does this mean no two boys share the same shirt, or does it mean no two shirts belong to the same boy? I suppose the former, but then what is the most succinct way ...
3
votes
1answer
138 views

Arithmetical hierarchy and skolemization

What's the point of classifying statements in an arithmetical hierarchy if you can use skolemization to construct equisatisfiable $\Pi^0_1$ formulas for any non-$\Pi^0_1$ formula?
4
votes
0answers
136 views

Cutest proof that PA proves its finitely axiomatised subtheories are consistent?

Back in 1952, Mostowski proved that PA proves the consistency of its finitely axiomatised sub-theories. Any pointers to particularly nice later proofs of this lovely result? Or indeed particular nice ...
2
votes
1answer
232 views

What is the predicate of an n-ary propositional function?

I'm self-studying discrete mathematics using the Rosen textbook, and I'm trying to get some predicate logic terms straight. Using definitions from that textbook: The propositional function ...
7
votes
1answer
137 views

Learning how to prove that a function can't proved total?

In proof-theory one can prove that in, say, Peano Arithmetic one can't prove a function $f$ total. Often this seems to mean $f$ is growing too fast to be provably total. I have some background in ...
5
votes
1answer
473 views

What is the $\tau$ symbol in the Bourbaki text?

I'm reading the first book by Bourbaki (set theory) and he introduces this logical symbol $\tau$ to later define the quantifiers with it. It is such that if $A$ is an assembly possibly contianing $x$ ...
0
votes
2answers
172 views

Two forms of quantified conditional statement: equivalent?

There seems to be two forms of the conditional statement in predicate logic. $$\forall x\,(P(x)\Rightarrow Q(x))$$ versus $$(\forall x\in S)\Rightarrow Q(x)$$ $$S=\{x:P(x)\}$$ Are these ...
5
votes
3answers
292 views

How are the full semantics of SOL and HOL specified?

In relation to this question about the "fundamental" character of possible logical systems, I realized that I just had an intuitive (and so, inadequate) understanding of the way logics higher than FOL ...
0
votes
1answer
302 views

Request for Help with Predicate Logic Proof

Given the premises in lines 1 and 2, I need to prove that $(\forall x)(\exists y)(Cx \rightarrow Axy)$. $(\exists x)(\forall y)Ayx \lor (\forall x)(\forall y)Bxy$ $(\exists x)(\forall y)(Cy ...
1
vote
1answer
85 views

How can the set of the deducible WFF $\{\phi\mid\Sigma\vdash_K\phi\}$ be denoted?

I am relatively new to the formalism of Mathematical Logic, and don't know how denote the set of the wff logically deducible by a given set of premises $\Sigma$ in a predicate calculus $K.$ I have ...
2
votes
2answers
436 views

An example showing that a Skolem normal form of $A$ can be not logically equivalent to $A.$

I am trying to learn a little about Mathematical Logic. Precisely now I am reading about Prenex Normal Forms from E. Mendelson, Introduction to Mathematical Logic, 2nd Edition. I would like to know ...
6
votes
3answers
1k views

All real functions are continuous

I've heard that within the field of intuitionistic mathematics, all real functions are continuous (i.e. there are no discontinuous functions). Is there a good book where I can find a proof of this ...
16
votes
2answers
656 views

Is First Order Logic (FOL) 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 ...
3
votes
1answer
167 views

question about Skolem theories

Right now I am reading a proof of Downward Löwenheim-Skolem theorem in Hodges, but I am slightly confused about a proof Hodges makes. Let me write down some of the definitions. Definition: Let ...
0
votes
1answer
256 views

Using existential instantiation (logic)

Am I using EI right on line 6? (Actually, I'm pretty sure the answer is 'no', and there's a few sketchy lines after that, too. So maybe you could also give a hint about how to do this). Prove: ...
8
votes
1answer
478 views

Intuitionistic Banach-Tarski Paradox

While the Banach-Tarski paradox is a counter-intuitive result which requires the Axiom of Choice, leading some people to argue specifically against Choice, and others to argue for constructive ...
3
votes
2answers
258 views

Velleman exercise 1.5.7a [duplicate]

I've been trying to solve the exercise 7(a) of Velleman's "How To Prove It" and haven't succeeded. It asks the verification of the following equivalence: $$ (P \to Q) \land (Q \to R) = (P \to R) ...
4
votes
3answers
386 views

Aftermath of the incompletness theorem proof

This is somewhat of a minor point about the incompletness theorem, but I'm always a little unsure: So one proves that there is a formula which is unprovable in the theory of consideration. Okay, at ...
2
votes
3answers
249 views

How to prove the tautology $ \neg \forall{x} \exists{y} (Py \wedge \neg Px) $?

I've been beating my head trying to prove the following tautology for some time: $$ \therefore \neg \forall{x} \exists{y} (Py \wedge \neg Px)$$ I think there's some tricky intermediate step that I'm ...
3
votes
2answers
250 views

This classic from euclid's elements, is it accepted everywhere?

I was reading linear vector spaces. When doing some exercise to prove some statements based on the properties defined for linear vector spaces, i suddenly noticed, outside the things defined, i'm ...
0
votes
1answer
78 views

Are the consequences of contradictions avoidable?

In common natural languages, there are two interpretations of the word "or". Can you construct a formal logic based on the excluding notion of "or", such that from a contradictory ($A$ and ...
2
votes
2answers
851 views

Proof using Reductio ad absurdum (RAA)

Note: $\neg$ means 'not', $\rightarrow$ is 'conditional', $\land$ is 'and', $\lor$ means '(inclusive) or'. Prove: $[\neg D \lor (A \land B)] \rightarrow[(J \rightarrow \neg A) \rightarrow (D ...
3
votes
1answer
139 views

properties of the provability predicate applied to open formulas

Good day! Let $\mathrm{T}$ be a first-order theory which contains the Peano arithmetic and has a recursively enumerable set of axioms. It is well known that one can construct a predicate ...
10
votes
4answers
496 views

What are the reasons for not supporting constructive mathematics

It is obvious that in constructive mathematics, you cannot use the law of excluded middle. What else would be the reasons for not adopting constructive stance in mathematics?
22
votes
6answers
841 views

How to avoid perceived circularity when defining a formal language?

Suppose we want to define a first-order language to do set theory (so we can formalize mathematics). One such construction can be found here. What makes me uneasy about this definition is that words ...