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

pinpoint the position of devices

My question is I know the distances d1, d2 and d3, thats the only information I have access to, but am build a android app where I need to indicate the positions of where the devices that are ...
1
vote
1answer
33 views

How to represent a function that says “send least element to least element and next to next” using a first order formula?

Suppose that $A$ is a finite set. $<_1$ and $<_2$ are two well-orderings on $A$. Suppose that I want to find a formula that repesents the function $F$ that says " send least element in ordering ...
4
votes
3answers
291 views

What is the mistake in this proof?

During a long night without sleep I managed to come up with a proof for a statement I know is false, and for the life of me I cannot figure out what I did wrong. Where is my mistake? Theorem: Let ...
2
votes
2answers
63 views

elementary substructure in a satureted model

Suppose you have a saturated model N of a complete theory T without finite models. How is it possibile to construct a proper saturated elementary substructure of N of the same cardinality of N ?
2
votes
1answer
24 views

How to correctly draw logic formation trees?

I had an exam on Logic and came across a question which asked me to draw the logic formation tree for the following: $$\exists xP(x,x) \lor Q(x) \land \neg \forall y R(x) \to x = y$$ The formula was ...
0
votes
1answer
29 views

Intuition of the function defined in first order logic

According to first-order logic, $\models_{\mu} \forall x \phi [s]$ if and only if for every $d \in |\mu|$, we have $\models_{\mu} \phi [s(x|d)]$, where $$ s(x|d) = \left\{ \begin{array}{lr} ...
1
vote
2answers
35 views

analytical ability and logical reasoning

There are $6561$ balls out of which $1$ is heavy. Find the minimum number of times the balls have to be weighed for finding out the heavy ball. How can I solve this step by step?
0
votes
1answer
23 views

Prove the following logical implications

Prove the following logical implications: (a) $\forall v_1 Qv_1\models Qv_1$ (b)$Qv_1\models \forall v_1 Qv_1$ The two questions are extracted from the book 'A Mathematical Introduction to Logic' ...
0
votes
2answers
27 views

Truth Value for Quantifier

What would be the truth value for the following two quantifiers if n and m are both integers? I have trouble proving each of these statements. I appreciate any help you can provide! a)   ...
2
votes
1answer
113 views

I need help understanding Frege's definition of number

I have really been trying to understand Frege's definition of a number or at least gain a strong intuition of it. However, my attempts have not been fruitful. If someone could help me it would be much ...
2
votes
1answer
73 views

The definition of the $false$ truth value

In "Topoi: The Categorial Analysis of Logic" by R. Goldblatt the $false: 1 \to \Omega$ truth value is defined as the characteristic arrow of the arrow $0_1: 0 \to 1$. This definition requires that ...
0
votes
1answer
27 views

Let $M,N$ be structures with relation $E$. $E^N$ and $E^M$ are equivalence relations, find sufficient and necessary condition for isomorphism

Let there be signature $S=\{E\}, n_E=2$, and let $M,N$ be S-structures. $E^N$ and $E^M$ are equivalence relations, find a sufficient and necessary condition for $M$ and $N$ being isomorphic. I ...
0
votes
1answer
18 views

Predicate Logic - Translations

I'm having a hard time translating logic statements into english because most of the time I don't know how to translate a pattern I have not seen before: There are two relations where $lecturer(x)$ ...
1
vote
3answers
65 views

Are there infinite sequences not reproducible by finite algorithms?

Let me know if this is a repeat question. I was thinking that sequence of integers we deal with (e.g., the digits of $\pi$, the prime numbers, the Fibonacci numbers, pseudorandom numbers) seem to be ...
0
votes
0answers
98 views

Does removing the (1) in $\Phi{(1)}$ affect the proof that $ K_0 \leq_m K$ or not?

The fragment below from Martin Davis' book shows $ K_0 \leq_m K$ and also proves $ K_0 \leq_1 K $. My question is if we remove the $(1)$ of $ \Phi^{(1)}$ in the definition of $Y$ (i.e fifth line in ...
2
votes
0answers
21 views

Structure for first order language

Suppose our first order language has two binary function symbols $f,g$ and a constant symbol $c$. Let the structure $\mu$ be defined as $|\mu|=\{ 0,1,2,3 \}$, $f^{\mu}$ is addition modulo $4$, ...
3
votes
1answer
43 views

How to prove $(\forall x,y\in\mathbb{Z})(5\nmid xy\to(5\nmid x\land 5\nmid y))$

Question: Prove $x,y\in\mathbb{Z},\Bigl((5\nmid xy)\to(5\nmid x\land 5\nmid y)\Bigr)$ where $\forall a,b\in\mathbb{Z},\bigl((a\nmid b)\leftrightarrow(\forall k\in\mathbb{Z},b\neq ak)\bigr)$ and ...
1
vote
2answers
46 views

