Tagged Questions

Questions about logic and 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
8 views

Robinson arithmetic and its incompleteness

Wikipedia in Italian has a sketch-of-proof that Robinson arithmetic is not complete, since commutativity of addition is undecidable. The sketch of proof creates a model that adds two elements, $a$ and ...
0
votes
0answers
49 views

Is “to be married” a transitive relation?

If you define a relation on the set of people, given by $R=\{x,y : x\text{ is married with } y\}$. Is this relation transitive? I would say it depends: In the western culture: If $x$ is married with ...
2
votes
1answer
16 views

How to prove that a set of connectives is adequate

I have this Table: $$\begin{array} {|c|} \hline A & B & A*B\\ \hline 1 & 1 & 0\\ \hline 1 & 0 & 1\\ \hline 0 & 1 & 1\\ \hline 0 & 0 & 0\\ \hline \end{array}$$ ...
2
votes
0answers
23 views

Type-definable Forcing or forcing in a non-first order setting

Roughly speaking, in set forcing the forcing notion is a set from ground model's perspective and in class forcing its a definable subset of the ground model given by solutions of some formula with ...
2
votes
0answers
18 views

Is it true that each large cardinal which is not first order expressible has no extender characterization?

It is well-known that Reinhardt cardinal (i.e. The critical point of a non-trivial self-elementary embedding of the universe in $ZF$) is not first order expressible. Does this imply that Reinhardt ...
3
votes
1answer
176 views

Is there any category theoretic proof for independence of Continuum Hypothesis?

Both of set theory and category theory could be a foundation for mathematics. Many set theoretic arguments could be translated to a category theoretic argument and vice versa. Question: Is there ...
2
votes
1answer
20 views

How can universal quantifier manipulation rules be made redundant by the generalization rule (metatheorem)?

On the Wikipedia page for Hilbert style axioms, in the "Logical axioms" section, it gives the axioms to manipulate universal quantifiers : $Q5. \forall x(\phi)\rightarrow \phi[x:=t] $ $Q6. ...
0
votes
1answer
16 views

using the elimination rule in natural deduction

Prove that $$(A ∧ B) \to C ⊢ A \to (B \to C)$$ Am I using the conjuction elimination rule correctly? Or am I assuming too much? $(A ∧ B) \to C$ (Given) $A \to C , B -> C$ (∧E 1) $A ...
2
votes
4answers
53 views

Prove $Q \rightarrow \neg(Q \rightarrow \neg P)$

I have an exercise about proving statements: Suppose that P is true. Prove that Q → ¬(Q → ¬P ) is true Givens: $P$ $Q \rightarrow \neg P$ Goal: $\neg Q$ which I simply prove ...
1
vote
3answers
49 views

If true for the general element, then true for all. What's this?

In mathematics often (always) one proves that a property is true for the general element of a set. From that, one can say that that property is true for all the elements of that set. Is that a ...
1
vote
1answer
27 views

Reference request basic logic/model theory

I'm taking a knowledge representation class and need more perspective on basic model theory. We're currently using Levesque and Brachman. Specifically, a question on the midterm was something like, ...
3
votes
1answer
21 views

Show functionally completeness property for propositional logic

Let $n>0, n\in \mathbb{Z}$ and let t,f denote true and false. For every function $$g:\{t,f \}^n \to \{t,f\} $$ There is a propositional forumala $B$, using only the connectives ...
1
vote
3answers
93 views

Proof of the Principle of mathematical Induction [duplicate]

We always use the Principe of Mathematical induction and we have two versions of it. I myself have been using it for many years. But it just came to my mind that I have never seen a proof of the ...
2
votes
3answers
55 views

How to show that something is not logically entailed?

I was just thinking about entailment and would like to know if you can show that something is NOT entailed by the premises. I know that to show $A, A → B \vdash B$, I could just provide a proof ...
1
vote
3answers
42 views

Where to put the “such that”, given multiple quantifier

Personally, I would put the "such that" (i.e. the symbol $:$ or $|$) behind any quantification. That is given an assertion $A(x,y)$, I'd write $$ \forall x\in X\exists y\in Y:A(x,y)\\ \exists x\in ...
4
votes
4answers
55 views

semantics(truth) vs formal system?

my first question is can we just define semantics in logic and not define a formal system ? why do we need a formal system to prove a proposition when for example we know the proposition is true ? ...
2
votes
3answers
49 views

What does 'any' mean in predicate calculus

I need to translate an English sentence into a well-formed predicate calculus formula. The sentence starts off as: Any tiger who chases every creature also chases itself. Does 'any' translate ...
2
votes
2answers
22 views

The existence of conjunctive/disjunctive normal forms?

