Questions about logic and 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)

2
votes
1answer
36 views

Is there a phrase to describe those objects of $\mathbf{C}$ that can be expressed as quotients of the algebra freely generated by $X$?

Let $\mathbf{C}$ denote the category of models of an algebraic theory in $\mathbf{Set}.$ Now suppose $X$ is an object of $\mathbf{Set}$. Is there a traditional phrase used to describe those objects of ...
1
vote
1answer
43 views

Model-theory : questions regarding partial isomorphism

I'm having problems with the first pages of Bruno Poizat, A Course in Model: Theory An Introduction to Contemporary Mathematical Logic (ed or 1985), specifically with local isomorphism and back- and ...
0
votes
1answer
38 views

Decidability…

I'm confused about what my book is saying here. It's a bit long so I have an image of it here (if that's okay?) https://docs.google.com/document/d/1ssy3P06dqSAhREuRbr9PNj6CYYe4_HdcITg1X4kx8PM/edit ...
1
vote
1answer
29 views

What techniques are there to search for first order sentence equivalence?

Suppose we have a first order sentences $\phi$, $\psi$, and $\chi$ such that: $\phi$ $\longleftrightarrow$ ($\psi$ $\land$ $\chi$) And $\phi$ and $\chi$ are known or fixed. How can we search for a ...
1
vote
1answer
52 views

What paradigm of automated theorem proving is appropriate for Principia Mathematica-style formalization?

I am in possession of a book, which, inspired by Russell's Principia Mathematica (PM) and logical positivism, attempts to formalize a specific domain by determining axioms and deducing theorems from ...
7
votes
1answer
144 views

Gödel's way of teaching non-standard models to Takeuti.

In Memoirs of a Proof Theorist, Gaisi Takeuti relates how Gödel taught him about nonstandard models in an "interesting" way: It went as follows. Let T be a theory with a nonstandard model. By ...
2
votes
2answers
39 views

$(\forall x\in S)P(x)\equiv \forall x(x\in S\Rightarrow P(x))$ What does it mean?

$(\forall x\in S)P(x)\equiv \forall x(x\in S\Rightarrow P(x))\\(\exists x\in S)P(x)\equiv \exists x(x\in S\wedge P(x))$ What I think it means: 1) For all $x$ in $S$, $P(x)$ holds true = for all $x$, ...
1
vote
1answer
31 views

From statement to logic

I have a problem with the modelling of the following statement in propositional logic (warning, I translated it from italian): Martha is not a singer, and she doesn't play violin or flute, but not ...
2
votes
4answers
450 views

What is the truth table for demorgan's law?

From Demorgan's law: $(A \cup B)^c = A^c \cap B^c$ I constructed the truth table as follows: $$\begin{array}{cccccc|cc} x\in A & x \in B & x \notin A & x \notin B & x \in A^c ...
0
votes
2answers
53 views

Finding boolean/logical expressions for truth table + explanation [closed]

I'm having very hard time finding boolean expressions from truth tables. I've also tried many tricks but still can't get through...think you guys can help me with this??...you'll be doing this lil ...
0
votes
1answer
21 views

Simplification of a Disjunctive Normal Form Logic Equation

So I'm fairly new to logic equations and I've been given a pretty big logic equation to simplify and just need a bump in the right direction to figure out where to go. I've been told it's going to be ...
-3
votes
2answers
53 views

check the formulas for satisfiability and validity [closed]

Could perhaps somebody explain me how to define if a formula is valid, satisfiable, or not satisfiable if ...
0
votes
1answer
53 views

particular property and completeness?

I was puzzeling with the almost standard definition of completeness: In mathematical logic and metalogic, a formal system is called complete with respect to a particular property if every formula ...
6
votes
1answer
170 views

What is semantics of “type”? Do “types” of “type theory” semantically differ from “set” of set theory?

"To be of a (certain type)" is a fundamental relationship for ontology and the computer science "ontologies" are in the core of Semantic Web (which is my interest). But I did not encounter a ...
4
votes
2answers
161 views

Simplifying a categorical proof of constructive dilemma

