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)

1
vote
0answers
55 views

Show if theory T is ∀∃-axiomatizable, then T has an existentially closed model.

Setting Definition $\mathcal{M} \models T$ is existentially closed if whenever $\mathcal{N} \models T$, $\mathcal{N} \supseteq \mathcal{M}$, and $\mathcal{N}\models \exists \bar{v} ...
1
vote
0answers
25 views

Help with the interpretation method in logic

I am a begginer student of logic and I am experiencing some trouble at finding interpretations that help me prove depence/independence of axioms, consistency, as well as the independe of primitive ...
1
vote
0answers
58 views

Definitions of isomorphism and elementary substructures

Let us define -all the definitions are from V. Manca, Logica matematica, 2001, 'mathematical logic'- a $\Sigma$-morphism as a function $f:D_1\to D_2$ between models $\mathscr{M}_1$ and ...
1
vote
0answers
25 views

predicate logic proofs

I'm posting from my phone so I apologise for any formatting errors. The question asks me to determine if the following arguments are valid. $\begin{array}{rcr} A) & \forall x \forall y K(x, y) \, ...
1
vote
0answers
30 views

How do I notate this statement about a state of affairs (similar to a possible world)?

I'd like to notate this statement formally: If any given agent desires that a certain state of affairs obtains, then there is no state of affairs in which she enjoys greater security than that one. ...
1
vote
0answers
20 views

House allocation with existing tenants

In a house allocation with existing tenants model using the TTC mechanism, consider the incentive of an agent to misreport his/her preferences. Can it ever be that misreporting the true preferences by ...
1
vote
0answers
50 views

A computable set of sentences neither probable nor disprovable from $PA$

I need to prove that, given a computable binary tree $T$ whose paths are exactly the complete extensions of $PA$ (via some Gödel coding), there is a computable $X\subseteq\mathbb{N}$ such that for all ...
1
vote
0answers
62 views

Henkin Construction: Goedel completeness Theorem

I am trying to understand better the Henkin construction, which consist first in an extension of the signature and then of the theory. Here are my question about this topic: we extend the ...
1
vote
0answers
34 views

Does the class of all periodic subsets of $\mathbb{Z}$ of peroid greater than $k$ form a field of sets?

We say that a subset $X\subseteq \mathbb{Z}$ is a periodic subset of $\mathbb{Z}$ of period $k$ if the set obtained from $X$ by adding $k$ to each element of $X$ is $X$ itself. Does the class of all ...
1
vote
0answers
69 views

what does “a wff f(x, y)” mean exactly? (context: transfinite recursion)

I'm currently working through Herbert B. Enderton's book "Elements of set theory". I have a question concerning notation in logic, of which I know the basics but in which I'm not that firmly grounded. ...
1
vote
0answers
49 views

Would a “Prenex Sum of Products” be canonical?

I know that prenex normal form (PNF) is not canonical, and there is an example in Wikipedia showing two equivalent formulae in PNF that differ in their prefixes, but have equal matrices: $\forall x ...
1
vote
0answers
37 views

Confusion between categoricity and indiscernability

From wikipedia: Indiscernibles are objects which cannot be distinguished by any property or relation defined by a formula. Usually only first-order formulas are considered. Is this because ...
1
vote
0answers
54 views

Importance of Gödel Numbering System

How important is Gödel numbering to his incompleteness proofs, set theory, logic theory in general and proofs employing ZFC? Can we use some other numbering or 'meta' programming? How about if one ...
1
vote
0answers
44 views

Logic in Science

I am in the process of writing an essay about how disciplines interlink. In one of my paragraphs I am talking about logic, where is say how logic is a subset of mathemtics (logicism) and therefore any ...
1
vote
0answers
30 views

$\exists G \in L'. G \iff \mathtt{True}(gn(\neg G))$ in the language $L'$ with Godel numbering $gn$ and $\mathtt{True}$ predicate?

I am reading a paper Definability of Truth in Probabilistic Logic . Given a language $L$ with the Godel numbering $gn:L \to \mathbb{N}$ the authors extend it with a predicate $\mathtt{True}$ to a ...
1
vote
0answers
32 views

Some doubts regarding decidable sets

I've been working at one of the problems, related to the decidability. Let's denote $ f: \mathbb{N} \rightarrow \mathbb{N}$ as a computable increasing function, $A \subset \mathbb{N}$ is a ...
1
vote
0answers
22 views

Richardson's Theorem - Simple example

Does anyone know an actual expression $E$ built according to the conditions of Richardson's Theorem that makes the predicate $E=0$ recursively undecidable?
1
vote
0answers
62 views

