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
1answer
13 views

Number of Distinct Axiomatic Systems

This may well be a vaguely formulated question. Please bear with me and help me modify it to make it meaningful and rigorous, or show that it is hopelessly meaningless. I understand an axiomatic ...
0
votes
0answers
7 views

How do I input this Boolean Expression into a K map?

Determine the minimum SOP, sum of products expression using K-Map F(A,B,C,D,E) = (A’ + B + C’ + D + E’)(A’ + C’ + D + E )(A’ + C’ + E )AC’ Do i have to actually simplify it first by multiplying ...
0
votes
2answers
18 views

How to work with a premise containing multiple ' if 's?

Premise 1: If $A_1$ if $A_2$ ... if $A_a$, then $C_1$. Premise 2: If $B_1$ if $B_2$ ... if $B_b$, then $C_2$. $\ ----$ Conclusion: Then $C_3$ (whatever this is). Please explain in simple ...
0
votes
0answers
35 views

How does $\;$ 'B unless J' $\;$ mean: $\;$ If J, then not B $\;$?

[Source:] Edit: As a further example of the perils, here's an alternative use for "unless". See how time (as tense) can make a difference: (14) The box is empty unless John filled it. [John ...
0
votes
0answers
21 views

Vacuous Probabilities

Suppose it we have that for all $x \in X$, $\neg ( Ax \wedge Bx)$ holds. Then can we say anything about the value of $P(Ax \mid Bx \wedge x \in X)$? Can we say, for example, any of the following? ...
4
votes
2answers
44 views

Choosing a Cauchy sequence for a real

It is easy to form in ZF, for each real $a$, a "canonical" Cauchy sequence that converges to $a$. For example, one can take the sequence of finite initial segments of the decimal expansion of $a$, ...
1
vote
1answer
35 views

Axiom of choice for singletons

Let $\mathscr C \subseteq \mathscr P (\mathbb R )$ be a family of singletons, i.e.: each element of $\mathscr C$ contains exactly one real number. Let $f: \mathscr C \to \mathbb R $ be the function ...
0
votes
1answer
15 views

Example for universal sentence that is true in substructure but not in structure

I'm looking for an example for structures $\mathcal{A} \subseteq \mathcal{A'}$ and a universal sentence $\Phi$ such that $\mathcal{A} \models \Phi$ but $\mathcal{A'} \not\models \Phi$ (in ...
1
vote
1answer
26 views

What is the stone space $S_n(T)$ for a theory with infinitely many equivalence classes, each class infinite?

What is the stone space $S_n(T)$ for each $n$, for a theory $T$ with infinitely many equivalence classes, each class infinite.
2
votes
2answers
83 views

How to understand this informal description of the levels of the arithmetical hierarchy?

In my class notes I do not understand why the following statement is true, nor what it means: Informally, the lowest level in the Arithmetical Hierarchy in which $n$-ary relation $R$ is definable ...
0
votes
1answer
17 views

Proving that $B_1$ and $B_2$ doesn't have maximal element

This is one of the problem I have been solving form Velleman's How to prove book: Suppose $R$ is a partial order on $A$, $B_1 \subseteq A$, $B_2 \subseteq A$, $\forall x \in B_1 \exists y \in B_2 ...
1
vote
0answers
23 views

Proof verification for structure construction

This question is from Enderton's mathematical logic. Question 8 sec 2.5 pg 146. It says assume the language that has $\forall$ and P, where P is a two place predicate symbol. Let A be the structure ...
1
vote
1answer
23 views

Proof set theory involving instantiation

Is it okay to instantiate with the same element in universal and existential instantiation? Here follows my proof of the following theorem. Theorem If $A \subseteq B \setminus C $ and $A \not = ...
1
vote
2answers
33 views

$A\subseteq B\to C\setminus B\subseteq C\setminus A\,$ — how to prove this?

Given $A \subseteq B $. Prove for every set $C, C\setminus B \subseteq C \setminus A $. Logical Argument: Given: $\forall x, x \in A \rightarrow x \in B $ Goal: $\forall C \forall x , x\in ...
-1
votes
0answers
19 views

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

Define the set of propositional formulas using Type 2 (context-free grammar). Does anyone have an Idea?
0
votes
1answer
22 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
146 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
18 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
39 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
12 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
73 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
19 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
22 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
2answers
32 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
36 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
28 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
33 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
40 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
51 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
32 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
54 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
44 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
78 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
99 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
66 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
24 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
41 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
36 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 ...
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
108 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
101 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 [closed]

let A = {e| e codes a consistent set of sentences}. Locate A in the arithmetic hierarchy.
1
vote
1answer
30 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
32 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 [closed]

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
47 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 [closed]

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
41 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 ...