In axiomatic propositional calculus the following axiom schema captures constructive dilemma: $\newcommand{\lif}{\supset} \renewcommand{\land}{\&}$ \begin{equation} (a \lif c) \lif ((b \lif c) ...
1
vote
0answers
46 views

Divisibility is not definable over $\mathbb{N}$ with coprimality relation

I am asked to show that the divisibility relation "|" is not definable over $(\mathbb{N},\perp)$, where "$\perp$" is the coprimality relation. I am pretty sure that I should use the following: ...
1
vote
1answer
66 views

Show that if $L$ is countable and contains a two-place predicate symbol, there are $2^{2^{\aleph_0}}$ classes of $L$-structures closed under $\equiv$

We say that a class of structures $K$ is closed under elementary equivalence ($\equiv$) if for all $A, B$, if $A \in K$ and $A \equiv B$, then $B \in K$. How to show that if $L$ (as a set of specific ...
1
vote
1answer
46 views

Completeness theorem for intuitionistic logic

Reading from Wikipedia about intuitionistic logic, I am guessing that there is a formal proof system for intuitionistic logic. (Note: My knowledge of intuitionistic logic is almost nil). My ...
1
vote
2answers
39 views

Abelian/Isomorphic logic statement

I don't understand this logic statement. I don't think the context helps at all but I thought i'd include it anyway. $G$ is abelian and $H$ is not abelian, then $G\ncong H$, is the same as: $G$ ...
0
votes
2answers
30 views

Showing that $A \cap X = A$ for all $A$ if and only if $X = S$.

I have the following task: Let $S$ be a nonempty set. All capital letters will denote subsets of $S$. Show that $A \cap X = A$ for all $A$ if and only if $X = S$. This does not seem to true. ...
1
vote
1answer
22 views

Propositional calculus , axiom scheme independence proof

I am studying mathematical logic from Mendelson's "Introduction to mathematical logic" and have difficulty understanding the intuition behind his proof of independence of axiom schemes introduced for ...
1
vote
2answers
45 views

Derivation of Null Quantification in Logic?

I was reading page 10-8 of this: https://faculty.washington.edu/smcohen/120/Chapter10.pdf and I was wondering if the distributive qualities could be derived, e.g. $\forall x (P \lor Q(x)) ...
0
votes
0answers
20 views

Can a non-cyclic infinite proof tree with always-reachable provable nodes be used to construct a proof?

Suppose that I have a finite number of basic elements x,y,z ... and a finite number of operators +, * ... Terms X,Y,Z ... are created by combining basic elements and operators. For example, x+y, and ...
1
vote
1answer
30 views

Rules of inference: The Rules of Disjunctive Syllogism and Double Negation

I have a question about the use of Double Negation in relation to this problem I found in my textbook examples. Problem: $\;¬(r \land t) \lor u$ $\;r \land t$ Therefore, $u$. In my textbook it ...
1
vote
1answer
35 views

Can a predicate in logic operate on something undefined ? Is $P(x)$ true or false for $x$ undefined, where $P$ is a predicate?

Can a predicate in logic operate on something undefined ? Is $P(x)$ true or false for $x$ undefined, where $P$ is a predicate ? To be more concrete: Is $x \le 5$ true or false for $x$ undefined ? ...
-1
votes
1answer
72 views

Mathematical Logic Problems [closed]

True or false(and why): If T is a set of logical sentences which is logically contingent and T' so that T' $\subset$ T, then T' is also logically contingent Prove that $$\phi \lor \psi, \lnot \phi ...
0
votes
1answer
50 views

Why are there $\leq$ $2^{\operatorname{card}(\operatorname{Form}(L))}$ elementarily nonequivalent structures for $L$?

Let $L$ be a set of specific symbols and $\operatorname{Form}(S)$ be the set of all first-order formulas over $L$. Why are there $\leq$ $2^{\operatorname{card}(\operatorname{Form}(L))}$ ...
1
vote
1answer
80 views

Arrows-only implication & disjunction in $\mathbf{Set}.$

Just before the truth-arrows in a topos subsection of Goldblatt's "Topoi: A Categorial Analysis of logic," descriptions of the truth functions $\Rightarrow$ and $\smallsmile$ are given in ...
0
votes
2answers
56 views

Ordinal existence

Is there any ordinal $\alpha$ such that $\omega ^ {\omega ^ \alpha} = \alpha$? Could you please suggest me how to even try to solve this?
2
votes
1answer
21 views

Proposition Question

I am trying to translate this into propositional symbols but (for me) it's so complicated. Can someone help me figure this out. "If it rains then I will carry a sharp object and I will start laughing ...
2
votes
1answer
55 views

How to prove that $max(\aleph_{0}, card(X)) = max(\aleph_{0}, card(L(X)))$?

I struggle with the following problem. Let $X$ be a set of elementary sentences and $L(X)$ be the smallest elementary language in which we can express all the sentences from $X$. How to prove that ...
0
votes
0answers
53 views

I there a rigorous, mathematical, approach to definitions (denotations)?

In mathematical logic, a definition is treated as an abbreviation - a denotation which simplifies the discourse making it shorter. This is so much so that in a formal theory or a logic we can do ...
0
votes
1answer
38 views

How to prove this expression in mathematical logic

How to prove that the problem is a tautology, using only replacement by equivalence(s) (1. negation, 2. distribution, 3. de Morgan's laws, 4. $x\leftrightarrow y\equiv(x\rightarrow ...
1
vote
1answer
42 views

Provide the Proof for $\forall x\,\bigl ( P(x) \land Q(x)\bigr ) \leftrightarrow \forall x \,P(x) \land \forall x\, Q(x)$

Provide the Proof for $$\forall x\,\bigl ( P(x) \land Q(x)\bigr ) \leftrightarrow \forall x \,P(x) \land \forall x\, Q(x)$$ This is all i got so far: Assume $\forall x \,\bigl( P(x) \land Q(x) ...
2
votes
2answers
32 views

Logic question for a program I'm designing

I'm developing an application in ASP.NET with C# and i'm trying to figure out the best way to implement a logic statement that will stop the system from allowing another reservation to be taken if the ...
0
votes
2answers
62 views

How to express $\lnot (a < b < 0)$ or the contrapositive of this statement?

I can't seem to get the negation, $\lnot (a < b < 0)$, right. I thought I could break it into 3 parts: a < b, a < 0, b < 0, but that leaves me with a > b or a > 0 or b > 0 (greater or ...
0
votes
1answer
33 views

A Logical Equivalence?

Is $\exists y \forall x (P(y) \ \wedge (P(x) \Rightarrow (x=y)))$ the same as $\exists x \forall (y\neq x) (\neg P(y) \wedge P(x))$? I think they are, but I can't think of a way to transform from one ...
3
votes
1answer
80 views

If $\mathbb{Z}$ satisfies an identity $\eta$, then every **commutative** ring satisfies $\eta$? And related questions.

Assume all rings have unity and that ring homomorphisms preserve unity. Now by general principles, if every free object in the category of rings satisfies an identity $\eta$, then every object in the ...
1
vote
1answer
45 views

“If… then” equivalence [duplicate]

This website states that the equivalent statement to if A then B is if NOT B then NOT A This doesn't make sense. I also am a ...
0
votes
1answer
76 views

Can variables of quantification be repeated?

For example, is the following valid? $\forall x \forall x \alpha$ Is so, then how is it evaluated user the basic semantic definition?
5
votes
1answer
23 views

same variable bound by different quantifiers

In studying first-order logic, I have come across this sentence: $\exists x\, P(x)\land\exists x\, R(x)$ If there is some $x$ such that $P(x)$, and there is some $y$ such that $R(y)$, is this ...
2
votes
1answer
101 views

Cardinalities of Collections of Models

Let $T$ be a complete theory in a countable language (with only infinite models). Recall the spectrum function: $I(\aleph_\alpha,T)=$ the number of non-isomorphic models of $T$ of cardinality ...
0
votes
0answers
47 views

Two conditions, necessary and sufficient conditions.

I am currently studying for a test for a scholarship, in such a test, the following question appears (The part that I'm having trouble with in is in bold): For each of $A$ ~ $D$ in the following ...
4
votes
1answer
44 views

A model which has only one undefinable element over a language with only a finite number of symbols

I try to solve the problem 1.3.14 in Chang and Keisler's Model theory: For each $n\in\omega$, find a model $\mathfrak{A}_n$ for $\mathcal{L}$ a language with only a finite number of symbols, which ...
0
votes
1answer
69 views

Criticism on truth of Gödel sentence in standard interpretation

Mendelson in his book mentioned the Gödel sentence and argued that in standard interpretation it is true. But Peter Milne in his article (On Godel Sentences and What They Say) criticized: "But we know ...
1
vote
3answers
86 views

Defining a partial function in a formal theory

Assume we have a first-order theory $T$ of arithmetic (i.e., number theory). Suppose I wish to introduce a new function symbol $f$ in the theory, so that $f$ is a partial number function (namely, it ...
7
votes
3answers
113 views

Can $(\Bbb N,\leq)$ have an $\aleph_0$-categorical theory (in a larger language)?

One of the nicer consequences of compactness is that there is no statement in first-order logic whose content "$\leq$ is a well-order". So we can show that there are countable structure $(M,\leq)$ ...
0
votes
1answer
55 views

Truth of Godel's sentence in standard interpretation

It is siad that the Godel's sentence: g is true in the standard interpretation. But I have problem in truth of g in the standard interpretation. We proved that if theory K is consistent g is not ...
2
votes
5answers
84 views

Showing that $\lnot Q \lor (\lnot Q \land R) = \lnot Q$ without a truth table

I've done a truth table after reducing it to this and it seems to be equal to $\neg Q$: $$\lnot Q \lor (\lnot Q \land R) = \lnot Q$$ But when I try to show it without a truth table (with just ...
3
votes
2answers
92 views

Why is removing the negation worse than adding it?

Natural Deduction Rule (¬I): Natural Deduction Rule (RAA): My book [Ian Chiswell & Wilfrid Hodges, Mathematical Logic (2007)]presents these two rules and then adds: The use of (RAA) can ...