Logic - 2018-10-24

3:58 AM

@towc: Oops I forgot you're just starting on propositional logic. Here are some exercises in propositional logic:

(1) A or ( B and C ) implies ( A or B ) and ( A or C ).
(2) ( A or B ) and ( A or C ) implies A or ( B and C ).
(3) ( A or B ) and ( B or C ) and ( C or A ) implies ( A and B ) or ( B and C ) or ( C and A ).
(4) ( A implies B ) or ( B implies C ).
(5) ( A implies B or C ) implies ( A implies B ) or ( A implies C ).

@user525966 In propositional logic, yes "proposition" and "statement" and "well-formed (propositional) formula" and "sentence" are synonyms. But people don't normally say "expression" because it's a little vague; if you say "boolean expression" then it should be clear enough.

user525966

in FOL these things are all different?

a sentence/statement/proposition not the same as an expression/predicate?

user21820

In first-order logic, standard texts use "sentence" to mean "well-formed formula with no free variables". Notice that I never used "well-formed formula" when teaching, because in my system every variable is bound (declared), so there is no need for "well-formed formulae".

user525966

even with bound variables though they're still technically wffs

formulas constructed recursively by construction rules from an alphabet

user21820

They are, but there's no need for the term wff.

user525966

what do you call them instead?

e.g. something like "10 > 5" or "x > 5" or "for all x in N, x >= 1"

user21820

4:06 AM

My system only has statements/sentences within contexts, so "x > 5" is a sentence only within a context that has declared "x".

@user525966 I also use "expression" in the standard sense (both in mathematics and programming), to refer to any expression that makes sense. So that's why a sentence/proposition is basically a boolean expression, and that's why I use "object expression" to refer to any expression that refers to an object, such as "1+2". As noted in my post, object expressions are called "terms" in standard texts.

user525966

What would your system say about scenarios like these? math.stackexchange.com/a/769338/525966

user21820

@user525966 I simply say that it's confusing. Just because standard logic texts do it a certain way does not mean it's pedagogically good. When you write "x > 5", for example, I can obviously say that it's ill-defined, because you didn't declare what type of object x is. If you say it can be anything, then it doesn't make sense, because what if x is an elephant?

In my years of teaching, I noticed that many students make very basic type errors because they were not taught to be precise in what they say, nor were they taught to type-check what they say.

user525966

is a "term" the same as a "predicate"?

user21820

No, it's just "object expression".

A predicate is a parametrized boolean expression, meaning a syntactic object that gives you a boolean expression once you fill in some parameters. In my post I use the other standard name for it: "property".

If P is a (1-parameter) property and E is an object expression, then "P(E)" is a boolean expression.

user525966

4:24 AM

I don't see the difference between a predicate and an object expression / term

user21820

@user525966 I also want to say that the argument is structurally much cleaner if expressed in Fitch-style (and without the silly use of "Alice"):

Everyone loves pizza. (1)
Everyone who loves pizza loves ice-cream. (2)
Given any person P:
	P loves pizza. [by (1)]
	Thus P loves ice-cream. [by (2)]
Therefore everyone loves ice-cream.

@user525966 "boolean expression" ≠ "object expression".

And if P is a property, then P is certainly not the same as "P(E)".

"Colourful" is a property. "I" is an object expression. "I am colourful." is a boolean expression.

(The context determines what "I" refers to, of course.)

You know programming; it's exactly the same there. A property is a function that returns a boolean. There are some inbuilt-functions (like "==") that return booleans. Those correspond to predicate-symbols. You can define other properties that are not inbuilt.

user525966

hmmm something isn't tying out for me

for example let's say we had "for all x, x + 10 > x + 5

x + 10 and x + 5 are both terms / object expressions are they not?

user21820

Yes they are. That's why you can put them both into the predicate-symbol ">" and out comes a boolean.

"x + 10 > x + 5" is a boolean expression in the context where x is a real number.

user525966

is the predicate symbol a "relation"?

user21820

