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
3answers
91 views

Can we make illegitimate operations with $0$ legitimate by adding a few more axioms? [duplicate]

Just out of curiosity, can we make illegitimate operations with $0$, say, division by $0$ legitimate simply by imposing additional axioms? If so, then what consequences may follow? If the answer is ...
2
votes
4answers
95 views

Analyzing the logical form of “All married couples fight”

This is one of the example problems in Velleman's How to Prove book: Analyze the logical forms of the following statements. All married couples have ...
0
votes
1answer
45 views

complements of a powerset

I have a function $Q(n)=p(\{1,\ldots,n\})\setminus\{\{\}\}$ such that it won't have the empty set in it. Note, if you are going to change out my equations for Latex, I would greatly appreciate it ...
-2
votes
1answer
138 views

Inference in First Order Logic Problem [closed]

I read one logic note by Michle Sipser from MUT. I get stuck in inference. please help me in step by step inference? By using First order logic and Resolution Rules, and Proof by contradiction from ...
3
votes
5answers
208 views

Is $'' \sum_{n = 1}^{\infty} (-1)^n \; \text{is a real number}''$ an invalid statement or a false proposition?

So we're beginning an introductory logic course and my professor is giving examples for valid statements/ propositions - meaningful statements that are either true or false but not both. So he puts ...
4
votes
1answer
210 views

Replacing the “if $x ≤ y$, then $x + z ≤ y + z$” axiom in Reals.

How can I prove that we cannot (or maybe can) replace preservation of order under addition i.e. "If $x \leq y$, then $x + z \leq y + z$ with "if $0<x$ and $0<y$ , then $0<x+y$" in axioms ...
2
votes
0answers
55 views

On the back and forth conditions for a set of partial isomorphisms

I've recently begun reading Poizat's A Course in Model Theory and already in the first pages I had some doubts. One odd (not necessarily bad) thing is that he defines notions such as isomorphism only ...
1
vote
2answers
190 views

How many undecidable statements are there in ZFC?

There are several statements known to be undecidable in ZFC, with the continuum hypothesis probably being the most "popular" one. Is it known how many undecidable statements are there in ZFC? I.e. ...
15
votes
1answer
261 views

If a first-order theory $T$ has an infinite model, does $T$ necessarily have two isomorphic models that look non-isomorphic inside a subuniverse?

Assume a proper class of inaccessibles. I find the following general question interesting: for which isomorphism classes $C$ of first-order structures sharing a common signature does there exist a ...
-1
votes
1answer
204 views

looking at the alphabet ,the letters are numbered 1-26 ,

looking at the alphabet ,the letters are numbered 1-26 , such that 1 =one=15+14+5=34 (O=15, N=14, E =5 ) 2=two=20+23+15=58 (T=20, W=23, 0=15) 3=three =56 4=four=60 ...
1
vote
1answer
89 views

Laws of equivalence needed to prove $\;q \leftrightarrow (¬p ∨ ¬q) ≡ (¬p ∧ q)\;?$

I'm not sure which laws should be applied and how I can tell for myself how to discern which laws I should use - any and all help is appreciated.
0
votes
2answers
176 views

Concluding Truth Value from Universe of Discourse

I have been working on the following problem from Velleman's How to Prove book: Are these statements true or false? The universe of discourse is the set of ...
3
votes
3answers
663 views

Idiomatic mathematical english statement for ∃x[P(x) ∧ ∀y(P(y) → y ≤ x)]

I have been working on problems from Velleman's How to Prove book and hit upon the following problem: Translate the following statements into idiomatic ...
2
votes
2answers
118 views

Exercise about truth functions in J.R.Shoenfield's “mathematical logic”

The first exercise in Joseph R. Shoenfield's "mathematical logic" is: An n-ary truth function $H$ is definable in terms of the truth functions $H_1,\dots,H_k$ if $H$ has a definition ...
3
votes
3answers
94 views

If $(A \vee B) \wedge (¬B \vee C)$ is true, then $(A \vee C)$ must be true … can I argue that?

If $(A \vee B) \wedge (¬B \vee C)$ is true, then $(A \vee C)$ must be true ... can I argue that? I don't see how I can argue that $(A \vee C)$ must be true because can't we have $(T \vee T) ...
3
votes
0answers
69 views

Manifolds of Non-Standard Dimension

