Questions about mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Questions which merely seek to apply logical or formal reasoning to other areas of mathematics should not use this tag. Consider using one of the ...

learn more… | top users | synonyms (1)

0
votes
1answer
32 views

proof by resolution?

Consider the following sentence: $$[(F \implies P)\vee(D \implies P)] \implies [(F \wedge D) \implies P]$$ I am not too familiar with how to prove by resolution, from what I found online, I need to ...
0
votes
2answers
30 views

Is it true that $X\iff Y$ is equivalent to $[X\land Y]\lor [\neg X \land \neg Y]$?

Is it true that $X\iff Y$ is equivalent to $[X\land Y]\lor [\neg X \land \neg Y]$? I don't see anything wrong with the statement. Could someone confirm?
0
votes
1answer
25 views

false implication (A => B) = 0

this is a question about logical implication. I need to prove that the implication $X \Rightarrow Y$ is verified. I use a proof by contrapositive, that is, I assume $Y = 0$ and I want to prove $X = ...
1
vote
1answer
52 views

Completeness Theorem in logic and Completeness of a theory

Completeness Theorem says: $\Gamma \models \phi \longrightarrow \Gamma \vdash \phi$ And from definition of satisfaction: $\neg(\Gamma \models \phi) \longleftrightarrow \Gamma \models \neg\phi$ Now ...
0
votes
1answer
24 views

Equivalence classes in the logical equivalence on some finite set of propositional formulas

I'm having trouble understanding the following problem: Let $S_n$ be the set of all formulas that can be built up with the atoms $\{A_1,...,A_n\}$. How many equivalence classes does the ...
0
votes
1answer
37 views

Providing motivation for the importance of the concept of a 'basis'.

In a few situations, I found myself being asked by younger students why the concepts of a basis was important. First, in the concept of linear spaces, it's easy to explain that having a basis allows ...
0
votes
0answers
22 views

expressability of finite and infinite ramsey theorems in Peano arithmetic

finite ramsey theorem: for all e,k,r natural numbers, there exists a least natural number m=R(e,r,k) so that for all sets M when cardinality of M is larger or equal m and all of the e- tuples of M are ...
0
votes
0answers
18 views

Prove set L is recursive iff there is an increasing total computable function which it's range is L.

Set L is recursive iff there is an increasing total computable function which it's range is L. The function is on $\Sigma^{*} \rightarrow \Sigma^{*}$. And by increasing it means that if a comes ...
3
votes
1answer
67 views

How can the law of the excluded middle possibly be true if we acknowledge that some logical statements are undefined?

The law of the excluded middle (LEM) states that for any proposition, either it is true or its inverse is true. In other words, there is no "middle ground" between truth and falsehood in mathematical ...
0
votes
1answer
28 views

Express GCD of two numbers by Quantifiers [closed]

How to express $\gcd(m,n)$ by means of universal and existential quantifiers?
0
votes
0answers
23 views

design a finite state automaton that divides by 2

I'm super confused in my computation class. How do you compute an FSA that divides by 2? Thank you. We can only use 1's and 0's.
0
votes
3answers
44 views

Question about universal quantifier

when I was reading a paper about the universal quantifier, I met this equation, says we can do conversions like the following: A -> B ≡ ¬A v B can anyone help ...
0
votes
0answers
31 views

Language of groups (Logic)

In the language of groups: I have to show that if $\Gamma$ is a theory such that every finite group is a model of $\Gamma$,then there is an infinite group that is a model of $\Gamma$. Show that if ...
0
votes
0answers
13 views

Exercise Henkin Theory

I'm doing some excercises from the book "The Incompleteness Phenomenom" from Goldstern and Judah. I have to do this excercise: Assume that Γ is a theory satisfying the following: Γ is a Henkin ...
1
vote
0answers
37 views

$4$ or more type $2$ implies $3$ or less type $1$

I'm having difficulties with the logic with the last part of the reformulation part of the problem below. Let $x_i$ be the the number of ships of type $i$ to purchase. For $4a:$ (the ...
0
votes
2answers
57 views

What is the meaning of the notation $A :\Leftrightarrow B$?

This is the text from my book: To define a statement $A$ so that it is true whenever the statement $B$ is true, we write $$A :\Leftrightarrow B$$ and say '$A$ is true, by definition, if $B$ is ...
3
votes
0answers
51 views

Is there a name for this principle of logic? From $\exists a P(a), !bQ(b), \forall a(P(a) \rightarrow Q(a)),$ infer $\forall a(Q(a) \rightarrow P(a))$

In set theory, we have the following: Observation 0. Let $X$ denote a set. Let $A$ and $B$ denote subsets of $X$. Then if $A$ has at least one element, $B$ has at most one element, and $A ...
1
vote
2answers
37 views

Equivalence of $\forall x P(x) \lor\forall x Q(x)$ and $\forall x (P(x) \lor Q(x))$