@user525966 No. A relation-symbol is a predicate-symbol, but "colourful" is a 1-input predicate-symbol and I don't think you will call it a 'relation' of any sort.

user525966

4:38 AM

I don't know why I am finding these hard to separate for some reason

user21820

Separate what?

user525966

when we say "colorful" are we saying something like "bool is_colorful(object expression) {"

user21820

Yes! "I am colourful" in first-order logic syntax would be expressed as "Colourful(I)" where "Colourful" is a 1-input predicate-symbol.

user525966

we're counting the entire string "colorful" as a single "predicate symbol"?

is this similar to defining "implies" as a 2-input logical connective? Or "not" as a 1-input logical connective? or "falsum" as a 0-input logical connective?

user21820

Yes. Don't you prefer using whole words rather than single-character symbols?

user525966

4:41 AM

yes, just trying to get the lay of the language here a little :P

user21820

Sorry I assumed you were used to multi-character identifiers from programming.

user525966

I am, just making the connections here is all

was not used to referring to strings as symbols

I always sort of equated 1 character = 1 symbol

user21820

Ah. No wonder.

user525966

okay so "relation symbols" are specific forms of the more generalized "predicate symbols", where relation symbols are things like >, >=, <, <=, =, ....can't think of any more. "contains" maybe if we're getting into set theory.

user21820

Right.

user525966

4:46 AM

"function symbols" being things like +, -, x, /, which unlike relation symbols, return another term rather than a boolean expression, I think

user21820

Right.

Oct 21 at 2:57, by user21820

Basically, in any context where a variable "x" is defined, "x" itself is an object expression (because well "x" refers to an object). Also, if you have a function-symbol f and you apply it to the correct number of object expressions "t",...,"u" of the correct types, then "f(t,...,u)" is also an object expression.

user525966

I suppose we technically could still use logical connectives for returning a boolean T/F when given boolean inputs... are logical connectives considered predicate symbols as well?

user21820

By the way it's convention that we write "1+2" instead of "+(1,2)", so it's just 'too bad' we have to be able to parse both in actual mathematics.

(It's of course good, since we can have a default left-to-right parsing so that "1+2+3+4" means "((1+2)+3)+4" and don't have to write "+(+(+(1,2),3),4)".)

@user525966 The logical symbols (not, and, or, implies, iff, forall, exists, equals) are considered separate.

For "and", you can think of it as an inbuilt 2-input function from booleans to boolean. So it's not really like a predicate-symbol.

Historically, there was no notion of booleans as objects, even in classical logic, which may explain why there is a distinction.

user525966

5:11 AM

So logical connectives accept booleans and return a boolean. Relation symbols accept terms and return a boolean. Function symbols accept terms and return a term. Quantifiers... accept terms and return a boolean?

user21820

@user525966 Quantifiers cannot be viewed in the same way as the rest.

"forall x in S ( P(x) )" can be viewed as 'taking' a type S and a property P and returning a boolean, but cannot be expressed in programming notions unless S is finite.

user525966

5:30 AM

@user21820 To generalize on what a "predicate" is, would you say it can be thought of as a mapping of n-terms to a boolean?

where a "relation" is just the case where n >= 2?

n = 1 being a "property" and n = 0 being a... I don't really know, true/false constant or something

user21820

@user525966 Yes. Nobody uses 0-input predicate-symbols, for the reason you see. 0-input function-symbols are constant-symbols.

I prefer to be clearer on the distinction between expressions and the objects they refer to. "1+2" refers to 1+2. A predicate-symbol is like a mapping from object expressions to boolean expressions, because you literally use it by 'plugging in' object expressions. You can also think of a predicate-symbol as referring to some function from objects to booleans.

Just like "<" is a predicate-symbol referring to the abstract <.

But I'm sure you already got the main idea. Just being picky. =)

user525966

but isn't a "predicate symbol" different from a "predicate"?

user21820

@user525966 Yes that's why I said "like" and put "plugging in" in quotes.

I mean, there are a lot of different ways to think about it, just be consistent in whatever way you choose.