I am studying propositional logic/calculus and I am currently learning about normal forms. The algorithm to construct a conjunctive/disjunctive normal form from any given formula is straightforward. I ...
2
votes
2answers
44 views

Syntax of an epsilon delta proof/why is this version incorrect [duplicate]

So we have the regular $\delta$-$\epsilon$ definition of continuity as: (1) For all $\epsilon>0$, there exists a $\delta>0$ such that, if $|x-a|<\delta$, then $|f(x)-f(a)|<\epsilon$. My ...
1
vote
1answer
21 views

proof checking - power set and family set

Decide if it is true that $P(A) \subseteq P(B) \implies \bigcup A \subseteq \bigcup B $ where $P(A), P(B)$ are power set and $A,B$ are family of sets My proof: Let $x \in P(A)$ then we have ...
1
vote
1answer
21 views

find URM program for the following function

find URM program for the following functions: a)$(m,n) \longrightarrow 2m+5n$ b)$(m,n) \longrightarrow m\times n $ answer: this program showes $(m,n) \longrightarrow m+n$ 1)$J(2,3,5)$ 2)$S(1)$ ...
1
vote
1answer
24 views

Generic in Boolean-Valued-Models

Let $M$ be a transitive $\in$-interpretation of a extension $T$ of $ZF$ in $ZF$,and let $B$ such that $$T\vdash B\in M\wedge B\text{ is a complete Boolean algebra}$$ Then, using the fact that any set ...
1
vote
1answer
38 views

Bases of complex vector spaces and the axiom of choice

In Zermelo-Fraenkel set theory $ZF$ consider the following statement defined for every field $K$: $B_K$ : Every vector space over $K$ has a basis. It is well-known that $AC \Rightarrow \forall K ...
0
votes
3answers
44 views

Recommendation on Quine's text

I'm planning to study logic seriously and I think Quine's style is fine to me so i'm going to read his book. There are two famous books by him. Namely, "Methods of logic" and "Mathematical logic". I ...
0
votes
1answer
40 views

Problem in solving a logical Equivalence

Prove or disprove the following equivalence: $$ ∀x Px \wedge ∀x Qx \Leftrightarrow ∀x ∃y ( Px \vee Qy ) $$ I've tried it, but I do not know how to solve logical equivalences involving quantifiers.
3
votes
0answers
54 views

Propositions logic and problem solving

How can a question of this nature be approached: Two avid game players Alice and Bob play three different games. They are very competitive and so would do anything within the rules of the game to ...
3
votes
1answer
45 views

What is a list of book that i need to read as a prerequisite before start reading “lectures of logic and set theory vol.1 by George Tourlakas”?

What is a list of formal textbook that i need to impose myself to read as a prerequisite before start reading a book called lectures of logic and set theory vol.1 by George Tourlakas? That book is ...
0
votes
1answer
19 views

How does the following example prove that this set of axioms for a probability field is consistent?

This is froms Kolmogorovs Foundations of probability theory. He gives the following five axioms. Let $E $ be a set and $\mathcal F $ be a set of subsets of $E $. I $\mathcal F $ is closed under ...
0
votes
1answer
36 views

Cardinality of the set of non isomorphic structures of fixed cardinality

Let $L$, be a language and $\alpha$ be a cardinal; let $\Gamma:= \{\text{set of non isomorphic $L$ structures, having cardinality $\alpha$}\}$. Prove that $\operatorname{Card}(\Gamma)\leq ...
1
vote
1answer
35 views

Set theory, operation with products, union and intersection