What are examples of predicates $P(x)$ and $Q(x)$ and domains where the above two statements are equivalent? My stab at the problem: Let the domain of discourse be all positive whole numbers, $P(x)$ ...
0
votes
1answer
28 views

Finding the expected value of recursive algorithm/pseudocode?

Need a bit of help understanding how to evaluate the expected value of a recursive algorithm, particularly in the form of code. My pick(p) method is basically a simple Bernoulli distribution, and n ...
2
votes
1answer
31 views

Painting plane with 2 colors (2 points separated by 10 cm different colors )

Can you paint a plane using 2 colours, so that any 2 points which are separated by 10 cm will have different colours?
2
votes
1answer
34 views

Q: Is the set of all binary connectives having an even number of Truth in their truth table is functionally incomplete?

Is the set $TC$ of all binary connectives having an even number of Truth values assigned to the entries of their truth table (i.e. 0, 2 or 4) is functionally incomplete? It's easy to see that the ...
0
votes
2answers
32 views

How do these two definitions of $a{\implies}b$ agree with each other?

Let $a$ and $b$ be WFFs. One definition of $a{\implies}b$ one can often encounter is "if $a$, then $b$". The other is ${\lnot}(a\,{\land}\,{\lnot}b)$. How do these two agree with each other? For ...
0
votes
0answers
12 views

Hypothesis testing/likelihood with logical operators

I am working on a problem that involves a hypothesis test of the form $H_0: A$ and $B $ tested against $H_1:$ (not $A$) or (not $B$) I'm asked to compute the likelihood ratio $\Lambda(H_0; H_1)$ ...
-2
votes
2answers
35 views

Truth table for $p \implies q$ [duplicate]

I didnt understand the truth table for $p \implies q$ (where $p$ and $q$ are statements). Can someone please explain it to me? It would be better if someone explains with an example.
0
votes
0answers
8 views

Showing a function that makes only substitutions in a sequence is primitive recursive?

Show that there is a primitive recursive function $sub(s,c,d)$ such that if $s$ codes a sequence, then $sub(s,c,d)$ is the code for the sequence that results from replacing all occurrences of $c$ ...
2
votes
1answer
43 views

Making a “larger than” function with only basic arithmetic

Is it possible to make a function using only arithmetic (no logic operators), that can return 1 if it's input x is larger than a given number a, and 0 if it's less than a? If it is, how would one ...
1
vote
0answers
36 views

Find a number a using strange computer

IN the $\#1$ slot of the computer memory there is number $a$. The computer is able to sum, multiply, divide and subtract from selected slots, writing the result in to the selected slot. It is also ...
1
vote
2answers
31 views

A semi-recursive infinite set is the range of some injective recursive total function

The wikipedia article for semi-recursive sets (formally titled "recursively enumerable sets") claims: A set S of natural numbers is called recursively enumerable if there is a partial recursive ...
0
votes
0answers
31 views

Need to prove that convex property is the intersection of an increasing and decreasing property for graph

I need to prove that any convex property for graphs can always be expressed as the intersection of an increasing property and decreasing property for graph, specifically that: $\forall A\subset ...
3
votes
1answer
17 views

Showing the number of y < x such that xRy is primitive recursive.

Suppose that $Rxy$ is a (primitive) recursive relation. Let the function $ \phi $ be defined as follows: $\phi(x)$ = the number of $y < x$ such that $Rxy$. Show that $ \phi $ is ...
2
votes
1answer
37 views

Ramsey theorems for the naturals and for general infinite sets

In reverse mathematics and in recursion theory, the infinite Ramsey theorems are usually stated in terms of coloring of $[\Bbb N]^n$. How do these (not) imply the Ramsey theorems for general infinite ...
1
vote
2answers
21 views

Does the fact that a modal operator distributive over disjunction imply that a modal operator is distributive over conjunction?

If L is an arbitrary operator on two propositions p and q: Does L(p $\vee$ q) $\Rightarrow$ Lp $\vee$ Lq imply L(p $\land$ q) $\rightarrow$ Lp $\land$ Lq?
1
vote
1answer
33 views

Model isomorphisms of a set of sentences

I have a question about models of a set of sentences $T$, specifically the following: Let $S=\{R\}$ where $R$ is a unary relation symbol. Let $T$ be the set of sentences that for each $n\geq 1$ ...
1
vote
1answer
64 views

proof that $\{\rightarrow, \land \}$ is not a complete set of logical connectives

I need some help to prove that the set $\{\rightarrow, \land \}$ of logical connectives is not a complete set. can someone help me to understand what should I do? thanks!
0
votes
2answers
27 views

Prove {$x|P(x) \land S(x)$}$ \cup $ {$x|P(x) \land \neg S(x)$} $= ${$x|P(x)$}

