Can we construct a truth table with infinitely many variables?

[cragar]

If I had a truth table with a countably infinite number of variables. How many rows would my truth table have. For finite truth tables it is 2^n n is the number of variables.
Does this work for infinite truth tables?

 

[mathman]

It looks like you have something equivalent to all numbers between 0 and 1 in binary.

 

[cragar]

are you saying that the rows in the truth table are uncountable?
That seems weird.

 

[mathman]

are you saying that the rows in the truth table are uncountable?
That seems weird.

Weird or not - it happens to be true.

 

[cragar]

that means that we can't construct the rows of the truth table. We wouldn't be able to write them down. But how could I have a countable number of variables and and uncountable number of rows. It seems that all the possible number of combinations in my truth table should be countable.

 

[HallsofIvy]

Why does it seem that way?

 

[cragar]

Would I be able to write down the rows of the truth table? Or at least start to.
Even though I have a countable infinite number of variables. It seems I should be able to compare all these variables by constructing them one line at a time. and why
should 2^n hold for infinite tables.

 

[chiro]

Would I be able to write down the rows of the truth table? Or at least start to.
Even though I have a countable infinite number of variables. It seems I should be able to compare all these variables by constructing them one line at a time. and why
should 2^n hold for infinite tables.

Think of your truth table as a mapping of G1 x G2 -> {0,1}, where G is some input corresponding to a binary vector.

Now let's say that G1 and G2 refer to the same set. If G1 has infinitely many combinations, why should G2 not either?

 

[mathman]

that means that we can't construct the rows of the truth table. We wouldn't be able to write them down. But how could I have a countable number of variables and and uncountable number of rows. It seems that all the possible number of combinations in my truth table should be countable.

The proof is essentially the same as the Cantor proof that the reals are uncountable. Short version: Assume that all the rows are in a (countable) list. Then (following Cantor) I can create a row that is not on the list - contradicting the assumption you have all the rows.

The first entry is the opposite of the first entry of the first row, the second entry is the opposite of the second entry of the second row, ..., the nth entry is the opposite of the nth entry of the nth row, etc. You now have a row which differs from all the rows on list, so the list in incomplete, contradicting the assumption it was complete.

 

[cragar]

ok, how do we know that combination needed to be on the table.
Is it because we need an infinite amount of combinations.
What If I constructed my table in such a way that if it had an infinite amount of variables , but I picked the connectives in such a way that we didn't necessarily need all the possible combinations. for example for an if then statement if the first value is false
then it will be true no matter what the second one is. Maybe I am way off. What do you think.

 

[mathman]

ok, how do we know that combination needed to be on the table.
Is it because we need an infinite amount of combinations.
What If I constructed my table in such a way that if it had an infinite amount of variables , but I picked the connectives in such a way that we didn't necessarily need all the possible combinations. for example for an if then statement if the first value is false
then it will be true no matter what the second one is. Maybe I am way off. What do you think.

Sorry - you lost me. could you illustrate what you are trying to describe?

 

[cragar]

Lets say we use a bunch of if-then statements on our truth table.
so if the first truth value is false then it doesn't matter what the second value is,
So maybe cantors diagonal argument doesn't necessarily apply to this table, because we could generate all the possible truth combinations without having every line be a unique line.

 

[chiro]

Lets say we use a bunch of if-then statements on our truth table.
so if the first truth value is false then it doesn't matter what the second value is,
So maybe cantors diagonal argument doesn't necessarily apply to this table, because we could generate all the possible truth combinations without having every line be a unique line.

The thing is though that if you are doing some computation on two inputs and the number of inputs is infinite, then under the Turing model you won't be able to do the computation in a finite amount of time.

For an infinite input space, you will need infinite numbers of bits for every element. For a general truth table, it is not computationally possible under a model like a Turing machine to even calculate the value from an algorithm or look up the entry from some memory location if it is in a table of some sort.