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)

0
votes
1answer
23 views

List of Appointments - Show Only Available Start Times

I have a list of appointments for a day. There are 10 available appointments 15 minutes apart (I'm referring to each 15 minute appointment as a slot) and the list might look like this: ...
-1
votes
2answers
46 views

Two sentences that are in-decidable in PA but “or” connective is true

Find two sentences in PA, such that 1. $PA ⊬ \phi$ and $PA ⊬ \neg\phi$ 2. $PA ⊬ \psi$ $PA ⊬ \neg\psi$ but 3. $PA \vdash \psi \lor \phi$
0
votes
1answer
66 views

Is there a rule to justify the following logical statement?

I have to derive the following expression and reach the second one: $$\begin{gather} ( ( \forall x , Q \Rightarrow \neg P (x) ) \wedge ( \forall x, \neg Q \Rightarrow \neg P(x) ) ) \\ \iff \\ ( ...
0
votes
1answer
88 views

Proving that an infinite set is uncountable.

I've been doing some practice questions for my course and I found the following question quite difficult to understand. Prove that the following set is uncountable $B_\infty = \{ s \in B : s ...
9
votes
8answers
6k views

Prove that the union of countably many countable sets is countable.

I am doing some homework exercises and stumbled upon this question. I don't know where to start. Prove that the union of countably many countable sets is countable. Just reading it confuses me. ...
2
votes
3answers
127 views

In predicate logic, can the form of a translation of an existentially quantified sentence be used with a universally quantified sentence?

In predicate logic, can the form of a translation of an existentially quantified sentence be used with a universally quantified sentence? That's a lot of words for a simple question. But here's ...
2
votes
1answer
144 views

Set of formulas in Model Theory

I'm reading the book Model Theory by Chang and Keisler and there is one thing that always bugs me. Very frequently we have something like $\Sigma(x)$ representing the set of all formulas in a language ...
1
vote
2answers
54 views

Can I do this? $A^c - B^c$

If not how can I work with it? (A and B are sets) $A^c - B^c$ I am trying to simlify the above... $= (B-A) - (A-B) $ $= 2B - 2A $ $= B-A$ Is it safe to say that $A^c = B - A$? Furthermore is my ...
3
votes
3answers
226 views

Are universal quantified statements defined for inequalities even if the inequality is undefined?

The following universally quantified statement has an undefined inequality when $x = 1$: $∀x∈ℝ \dfrac 1{(x−1)^2}>0$ Is such a statement false or undefined?
9
votes
1answer
87 views

Is there such a thing as “coaxioms”?

Loosely speaking, category theory suggests that "equivalence relation" is dual to "subset." Anyway, since axioms correspond to subclasses of the possible models of a signature, is there some notion of ...
2
votes
2answers
46 views

There exists in predicate logic

I've got this sentence: $\exists x \forall y (U(y) \rightarrow ( y = x \vee y = root))$ where U(x) means the program is to be upgraded and root is a constant that ...
0
votes
1answer
35 views

$|x-y|<|y|/2 \Rightarrow |x|>|y|/2 ?$

Although I cannot think of any counter-examples where this fails, I cannot quite understand the intuition behind the result either. If two values are quite close to each other, then this implies that ...
1
vote
1answer
80 views

Variable numerical quantifiers

In first order logic with equality, it is easy to define numerical quantifiers such as "there exist exactly two x such that...", or "there exist at least six x such that...". I am trying to develop a ...
0
votes
2answers
134 views

Logical implication

I had asked this earlier but perhaps I could not put it precisely enough. Consider the atomic formulae $\forall xPx$ and $Pa$, and the logical axiom $\forall xPx \rightarrow Pa$. Can we define a ...
0
votes
1answer
85 views

Models and their meaning in a proof of any formula

Behind the scenes all formula $\phi$, we must define a model, M = (F, P) over a Universe, where F = set of Functions and P = set of Predicates, on a table of free variables in $\phi$ ? Ie any $\phi$ ...
1
vote
2answers
151 views

Formal proof involving existential quantifier

It is common sense that to derive a formula with existential quantifier is only necessary to prove that a formula is valid for any term , ie: $\Gamma$ , $\phi$ [t/x] $\vdash$ $\exists$x$\phi$. By ...
1
vote
1answer
141 views

Write the negation:

Write a negation of the following statement without using words of negation: A bounded real function cannot be surjective." Which is true, the statement, or its negation? Justify your answer. ...
0
votes
2answers
45 views
0
votes
1answer
131 views

Cardinality of the set of all well formed formula in propositional logic?

Here's the simple grammar for propositional logic I'm using: For all $n \in \mathbb{N}$, $P_n$ is a WFF (Well formed formula). If $\phi$ and $\psi$ are WFF's then $(\phi \rightarrow \psi)$ is a WFF. ...
1
vote
2answers
46 views

Why these are equivalent?

Situation: operator theory, spectrum of a operator. We consider this as definition: $\lambda$ is a eigenvalue if $\lambda x=Tx$ for some $x\ne 0$ but I see someone saying this: $\lambda ...
0
votes
1answer
56 views

Nested Quantifiers - Differentiating between $\forall x \forall y$, $\forall x \exists y$, and $\exists x \exists y$

I have a few questions regarding quantifiers which I'm still not clear about. 1) $\forall x \forall y (x^2 + y^2 = 9)$ I believe this is false as x and y could be 2 and results in 8. 2) $\forall x ...
2
votes
2answers
38 views

What do we call functions that return axioms / axiom schemata?

Consider the function $\mathrm{Assoc}$ defined by: $$\mathrm{Assoc}(X,*) = (\forall x,y,z \in X)((x*y)*z=x*(y*z))$$ This is a function that accepts symbols $X$ and $*$ and returns the axiom (a ...
1
vote
1answer
66 views

Find formulas for the statements

The task is: solve the following problems and justify your answers. ...
0
votes
1answer
264 views

Translate English sentences in statement logic

The task is: Give agood translationof the following puzzle into formal statement logic. ...
0
votes
1answer
91 views

Truth table to prove statements

A, B and C. When questioned A says ''If B did not do it, then it was C." B says ''A and C did it together or C did it alone". C says ''We all did it together." How would i be able to put these into ...
2
votes
1answer
70 views

Negation of $R = \exists x \in \mathbb R :\left[(x^2 = (x+1)^2)\land({x^3 \in \mathbb Z})\right]$

what is the negation of $$R = \exists x \in \mathbb R :\left[(x^2 = (x+1)^2)\land({x^3 \in \mathbb Z})\right]$$ ATTEMPT $$( \forall x \in \mathbb R )\text{ }[(x^2 \neq (x+1)^2) \lor ({x^3 \notin ...
1
vote
1answer
45 views

Which of the following expressions are formulae of statement logic?

My task is: which of the following expressions are formulae of statement logic? Justify your answer. If an expression is a formula, in which brackets are omitted, then rewrite this formula with all ...
0
votes
1answer
44 views

Write $p \rightarrow \lnot q$ in CNF form with only and ,or and brackets

Write $p \rightarrow \lnot q$ in CNF form with only and, or, and/or brackets How on earth would I even do this? Completely lost! Any help appreciated.
2
votes
3answers
84 views

First order logic. Describe that a set has more than 2 elements.

I would like to describe that a set has at least 3 elements using first order logic, would this be a valid way to do that? $\forall x\exists y\exists z(\neg(x=y)\wedge\neg(x=z)\wedge\neg(y=z))$ I ...
4
votes
1answer
192 views

Numbers permutation

Given $n$ numbers and $k$ positions I want the total number of permutations of these n numbers on these $k$ positions if repetition is allowed and if the following two arrangements are considered ...
2
votes
2answers
74 views

Translation from colloquial english(FOL)

As homework, I had to translate the following sentence into FOL: One can travel between any two Canadian cities by airplane, train, or bus. P(x) - x is a Canadian city; Q(x, y) - one can travel by ...
-1
votes
2answers
78 views

Decidability of a predicate.

I have the following problem: Let the following predicates be: $P1, P2, Q1, Q1 : R \to \{0,1\} $ . It is given that $P1 \lor P2$ and $Q1 \lor Q2$ are semidecidable and $P2 = \lnot Q2$ What can it ...
1
vote
1answer
511 views

Natural Deduction - Choosing the assumptions

I have been trying to understand how to use natural deduction rules to solve problems in logic. I understand the different rules. However, I find it the most difficult to determine what can be set as ...
0
votes
2answers
145 views

Compactness Theorem explanation

Compactness Theorem definition: If $T$ is a theory in a first-order language $L$, then $T$ has a model iff every finite subset $S$ of $T$ has a model. A number of questions regarding this ...
10
votes
1answer
194 views

Is it possible that P != NP cannot be proved?

I am probably asking a stupid question but what I gather from a layman explanation of Godel's incompleteness theorem is that it is completely possible that a true statement cannot be derived from ...
0
votes
1answer
57 views

2-type not-realised in Q

my question is the following: given the additive group of rational numbers, i.e. $Q = \langle {\mathbb Q},+,0\rangle$ and $T$ the theory of $Q$, how can I find (explicitly) a 2-type which is not ...
6
votes
2answers
118 views

Generic filters in the ground model (forcing)

In his book Set Theory (second edition), page 203, Thomas Jech writes Lemma 14.4 Let $\mathfrak{M}$ be a countable model of ZFC and $P$ be a partially ordered set. If $p\in P$, there exists a ...
4
votes
1answer
124 views

Advice regarding best-practice mathematics / categorial logic.

A good heuristic is: If it doesn't cost anything, generalize. In particular, if we have a theorem, and a proof thereof, then we ought to look for a maximal generalization of this theorem, ...
4
votes
2answers
145 views

Constructive proofs and omega-consistency

That old MSE question discusses the notion of “constructive proof”, and the answers explain that there is no one definition of what "constructive" or "non-constructive" means. Recently, I thought of ...
0
votes
1answer
116 views

Boolean formula vs boolean function.

Is there a technical difference between boolean formulas and boolean functions?
3
votes
1answer
78 views

Finitely many countable models implies decidability

Suppose $T$ is decidably axiomatizable first order theory and has no finite model. We shall focus on countable models. If $T$ has just one countable model (up to isomorphism), which means $T$ is ...
0
votes
1answer
33 views

first order definability with $<$ vs $Succ, 0$.

In first order logic formulae with just the predicate $<$ could describe more structures than first order formulaes with $Succ$ (successor predicate) and a constant $0$ such that $\forall x (\neg ...
0
votes
2answers
99 views

Why is … $A \lor ( \neg A \land B)$ … not … $A \lor ( A \lor\lnot B)\,?$

I have this expression: $$A \lor ( \neg A \land B)$$ So I transformed it to: $$ A \lor ( A \lor \neg B)$$ But my expression table says that I'm wrong! Why?
2
votes
1answer
40 views

Logic implication with first degree equation and a sentence

My sister got a great math test back but had some errors with the logic equivalences. For example: $x - 17 = 2 \iff x = 2 + 17 \iff x = 19$ Now, the teacher took some points for forgetting the last ...
1
vote
3answers
50 views

What is the opposite of this condition?

Condition: $(A=1) \land (C>1) \land (B<6)$ Opposite Condition: $(A\ne 1) \lor (C\le 1) \lor (B\ge 6)$ Is that true?
1
vote
1answer
49 views

Translating statement to first order logic

I can use the following literals: Has(Batman,x), Slow(x), Fast(x), Car(x) Batman has a fast car: Ex Car(x) ^ Fast(x) ^ Has(Batman,x) All of Batman's cars are fast: Ax Car(x) ^ Has(Batman,x) -> ...
2
votes
0answers
93 views

Cut-off Subtraction in Coq

I am new to the world of computer assistant proof programs in general, and Coq in particular. As a result, I have sought to prove some elementary results about integers as a way to … At the moment, I ...
0
votes
1answer
51 views

prove two different forms of the same uniqueness theorem are logically equivalent

One may take either of the statements below as a definition of $(\exists!x)(P_x)$, where $P_x$ is a predicate concerning the set $x$. Prove that they are logically equivalent. $$ (\exists x)(P_x) ...
3
votes
4answers
231 views

Does cardinality really have something to do with the number of elements in a infinite set?

I've seen some videos and read some texts (non-rigorous ones) that explained the concept of cardinality, and sometimes I see someone asking if there are more numbers between the reals in $[0,1]$ then ...
1
vote
2answers
209 views

Use logical Equivalence and rules of inference to prove the proposition

If $\{w\Rightarrow x,(w\Rightarrow y)\Rightarrow(z\wedge x),\neg z\}$, then conclusion is $x$. (Can you show what rules you are using to solve this problem?)