So far, I have only expanded the left hand side to [ {$x|P(x)$}$\cap ${$x|S(x)$} ] $\cup $ [ {$x|P(x)$ }$\cap ${$x|\neg S(x)$} ] and I'm not sure what to do next.
3
votes
1answer
61 views

Weakly Compact Cardinals are Mahlo Proof

I have a question about a corollary in Jech's set theory text which states: Corollary 17.19. Every Weakly Compact cardinal $ \kappa $ is a Mahlo cardinal, and the set of Mahlo cardinals below $ ...
2
votes
1answer
47 views

Rewriting ∃! using predicate logic expressions ( “=” excluded)

A(x) is a predicate logic formula. A is a property (predicate), x is a variable. ∃!A(x) would mean that exactly one x exists which has the property A. First thing that comes up is: ∃x( A(x) ∧ ∀y( ...
0
votes
1answer
44 views

Definability in $\Bbb N$ + $\Bbb Z$

Which elements are definable in $\Bbb N$ + $\Bbb Z$? Where an element, a, is definable if there exists a formula such that $\forall x(\phi(x) \rightarrow x = a) $. I have that all elements of $\Bbb ...
1
vote
2answers
45 views

Definability of the $<$ order relation on the natural numbers using addition. [closed]

Show that the usual order relation $<$ on the natural numbers is definable in the structure $(\mathbb{N}, +)$ with only addition. My teacher has clarified this for me and quantifiers can be used. ...
1
vote
1answer
28 views

How to arrange the following sets?

Given the set $\mathcal{P}(\mathbb{N})$ for the following order: For $A,B \in \mathcal{P}(\mathbb{N}) $ applies $A \leq_{set} B \Longleftrightarrow_{def} A = B$ or$ ~$ min$(A\triangle B)\in B$ We ...
1
vote
2answers
37 views

show that ∀ x P ( x ) ∨ ∀ x Q ( x ) is logically equivalent to ∀ x ∀ y ( P ( x ) ∨ Q ( y )) . (Domains for x and y are the same).

My attempt at a solution: Proof that $\forall xP(x)\vee\forall xQ(x)\equiv\forall x\forall y(P(x)\vee Q(y))$: Suppose $\forall xP(x)\vee\forall x Q(x)$ is true. Then $P(x)$ is true for ...
-2
votes
1answer
34 views

Vacation: how many days without rain

A boy talks about his vacation: "There were seven half-days with rain. When it rained in the morning, it was sunny in the afternoon. There were 5 mornings and 6 afternoons without rain. " What was ...
0
votes
2answers
31 views

How does this example agree with a common definition of ${\land}$?

Let ${\lnot}$, ${\in}$ and ${\implies}$ be undefined notions. Then, in the language of set theory, $p{\land}q{\iff}{\lnot}(p{\implies}{\lnot}q)$, where $p$ and $q$ are some WFFs. Let $p$ be ...
2
votes
2answers
46 views

What is $for$ and why isn't it an undefined connective in the language of predicate calculus?

Taking $\lnot$ and $\land$ as undefined notions, I have seen the following definitions $a\lor b\textit{ for }\lnot(\lnot a\land\lnot b)$ $a\implies b\textit{ for }\lnot(a\land\lnot b)$ ...
-1
votes
0answers
25 views

What are good strategies for logic proofs without premises?

I do have a specific one in mind: No premises RTP: (if A then B) or (if B then C) I know I only need to prove half of the disjunct to have a solution to the question, but I can't figure out how to ...
4
votes
3answers
65 views

Undefinability of evenness in first order logic

My question is to show there is no sentence $\psi$ in a language of first order logic without any non-logical symbols such that for every finite structure $\mathcal{A}$: $$\mathcal{A} \vDash \psi \; ...
0
votes
0answers
38 views

Is there a standard notation for coding finite sets of numbers as numbers?

Hajek and Pudlak Metamathematics of First-Order Arithmetic use the Ackermann encoding of hereditarily finite sets, but they use no notation for codes. They let the reader see from context when a ...
0
votes
2answers
34 views

propositional calculus problem, how to prove this right or wrong?

$A$$\rightarrow$$(B$ $\vee$ $C$ ) , $B$ $\rightarrow$ $C$ $\vDash$ $A$ $\rightarrow$ $D$ I think it's wrong but I have no idea how to prove.
4
votes
3answers
1k views

Why can't Axiom of Choice be proven by Rule C

Rule C is appeared in the textbook: Introduction to mathematical logic by Mendelson (Page 81 in the fourth edition). It is said "It is very common in mathematics to reason in the following way. Assume ...
0
votes
1answer
20 views

Partial correctness while loop [closed]

I have some trouble with proving the partial correctness of the following while loop: $\{x=1\}$ while $x>0$ do $x:=x+1$ od $\{x=42\}$ The while loop works against my common sense and I tried to ...