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
18 views

Pointclass of $\text{dom}(F)$ where $F:\omega^\omega\rightarrow\omega^\omega$ is partial recursive.

The definition I am working with: A partial function $F:\omega^\omega\rightarrow\omega^\omega$ is said to be partial recursive iff the partial function $G:\omega^\omega\times\omega\rightarrow\omega$ ...
1
vote
4answers
67 views

Proving $ \neg ( \neg \alpha \wedge \neg \neg \alpha )$

I'm training to prove this statement , but first I need to know if this statement can be proved in : 1 - both in classical and Intuitionistic logic ( in this case i need to provide demonstration in ...
4
votes
2answers
79 views

How should the relativized Kleene pointclass $\Sigma^1_1(A)$ be defined?

How should the relativized Kleene pointclass $\Sigma^1_1(A)$ be defined, when $A$ is a set of reals ($A \subset \omega^\omega$)? I assume that there is a standard definition, but I can't seem to find ...
26
votes
3answers
2k views

A transfinite epistemic logic puzzle: what numbers did Cheryl give to Albert and Bernard?

I expect that nearly everyone here at stackexchange is by now familiar with Cheryl's birthday problem, which spawned many variant problems, including a transfinite version due to Timothy Gowers. In ...
0
votes
3answers
104 views

Isn't the axiom of determinacy inconsistent with ZF? What am I overlooking?

I'm sure there's something I'm missing here; probably a naive confusion of mathematics with metamathematics. Regardless, I've come up with what looks to me like a proof that (first-order) ZF+AD is ...
2
votes
1answer
32 views

Proving that a set with a ternary logical connective is functionally incomplete (i.e. inadequate)

I am stucked at trying to prove that the set $\{\lnot ,G\}$ of logical connectives is inadequate where $G$ is a ternary connective that gives $T$ (True) if most of its arguments are $T$. For example: ...
1
vote
3answers
44 views

How to prove this tautology using equivalences?

I am trying to prove that the following is a tautology: $(A \implies (B \implies C)) \implies ((A \implies (C \implies D)) \implies (A \implies (B \implies D)))$ To make progress, I thought I'd ...
-6
votes
2answers
44 views

how is this possible please? can someon explain [on hold]

$({\sim}p \lor {\sim}q)\lor(p \lor q)=({\sim}p \lor p)\lor({\sim}q \lor q)$
0
votes
1answer
20 views

Find transitive closure of $D_r$

This is one of the problem I have been solving in Velleman's How to prove book: Find the reflexive, symmetric and transitive closures of the following ...
0
votes
1answer
653 views

Convert expression to NAND only

Endless youtube videos and reading through notes later I am yet again stuck. I have to covert the following to NAND only $$\bar{A}\cdot\bar{B}\cdot\bar{C} + A\cdot\bar{B}\cdot C + A\cdot B\cdot ...
6
votes
1answer
82 views

Propositional Logic: Proof involving only the symbols $\{\rightarrow,F \}$

I feel like I literally tried everything. I'm exhausted, and could really use some help. I was instructed to prove some logic proposition using only the symbols $\{\rightarrow,F \}$. Let me first ...
2
votes
1answer
18 views

Recursively enumerable sets and omega consistency

I have a question about a passage in Enderton's "A Mathematical Introduction to Logic", p. 241. He writes that if some formula "∃vρ" defines a recursively enumerable set, Q, in Th R, then it cannot ...
1
vote
0answers
16 views

Bound variable in a formula

Let $S$ be an arbitrary set of symbols, $x$ variable and $\Phi$ $S$-formula. Assume that $x$ occurs as bound variable in $\Phi$. I want to show: There exist words/strings $\zeta_1, \zeta_2$ and ...
1
vote
2answers
38 views

What sequent does this derivation prove?

Trying to learn sequent calculus and so I am trying to work thru some examples to get a better grip/understanding but the following question is not answered at the back of the book. I wrote my guess ...
5
votes
1answer
66 views

Is there any formula of monadic second-order logic that is only satisfied by an infinite set?

Is there any formula, of monadic second-order logic, that is only satisfied by an infinite set?
2
votes
1answer
23 views

how to prove that a relation is antisymmetric?

I have this question that I didn't know how to prove it and need your help. $R$ is a transitive and not reflexive relation on $A$. Prove that $R$ is antisymmetric. I tried to apply the definition of ...
1
vote
0answers
63 views

How can nontrivial elementary embeddings of the universe to some inner model be surjective?