Technically, the predicate-symbol is just that one symbol, like "<", and isn't a mapping and can't do anything.

user525966

5:49 AM

So an interpretation in prop logic is an assignment of true/false to the propositional variables... in FOL, an interpretation would be an interpretation of the function symbols, predicate symbols, and all the atomic variables again? (and therefore giving recursive interpretations to all terms, formulas, etc)?

user21820

@user525966 If you have free variables, yes you have to interpret all the free variables. If you don't, such as in my system, then you only need to interpret the function/predicate-symbols.

Also, my system is similar to multi-sorted first-order logic in standard texts, and an interpretation will also need to specify what each type means. For example an interpretation of PA could specify that N is the type of all natural numbers, and 0,1,+,·,< are the usual natural number constants and operations. Another interpretation could specify that N is the collection of unary strings in some specific physical storage medium, 0 denotes "", 1 denotes "1", + denotes concatenation, and so on.

Arrow

2:06 PM

Suppose I have a set $A$ on which there are two commuting equivalence relations $U,V$. Given elements $a,b\in A$ with $a V\circ Ub$, is there some canonical way to produce an equivalence class of $U\cap V$?

user21820

@Arrow What does "commuting equivalence relations" mean at all?

Arrow

Composition of relations

In the mathematics of binary relations, the composition relations is a concept of forming a new relation S ∘ R from two given relations R and S. The composition of relations is called relative multiplication in the calculus of relations. The composition is then the relative product of the factor relations. Composition of functions is a special case of composition of relations. The words uncle and aunt indicate a compound relation: for an uncle to exist there must be a parent with a brother (or with a sister for an aunt). In algebraic logic it is said that the relation of Uncle ( xUz ) is th...

Both ways to compose $U,V$ are equal

user21820

Oh commuting under composition, okay.

Arrow

All I see is $a U c V b$ and $a V c^\prime U b$, which gives $c U\circ V c^\prime$, but I don't see any two elements that are related in $U\cap V$...

user21820

You know you can type ' for ^\prime, right? Your question is rather interesting, and certainly not "basic mathematics". =)

Arrow

2:17 PM

Sorry about the ^\prime, guess I just did it automatically here.

Are you interested in this question or should I probably ask it elsewhere?

user21820

@Arrow I presume you mean to ask for canonical representatives of U ⋂ V, rather than canonical equivalence classes, since the U ⋂ V is already an equivalence class.

Arrow

I am asking for a canonical equivalence class of $U\cap V$ somehow induced by $a,b$ along with the knowledge $a V\circ Ub$.

user21820

@Arrow I'm not sure what you mean by that. I suggest you give an explicit mathematical statement that you want to prove/disprove.

Arrow

This comment formulates an assertion. I am trying to prove this assertion for sets (the proof will carry on verbatim for other theories).

user21820

2:34 PM

@Arrow I see. I have noticed that fact about partitions before, and how it immediately yields the second isomorphism theorem for groups, rings, modules, ... But it was readily expressible without any need for category theory, and I've never bothered to learn much about category theory. So you may know more than me in that area.

Arrow

I am only looking to prove it for sets, i.e just equivalence relations on a set. I feel I am missing something very simple

user21820

If you can just state what you want as a formal mathematical statement, I may be able to help. But right now I can't really see how the comment is related to your question above.

Arrow

Let $A$ be a set and $U,V$ equivalence relations on $A$. Prove $A/(U \wedge V) \cong A/U \times_{A/(U \vee V)} A/V$.

Assuming $U\circ V=V\circ U$, that is.

user21820

2:51 PM

That's very different from how I read your original question. By asking for "canonical ...", it seemed as if you wanted some constructive proof for some notion of "constructive". Anyway now I do understand your question, and I'll ping you if I've anything to say about it. But...

← 19 messages moved from Basic Mathematics

Arrow

@user21820 hello again :)

user21820

@Arrow Hello and welcome! For all I know, someone like @LeakyNun here may already know the answer to your question, in which case I won't have to think about it. Anyway I'm going to be away, but I'll think about it again if you don't get an answer.