Predicate Logic and Calculus

Question of the week came up in my schools logic club but there is not much information to it. Here is the question: Show that $$ \exists x\,[R(x)\wedge \lnot Q(x)],\ \forall x\,[P(x)\to Q(x)],\, ...
0
votes
1answer
42 views

Predicate Calculus - Resolution

A question came up at the our schools logic club this week which involves using resolution to prove an argument in predicate calculus. I am slightly aware of how to find prenex normal forms but to ...
1
vote
1answer
49 views

Defining integer sum without using infinite sets

In ZFC minus infinity (let us call this system $T$), one can still define ordinals, and then define integers as ordinals all of whose members are zero or successor ordinals. Combining the power set ...
4
votes
1answer
87 views

Integer induction without infinity

In ZFC minus infinity (let us call this T), one can still define ordinals, and then define integers as ordinals all of whose members are zero or successor ordinals. I am looking for a formula $\psi$ ...
1
vote
1answer
62 views

Is there a single logic symbol for “implies the negation of”?

Is there a single logic symbol for "implies the negation of"? (I came up with this question when studying English grammar, on realising that such a symbol when reversed and itself negated could be ...
1
vote
1answer
60 views

Counterexample to Fraissé's Theorem for infinite signature

Let S be a finite signature and $\mathfrak{A}, \mathfrak{B}$ S-structures. Fraissé's Theorem states: $$\mathfrak{A} \equiv \mathfrak{B} \Leftrightarrow\mathfrak{A} \cong_f \mathfrak{B}$$ Where ...
2
votes
1answer
73 views

Why does a nontrivial $V \to V$ have a critical point?

Let $V$ denote the von Neumann universe, and let $j: V \to V$ be a nontrivial (non-identity) elementary embedding. The critical point is the smallest $\kappa$ such that $j(\kappa) > \kappa$. The ...
1
vote
2answers
60 views

Why is the Generalization Axiom considered a Pure Axiom?

If $\varphi$ is a formula in a first order language $\mathcal{L}$ and $x$ is a variable that is not free in $\varphi$, then the following is a pure axiom $$\varphi \to \forall x\varphi$$ The ...
2
votes
1answer
60 views

A Characterization of Categories with a Conservative Forgetful Functor to SET

Examples of categories over $\bf{Set}$ such that the forgetful functor is conservative include the "algebraic" categories of groups, rings, modules, monoids, etc., but does not include the ...
1
vote
1answer
49 views

Prove validity of argument

I am trying to prove the validity of the following argument: (p $\rightarrow$ q) $\land$ (r $\rightarrow$ s) p $\lor$ r Therefore: q $\lor$ s I am stuck pretty early on. I removed the ...
3
votes
2answers
81 views

Predicate calculus (formal deduction vs resolution) [closed]

I am part of the logic club at my school and the question of the week was; Use formal deduction for predicate calculus to show that the following argument is valid. State each rule you use. Premise ...
2
votes
1answer
40 views

How to computably reduce the number of colors in (infinite) Ramsey's theorem

Suppose we have an "oracle" that gives a homogeneous set for a 2-coloring $\hat c : [\omega]^2 \rightarrow 2$ of pairs of integers. Using this oracle, can we "compute" a homogeneous set for a ...
1
vote
1answer
53 views

Let $\tau$ be a closed tableau. Prove that $\tau$ is not satisfiable.

Let $\tau$ be a closed tableau. Prove that $\tau$ is not satisfiable. Okay can prove this by contradiction. So we say that a tableau $\tau$ is $\textit{satisfiable}$ iff there exists an ...
0
votes
1answer
18 views

Find if relation is partial / total ordered

These are two problems of the Velleman's How to prove book in which it has been asked to find if $R$ is an partial order or/and an total order: $R1 = \{(x,y) \in A ...
0
votes
1answer
23 views

Constructing Logical Derivation

All Texans speak to anyone whom they know intimately. No Texan speaks to anyone who is not a Southerner. Therefore, Texans know only southerners intimately. (We have to use These predicates : $Tx, ...
0
votes
0answers
28 views

Can you name a set of criteria if a number of sets satisfy the criteria?

I'm trying to set out a definition that involves a function from any set that meets these criteria: $ \langle p| p\in\mathbb{R}\ \land p \geq0 \, \, \land \sum p= 1 \rangle$ (I've only used sigma ...
2
votes
1answer
58 views

Prove $\exists x(\varphi\wedge\psi)$ is $\underline{not}$ logically equivalent to $\exists x\varphi\wedge\exists x\psi$

Question: Prove for all $\mathcal{L}$-formulae $\varphi,\psi:$ $\exists x(\varphi\vee\psi)$ is logically equivalent to $\exists x\varphi\vee\exists x\psi$ Show that it is $\underline{not}$ the ...
1
vote
1answer
15 views

An effective way to find missing minterms

I've been messing with logic formulas lately and there was one thing that was often causing me headache. I'll describe it briefly. When using Quine-McClausky's algorithm for finding MDNF and MCNF, I ...
2
votes
1answer
61 views

Acyclicity of Flasque sheaves without A.C.

I say that a sheaf on a space X, is flasque if the restriction maps are surjective, that is any local section extend to a global section. Now it is a fact that if $F_1$ is flasque and if $0 \to F_1 ...
0
votes
1answer
58 views

Existence only as a result of its presupposition?

Is there an analogy in logic to the paradox that a concept comes into existence only by presupposing it as already existing?
0
votes
2answers
44 views

How can metalanguage be a formal language?

It is said metalanguage is a formal language. If this site about computer science is right (http://interactivepython.org/courselib/static/thinkcspy/GeneralIntro/FormalandNaturalLanguages.html), formal ...
1
vote
3answers
88 views

Why are $\vdash$ and $\vDash$ symbols from metalanguage?

I've read in some textbooks that $\vdash$ and $\vDash$ are symbols present only in metalanguage. From this, I infer that their use in object language is unacceptable. I would like to know why. Can't ...
0
votes
2answers
31 views

Order of logical quantifiers within a statement

I understand that the order of the quantifiers of a statement determine the truth value of statement. For example, $$\forall x \in \mathbb{R}, \exists y \in \mathbb{R}\ \text{such that}\ ...
1
vote
1answer
34 views

Meaning of at least as late in the alphabetical order

I'm working some problem in Velleman's How to prove book and is faced with a set in it which goes like this: $R1 = \{(x,y) \in A \times A \mid \text{the word $y$ occurs at least as late in ...
1
vote
1answer
81 views

direct hint to showing a formula is valid?

we know A formula is logically valid (or simply valid) if it is true in every interpretation. These formulas play a role similar to tautologies in propositional logic. which one could direct me to ...
4
votes
1answer
51 views

Show $\models(\phi\rightarrow(\psi\rightarrow\theta))\rightarrow((\phi\rightarrow\psi)\rightarrow(\phi\rightarrow\theta))$

Question: Show $\models(\phi\rightarrow(\psi\rightarrow\theta))\rightarrow((\phi\rightarrow\psi)\rightarrow(\phi\rightarrow\theta))$ Answer: (1) Let, ...
0
votes
1answer
43 views

how we can prove that argument $P_1,P_2,…,P_n $?

I ran into a one claims on LOGIC. how can add more direction or hint to me? if we have an argument $P_1,P_2,...,P_n $ such that $ n>3$ ($p_i$ is premise) why $P_1,P_2,....,P_n,P_1$ is ...
2
votes
2answers
79 views

Is there a way of making the notion of “stronger theorem” precise?

Mathematicians frequently speak of a theorem being stronger than another. But on its face, this does not make sense, since all theorems in a formal system imply each other, hence are equivalent. Is ...
0
votes
1answer
24 views

Show that there are only finitely many $\mathcal{L}$-structures with domain $D$

Question: Let $D$ be finite and non-empty, let $\mathcal{L}$ be finite. Show that there are only finitely many $\mathcal{L}$-structures with domain $D$ Answer: (1) Let $k$ be the cardinality of ...
1
vote
1answer
35 views

Quantifiers for mutually distinct variables

Okay, this is freaking me out, I'm going nuts. In a first-order condition with formula $\phi$ containing $x, y$ such as $\forall x\forall y . \phi$ I need to ensure that the second variable bound ...
2
votes
1answer
36 views

Natural deduction proofs without a premise?

How do I prove a formula without a premise? The question looks like this ⊢ (P→Q) I have started by making the assumption NOT(P→Q) to get a contradiction, and ...
1
vote
0answers
37 views

How we can prove that the logical result of a set is effectively enumerable? [duplicate]

How we can prove that the logical result of $\{(p_i \vee $~ $p_{i+1}$$) $$: i \in \mathbb{N} \}$ is effectively enumerable ? Update: as one user requests, I add my method. I use truth table for ...
0
votes
1answer
40 views

Proving tautology without using truth tables

I have a statement (P∧Q∧(R∧P⇒~Q))⇒~R that I need to prove tautology without using truth tables. I understand I'll be using inference rules. Here's what I've tried ...