Consider $\kappa$ to the least measurable cardinal, or equivalently $\kappa$ is the critical point for an elementary embedding $j:V \rightarrow M$ from the universe $V$ to an inner model $M$ (critical ...
1
vote
1answer
57 views

What does “Fixed-Point Lemma” says intuitively?

The lemma as stated in Enderton's logic says: Fixed-Point Lemma.   Given any formula $\beta$ in which only $v_1$ occurs free, we can find a sentence $\sigma$ such that $$ A_E \vdash ...
0
votes
3answers
51 views

proving logic equation in logic algebra

Im trying to prove the following logic equations are equal and am having trouble. $ab'e'f + a'b'ef + acd'e' + a'cd'e + b'c'f + b'df = acd'e' + a'cd'e + b'c'f + b'df$ $a' = \neg a$ I am pretty new ...
0
votes
1answer
39 views

Assumptions, Axioms and Premises

The following attempt of mine at defining these terms, reflects my current understanding of them: Assumption: $\quad$ A statement accepted as true without proof being required. ...
3
votes
2answers
55 views

Help in proving a tautology

I am having real trouble deriving this tautology: $\forall(x) ((x=a) \lor (x\neq a))$ It is easy to solve this by assuming the negation, unpack the negation with DeMorgan's Law, and derive from ...
4
votes
2answers
84 views

How to intuit 'only if'?

I already know, and so ask NOT about, the proof of:   $A$ only if $B$   =   $A \Longrightarrow B$. Because I ask only for intuition, please do NOT prove this or use truth tables. My problem: I try ...
-4
votes
1answer
39 views

What does a separation in lines mean? [on hold]

does putting a problem on two different lines make it two seperate problems? 1+1 1+1 Is this the same as 1+11+1 Or does the line break indicate a seperation of problems? Is there a specific ...
26
votes
3answers
969 views

Murder at Hilbert's Hotel!

I'm sorry if this is a duplicate in any way. I doubt it's an original question. Due to my ignorance, it's difficult for me to search for appropriate things. Motivation. This question is inspired by ...
1
vote
1answer
32 views

Positive and negative logical connectives

By inspecting the rules of inference for (intuitionistic) predicate calculus (or, alternatively, thinking about double negation translation), one sees that there is a certain dichotomy between two ...
2
votes
1answer
43 views

Satisfiability proof of formulas with pure literals

Let $\varphi$ be any propositional formula in negation normal form (NNF). A literal $\ell$ is pure in a formula $\varphi$, if the complement of $\ell$, $\ell^c$, does not occur in $\varphi$, where ...
0
votes
0answers
27 views

Conservative extensions and elementary equivalence- anything in common?

What is the difference between a Conservative extension, T', of a theory T, and a theory that is elementarily equivalent to T (but non-isomorphic, having, say, more elements). As far as I gathered, T' ...
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 ...
21
votes
0answers
234 views

When are two proofs “the same”?

Often, we find different proofs for certain theorems that, on the surface, seem to be very different but actually use the same fundamental ideas. For example, the topological proof of the infinitude ...
0
votes
1answer
39 views

Which mistake(s) in my argument re: representability, definability and the halting problem?

I'd like to ask for your help in showing me the (quite likely: several) flaws in my argument below, relating weak and strong representability in a formal system and the halting problem. At least ...
1
vote
2answers
2k views

From DNF to CNF

What is the most efficient way to switch from DNF to CNF?.
2
votes
1answer
68 views

Hilbert–Bernays provability conditions

Let "provability formula" ${\rm Prf}(x, y)$ written in the manner that provability operator $\square A$ defined as $\exists x\ {\rm Prf}(x, \overline A)$ satisfying Hilbert–Bernays axioms: If ZF ...
-2
votes
0answers
33 views

Textbook with full solutions: To self-learn logic for the first time [on hold]

I never studied logic before; so I'm seeking an intelligible textbook (written in simple English) with practice problems that MUST be accompanied with full detailed solutions. I read ...
1
vote
2answers
51 views

can someone explain the proof of russels paradox (barber)?

So I understand Russels paradox (barber) but I do not understand the proof, I've looked everywhere online and youtube videos but it doesn't seem to make sense. Please note, I have compensated ...
2
votes
1answer
46 views

Show For any language L two L-structures M and N are elementarily equivalent iff they are elementarily equivalent for every finite sublanguage.

Setting For any language $\mathcal L$, two $\mathcal L$-structures $\mathcal M$ and $\mathcal N$ are elementarily equivalent iff they are elementarily equivalent for every finite sublanguage. ...
8
votes
7answers
1k views

If yesterday were tomorrow, then today would be Friday.

(S) If yesterday were tomorrow, then today would be Friday. Question: What day is today? This seems to be an old puzzle, and depending on the interpretations, the answers are Wednesday or ...
0
votes
0answers
39 views

Validity of a first-order formula

How can I see (and prove) whether the given first-order formula $\varphi$ is valid or not? $\varphi = \forall x \forall y [ (r(x,y) \rightarrow (p(x) \rightarrow p(y))) \land (r(x,y) \rightarrow ...
0
votes
1answer
54 views

How to prove that a set containing G$\phi$ and G$\neg \phi$is inconsistent without completeness but with soundness.

I'm stuck with this problem... The logic is a adaptation to temporal logic from $K_4$ of modal logic. The interpretation of G$\phi$ is always true in the future (now is not included). The axioms for ...
0
votes
1answer
70 views

Which one of the following logical propositions is to be preferred?

I'm trying to update the symbolism of Giuseppe Peano's "Arithmetices Principia", to make the translation freely available. Might I ask you, which of the following might be a correct mathematical ...
1
vote
2answers
61 views

Write the negation of the following

$P(x,y)$ is the set $\{0,1,2,3,4,5\}$ $ \forall\ y\ \neg P(2,y)$ I solved this is it correct? $$\neg P(2,0) \wedge P(2,1) \wedge P(2,2) \wedge P(2,3) \wedge P(2,4) \wedge P(2,5)$$
3
votes
2answers
85 views

Determine whether or not $\neg q \to \neg (q \land (p \to \neg q))$ is a tautology

I have been trying to solve this but I got stuck at the end. $$\begin{align} \neg q \to \neg (q \land (p \to \neg q)) &\equiv \neg \neg q\lor \neg (q \land ( \neg p\lor \neg q)) \\& ...
0
votes
1answer
41 views

Given L = {<,c0,c1,…} and T3 the theory of DLO with sentence asserting co < c1 < …, Show T4 is complete with four countable models.

Let $\mathcal L_3 = \{<,c_o,c_1,\ldots\}$, and $T_3$ be the theory of DLO with sentences added stating $c_o < c_1 < \ldots$. Now let $\mathcal L_4 = \mathcal L_3 \cup \{P\}$, where $P$ is a ...
0
votes
1answer
29 views

Negating multi-layered statement regarding a formal language

I'm having trouble negating a nested statement. Let $\Sigma$ be an alphabet, $L\subseteq\Sigma^{*}$ a language and $n\in\mathbb{N}$ a natural number. For all words $x\in{}L$ with $|x|\geq{}n$ there ...
1
vote
1answer
40 views

Are the implicitly definable sets of a second-order theory the sets the second-order quantifiers range over?

I know that in a second-order setting, due to the failure of the Beth definability theorem, implicit and explicit definition come apart (i.e., there are predicates which can be implicitly, but not ...
1
vote
1answer
34 views

Am I right in this discrete mathematics question?

$A = \{0, 1, 2\}$ $B = \{x \in R\mid−1 \le x \lt 3\}$ $C = \{x \in R\mid−1 \lt x \lt 3\}$ $D = \{x \in Z\mid−1 \lt x \lt 3\}$ $E = \{x \in Z+ \mid−1 \lt x \lt 3\}$ I put that $A=D$, $A=C$, and ...
3
votes
3answers
65 views

How various properties of numbers, operations are found?

I know that how the term "property" is defined. Definition: An attribute, quality, or characteristic of something. Like one of the property of addition is "commutativity" which behaves like, ...
2
votes
3answers
44 views

Determining if a relation is reflexive, symmetric, or transitive [closed]

Let $A = \{0,1,2,3\}$ Define a relation $T$ on $A$ as follows: $T = \{(0,1),(2,3)\}$ Is $T$ reflexive? symmetric? transitive?
0
votes
3answers
25 views

Finding the equivalence classes of a relation R

Let A = {0,1,2,3,4} and define a relation R on A as follows: R = {{0,0},{0,4},{1,1},{1,3},{2,2},{3,1},{3,3},{4,0},{4,4}}. Find the distinct equivalence classes of R. How do I solve this problem? ...
0
votes
1answer
29 views

Proving Equivalence Relations On A Set

Let X be the set of all nonempty subsets of {1,2,3}. Then X = {{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}} Define a relation R on X as follows: for all S and T in X, SRT if, and only if, the least ...
1
vote
2answers
49 views

Discrete Math: Implication

If $\neg(P) \to \neg(Q) = Q \to P$ works as a Rule, then why doesn't $\neg(P) \to \neg(Q) = P \to Q$ work as a rule.