7 mins ago, by Arrow

Let $A$ be a set and $U,V$ equivalence relations on $A$. Prove $A/(U \wedge V) \cong A/U \times_{A/(U \vee V)} A/V$.

Arrow

Thanks!

towc

7:05 PM

@user21820 still around? Trying to prove (A and B, not A) derives (B)

found a neat way, but I need to prove de morgan laws

my proof of the de morgan laws involves proving the first thing

in my format:

∨E1
A ∨ B, ¬A ⊦ B
1. A ∨ B    by data
2. ¬A       by data
3. ¬B → A ∨ B
  1. ¬B     assume
  2. A ∨ B  by 1
4. ¬B → ¬(A ∨ B)
  1. ¬B     assume
  2. ¬A ∧ ¬B  by ∧I 2,4.1
  3. ¬(A ∨ B) by de morgan
5. B

de morgan
¬A ∧ ¬B ⊦ ¬(A ∨ B)
1. ¬A ∧ ¬B  by data
2. ¬A       by ∧E 1
3. ¬B       by ∧E 1
4. A ∨ B → ¬A ∧ ¬B
  1. A ∨ B    assume
  2. ¬A ∧ ¬B  by 1
5. A ∨ B → ¬(¬A ∧ ¬B)
  1. A ∨ B    assume
  2. ¬A ∧ ¬B → B
    1. ¬A ∧ ¬B  by 1
    2. B        by ∨E1 2,5.1
  3. ¬A ∧ ¬B → ¬B
    1. ¬A ∧ ¬B  by 1
    2. ¬B       by 3
  4. ¬(¬A ∧ ¬B) by ¬I 5.2,5.3
6. ¬(A ∨ B) by ¬I 4,5

this obviously can't fly because it's circular logic, but I can't seem to manage de-circulate it

user525966

that's a contradiction though

A and B means you can deduce A as well as B

but then A contradicts not A

towc

oh, sorry, I meant (A or B, not A) derives (B)

user525966

I think an easier way is this

towc

I'm not familiar with that syntax

user525966

7:21 PM

If you assume A, you contradict your premise not A, so from ex falso you can conclude anything, so we can say A -> B. And B -> B obviously. So from or elimination we have (A or B, A -> B, B -> B) deriving B

towc

omg duh

wow

thanks

∨E1
A ∨ B, ¬A ⊦ B
1. A ∨ B    by data
2. ¬A       by data
3. A → B
  1. A      assume
  2. ¬B → ¬A  triviial by 2
  3. ¬B → A   trivial by 3.1
  4. B
4. B → B    trivial
5. B        ∨E 1,3,4

I need way more practice

now, there's probably a simpler proof for de morgan

user525966

I did de morgans the other day

kind of long though

which form of it are you trying to prove

towc

16 mins ago, by towc

de morgan
¬A ∧ ¬B ⊦ ¬(A ∨ B)
1. ¬A ∧ ¬B  by data
2. ¬A       by ∧E 1
3. ¬B       by ∧E 1
4. A ∨ B → ¬A ∧ ¬B
  1. A ∨ B    assume
  2. ¬A ∧ ¬B  by 1
5. A ∨ B → ¬(¬A ∧ ¬B)
  1. A ∨ B    assume
  2. ¬A ∧ ¬B → B
    1. ¬A ∧ ¬B  by 1
    2. B        by ∨E1 2,5.1
  3. ¬A ∧ ¬B → ¬B
    1. ¬A ∧ ¬B  by 1
    2. ¬B       by 3
  4. ¬(¬A ∧ ¬B) by ¬I 5.2,5.3
6. ¬(A ∨ B) by ¬I 4,5

it's a proof, now that you've helped me prove ∨E1

but it's probably longer than it needs to be

user525966

I think that's the same thing I did

basically proof by contradiction showing that A ∨ B can't be true

towc

7:56 PM

I'm also stuck trying to prove A → B ⊦ ¬A ∨ B -_-