Mathematical Logic Puzzles

The following are some puzzles from a Mathematical Logic course. I sat in on the first lecture but unfortunately, it didn't work with my schedule. However, I did take an problem sheet and I'm curious ...
1
vote
0answers
54 views

Logic and Generalizations

As as logic student, I often encounter the following: a situation where a formal system can't see a generalization is true, but I can. The usual case is that of $\omega$-incompleteness. It is often ...
1
vote
0answers
29 views

Contrapositive verifications

The contrapositive of: The product of an irrational number and a non-zero rational number is irrational. is: If the product of two numbers is rational, then it cannot be the case that one ...
1
vote
0answers
33 views

How to prove that a function f(x) is O(g(x)), using the definition (finding C and k)

We say that $f(x)$ is $O(g(x))$ if $$(∃C ∈ \mathbb(R)❘)(∃k ∈ \mathbb(R)❘)(∀x ∈ \mathbb(R)❘)$$ $$(x ≥ k → |f(x)| ≤ C · |g(x)|)$$ In English: We can find $C$ and $k$ so that, once we get past the “small ...
1
vote
0answers
13 views

Expressing an equal sized partition in second order logic

I would like to characterize the class of (finite) structures that can be partitioned into two disjoint sets $X,Y$ having the same cardinality, using second order logic (with usual logical connectives ...
1
vote
0answers
28 views

Algorithm to force decidability of statements using an intuitionistic series of new axioms

Consider pairs $(\Phi,n)$ where $\Phi$ is a finite set of statements in Peano arithmetic and $n$ is an integer. Say that $p'=(\Phi',n')$ is an elementary intuitionistic extension of $p=(\Phi,n)$ iff ...
1
vote
0answers
42 views

question in math logic: find the d.n.f. and c.n.f.

The question is as follows: Find the disjunctive and conjunctive normal forms of the following: $$ (A \to (B \to C)) \to ((A \to \neg C) \to (A \to \neg B)) $$ My solution is as follows, but I ...
1
vote
0answers
38 views

Relations between equations in a theory, and the number of independent equations

I have a question on equational reasoning in theories, which is made quite often in mathmeatics, and I am trying to make this more formal. So for my attempt to make this more rigouros, I choosed ...
1
vote
0answers
78 views

Is “to be married” a transitive relation?

If you define a relation on the set of people, given by $R=\{x,y : x\text{ is married with } y\}$. Is this relation transitive? I would say it depends: In the western culture: If $x$ is married with ...
1
vote
0answers
39 views

Is it true that each large cardinal which is not first order expressible has no extender characterization?

It is well-known that Reinhardt cardinal (i.e. The critical point of a non-trivial self-elementary embedding of the universe in $ZF$) is not first order expressible. Does this imply that Reinhardt ...
1
vote
0answers
31 views

Infinite strings and infinite theorems - Is there a theory on these stuffs?

I can have an alphabet $\mathcal{A}$, a set of axioms $\mathcal{X}$ which are finite strings of $\mathcal{A}$ and a set of rules $\mathcal{R}$. Every finite strings produced by applying a finite ...
1
vote
0answers
35 views

How to prove unicity in a disjunction of $n$ propositions

Let's suppose I have the propositions $\varphi_1, \varphi_2,...,\varphi_n$ and I want to prove that there happens exactly one of them. How do you do it? To do it the hard way I guess we first need to ...
1
vote
0answers
90 views

A symbolic logic problem generator, or at least a huge ready-made collection?

I am an amateur student of formal logic, and I was wondering other Gensler's LogiCola program, is there anything out there that produces logic proof problems? For example, the LogiCola program I am ...
1
vote
0answers
29 views

How do I know that min-term can't be combined any further?

I'm trying to learn (and implement) Quine-McCluskey algorithm for boolean function minimalisation. I'm learning the algorithm from wikipedia example. From that I understood the following: Take all ...
1
vote
0answers
50 views

Predicate logic. Check if I have done this correctly

I need someone to verify if I have translated a sentence into predicate logic correctly. Given predicates: Empty(x) : the list x is empty Sorted(x) : the list x is sorted in ascending (not ...
1
vote
0answers
48 views

Ordinal arithmetic and functions

I have two function $G$ and $F$ defined on ordinals and I know that $$G(\alpha +\omega )\subseteq F(\gamma +\alpha+\omega)$$ when $G(\alpha)\subseteq F(\gamma)$ and $\alpha$ is a limit ordinal. I ...
1
vote
0answers
47 views

Give complete derivation in natural deduction - My approach

Give a complete derivation in natural deduction of the following formula: $$((\varphi \rightarrow \psi) \rightarrow \psi) \leftrightarrow (\varphi \lor \psi)$$ My derivation I did the right ...
1
vote
0answers
160 views

Convert from sum of products to product of sums (Boolean algebra)

I had to simplify a boolean expression with a k-map then put it into a NOR-gate implementation circuit. I haven't made the circuit yet, but here is the work I've done: Original function: $$F(w, x, ...
1
vote
0answers
48 views

Questions on logic behind “proof by contradiction”

I'm trying to understand the logic behind "proof by contradiction" and hoping that I can clear up a few things in this post. First of all, suppose I have a proposition $P$ and from this I can imply ...
1
vote
0answers
110 views

Types realized in ultrapowers consisting of definable functions

Let $\mathcal{M}$ be a nonstandard model of arithmetic and let $M$ be its universe. Let $U$ be a nonprincipal ultrafilter over $M$ and let $\mathcal{N}$ be the ultrapower $\mathcal{M}^M / U$. Let $F$ ...
1
vote
0answers
33 views

Definition of decidable sentence

Let $P(n)$ is a sentence which mentions natural number $n \in \mathbb{n}$ For example, "$n > 5$" or "There is no $n$ such that $3^n+4^n=5^n$ " can be $P(n)$. I want to define a set A as a set ...
1
vote
0answers
59 views

Is a sentence in $\Pi_1$ true given $Q \vdash \lnot\varphi$?

If $Q \vdash \lnot\varphi$ (Q is the Robinson arithmetic), and if I assume that $\varphi \in \Pi_1$; Can I say that $\varphi$ is a true sentence? My thoughts are that, given that Q is $\Sigma_1$- ...
1
vote
0answers
81 views

First Order Model Existence without Weak Konigs Lemma or Choice

In studying Godel's Completeness Theorem and its various related formulations like the Model Existence Theorem and the Lowenheim-Skolem Theorem there is one rather subtle point that I have not yet ...
1
vote
0answers
34 views

Types,realizing,conjunction

Define for types (finitely satisfiable maximal sets of formulas with parameters in some model $\mathcal M$) $p,q$ : $p \vDash q$ when every sequence realizing p realizes q. Why it suffices ...
1
vote
0answers
54 views

In Whitehead and Russell's PM, are homogenous relations the only ones that have relation numbers?

Given the definition of ordinal similarity: ✳151.01 $P \overline{smor} Q = \hat{S}\{ S\in 1\rightarrow 1. C‘Q=ConverseD‘S. P=S^;Q\}$ Df. $Q$ has to be homogeneous, otherwise $C‘Q$ is meaningless. ...
1
vote
0answers
76 views

Universal and Existential Quantifiers

Are there any examples of a predicate P(x ) of a variable x such that the truth value of P(x) remains invariant under exchange of the Universal Quantifier ∀ and the Existential Quantifier ∃ -thanks
1
vote
0answers
93 views

Is “There are no absolute truths” a paradox?

I was wondering if the statement: There are no absolute truths is a paradox or, rather, can be considered at face value. Also, this is just a naive guess, could this statement be ...
1
vote
0answers
40 views

When is the higher-order theory of a model categorical?

I'm interested in (classical) type theories $L$ with the following property. For $M$ any model of $L$ (in Set), let $T(M)$ be the type theory of $M$, i.e., the strongest extension of $L$ satisfied by ...
1
vote
0answers
95 views

Are there axiomatizations of first order logic or set theory defined in first order logic or set theory?

There are several axiomatizations for number theory, group theory, and other theories represented in first order logic. Further, these theories are also representable in set theory such as $\sf ZFC$ ...
1
vote
0answers
82 views

How do I read a ⊢ ab in mathematical logic?

I'm beginning to read the interesting Introduction to Mathematical Logic, by Detlovs and Podnieks, but I'm having some troubles with a few simple concepts. In an early paragraph, the following theory ...
1
vote
0answers
124 views

A Question Regarding Consistent Fragments of Naive (Ideal) Set Theory

It is well known that Naive (to some, otherwise known as Ideal) set theory, that is, the set theory generated by the axioms: (EXT) (x)(x $\in$ A iff x $\in$ B) iff A=B (COMP) ($\exists$y)(x)(x ...
1
vote
0answers
45 views

Conjunctive Normal Form representation/ First Order Logic.

in my research problem, I need to represent three types of three types of relationships between the variables x,y as the following:: " y Cooperates with x" relationship: means if there is two ...
1
vote
0answers
51 views

How to simplify this term? (KV-Diagram)

I've got the following term and preconditions: Preconditions: a <= b && x <= y The term: ...