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
0answers
13 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
41 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 $$ ...
1
vote
0answers
32 views

First order logic and Second order logic: a question regarding domains

(1) I understood that in the language of first order logic quantification cannot be over sets (there are no predicate variables that can be bound by quantifiers), whereas the language of second-order ...
8
votes
4answers
934 views

What is an Empty set?

We define the term "Set" as, A set is a collection of objects. And an "Empty set" as, An empty set is a set which contains nothing. First problem I encountered: How the definition of ...
0
votes
0answers
40 views

First order logic and first order set theory

(1) I understood that in the language of first order logic quantification cannot be over sets (there are no predicate variables that can be bound by quantifiers), whereas the language of second-order ...
0
votes
1answer
37 views

Semidecidability

The set of satisfiable formulas (A formula is satisfiable if it is possible to find an interpretation (model) that makes the formula true) of FOL is a subset of the set of valid formulas (A formula is ...
4
votes
1answer
64 views

How to define multiplication in $\mathbb{Z}$ with divisibility and addition?

Q: Show that $(\mathbb{Z},|,+,0,1)$ defines multiplication in $\mathbb{Z}$. I know how to do this in $\mathbb{N}$, but I'm stuck trying to do this is $\mathbb{Z}$. The idea I have is to define lowest ...
2
votes
1answer
78 views

Use of either/or in maths

I have been using these two words for a long time, especially when representing the solutions to quadratic equations. But I am little confused. These terms are often used simultaneously, but it seems ...
2
votes
2answers
40 views

Propositional Calculus, Can someone answer the following?

Can somebody please solve the following equations: \begin{align} 1. \quad (A \rightarrow B)\land (A\rightarrow \neg B)=\lnot A \quad \quad \\ \end{align} What I have got for it so far is ...
0
votes
0answers
27 views

6 teams, 5 shifts, 5 different activities

We have to plan a sportsevent/tournament. In this event 6 teams are participating and we have 5 different activities. - Each team has to meet the other 5 teams one time - And each time must try ...
1
vote
1answer
19 views

If $Q(c) \iff \Sigma \vdash \phi[c]$, is $\lnot Q(c) \iff \Sigma \not\vdash \phi[c]$?

$Q$ is a relation as described above, $\Sigma$ is consistent, and $\phi$ is a formula with one variable. I think the relation in above holds because if $c$ does not belong in $Q$, then by the relation ...
7
votes
3answers
93 views

role of definitions in proofs

Definitions are needed to define objects and such, however I am confused as to where definitions come from. I feel that they cannot be something that we arbitrarily define because simply saying ...
1
vote
2answers
29 views

Prove that the sum of two positive real numbers is equal or greater than the square root of their product.

Trying to prove this: A and B are positive real numbers. A + B ≥ √ AB  This is what I wrote: Proof by Contradiction A + B < √ AB  (A + B)2 < AB A2 + AB ...
1
vote
1answer
45 views

Find all the automorphisms of $(\mathbb{R},<)$, the real numbers with the usual ordering

Find all the automorphisms of $(\mathbb{R},<)$, the real numbers with the usual ordering Obviously the identity mapping, $\iota : \mathbb{R} \to \mathbb{R}, \iota(r) = r$ and the mapping of ...
1
vote
3answers
45 views

Proving uncountability of $\mathbb R$ only using the complete ordered field axioms

If we define the real numbers abstractly as a complete ordered field (like described in the Wikipedia page), how can we prove that they are uncountable? In other words, using just the axioms of a ...
2
votes
3answers
54 views

Solving this logical puzzle by resolution doesn't work for me

In this document there is a logical puzzle: If the unicorn is mythical, then it is immortal. If the unicorn is not mythical, then it is a mortal mammal. If the unicorn is either immortal or a ...
4
votes
0answers
58 views

Definability in $L(\omega_1)$

I'm trying to solve problem II.6.35 in Kunen's book, which asks to prove that if $V=L$, then the set $B$ of $\beta<\omega_1$ such that $L(\beta)\models ZF-P$ and every element of $L(\beta)$ is ...
2
votes
1answer
61 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$ ...
3
votes
4answers
121 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 ...
2
votes
4answers
71 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
45 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)$
2
votes
1answer
39 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: ...
2
votes
1answer
22 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 ...
2
votes
1answer
26 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 strings $\zeta_1, \zeta_2$ and ...
2
votes
1answer
24 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
2answers
43 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 ...
1
vote
3answers
128 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 ...
1
vote
0answers
79 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
60 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
1answer
49 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
57 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 ...
6
votes
2answers
99 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 ...
-4
votes
1answer
40 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 ...
4
votes
2answers
95 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 ...
1
vote
1answer
33 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 ...
0
votes
0answers
28 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
3answers
56 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 ...
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
0answers
33 views

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

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 ...
2
votes
1answer
69 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 ...
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 ...
2
votes
1answer
47 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
1answer
43 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 ...
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 ...
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. ...
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)) \\& ...
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 ...
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
26 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? ...