oh wait

duh, again

can use de-morgan

would look like this:

→E1
A → B ⊦ ¬A ∨ B
1. A → B        by data
2. A ∧ ¬B → B
  1. A ∧ ¬B     assume
  2. A          by ∧E 2.1
  3. B          by →E 1,2.2
3. A ∧ ¬B → ¬B
  1. A ∧ ¬B     assume
  2. ¬B         by ∧E 2.1
4. ¬(A ∧ ¬B)    by ¬I 2,3
5. ¬A ∨ B       by de-morgan 4

if you need to prove de-morgan in that too, though, it would be a huge proof. I wonder if there's a shorter version

user525966

8:50 PM

you can use proof by contradiction too, it's just long

nevermind not that long,

assume not(not A or B) and then show that if we assume A, we can arrive at a contradiction, so not A must be true. But then if not A is true, we can write not A or B, which is also a contradiction, so not not(not A or B) is true (and then you use DNE to make it not A or B)

(not-elim in the above screenshot is really the same as not-intro + DNE)

towc

10:11 PM

huh, good one

would look like this in my system:

A → B ⊦ ¬A ∨ B
1. A → B
2. ¬(¬A ∨ B) → ¬(¬A ∨ B)
  1. ¬(¬A ∨ B)  assume
  2. ¬(¬A ∨ B)  by 2.1
3. ¬(¬A ∨ B) → ¬A ∨ B
  1. ¬(¬A ∨ B)  assume
  2. A → ¬A ∨ B
    1. A        assume
    2. B        by →E 1,3.2.1
    3. ¬A ∨ B   by ∨I 3.2.2
  3. A → ¬(¬A ∨ B)
    1. A        assume
    2. ¬(¬A ∨ B)  by 3.1
  4. ¬A         by ¬I 3.2,3.3
  5. ¬A ∨ B     by ∨I 3.4
4. ¬A ∨ B       by ¬E 2,3

considerably shorter than expanding the de-morgan

need more exercises

need more patterns to get used to :P

gives me the thrill of feeling as clueless as when I first started out programming

I thought I'd never feel like this again, which was depressing

user525966

@towc You could try proving the contraposition law

(￢B → ￢A) ↔ (A → B) (both ways, hence the iff)

or try proving DNE using LEM and ex falso
or try proving LEM and ex falso using DNE

towc

10:33 PM

contraposition is trivial with de-morgan

a more interesting challenge without it

oh, not even de-morgan

but A → B ⊦ ¬A ∨ B

and ¬¬A ⊦ A

towc

11:00 PM

no joke took me over 30 minutes

¬B → ¬A ⊦ A → B
1. ¬B → ¬A    by data
2. B → (A → B)
  1. B        assume
  2. A → B
    1. A      assume
    2. B      by 2.1
3. ¬A → (A → B)
  1. ¬A       assume
  2. A → B
    1. A      assume
    2. ¬B → A
      1. ¬B   assume
      2. A    by 3.2.1
    3. ¬B → ¬A
      1. ¬B   assume
      2. ¬A   by 3.1
    4. B      by ¬E 3.2.2,3.2.3
4. ¬(B ∨ ¬A) → ¬(B ∨ ¬A)
  1. ¬(B ∨ ¬A)  assume
  2. ¬(B ∨ ¬A)  by 4.1
5. ¬(B ∨ ¬A) → (B ∨ ¬A)
  1. ¬(B ∨ ¬A)  assume
  2. ¬B → ¬A    by 1
  3. ¬B → A
    1. ¬B       assume

and there's probably a much simpler proof

also, this is only one way

I don't know how long it should normally take

in time

user525966

11:26 PM

I did it this way:

towc

11:37 PM

wow, with that method, in you do in 6 lines what I did in 35 :D

what am I missing?

maybe I focus on some routes that I think might work, instead of looking at other possible routes

your solution seems so obvious

Transcript for

♦ $Mathematics$ Logic

Transcript for

♦ Logic

♦ $Mathematics$ Logic