Can there exists (non-trivial) manifolds of non-standard dimensions? Certainly, there do exist manifolds of dimension $n$ for any $n \in \mathbb{N}$ (as well as manifolds of countably many ...
0
votes
3answers
318 views

Blue Eyes: A Logic Puzzle, has a puzzling solution (a.k.a. What does common knowledge have to do with it?)

In Blue eyes: a logic puzzle (specifically, the follow up questions), the most common answer is that it needs to be common knowledge that someone has blue eyes for all the blue-eyed people to leave. ...
3
votes
2answers
56 views

How to prove the following using direct proof

$[(\sim p \vee q) \wedge p ] \Rightarrow q $ What should be done next in order to apply direct proof to the example above? The following process has been already done but seemingly it's incorrect: ...
0
votes
1answer
26 views

FO-axiomatizable class?

I came across this question while preparing for my logic exam. Can this class be (finitely) axiomatizable, where the class contains all structures $\mathfrak{A} = (A, <, f)$, and for no $a \in A$ ...
0
votes
2answers
68 views

Questions regarding Universal Quantifiers

The question is to show that: $$\exists x:(P(x) \implies Q(x))\qquad\equiv\qquad\forall x:P(x) \implies \exists x:Q(x)$$ First I use double negation to get to the universal quantifier since it ...
0
votes
0answers
29 views

Connection between quantifier rank and Ehrenfeucht-Fraïssé Games

"Two $\tau$-structures $\mathfrak{A}, \mathfrak{B}$ are $m$-equivalent ($\mathfrak{A} \equiv_{m} \mathfrak{B}$) when... $\mathfrak{A} \models \psi$ iff $\mathfrak{B} \models \psi $ for all ...
3
votes
2answers
78 views

Proving $\vdash \exists x (x=c)$ for each term $c$.

I wish to prove that $\vdash \exists x (x=c)$ for each term $c$. It seems quite obvious that this would be the case, for $c$ is such an $x$, but creating a formal proof of this is escaping me. ...
0
votes
2answers
107 views

Understanding logical form of “Nobody in the calculus class is smarter than everybody in the discrete math class”

I'm self studying How to Prove book and have been working out the following problem in which I have to analyze it to logical form: Nobody in the calculus class ...
1
vote
2answers
63 views

Proving that $\sqrt{pq} \ne (p + q)/2$ implies $p \ne q$ using the contrapositive

Prove by the contrapositive method, that if $p$ and $q$ are positive real numbers with the property that $\sqrt{pq}$ is not equal to $(p+q)/2$, then $p$ is not equal to $q$. The proof is easy enough ...
0
votes
1answer
42 views

Analyzing Logical Forms involving quantifiers

I have been solving the following problem from How to Prove book: Analyze the logical forms of the following statement: Everyone likes Mary, except Mary ...
-2
votes
2answers
88 views

What's wrong with this induction based proof?

Claim: $\forall x \in \mathbb{R^+} ,$ $ x^n=1 $ $where$ $ n\in \mathbb{N}$ Proof by induction on n: Basis step: $\forall x \in \mathbb{R^+} ,$ $ x^0=1 $ Induction Step: Let this holds for all ...
5
votes
1answer
114 views

How much maths can we do in NF(U)?

I have recently become interested in non-standard set theories, particularly in NF and NFU and have been reading some things here and there. Of course, I don't know much about it and I'm still trying ...
1
vote
3answers
130 views

How and why can a true statement *never* imply something false?

The premise of 'proof by contradiction' is that a true statement can never imply a false statement. In my lectures (intro to logic), this has been brushed aside as 'obvious', but is there a formal ...
2
votes
1answer
139 views

Are there any “obviously” true propositions in number theory?

After all efforts spent on wrong proofs of famous number theory conjectures and theorems like Goldbach's or Fermat's last theorem, could one find some simple statements (might be correct ones) whose ...
2
votes
1answer
37 views

satisfiability in a structure implies satisfiability in a substructure?

My level: I've studied mathematics and now work through Hebert Enderton's book "An introduction to mathematical logic", second edition, in my free time. Relevant pages: 135-142, specifically 140 ...
1
vote
2answers
64 views

Validity in propositional calculus.

I have read some of the answers on similar questions but I can't really get my head around this. So, here are 2 questions I need to answer. Show using a truth table: That the inference ...
1
vote
1answer
58 views

Confusing about logic gates

Says i have this logic : X = (A & B) | ~B Which can be shorten to : X = ~(~A & B) and then : X = A | ~B so : (A & B) | ~B = A | ~B About this one, i can prove ...
5
votes
2answers
502 views

What's the difference between a logic, an internal logic (language) of a category, an internal logic of a topos and a type theory?

maybe this question doesn't make sense at all. I don't know exactly the meaning of all these concepts, except the internal language of a topos (and searching on the literature is not helping at all). ...
1
vote
2answers
45 views

Consending logic gates

Given this logic gate : A AND B OR B AND C AND (B OR C) it can be shorten as : B AND (A OR C) How do we do this ? I ...
1
vote
1answer
121 views

Please help with translation of English to first order logic

In a certain work on mereology, Alfred Tarski claims that the third following statement is deducible from the previous two: The sum of a class is defined as follows: $y$ is the sum of a class ...
1
vote
2answers
43 views

Axiomatizability of finite Isomorphic Classes

If $\mathfrak{A}$ is a finite $\tau$-structure and $\tau$ is a finite signature, is the isomorphic class $K_{\mathfrak{A}} = \{\mathfrak{B} \, | \, \mathfrak{A} \cong \mathfrak{B} \}$ ...
2
votes
1answer
77 views

Using logical OR to combine inequalities.

I have a physical system that must satisfy one of two inequalities: $x\leq y$ OR $p\leq q$ But not necessarily both simultaneously. Is there a way to combine this into a single inequality? ...
9
votes
2answers
221 views

The mother of all undecidable problems

It is usual to show that a problem P is undecidable by showing that the halting problem reduces to P. Is it the case that the halting problem is the mother of all undecidable problems in the sense ...
2
votes
1answer
90 views

Finite sets defined by First Order Logic

Why is a class of, say, finite groups $(G,\circ,e)$ not axiomatizable by FO logic (we use the compactness theorem to prove this statement) but a finite linear order $(A,<)$ on the other hand can be ...
2
votes
0answers
107 views

Relation between existential and universal quantificator in category theory

Let $\mathscr C$ be a cartesian (i.e. with finite limits) category with subobject classifier $\Omega$ and generic subobject $\tau:I\to\Omega$ (here $I$ denote the terminal object). Let $f:X\to Y$ and ...
6
votes
1answer
265 views

How much mathematics should a student of mathematical logic know?

I would like to know what areas of mathematic are directly related to mathematical logic, besides the usual courses on model theory, proof theory and computability. If you suggest only one book on ...
1
vote
1answer
70 views

Thinking logically instead of Venn diagrams

I hit upon the following identity while reading the book How to Prove: $$(A \cup B) \backslash B \subseteq A$$ Now if I solve this logically I can reduce this like this: $$ \begin{gather*} x \in (A ...
2
votes
1answer
144 views

Keisler Order: Saturated Ultrapowers

Keisler's paper "Ultraproducts which are not Saturated" states the following theorem as a corollary to a (much more) generalized theorem. However, I cannot figure out how to prove it for the specific ...
0
votes
1answer
45 views

Translating to English: $\forall x ¬(\forall y P(x, y)) \rightarrow \forall x \forall y ¬P(x, y)$

$$\forall x ¬(\forall y P(x, y)) \rightarrow \forall x \forall y ¬P(x, y)$$ I'm trying to intuitively understand this idea by thinking about it in terms of English. The second half is easy. Where P ...
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
2answers
376 views

Names of 3 input logic gates

I've tried to look this up online, I may have used the wrong terminology. This question is about the names of logic gates with three boolean inputs, and one boolean output. This is a truth table for ...
1
vote
2answers
62 views

Proof that there exist no finite axiomatic system with Compactness Theorem

Say we would like to prove that the class of all infinite groups $(G, \circ, e)$ is not finite axiomatizable by making use of the compactness theorem. We normally prove this by contradiction since we ...
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
2answers
125 views

How to prove or disprove $ \forall x \in \mathbb R, \exists y \in \mathbb R $ |x| = xy

I think that the statement is true in general considering +1 or -1 for y. How can I prove it in proper notation. Similarly I need to prove $ \exists y \in \mathbb R, \forall x \in \mathbb R st, x^2 ...
2
votes
1answer
88 views

How to find the truth values of something like this? If 3×5 = 15, then 3+5=10

The question was to find the truth values of if 3×5=15, then 3+5=10? Is the truth table corresponding to p $\implies $q ? Or is it more complicated than that? Do we have to consider something like ...