I need to show the following using logical connectives: $B\setminus (B \setminus A)=A \cap B $ $(A \setminus B)\cup(B\setminus A)=(A \cup B)\setminus(A \cap B)$ $(A\times B\setminus C )=(A\times ...
1
vote
2answers
27 views

logical associative expressiveness with no negation operator

Let's suppose we can only use $\wedge$ and $\vee$ operators (we have no negation operator), and by default we have associativity to the left. Is this subset of logic as expressive as the one with the ...
1
vote
1answer
33 views

Translate the following argument into propositional logic, and then assess it for validity.

This is question 9 from exercise 6.5.1 in Smith and Cusbert's Logic: The Drill. It wants a translation and test of validity for the following: Catch Billy a fish, and you will feed him for a ...
0
votes
0answers
23 views

Predicate-logic…proofs

For $x\in\mathbb{R}$, define by:$\lfloor x\rfloor\in\mathbb{Z}\land\lfloor x\rfloor \leq x \land (\forall z \in \mathbb{Z}, z \leq x \Rightarrow z \leq \lfloor x\rfloor)$. Use this definition to ...
0
votes
1answer
48 views

What is the formal way to define “class” in ZFC?

Unlike axiomatic systems deal with classes such as NBG, the term "class" is not a word in ZFC. How do I formally treat classes? Here is an example of what I'm exactly talking about. Example ...
1
vote
1answer
92 views

There are any known example of independence proofs about independence result?

(This question is inspired by deleted question, and the questioner who write the deleted question wrote new question.) It is well-known that consistency of "ZF + DC + every set of reals are Lebesgue ...
3
votes
3answers
63 views

Which texts do you recommend to study universal algebra and lattice theory?

As I'm planning to study some algebraic logic (a lot of!), I found that some knowledge of universal algebra, lattice theory and boolean algebras is a must. I wonder if you have any recommendation to ...
3
votes
1answer
33 views

Suppose a $\in \mathbb{Z}$. $a^{2}|a$ if and only if $a \in \{-1,0,1\}$

Suppose a $\in \mathbb{Z}$. Then $a^{2}|a$ if and only if $a \in \{-1,0,1\}$ So, I have started and this is what I have so far: Case 1: If $a^{2}|a$, then $a \in \{-1,0,1\}$. For the sake of ...
3
votes
2answers
45 views

Can this expression $(\neg B \land \neg D) \lor (\neg A \land B \land C) \lor (A \land C \land D)$ be further simplified?

I have assignment for computer architecture where I have to simplify a big boolean function: f(a, b, c, d) = a'b'c'd + a'bcd' + abcd + a'bcd + a'b'cd' + ab'cd' + ab'c'd' + ab'cd + a'b'c'd' ...
0
votes
2answers
45 views

How to prove $p \vee q \vdash \neg(\neg p \wedge \neg q)$?

I'm trying to complete a list of exercises but this question I still can not solve. Somebody could help me? updated: this is my conclusion 1 - $p\vee q$ Premise 2 - p Assume 3 - $\neg p\wedge\neg q$ ...
0
votes
0answers
38 views

What's the difference between a costant $k$ and $arity = 0$?

What kind of mathematical entities can have $arity = 0$ without being a constant ? Or there is a concept that generalize the concept of constant and I can't see it ? Background: I am having some ...
1
vote
2answers
86 views

Proving the non-derivability of formula using the of the kripke model

I try proving the non-derivability of $(p\to q) \to \lnot p \lor q$, using the of the kripke model. I tried using different combinations of $Wi$, but I get fail.
1
vote
1answer
29 views

How can I further simplify this $A$ + $\neg A B$?

I know there's a rule to simplify this formula $A$ + $\neg A B$, but I am not seeing it. Can someone tell me the name and how to do it?
0
votes
1answer
43 views

Show that $(A \oplus B) \oplus B = A$

I having some trouble proving $(A \oplus B)\oplus B = A$, I understand the truth table logic but can someone example to me in theory what the equation mean in set theory?
1
vote
1answer
58 views

How to better understand “ x occurs free in a wff ” in first order logic?

On page 121 of Herbert Enderton's A Mathematical Introduction to Logic, the author gives a proof of the following example : If x does not occur free in $\alpha$, then $$ \vdash ( \alpha \rightarrow ...
2
votes
2answers
102 views

Different models of ZF disagree on equality of explicit recursively enumerable sets

Assuming that ZF is consistent, are there two recursively enumerable sets defined by explicit enumerators that are the same in one model of ZF+Con(ZF) but different in another model of ZF+Con(ZF)? If ...
0
votes
1answer
31 views

Beautiful logical minimum construction

On a circle after equal intervals 25 points are located. On every point is a policeman. All policemen are numbered (from 1 to 25) in some way. Now they have to move to some other points through this ...
0
votes
0answers
20 views

prove or disprove these statements [on hold]

how can we prove or disprove these two claims? ([x] is floor of x) 1) for all x in R, for all e in R+, there exists some d in R+, for all w in R, if |x-w| < d --> |[x] - [w]| < e 2)the negation ...
2
votes
1answer
28 views

Mathematical XOR

I'm having some trouble understanding XOR in mathematical terms. I'm familiar with XOR in logical terms, meaning $A \oplus B$ meaning mutual exclusiveness, and I can easily write out the truth table ...
1
vote
0answers
28 views

Infinite strings and infinite theorems - Is there a theory on these stuffs?

I can have an alphabet $\mathcal{A}$, a set of axioms $\mathcal{X}$ which are finite strings of $\mathcal{A}$ and a set of rules $\mathcal{R}$. Every finite strings produced by applying a finite ...
0
votes
1answer
16 views

Proof Explanation: Existence of “fg-chains” Axiom of Choice implies Zorn's Lemma

I would be very glad if someone could explain the validity of a passage of this paper to me. In the proof of Lemma 3.3, "Fundamental Lemma", the notion of "fg-chains" is introduced and later on, we ...