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
votes
0answers
10 views

Define the set of propositional formulas using Type 2 (context-free grammar).

Define the set of propositional formulas using Type 2 (context-free grammar). Does anyone have an Idea?
0
votes
1answer
16 views

What is turing machine for $a^i b^j c^k$ where $i=j$ or $j=k$

I am trying to construct turing machine for $a^ib^jc^k$ where $i=j$ or $j=k$. Every time I come up with solution its getting fail for some other string.
2
votes
6answers
126 views

Intuition: “If P then Q” = 'Not P or Q' [on hold]

I already understand, and so ask NOT about, the Conditional Law: $P \Rightarrow Q \; \equiv \;\lnot P \vee Q$. But what's the intuition? Because I ask only for intuition, please do NOT prove formally ...
0
votes
1answer
17 views

Conditional Logic about limit points

Let $E$ be a subset of a metric space. Let $E'$ denote the set of all limit points of $E$. I know that if $E' \neq \emptyset$, then $E$ is infinite. Is this statement equivalent to if $E$ is finite, ...
-2
votes
1answer
33 views

Gödel numbers of proofs

On page 233 of Enderton's "A Mathematical Introduction to Logic", item 21. Enderton defines a function g(s): g(s) = the least d such that s is not the Gödel number of a sentence, or d is in the set ...
1
vote
0answers
11 views

Lebesgue Measurable Sets & Axiom of Determinacy

While reading some logic theory I bumped against the theorem which states that every set of reals is Lebesgue measurable, assuming the axiom of determinacy. To prove this theorem it apparently ...
0
votes
5answers
69 views

Intuition: Why is the biconditional true if both statements are false?

I already know that a false statement implies anything. Because I ask only for intuition, please do NOT prove this or use truth tables (which I already understand). Source: p 333, A Concise ...
0
votes
1answer
18 views

Rule of inference - Biconditional proposition

I'm having trouble with one of the questions given as an assignment which is to prove: $$(p\land q)\leftrightarrow(r\land s), \neg r\land q \vdash \neg p$$ I guess I should use proof by ...
0
votes
1answer
21 views

Check my logical argument for this proof.

if x is a real number $x \not =\ 1 $, then there exists y which is also a real number $ ((y+1) \div ( y-2) ) = x .$ Prove it's converse also. Logical Argument: given: $x \not = 1$ Goal: $ ...
2
votes
1answer
28 views

Set theory (containing Power Set) Need Help in a proof

I am confirming whether my proof is correct or not and need help. If $ A \subseteq 2^A , $ then $ 2^A \subseteq 2^{2^A} $ Proof: Given: $ \forall x ($ $ x\in A \rightarrow \exists S $ where $ ...
-2
votes
2answers
35 views

There's $10,000 . It needs to be distributed among 10 people using only the number 4. (4, 44, 444,44.4, ect). How do you distribute it in this way? [on hold]

There's $10,000 . It needs to be distributed among 10 people using only the number 4. (4, 44, 444,44.4, ect). How do you distribute it in this way?
0
votes
0answers
26 views

Logical Equivalence: $\exists x((P(x) \land \lnot Q(x))\Leftrightarrow R(x)) \iff (\forall xP(x)\Rightarrow \exists y(Q(y) \lor R(y)))$

I am trying to show LHS equivalent to RHS however, but I am unsure on this specific example. Any help would be appreciated. $$\exists x((P(x) \land \lnot Q(x))\Rightarrow R(x)) \iff (\forall ...
1
vote
1answer
28 views

Prove that the intersection of definable sets is definable

Hello I have a question : $F$ is a family of definable sets. Prove that the intersection of all the sets in the family is definable. ($F$ could be infinite) Definition (Definable): a set $K$ of ...
-2
votes
0answers
30 views

K is finitely definable if it has a finite support

I tried to prove that, but without a succes: Prove that K is finitely definable if and only if it has a finite support. *support of a set of assignments K is a set S that contains the atomic ...
-1
votes
2answers
87 views

'is an element of $\emptyset$' vs 'were an element of $\emptyset$'

[Source:] ... think a bit more about the seemingly obvious fact that, if A is a set, then $\emptyset$ is one of its subsets. To prove that, we need to establish the following: [$1.$] every ...
3
votes
2answers
47 views

Lindebaum's Lemma seemingly inconsistent with Gödel's incompleteness theorem?

Lindenbaum's Lemma: Any consistent first order theory $K$ has a consistent complete extension. First Incompleteness Theorem: Any effectively generated theory capable of expressing elementary ...
1
vote
0answers
30 views

Union of definable sets is a definable set [duplicate]

I tried to prove this question but without a success: Let $K_1 \text{and } K_2$ be definable sets, prove that $K_1∪K_2$ is definable. What I tried to do is to assume: $K_1=\text{Ass}(X)=\{v\mid ...
2
votes
1answer
53 views

Exercise $ 3.4.15 $ of David Marker’s “Model Theory”.

I was reading David Marker’s Model Theory and came upon the following problem in Chapter 3. Setting Let $ \mathcal{M} $ be a saturated $ \mathcal{L} $-structure. A definable subset $ X \subseteq M ...
-1
votes
0answers
42 views

How to intuit 'unless'? [duplicate]

Foreword: The following (seeking only intuition) does NOT duplicate this (which explains with formal proofs.) I already know, and so ask NOT about, the proof of: $A$ unless $B$ = $A$ if not $B$ = ...
1
vote
3answers
76 views

Is this a valid logical paradox?

In some recent cases, I have noticed some theorems are accepted to be intuitively or logically true if they themselves, as a unit, have no valid proof, but, their statements can be used to prove ...
0
votes
2answers
60 views

Union of definable sets

I tried to prove this question but without a success: Let $K_1$ and $K_2$ be definable sets, prove that $K_1\cup K_2$ is definable. What I tried to do is to assume: $K_1=Ass(X)=\{ v|v \vDash X \}$ ...
5
votes
1answer
63 views

How can the axioms (and primitives) of Tarski's axiomatization of $\Bbb R$ be independent?

While reading through this Wikipedia page about Tarski's axiomatization of the reals, a particular bit of text jumped out at me: Tarski proved these 8 axioms and 4 primitive notions independent. ...
0
votes
1answer
20 views

Sequence of indiscernibles in a theory with an equivalence relation with infinitely many equivalence classes

Let $\mathcal L$ be a language with a single binary relation $E$, and the theory $T$ where $E$ an equivalence relation with infinitely many equivalence classes, each of which is infinite. Are its ...
1
vote
1answer
37 views

Show that if $T$ is not $\aleph_0$-categorical then $T$ has a non-atomic model of size $\aleph_1$

Exactly as the title stated: Show that if $T$ is not $\aleph_0$-categorical then $T$ has a non-atomic model of size $\aleph_1$ Would like some pointers on how to proceed.
1
vote
2answers
34 views

Quick solution check for the TSP

Given a solution for the Boolean satisfiability or the Hamilton cycle problem it's obvious whether it's true or not, but how does one quickly check whether a solution for the TSP (travelling salesman ...
0
votes
0answers
49 views

Best Math to learn for logic problems?

I have a friend who can do any Math logic puzzle in a few seconds. The ones where they ask about for e.g. the one with monkey and coconuts or guys at the bar taking and giving each other change. A ...
1
vote
1answer
47 views

Find indefinable set that is included in definable set.

Find $K\subseteq \operatorname{Ass} $ and $ K'\subseteq K$ such that $K$ is definable but $K'$ is not. Definition (Definable): a set $K$ of assignments is definable if there is a set of formulas A ...
5
votes
1answer
107 views

What are numbers? [duplicate]

The title is a bit of clickbait, but I think it's justified. How did I came to ask this question In programming, many programming languages have concepts of a hierarchy of numerical types. Often ...
6
votes
2answers
100 views

Difference between proof of negation and proof by contradiction

I stumbled across this interesting article titled "Proof of negation and proof by contradiction" in which the author differentiates proof by contradiction and proof by negation and denounces an abuse ...
1
vote
1answer
70 views

I'm wodering if this statement is provable in logic $ \lnot \alpha \to \lnot \lnot \lnot \alpha ) $

I've encountered this statement in my final exam $$ \lnot \alpha \to \lnot \lnot \lnot \alpha ) $$ there was no open parenthesis and from what I know this is invalid (not a well-formed formula) so ...
-2
votes
0answers
24 views

Placing a set in the arithmetical hierarchy [on hold]

let A = {e| e codes a consistent set of sentences}. Locate A in the arithmetic hierarchy.
1
vote
0answers
27 views

Proving the principle of definition by generalized recursion using the inductive closure of an induction system

I'm working through Hinman's Fundamentals of Mathematical Logic in order to review some things, and got stuck in an exercise from section 1.2. Specifically, he asks us to prove (what he calls) the ...
1
vote
0answers
31 views

Truth value of a mathematical statement about circles?

Let $A$ be the set of circles in the plane with center $(0,0)$ and let $B$ be the set of circles in the plane with center $(-2,3)$. Furthermore, let $P(C_1,C_2)\colon C_1$ and $C_2$ have exactly one ...
0
votes
0answers
34 views

The logical basic of Galois theory [on hold]

Does Galois theory base on Peano axiom or it's already an example that we can't prove if the quintic functions can be solved only with Peano axiom(due to Gödel's incompleteness theorems) and we must ...
1
vote
1answer
46 views

What is satisfiable by a reduct of a model is satisfiable by the original model (and vice versa)?

My professor told me that any formula that is satisfiable by a reduct of a model is satisfiable by the model it is a reduct of, and vice versa (as long as the formula is interpretable on the ...
-1
votes
0answers
28 views

Unsolvability of ZF [on hold]

If ZF is consistent then ZF is unsolvable (i.e. there is no algorithm that for all formulas can say is it deducible or not). Without proof I can use representability of every solvable predicate ...
2
votes
1answer
40 views

Where does this function come from in this proof?

This is an excerpt taken from a proof: Let each $M_n(n\in\mathbb{N})$ be countable, Then there exists an injective function $f_n:M_n\rightarrow\mathbb{N}$. Now, set a function ...
0
votes
0answers
26 views

Decidability, axiomatisability and completeness

If Cn(T) is an axiomatisable and complete theory, then Cn(T) is decidable. Is it the case that if Cn(T) is decidable then it is an axiomatisable and complete theory? If this is the case, does this ...
2
votes
1answer
36 views

What's the need for a pair type $A \times B$ in Homotopy Type Theory?

I'm reading the Homotopy Type Theory book and I got confused about the following issue. The book defines a primitive $\Pi$-type as the generalization of the function type. The $\Pi$-type can be ...
3
votes
4answers
42 views

Using disjunction to prove that $A \setminus (A \setminus B) = A \cap B$

The problem is as follows: Suppose $A$ and $B$ are sets. Prove that $A \backslash (A \backslash B) = A \cap B$. I've rewritten the problem as a biconditional where $A \backslash (A \backslash B) ...
9
votes
4answers
599 views

Why is a statement “vacuously true” if the hypothesis is false, or not satisfied?

Why isn't a conditional statement said to "not apply" instead of be "vacuously true" if the hypothesis is not satisfied? That would seem more appropriate.
0
votes
0answers
39 views

Decidability of determining the definition of a function

Let's say a property is an SMT formula. Let's say a function has a property iff, with addition of the function symbol to an SMT (i.e., first-order formula over some signature) formula, that SMT ...
1
vote
2answers
38 views

Questions about mathematical arguments

I have a few questions about mathematical arguments (1) Suppose that I want to prove that if the statements $A, B, C$ hold true, then $Z$ holds. To prove this, I would assume $A,B,C$, which then ...
0
votes
1answer
42 views

What is the theorem that shows that second-order logic is the ceiling of model characterization?

I was reading this blog posting and the following claim was made: ...[T]here's tricks for making second-order logic encode any proposition in third-order logic and so on. If there's a collection ...
1
vote
1answer
41 views

Axiomatic set theory: definitions.

In his book axiomatic set theory, Supped writes: An equivalence P introducing a new n-place operation symbol O is a proper definition if and only if P is of the form ...
0
votes
0answers
22 views

Relationship between inductive reasoning and first order reasoning [on hold]

I know what is induction and tableau reasoning. I happen to see that if reasoning is done via induction, then the reasoning is not first order. Why inductive reasoning and first order reasoning are ...
1
vote
1answer
52 views

Linear Logic, what is it used for? [on hold]

I read a lot about Linear Logic recently but I failed to find any real use to the logic. I read that Yves Girard saw some kind of use in Databases but I'm not sure to understand what he meant by ...
10
votes
2answers
159 views
+50

Motive for the definition of inner product

Mathematicians pride themselves on writing proofs of propositions in an elegant way, but frequently (maybe even usually?) neglect to formally write motivations of definitions with the same elegance, ...
2
votes
0answers
23 views

A question about Goodstein's theorem

It is known that if Peano's Arithmetic (PA)-which is a first order theory-is consistent, then Goodstein's theorem is an example of a sentence of PA that can be neither proved nor disproved in PA. Is ...
0
votes
1answer
48 views

Non computational approach to this equation?

I was thinking about the following problem (not homework): Let $a,b,c,d \in {0,1,2,3,4,5,6,7,8,9}$ Find all four digit numbers $abcd$ where the two digit numbers $$ ...